消除間接左遞歸

我的大腦被炸，試圖消除生產規則中的一些左遞歸。我建立與JavaCC的一個編譯器，我需要用以下2生產規則：消除間接左遞歸

expression := fragment ((+ | - | * | /) fragment)* 

fragment := identifier | number | (+ | -) fragment | expression

但問題是，片段與表達這是關係到片段，即：間接左遞歸。

我看了看周圍的互聯網，似乎每個人都使用這種算法，可以發現here。該網站並沒有直接解釋左遞歸消除，你可以找到here

我結束了這樣的規則：

void expression(): {} 
{ 
    fragment() 
    (
    (<PLUS>|<MINUS>|<DIVIDE>|<ASTERISKS>) 
    fragment() 
)* 
} 

void k(): {} 
{ 
    (
    ((<PLUS>|<MINUS>|<DIVIDE>|<ASTERISKS>)fragment())*k() 
    | fragment() 
) 
} 

void fragment(): {} 
{ 
    (
    <ID>k() 
    | number()k() 
    | (<PLUS>|<MINUS>)fragment()k() 
) 
}

他們寫在用於JavaCC的代碼，所以希望你能理解他們。基本上我引入了一個規則K來處理遞歸，除了問題依然存在之外，因爲K的第一部分可以減少爲無，因爲它是*（0或更多次），這會留下更多的K - > k（）遞歸！

我不知道該從哪裏走，並失去了很多頭髮。任何見解將不勝感激！

來源

2012-12-12 carlmango11

你通常可以有'term'，'expression'，然後是一個終端符號，爲什麼這裏不夠好？ – 2012-12-12 19:10:32

我認爲'fragment'的定義不正確。「表達式」不應該出現在字面括號之間，比如'fragment：= ...'（'expression'）''？否則，在「片段」級別使用「表達式」是沒有意義的。請注意，我並不熟悉JavaCC，但這在其他解析器生成器中會遇到問題。 – user1201210

我在想同樣的事情提心吊膽。我似乎無法想象這樣一種情況，即片段中的「表達式」會被使用。然而，這些規則在決定我是一名講師的時候非常有用。也許我應該聯繫他？ H2CO3：你能解釋一下嗎？你的意思是我應該創建一個規則'term'？它會包括什麼？我實際上已經看到人們在網絡中使用「term」，但我認爲遵循該算法會更好。 – carlmango11

我建議重寫規則expression如下：

expression := (identifier | number | (+ | -) fragment) ((+ | - | * | /) fragment)*

實際上，這僅僅是在原有定義的fragment替代，與克林運營商方便地吸收一些術語。

當然，無論從解析這個結構創建的結構都需要被包容，如果它應該反映原始規則。

來源

2012-12-22 00:42:34

消除間接左遞歸

回答

相關問題