parsing - 使用 ocamlyacc 减少/减少冲突

Question

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

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

是否有任何解决方案可以解决此问题，而无需在解析过程中丢弃所有类型信息并始终在评估阶段检查它？

这是一个简短的语法示例(使用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 技术肯定不太适合，这就像用正则表达式解析嵌套括号一样。

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