什么时候减少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所以如果没有什么可以解析的话，你的lookahead总能返回EOF。