Bison Shift/Reduce 简单语法冲突

Question

我正在为我设计的语言构建一个解析器，其中类型名称以大写字母开头，变量名称以小写字母开头，以便词法分析器可以区分并提供不同的标记。此外，字符串“this”被词法分析器（它是一种 OOP 语言）识别并作为单独的标记传递。最后，数据成员只能在“this”对象上访问，因此我构建了如下语法：

%token TYPENAME
%token VARNAME
%token THIS

%%

start:
    Expression
    ;

Expression:
    THIS
    | THIS '.' VARNAME
    | Expression '.' TYPENAME
    ;
%%

表达式的第一条规则允许用户将“this”作为值传递（例如，从方法或方法返回它）传递给方法调用）。第二个用于访问“this”上的数据。第三条规则是用于调用方法，但是我删除了括号和参数，因为它们与问题无关。最初的语法显然比这个大得多，但是这是生成相同错误的最小部分（1 Shift/Reduce 冲突） - 我将它隔离到它自己的解析器文件中并验证了这一点，因此该错误与任何错误无关其他符号。

据我所知，这里给出的语法是明确的，因此不应产生任何错误。如果删除这三个规则中的任何一个或将第二个规则更改为

Expression '.' VARNAME

不存在冲突。无论如何，我可能需要有人清楚地说明为什么会发生这种冲突以及如何解决它。

Answer 1

问题是语法只能向前看。因此，当您看到 THIS 然后是 . 时，您是在第 2 行（Expression: THIS '.' VARNAME）还是第 3 行（< code>Expression: 表达式 '.' TYPENAME，根据第 1 行进行归约。

语法可以将 THIS. 简化为 Expression.，然后查找 TYPENAME 或将其转换为 THIS. 并寻找 VARNAME，但它必须决定何时到达 .。

Answer 2

我尝试避免 y.output 但有时它确实有帮助。我查看了它生成的文件并看到了。

state 1

    2 Expression: THIS.  [$end, '.']
    3           | THIS . '.' VARNAME

    '.'  shift, and go to state 4

    '.'       [reduce using rule 2 (Expression)]
    $default  reduce using rule 2 (Expression)

基本上它是说它看到了“。”并且可以减少或可以转移。有时，Reduce 会让我感到愤怒，因为它们很难被精细化。转变是规则 3 并且是显而易见的（但输出没有提及规则 #）。它看到的减少是“.”在本例中是行

| Expression '.' TYPENAME

When it go to Expression 它查看下一个字母（“.”）并进入。现在它看到 THIS | 所以当它到达该语句的末尾时期望“.”当它离开或出现错误时。然而它看到了这个“。”而它在 this 和 '.' 之间（因此输出文件中的点）并且它可以减少规则，因此存在路径冲突。我相信您可以使用 %glr-parser 来允许它尝试两者，但冲突越多，您就越有可能获得意外的输出或歧义错误。我过去曾犯过歧义错误。处理它们很烦人，特别是如果您不记得是什么规则导致或影响了它们。建议避免冲突。

在尝试使用 bison 之前，我强烈推荐这本书。

我想不出一个“伟大”的解决方案，但这不会产生冲突

start:
    ExpressionLoop
    ;

ExpressionLoop:
      Expression
    | ExpressionLoop ';' Expression
    ;
Expression:
      rval 
    | rval '.' TYPENAME
    | THIS //trick is moving this AWAY so it doesnt reduce
rval:

    THIS '.' VARNAME

---

替代方案您可以通过在规则中添加更多内容来使其稍后减少，这样它就不会减少，或者通过在之后或之前添加标记来明确要采取的路径或失败（记住，它必须在减少任何路径之前知道）

start:
    ExpressionLoop
    ;

ExpressionLoop:
      Expression
    | ExpressionLoop ';' Expression
    ;
Expression:
      rval 
    | rval '.' TYPENAME
rval:
      THIS '@'
    | THIS '.' VARNAME
%%

-编辑-注意如果我想做 func param 和 type varname 我不能，因为根据词法分析器 func 的类型是Var（A-Za-z09_）以及类型。 param 和 varname 也是 var，所以这会导致减少/减少冲突。你不能把它们写成它们本来的样子，而只能写它们的样子。所以写作时请记住这一点。您必须编写一个标记来区分两者，或者将其编写为两者之一，但在代码中编写附加逻辑（规则右侧的 { } 中的部分）以检查它是否是 funcname 或类型并处理这两种情况。