Shift-reduce：何時停止減少？

我正在嘗試瞭解shift-reduce解析。假設我們有以下的語法，使用強制操作順序遞歸規則，由ANSI C Yacc grammar啓發：Shift-reduce：何時停止減少？

S: A; 

P 
    : NUMBER 
    | '(' S ')' 
    ; 

M 
    : P 
    | M '*' P 
    | M '/' P 
    ; 

A 
    : M 
    | A '+' M 
    | A '-' M 
    ;

我們想用移減少解析解析1 + 2。首先，1被轉換爲NUMBER。我的問題是，它是減少到P，然後M，然後A，然後最終S？它如何知道在哪裏停止？

假設它一直減少到S，然後移動'+'。現在，我們不得不含堆棧：

S '+'

如果我們轉向「2」，削減可能是：

S '+' NUMBER 
S '+' P 
S '+' M 
S '+' A 
S '+' S

現在，在最後一行的兩側，S可能是P， M，A或NUMBER，並且從任何組合都是文本的正確表示形式來看，它仍然有效。解析器如何「知道」使它成爲

A '+' M

因此，它可以將整個表達式減少到A，那麼S？換句話說，它是如何知道在轉移下一個令牌之前停止減少的？這是LR分析器生成的關鍵難點嗎？

編輯：的除了問題如下。現在假設我們解析1+2*3。一些移位/縮小操作如下：

Stack | Input | Operation 
---------+-------+---------------------------------------------- 
     | 1+2*3 | 
NUMBER | +2*3 | Shift 
A  | +2*3 | Reduce (looking ahead, we know to stop at A) 
A+  | 2*3 | Shift 
A+NUMBER | *3 | Shift (looking ahead, we know to stop at M) 
A+M  | *3 | Reduce (looking ahead, we know to stop at M)

這是正確的（授予，尚未完全解析）？而且，向前看1個符號也告訴我們不要將A+M減少到A，因爲這樣做會在閱讀*3之後導致不可避免的語法錯誤？

來源

2010-04-13 Joey Adams

對於您提供的語法不是「1 + 2」會產生移位/縮減衝突嗎？ – mcabral 2010-04-13 03:14:55

沒有。野牛接受它沒有抱怨（當然包裝％標記NUMBER \ n %% \ n ... \ n %%後）。 – 2010-04-13 03:17:37

您正在描述的問題與創建LR(0)解析器有關 - 也就是說，自下而上的解析器不會對超出當前正在解析的符號的任何符號執行任何前瞻。你所描述的語法似乎不是一個LR(0)語法，這就是爲什麼當你試圖解析它而不是前瞻時遇到麻煩的原因。它確實看起來是LR(1)，但是，通過在輸入前面看1個符號，您可以輕鬆確定是否移位或縮小。在這種情況下，LR(1)解析器會在堆棧中有1時向前看，請參閱下一個符號是+，並意識到它不應該減少過去A（因爲這是它可以減少到的唯一東西在第二位仍然符合+的規則）。

LR語法的一個有趣屬性是對於LR(k)對於k>1的任何語法，有可能構造等效的LR(1)語法。但是，同樣不會一直延伸到LR(0) - 有許多語法不能轉換爲LR(0)。

在這裏看到更多的細節上LR(k) -ness：

http://en.wikipedia.org/wiki/LR_parser

來源

2010-04-13 03:50:24 Amber

如果我解析1 + 2 * 3，根據我的理解，堆棧在A + M結束。這可能會減少到A，但這在這裏是不正確的，因爲它會產生A * ...，對此沒有規則存在。向前看1個符號表明這種減少不應該發生嗎？我在原文中增加了更多細節。 – 2010-04-13 04:20:23

是的，它的確如此 - 因爲當你在堆棧中有「A + M」，並且你展望'*'時，你會發現*必須在* *的左邊有一個'M'，所以如果這會導致堆棧頂部不是'M'，則不知道如何減少。 – Amber 2010-04-13 04:24:01

我不能完全肯定的Yacc /鬼分析算法和時移寧願在減少，但是我知道，野牛支持LR（1）解析，這意味着它有一個前瞻標記。這意味着令牌不會立即傳遞到堆棧。而是等到沒有更多的減少可以發生。然後，如果移動下一個標記是有道理的，它就會應用該操作。

首先，就你的情況而言，如果你正在評估1 + 2，它會移動1.它會將該標記減少到A，因爲'+'超前標記表示它是唯一有效的過程。由於沒有更多的減少，它會將'+'令牌轉移到堆棧上，並將2作爲前瞻。由於A + M產生A並且表達式完成，它將會移動2並減少到M。

來源

2010-04-13 04:11:51 aduric

Shift-reduce：何時停止減少？

回答

相關問題