什麼時候減少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。