Bison 错误恢复和平衡括号

Question

假设我们有一个文件，其中每一行都由平衡括号的字符串组成。我们可以通过将以下经典语法放入 Bison 来认识到这一点：

/* ignoring preamble and lexer definitions */
%% 
lines: line | lines line;
line: balanced NEWLINE;

balanced: %empty
| balanced '(' balanced ')'
| balanced '[' balanced ']'
| balanced '{' balanced '}'
| balanced '<' balanced '>';

下一个改进是处理不平衡的括号（或大括号，或......）。在这种情况下，我们希望解析器盲目地消耗

NEWLINE

之前的所有内容，并在下一行重新开始。我们可以使用 bison 的错误恢复来做到这一点，尽管它很笨拙。但是下面遇到不平衡的括号时会移动

error

标记；它可以访问

any

非终结符，这使得它可以吞掉该行的其余部分。

%% 
lines: line | lines line;
line: balanced NEWLINE;

balanced: %empty
| balanced '(' balanced ')'
| balanced '[' balanced ']'
| balanced '{' balanced '}'
| balanced '<' balanced '>';

/* below are new */

any: %empty 
| any '(' | any ')' | any '[' | any ']'
| any '{' | any '}' | any '<' | any '>';

line:
balanced error ')' any NEWLINE
| balanced error ']' any NEWLINE { /* do something special when an out of order ']' is detected */ }
| balanced error '}' any NEWLINE
| balanced error '>' any NEWLINE;

我的问题是如何处理下一个改进：自动完成截断的行。例如，如果我们的线路是

<>(([])<

我希望能够确定结束字符串是什么，在本例中为

>)

或等效的

(<

，因为我可以反转订单并将结束字符串替换为开仓代币。我知道如何检测并跳过截断的行：

line: balanced error NEWLINE;

但这会导致从第一个左括号开始的所有内容都被丢弃。在弹出所有内容之前，有什么方法可以访问 bison 的内部令牌堆栈吗？或者某种语法结构可以让我一次展开一个？

我目前正在做一些令人厌恶的事情：推入左符号 [({< onto a stack in a context object from the lexer, and when

balanced

会减少弹出堆栈，所以如果我们进入错误恢复，我可以通过上下文访问左括号。但是，好吧，这已经烂了。

我也尝试过查看野牛解析器的内部结构，但似乎只有在弹出所有内容后才能通过语义错误操作访问内部堆栈。

Answer 1

您的第一组错误恢复规则不必要地复杂——错误恢复将根据恢复所需丢弃令牌，因此您永远不需要像

any

这样的规则。

回到你的基础代码（没有错误恢复），你只需要添加一条规则来获得“错误时，丢弃换行符之前的所有内容”的恢复操作：

line: error NEWLINE

仅使用此规则，当发生错误时，它将丢弃当前行的结果并继续下一行。

---

要了解其工作原理（并了解更复杂的情况），您需要了解移位归约解析器自动机以及错误恢复的工作原理。基本上，您有一个带有状态堆栈的状态机 - 堆栈顶部的状态是当前状态。在每一步中，它都会查看当前状态和前瞻标记来决定要做什么——shift（消耗前瞻并将另一个状态推送到堆栈上）、reduce（从堆栈中弹出 0 个或多个状态、运行用户操作，然后根据执行的规则执行 goto 操作），或错误（生成语法错误消息并平铺）。

如果你有错误恢复规则，那么每当发生错误时，它会：

1. 从堆栈中弹出状态，直到找到可以移动错误标记的状态
2. 移动错误标记（将另一个状态推送到堆栈上）
3. 丢弃输入中的令牌（可能没有），直到它可以执行操作。
4. 执行操作（移位或减少，然后转到）。如果是reduce+goto，则返回步骤3（继续丢弃标记）。只有当它执行了非错误标记的转换后，它才会返回到“正常”解析（其中另一个错误将导致另一个错误标记。）

在第一步中，如果它从未找到可以转移错误标记的状态，它只会以失败的方式退出解析器（如果没有错误恢复规则，这总是会发生）。

---

因此，仅使用

line: error NEWLINE

规则，当您输入不平衡时（如您的示例），当它到达换行符时，堆栈将看起来像

<top>
state for 'balanced: balanced '<' balanced ...
state for 'balanced: balanced '<' ...
state for 'balanced: balanced '(' balanced ...
state for 'balanced: balanced '(' ...
state for 'balanced: (line|balanced): balanced ...
state for the beginning of a line
state for the beginning of the input
<bottom>

在第一步中，它将弹出状态，直到到达“行的开头”状态，然后它将转移到唯一可能的操作是移动换行符的状态，然后它将丢弃前瞻，直到到达“行的开头”状态。换行符（在本例中没有换行符），那么它将移动该换行符。

如果您改为使用规则 'line: 平衡错误 NEWLINE

it will work just as well, but will finish step 1 one state earlier, and when it reduces the

line: 平衡错误 NEWLINE

, that action will have access to 

$1

which will be the result of the correctly parsed balanced prefix (just

<>

in your example -- the intermediate

([])` 会与堆栈上的第三个状态一起被丢弃。

---

所以现在我们可以尝试额外的规则来恢复中间状态。一种可能性是：

balanced: balanced '(' balanced error
        | balanced '[' balanced error
        | balanced '{' balanced error
        | balanced '<' balanced error

这将立即停止弹出状态，而不弹出任何内容（因为顶级状态可以处理错误），让您有机会在该状态下访问

$1

和

$3

。但问题是，直到它移动了一个（非错误）标记之后，它才会完成错误恢复，因此，如果存在第二个错误（如这里所示），它最终会丢弃换行符，这可能不是你想要什么。

此时，如果不考虑错误处理的内部结构，您就无法做更多事情。您可以让您的操作查看并修改

yychar

（前瞻标记）和/或

yyerrstatus

，但具体操作细节可能会因 yacc 或 bison 版本的不同而有所不同。