parsing - 何时在 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

?

自下而上的解析对我来说是相当新的，所以任何帮助表示赞赏。

score 1 · Accepted Answer

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

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

2 + 3

所以你建立了一个堆栈：

Program, Expr, Number

转移FLOAT，减少Number，减少Expr。现在你有一个选择，是减少Program还是转移'+'，所以你向前看是不是有一个'+'。如果是这样，你会改变并遵守Expr = Expr '+' Expr规则。

您可能仍然希望这样做，如果没有什么要解析的Program = Expr EOF，您的前瞻总是可以返回。EOF

1 回答 1