尋找關於使BNF語法適合LL（1）解析（左分解）

的建議我正在研究一個解析項目，該解析項目使用該語法適應Perl的正則表達式http://www.cs.sfu.ca/~cameron/Teaching/384/99-3/regexp-plg.html。我簡化了這個語法爲我自己的目的，像這樣（注意，因爲「|」是一個道理，我不是使用逗號「」對於一個給定的非終結所以單獨製作）：尋找關於使BNF語法適合LL（1）解析（左分解）

<RE>  := <union>, <simple> 
<union> := <RE> | <simple> 
<simple> := <concat>, <basic> 
<concat> := <simple><basic> 
<basic> := <zero>, <one>, <onezero>, <elem> 
<zero> := <elem>* 
<one>  := <elem>+ 
<onezero> := <elem>? 
<elem> := <group>, <any>, <literal>, <class> 
<group> := (<RE>) 
<class> := [<items>] 
<items> := <item>, <item><items> 
<item> := <range>, <literal>

我想要寫一個LL（1）解析器來處理這個語法，而對於一個LL（1）解析器，<items>的產品有一些不明確的地方。爲了解決這個問題，我可以離開因子他們加入了新的非終結<X>，就像這樣：

<items> := <item><X> 
<X>  := <items>, epsilon

但我想知道是，我能不能翻轉圍繞第二生產秩序<items>，像這個：

<items> := <item>, <items><item>

並避免添加新的非終結符？它看起來並沒有破壞任何東西，畢竟這個產品的全部要點是允許任何可變數量的連續符號，並且如果我們逆轉順序，我們仍然可以得到。我是否錯過了某些東西，或者僅僅是顛倒順序來實現與這種情況下的左派因素相同的目標？

來源

2015-11-29 Erik Nyquist

你正在試圖解決的問題是，

items → item 
items → item items

不剩，分解;兩個作品都以item開頭。

你的建議修復

items → item 
items → items item

並不能真正幫助（不管開始item仍然可以啓動或者生產items），但更重要的是，它是左遞歸的，這是禁止的爲LL文法。

原則上，「新的非終端」是正確的解決方案，但在遞歸下降解析器，你可能會做這樣的事：

def items(): 
    list = [ item() ] 
    while couldStart(item, lookahead): 
    list.append(item()) 
    return list

來源

2015-11-30 05:54:36 rici

啊哈，左遞歸。我可能需要從紅龍書中除塵......我忘了很多這些東西。感謝那。你是否暗示，在遞歸下降的真正實現中，這個問題可以在不留下語法的情況下解決？我看不到你用這個python片段提出的解決方案。 –

@ErikNyquist：也許僞python代碼沒有多大幫助。重點是一個實用的RD解析器使用循環而不是遞歸，並且可以將'X +'實現爲一個循環：首先識別一個'X'，然後重複，只要下一個標記可以開始一個'X'。在C中，我會把它寫成'do ... while'循環;也許這會更清楚。 'X *'也可以用循環來識別;唯一的區別是測試是在開始而不是結束時進行的。 – rici

好吧，我幫你。我確實會避免遞歸，所以我很快就會達到必須實現這一點的程度，並且我很欣賞這些建議。我一直無法找到任何與編譯器設計相關的IRC房間，或甚至更小的子區域（即LL解析器，BNF語法）。你知道任何討論這些東西的好論壇......除了stackoverflow嗎？ –

尋找關於使BNF語法適合LL（1）解析（左分解）

回答

相關問題