決定語法是LR（0）還是不是

Question

我是新來的編譯主題，剛開始練習Bottom-up解析。

我一直堅持下面的問題。

構建一個LR（0），以下語法分析表：

1) E –> E + T 
2) E –> T 
3) T –> (E) 
4) T –> id 


I0 : 

    E' –> .E 
    E –> .E + T 
    E –> .T 
    T –> .(E) 
    T –> .id 

E上的DFA下一狀態將是：

I1: 

    E' -> E. 
    E -> E. + T 

從我所學會爲止ISN」這是SR衝突嗎？ ，因爲解析器不知道是否減少或移位，因爲它沒有預見變量？ 所以這不應該是LR（0）語法？

但我正在閱讀的PDF已經構建了LR（0）表。 那麼在PDF中有沒有錯誤，或者我在理解概念的地方出錯了？

Answer 1

這實際上是一個轉變/減少衝突。這個語法不是LR（0）。你也可以看到這個，因爲它不是前綴免費;該語法包含多個相互前綴的字符串，因此它不能是LR（0）。這就是說，你仍然可以構造所有的LR（0）配置集並製作LR（0）自動機。由於轉變/減少衝突，它不會是確定性的。因此，你是對的，講義是對的。

希望這會有所幫助！

Answer 2

您用E' -> E擴充了語法。通常情況下，你會增加一個像E' -> E $這樣的產品，其中$是一個在語法中不會出現的（終端）符號，並且表示輸入結束。

所以I1實際上是

E' -> E. $ 
E -> E. + T 

並沒有衝突。 （我相信語法是 LR（0）。）