LL（k）文法に変換します

Question

私は練習問題を解決しようとしていましたが、私はサンプル回答と私とを比較しようとしたときに問題に直面しました。ここでは文法は、変換前にある：

E-> S* 
S-> SD 
S-> D 
D-> [D] 
D-> x 

開始記号はEであり、他非終端記号はSとDです。ここ

私の答えは次のとおりです。サンプルの回答で

E-> S* 
S-> DS' 
S'-> DS' 
S'-> 
D-> [D] 
D-> x 

、彼らはS-> DS'を持っていない、とEはE-> DS'*になります。左再帰を除去するための本で使用される方法、

A -> Aa 
A -> b 

=> A -> bA' 
    A' -> aA' 
    A' -> 

にS-> DS'があるはずです。私は今これについて混乱している、そしておそらく私はちょうどこのメソッドを理解していない。誰も私にこれについてのヒントを教えてもらえますか？また、星記号の意味を教えていただけますか*ここにありますか？どうもありがとう！

Answer 1

あなたの答えに間違いはありません。サンプルの答えは、それを変換した後の文法を単純化するだけです。

E -> S* 
S -> DS' 

S'とDのルールを与えられ、SとEが他の作品には存在しないと仮定すると、文法のこの部分は、最初の製造におけるSは単にた

E -> DS'* 

と等価です除去された第2の生産物に定義されているように、DS'に置き換えられる。

*シンボルはおそらくKleene starです。これは、Sが任意の回数（ゼロを含む）発生する可能性があることを意味します。しかし文脈がなければ、それは伝えるのが難しく、また別のことを意味するかもしれません。