使用ocamlyacc减少/减少冲突

问题描述

我正在努力处理一种语法，该语法涉及类型化的表达式以及变量访问.解析期间无法确定此访问的结果类型，并在第二步中对其进行评估.这种评估不是问题，但是似乎很难编写明确的解析器规则.

I am struggling with a grammar that involves typed expressions as well as variable access. The result type of this access is not ascertainable during parsing and is evaluated in a second step. This evaluation is not a problem, but it seems hard to write unambiguous parser rules.

适用于不同类型的所有操作(例如比较运算符)都会产生reduce/reduce冲突.显然，这是因为解析器无法确定将"x.a = y.b"解析为"bool_expr EUQAL bool_expr"还是解析为"num_expr EUQAL num_expr"，因为类型不确定.但是，comp_op规则的结果类型是确定的(因为它始终是布尔值).

All operations that work on different types (e.g. compare operators) produce a reduce/reduce conflict. Clearly, this is because the parser can not decide if "x.a = y.b" should be parsed as "bool_expr EUQAL bool_expr" or as "num_expr EUQAL num_expr" because the type is uncertain. However, the result type of the comp_op rule is certain (as it is always a boolean value).

在解析过程中不丢弃所有类型信息并始终在评估阶段对其进行检查的情况下，是否可以解决此问题?

Is there any solution to this problem without throwing all type information away during parsing and always check it in the evaluation phase?

这是一个简短的语法示例(使用 ocamllex 和 ocamlyacc ):

Here is a shortened grammar example (using ocamllex and ocamlyacc):

comp_op:
  | bool_expr EQUAL bool_expr  { T.Equiv (T.Wrapper $1, T.Wrapper $3) }
  | num_expr EQUAL num_expr    { T.Equiv (T.Wrapper $1, T.Wrapper $3) }
  /* the wrapper type basically just wraps the expressions to get a common type */

bool_expr:
  | TRUE                       { T.Bool true }
  | FALSE                      { T.Bool false }
  | access                     { T.BoolAccess $1 }

num_expr:
  | NUMBER                     { T.Num $1 }
  | access                     { T.NumAccess $1 }

access:
  /* some more complex rules describing the access to variables */

感谢您的帮助.

推荐答案

如ygrek所说，您不应尝试将解析和键入混合使用.编写解析器时只用一个语法类别来表达表达式，然后有一个单独的类型检查通道将其分类即可，这要容易得多.

As ygrek says, you should not try to mix parsing and typing. It's much easier to write your parser with only one syntactic category for expressions, and then to have a separate type-checking pass that will sort that out.

从理论上讲，这是因为这样的事实，即通过键入规则进行的区分比传统的解析技术所能表达的要好得多.他们一直在尝试使用属性语法等声明性地指定键入规则，但是您通常使用的LL/LR技术肯定不是一个很好的选择，就像解析带有正则表达式的嵌套括号一样.

Theoretically, this comes from the fact that the distinctions made by typing rules are much finer than what traditional parsing technologies can express. They have been attempt at specifying typing rules more declaratively using, for example, attribute grammars, but your usual LL/LR technology is certainly not a good fit, it's like parsing nested parentheses with a regular expression.

最后，您应该使用 menhir 代替ocamlyacc，因为这样做更好.您将拥有更具可读性和表达力的语法(命名参数，参数化规则...)，更好的错误报告和语法调试功能.

Finally, you should use menhir instead of ocamlyacc, because it's just better. You will have more readable and expressive grammars (named parameters, parametrized rules...), better error reporting and grammar debugging features.

这篇关于使用ocamlyacc减少/减少冲突的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持！