为什么 yacc 生成的状态机状态不包含有效的下一个标记？

Question

我正在使用 PLY (Python Lex/Yacc) 作为解析器。我得到以下输出：

State  : 52
Stack  : <shortened preamble> primary_expr ARROW simple_name LPAREN ID COLON . LexToken(INTEGER,'Integer',13,362)
Action : Shift and goto state 116

State  : 116
Stack  : <shortened preamble> primary_expr ARROW simple_name LPAREN ID COLON INTEGER . LexToken(BAR,'|',13,370)
ERROR: Error  : <shortened preamble> primary_expr ARROW simple_name LPAREN ID COLON INTEGER . LexToken(BAR,'|',13,370)

您可以看到，在状态 52 中，它移动了 INTEGER 令牌，然后转到状态 116。状态 116 的状态机输出文件具有以下内容：

state 116

  (56) simple_type -> INTEGER .

  RBRACKET        reduce using rule 56 (simple_type -> INTEGER .)
  EQ              reduce using rule 56 (simple_type -> INTEGER .)
  SEMI            reduce using rule 56 (simple_type -> INTEGER .)

这好像只是为了INTEGER减少到simple_type的状态。然而 BAR 标记（出现在输入中的下一个）并未在此处列出。

我期望匹配的规则是：

iterator_expr : primary_expr ARROW simple_name LPAREN uninitialized_variable BAR other_expr RPAREN

这些其他规则提供了最后三个标记的减少以匹配规则。

simple_type : INTEGER
type_specifier : simple_type
declarator : ID COLON type_specifier
uninitialized_variable : declarator

So，在我看来状态机已全部设置为进入状态 116，将 INTEGER 减少到 simple_type，simple_type 到 type_specifier、ID COLON type_specifier 到 declarator、declarator 到 uninitialized_variable，然后从那里愉快地继续 BAR。不过好像要进入只有shift动作，抱怨下一个shift的状态了。提到的任何规则都没有 shift/reduce 或 reduce/reduce 冲突。

为什么需要接下来考虑BAR，为什么不在状态机中将其列为一种可能性？

编辑 2018 年 4 月 20 日：
我将期望匹配的规则更改为：

iterator_expr : primary_expr ARROW simple_name LPAREN declarator BAR other_expr RPAREN

（即，将 uninitialized_variable 更改为 declarator），并且 BAR 现在作为状态 116 中的下一个标记出现。解析器现在选择减少 simple_type -> INTEGER 而不是比 shift BAR 更匹配。我想知道是否必须匹配非终端 (unintialized_variable)，然后匹配一些终端 (ID、COLON) 和一些以某种方式阻止有效下一个标记检测的非终端。

我意识到没有完整的语法（不幸的是它是专有的）没有人可以调试它。但我有兴趣了解可能涉及的 yacc 原则，并且还希望为这些奇怪的问题记录良好的调试技术。对于在其他规则中包含 expression 非终结符的其他规则，我实际上遇到了这个问题——当显然 expression 非终结符时，像“+”这样的东西显示为无效的下一个标记应该覆盖它。如何创建下一个有效令牌列表，什么会阻止规则中如此明确列出的令牌出现？

Answer 1

当您的解析器出错时，这是因为存在语法错误——它没有有效的选项来转换或 reduce，因此可以断定您的输入没有' t 匹配语法。如果您不这么认为，一些观察可能有助于弄清楚为什么你们两个会得出不同的结论。

请记住，LALR 解析器生成一个用于解析输入的确定性状态机。无论它处于什么状态，给定下一个令牌，它都会做出一个决定并继续前进。您的语法必须以这样一种方式形成，即对于任何有效输入，状态机始终有一个有效的下一步操作。
语法错误是死胡同，但这并不意味着只有最后一转是错误的。 Shift/Reduce 和 Reduce/Reduce 冲突可能已存在于先前应用的规则中，并已以某种方式解决。这种方式可能会让您的其余输入与有效的下一步操作不匹配。

您的解析树很可能在早期就存在歧义，而解析器选择解决该歧义的方法使您的特定输入的其余部分变得不可接受。您需要检查解析历史以找到发生这种情况的时间点，了解您的语法似乎希望两个或多个选择同时有效的原因，并重新编写语法规则以防止这种情况发生。在历史中找到这一点的好技巧：

为您的输入字符串重建状态历史和规则应用。然后浏览您的 parser.out 文件以查找任何这些规则的冲突。查看该冲突是否会影响输入字符串的解析。
围绕您似乎涉及的语法部分创建一个简单示例。将简单的语法输入 JFLAP or JsMachines 等工具。让该工具解析一个有代表性的输入并查看它在每一步做出的决定。请记住，在这些工具中，'s#' 表示 "shift and go to state #"，'r#' 表示 "reduce according to rule #"，而“#”表示 "go to state #." 您将看到返回的状态在堆栈减少之后，这将有助于理解解析器认为它可能完成的规则。

对于像 PLY 这样的工具来说，生成一个状态机可能会非常好，该状态机在发生冲突时将解析置于记录这是发现冲突点的状态，然后自动进行到选择进行解析的状态。您也许可以将其添加到 PLY 的 yacc 模块中。

如果你需要你的语法来处理一些可能性，直到语法将它们解析为一个选项，你可以添加它可以跟踪的非终端规则。您实际上是在尝试强制状态机为一定数量的标记选择 "shift"，直到遇到解析语法。那么减少的应用应该是唯一的。要让它选择 "shift,"，必须有多个适用的产生式代表可能的选择，但要使归约独一无二，它们必须以某种独特的方式结束。您可能能够覆盖从歧义点到解决的语法元素，并获得您需要的可选性。

为什么 yacc 生成的状态机状态不包含有效的下一个标记？

Why does a yacc-generated state machine state not include a valid next token?

parsing

yacc

ply