对使用 Bison 进行解析感到困惑
Confused regarding parsing with Bison
我正在阅读 Levine 的“Flex & Bison”，我对解析的具体过程感到有点困惑。对于这个例子，我将对一个简单的计算器使用这些规则：
exp: factor | exp ADD factor | exp SUB factor
factor: term | factor MUL term | factor DIV term
term: NUMBER | ABS term | OP exp CP
我不会在此处包括扫描仪，但它可以满足您的期望。我的第一个混淆来源是 BNF 本身，或者更确切地说，它是如何连接到上下文无关语法的。我被介绍给 CFGs 作为一个 string-replacement/rewriting 系统，即在左边取一个符号，然后用右边的符号替换它，但在我看来解析器实际上是“向后”工作的，即它不会替换LHS 与 RHS，而是减少 RHS 与 LHS 的匹配。这是正确的吗？
我的第二个问题通过例子得到了最好的证明。假设我们希望解析 1 + 3 * 2。扫描器取 1 并给我们标记 NUMBER，这（我假设这里的解析器查看 all 出现在右边的规则-hand sides）它可以减少到“term”，因为除了那个之外没有以 NUMBER 开头的规则。按照同样的逻辑，它可以将“术语”减少为“因素”。然而，它不能将“factor”减少为“exp”，因为下一个标记可能是 MUL 或 DIV。所以它要求扫描器获取下一个令牌，即 ADD。所以现在解析器在它的堆栈中有“因素添加”。这不符合任何规则，因此“factor”可以安全地简化为“exp”。堆栈现在是“exp ADD”。此时我们需要另一个标记，它是 NUMBER。同样，减少让我们得到“exp ADD term”，然后是“exp ADD factor”。这就是让我感到困惑的地方。堆栈现在是“exp ADD factor”。为什么解析器不立即将其简化为“exp”，因为它直接匹配其中一个规则？相反，它实际做的是查看下一个标记，即 MUL，然后是下一个标记，即 NUMBER，然后它将 NUMBER 减少为“term”，这意味着堆栈现在是“exp ADD factor MUL term”
直到现在它才将最后三个符号减少为一个因子，然后将生成的“exp ADD factor”减少为“exp”。
The stack is now "exp ADD factor". Why doesn't the parser immediately reduce this to "exp", since it directly matches one of the rules?
因为 bison 生成的解析器足够聪明，可以意识到如果它在前瞻标记为 MUL 时确实进行了这种归约，它就会被卡住——没有匹配 exp MUL 的规则...所以它不能那样做。
基本上，由 bison 构建的“状态机”编码了所有可能的规则，这些规则可能会被堆栈上的 symbols/tokens 减少，以及可能在输入中的未来标记。所以根据当前的“状态”（实际上是一个栈符号，存储在状态栈顶）和当前的前瞻令牌它知道是否要移位（将与前瞻令牌对应的状态压入堆栈，并消耗令牌）或减少（从堆栈中弹出状态，然后根据减少的规则推送另一个状态，弹出后堆栈顶部的状态），这不会消耗前瞻性。
我正在阅读 Levine 的“Flex & Bison”，我对解析的具体过程感到有点困惑。对于这个例子，我将对一个简单的计算器使用这些规则：
exp: factor | exp ADD factor | exp SUB factor
factor: term | factor MUL term | factor DIV term
term: NUMBER | ABS term | OP exp CP
我不会在此处包括扫描仪，但它可以满足您的期望。我的第一个混淆来源是 BNF 本身，或者更确切地说，它是如何连接到上下文无关语法的。我被介绍给 CFGs 作为一个 string-replacement/rewriting 系统，即在左边取一个符号，然后用右边的符号替换它，但在我看来解析器实际上是“向后”工作的，即它不会替换LHS 与 RHS，而是减少 RHS 与 LHS 的匹配。这是正确的吗？
我的第二个问题通过例子得到了最好的证明。假设我们希望解析 1 + 3 * 2。扫描器取 1 并给我们标记 NUMBER，这（我假设这里的解析器查看 all 出现在右边的规则-hand sides）它可以减少到“term”，因为除了那个之外没有以 NUMBER 开头的规则。按照同样的逻辑，它可以将“术语”减少为“因素”。然而，它不能将“factor”减少为“exp”，因为下一个标记可能是 MUL 或 DIV。所以它要求扫描器获取下一个令牌，即 ADD。所以现在解析器在它的堆栈中有“因素添加”。这不符合任何规则，因此“factor”可以安全地简化为“exp”。堆栈现在是“exp ADD”。此时我们需要另一个标记，它是 NUMBER。同样，减少让我们得到“exp ADD term”，然后是“exp ADD factor”。这就是让我感到困惑的地方。堆栈现在是“exp ADD factor”。为什么解析器不立即将其简化为“exp”，因为它直接匹配其中一个规则？相反，它实际做的是查看下一个标记，即 MUL，然后是下一个标记，即 NUMBER，然后它将 NUMBER 减少为“term”，这意味着堆栈现在是“exp ADD factor MUL term” 直到现在它才将最后三个符号减少为一个因子，然后将生成的“exp ADD factor”减少为“exp”。
The stack is now "exp ADD factor". Why doesn't the parser immediately reduce this to "exp", since it directly matches one of the rules?
因为 bison 生成的解析器足够聪明，可以意识到如果它在前瞻标记为 MUL 时确实进行了这种归约，它就会被卡住——没有匹配 exp MUL 的规则...所以它不能那样做。
基本上，由 bison 构建的“状态机”编码了所有可能的规则，这些规则可能会被堆栈上的 symbols/tokens 减少，以及可能在输入中的未来标记。所以根据当前的“状态”（实际上是一个栈符号，存储在状态栈顶）和当前的前瞻令牌它知道是否要移位（将与前瞻令牌对应的状态压入堆栈，并消耗令牌）或减少（从堆栈中弹出状态，然后根据减少的规则推送另一个状态，弹出后堆栈顶部的状态），这不会消耗前瞻性。