轉換語法爲LL（1）語法：一些問題

Question

這是不完全作業，但它關係到我的學業：

A爲例語法是這樣的：

ë - > E + E | E * E | -E |（E）| ID

去除歧義成爲後

E->-F|F 
F->F+G|G 
G->G*H|H 
H->(E)|id 

（從最低優先級運營商開始）

和卸下左遞歸和左保（不需要在這種情況下）最終LL1語法後：

E->-F|F 
F->GF' 
F'->+GF'|e 
G->HG' 
B->*HG'|e 
H->(E)|id 

這給出了一個錯誤免費解析器表工作正常。 現在關於我面臨的問題，假設它的語法是這樣的：

ë - > E + E | E * E | ID = E |（E）| ID現在

我我無法生成沒有衝突的解析表，這意味着我的最終語法不是LL1。以下是具體步驟：

去除歧義後：

E->id=F|F 
F->F+G|G 
G->G*H|H 
H->(E)|id 

和卸下左遞歸和左保理後，語法變爲：

E->id=F|F 
F->GF' 
F'->+GF'|e 
G->HG' 
B->*HG'|e 
H->(E)|id 

但在解析器表中衝突我無法刪除，這意味着我已經錯過了一些步驟，或者在我無法找到的步驟中存在一些錯誤。請告訴我我做錯了什麼，以及如何解決這個問題。我一直在研究這個問題很長一段時間了。

Answer 1

假設：

E -> E+E|E*E|id=E|(E)|id 

將變爲：

E -> E+E|E*E|(E)|E' 
E' -> id=E|id 

那麼你就可以消除歧義和左手遞歸去弄：

E -> GF  FIRST(E) = FIRST(G) 
F -> +GF|e 
G -> HG'  FIRST(G) = FIRST(H) 
G' -> *HG'|e 
H -> (E)|E' FIRST(H) = {(} + FIRST(E') = {(, id} 
E' -> idE'' FIRST(E') = {id} 
E'' -> =E|e FIRST(E'') = {=} + {#} 

當然，問題是，你失去了給定的運算符優先級。

的語法將不會被LL（1）如果任何非終結N，會有任何共同要素在FIRST(N -> a)和FIRST(N -> b)爲N -> a，N -> b從N是不同的製作。

如您所見，在中添加生產N -> id=任何其他地方都會違反該規則。

您可以創建LL(2)語法（但這可能不是您想要的），它可以在任何地方生產id=E。 （FIRST2集合由2元素字符串組成）。

另外，如果你看一下語法呈現更多的時間：

E -> E+E|E*E|id=E|(E)|id 

這是一個高的機會，那上面我在溶液製造的運算符優先級是真實的應用程序是正確的。一探究竟！