什么时候在 shift-reduce 解析器中减少？

Question

这是我的自下而上解析器的框架：

while (!stack.empty())
{
    if (!reduce())
    {
        shift();
    }
}

我有这些规则：

Program -> Expr
Expr -> Expr '+' Expr
Expr -> Number
Number -> FLOAT | INTEGER  // These 2 are terminal symbols

如果我有以下输入：

2 + 3

2 被压入堆栈，然后缩减为一个数字，然后是一个表达式，然后是一个程序。所以它没有任何机会解析整个添加。我怎样才能强制解析器也解析其余部分？我应该做类似的事情吗：

Program -> Expr EOF

?

自下而上的解析对我来说是全新的，因此非常感谢您的帮助。

Answer 1

您可以使用前瞻来决定是移动还是减少。您的示例语法适合 LR(1) 语法系列，因此具有 1 符号前瞻性的自下而上解析器应该能够捕获它。

在您的示例中，您输入了：

2 + 3

所以你建立了一个堆栈：

Program, Expr, Number

转移FLOAT，减少Number，减少Expr。现在你有一个选择，是减少Program还是移位'+'，所以你看前面有没有'+'。如果是这样，你转移并遵循 Expr = Expr '+' Expr 规则。

您可能仍想执行 Program = Expr EOF 以便您的前瞻始终可以 return EOF 如果没有任何内容需要解析。

When to reduce in a shift-reduce parser?