編譯器：改變模糊文法

Question

這個練習有點問題。

鑑於這種語法：

S -> aX | X 
X -> aXb | b | eps 

a）所示，它是模糊的一個字符串

B）說什麼語言捕捉語法

三）改變語法和構建後裔解析器

我的解決方案：

a）我給出了曖昧與字符串「AB」：

- S -> aX -> ab 
- S -> X -> aXb -> ab 

二）語法抓住了這個語言：

L = {a^n b^n: n >= 0} U {a^n b^m: n=m+1, n,m >= 0} U {a^n b^m: m=n+1, n,m >= 0} 

C）我的問題是改變語法來構建解析器。我嘗試了不同的語法，但它們也不明確。 例如這樣的：

- G -> X$ 
    X -> aX' | b | eps 
    X' -> XB | eps 

你能幫我找到了鍛鍊正確的語法，或給我輸入？

Answer 1

作爲you.undoubtedly知道，

S -> X | a S b 

可以被描述爲 「被相同數目的a S和b小號環繞X的實例」 的語言。 X這裏是遞歸的基礎。

正如您所建立的那樣，目標語言的每個字母都有相同的數字，或者多個一個字母。所以我們可能會問，「X的簡單定義能產生這種語言嗎？」