使用ocamlyacc减少/减少冲突

Question

我正在挣扎于一种涉及类型表达式以及变量access的语法。在解析期间无法确定此访问的结果类型，并在第二步中对其进行评估。这个评估不是一个问题，但似乎很难写出明确的解析器规则。

所有在不同类型上工作的操作(例如，比较操作符)都会产生reduce/reduce冲突。显然，这是因为解析器无法决定"x.a = y.b“应该解析为"bool_expr EUQAL bool_expr”还是"num_expr EUQAL num_expr“，因为类型不确定。但是，comp_op规则的结果类型是确定的(因为它始终是一个布尔值)。

在解析过程中，如果不丢弃所有类型的信息，并且始终在评估阶段检查它，是否有任何解决方案来解决这个问题？

下面是一个简短的语法示例(使用ocamllex和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 */

谢谢你的帮助。

Answer 1

正如ygrek所说，您不应该尝试将解析和键入混合在一起。用一个表达式的语法类别编写解析器要容易得多，然后有一个单独的类型检查传递来解决这个问题。

从理论上讲，这是因为输入规则所产生的区别比传统的解析技术所能表达的要好得多。它们试图使用属性语法更具有声明性地指定类型规则，但是通常的LL/LR技术肯定不太适合，就像用正则表达式解析嵌套括号一样。

最后，您应该使用门希尔而不是ocamlyacc，因为它更好。您将拥有更具可读性和表现力的语法(命名参数、参数化规则.)、更好的错误报告和语法调试功能。

Answer 2

如前所述，您将很难编写一个“类型正确的解析器”--取决于您的语言，这甚至可能是不可能的。

无论如何，这里的问题是，您的语法不知道"access“产品的类型；据我所知，这种生成类似于从变量中读取，而在解析时，变量的类型是未知的。在我看来，您要么放弃100%类型正确的解析，要么找到一种“神奇地”了解变量类型的方法。您可以跟踪类型声明，让lexer查找它遇到的变量的类型；然后，lexer将根据变量的类型发送变量标识符-令牌。

我不确定这种方法是否有效，因为我不知道你的语言是什么样子的。