2 
E -> E+E|E*E|(E)|a

文法が与えられた場合、文法を LL(1) 形式に変換するにはどうすればよいですか?

E->aX|(E)
X->+E|*E|epsilon

これは LL(1) 文法ですか?

4

2 に答える 2

1

元の文法は再帰的に残されているため、LL(1) ではなく、実際には任意の k に対して LL(k) ではありません。

幸いなことに、左再帰は削除できます。標準アルゴリズムは、直接左再帰 (ここにあるように) と間接左再帰を別々に処理することによってこれを行います。即時左再帰は、2 つのうちの単純なケースです。ウィキペディアの記事では、ここで説明しています。

基本的に、再帰参照に続く部分を新しいプロダクション (テール) に移動します。これにはε代替手段もあります。

   X -> ε|+E|*E

次に、元のプロダクションから左の再帰的代替を削除しX、残りのすべての非再帰的代替を追跡できるようにします。

   E -> (E)X|aX

あなたの提案はX、括弧で囲まれた表現に従わないため、同じ言語を認識しないことに注意してください。

于 2013-08-17T09:49:07.993 に答える