解析語法交替並重復

Question

我能夠通過跟隨this question一起添加對我的解析器交替字符的語法（例如ababa或baba）的支持。

我現在正在通過允許重複字符來擴展它。

例如，我希望能夠支持abaaabab和aababaaa以及。在我的情況下，只允許重複a，但允許重複b的解決方案也是有用的。

給出的規則從另一個問題：

expr ::= A | B 
A ::= "a" B | "a" 
B ::= "b" A | "b" 

...我試圖擴大它支持重複，像這樣：

expr ::= A | B 

# support 1 or more "a" 
A_one_or_more = A_one_or_more "a" | "a" 

A ::= A_one_or_more B | A_one_or_more 
B ::= "b" A | "b" 

...但是，語法是不明確的。有沒有可能使這個明確無誤，如果有的話，任何人都可以幫助我消除歧義？

我使用的是一個LALR（1）解析器的lemon parser。

Answer 1

解析的點，在一般情況下，是到解析;即確定輸入的語法結構。這與簡單驗證輸入屬於某種語言明顯不同。

例如，其由能夠與正則表達式(a|b)*，其可以以BNF被寫爲

S ::= /* empty */ | S a | S b 

但是，這可能是不捕獲句法結構進行說明的a和b任意重複的語言你正試圖定義。另一方面，由於您沒有指定該結構，所以很難知道。

這裏有一對夫婦更多的可能性，從而建立不同的分析樹：

S ::= E | S E 
E ::= A b | E b 
A ::= a | A a 

---

S ::= E | S E 
E ::= A B 
A ::= a | A a 
B ::= b | B b 

當寫一個語法解析一種語言，它通過繪製你的提議解析樹開始是非常有用的。通常，您可以直接從樹的形式編寫語法，這表明正式語法主要是一個工具文檔，因爲它以非正式描述不能描述的方式清楚地描述了該語言。使用解析器生成器將該語法轉換爲解析器可確保解析器實現所描述的語言。或者，至少，這是目標。

Answer 2

這是一個很好的工具，用於在線檢查語法http://smlweb.cpsc.ucalgary.ca/start.html。它實際上接受the grammar you provided作爲有效的LALR（1）語法。

不同的LALR（1）的語法，其允許reapeating一個的，將是：

S ::= "a" S | "a" | "b" A | "b" 
A ::= "a" S .