2

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

所有适用于不同类型的操作（例如比较运算符）都会产生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 */

谢谢你的帮助。

4

2 回答 2

2

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

从理论上讲，这是因为键入规则所做的区分比传统解析技术所能表达的要精细得多。他们一直在尝试使用例如属性语法来更明确地指定类型规则，但是您通常的 LL/LR 技术肯定不适合，这就像用正则表达式解析嵌套括号一样。

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

于 2012-03-21T13:05:26.513 回答
0

如前所述，您将很难编写“类型正确的解析器”——根据您的语言，这甚至可能是不可能的。

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

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

于 2012-03-22T08:02:24.567 回答