コンパイラ：あいまいな文法を変更する

Question

私はこの演習で少し問題があります。この文法を考える

：

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

a）は、それは文字列

b）参照）文法

Cを捉えどのような言語と言う文法を変更し、子孫を構築して曖昧であることを示していますパーサー

解決方法：

a）

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）私の問題は、パーサーを構築するための文法を変更です：文法は、この言語をキャプチャ

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

B）：私は、文字列 'AB' があいまいな示しています。私は別の文法を試みますが、あまりにもあいまいです。たとえば は、この：

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

あなたは運動のために正しい文法を見つけるか、私に入力を与えるために私を助けることができますか？

Answer 1

you.undoubtedlyが知っているように、言語

S -> X | a S b 

は "a sおよびb Sの等しい数に囲まれたXのインスタンス" と記載することができます。 Xここは再帰の基底です。

設定したとおり、ターゲット言語には、それぞれの文字の数が等しいか、または1つの文字が1つあります。そこで、「Xの単純な定義はどのようにしてこの言語を生成できますか？