文法解析ツリー？

Question

この質問は私のCS宿題にあり、どのようにそれを行うのか分かりません。

は文法

S ← (L) 
S ← a 
L ← L , S 
L ← S 

が文(a , (a , a))

のための解析木を描く考えてみましょう私は、構造以下しようと、私も正しいとは思えない(L,(L,L))で終わります。誰かが正しい方向に私をプッシュできますか？

Answer 1

はあなたが後にしているものの一部です：

今、あなたは残りの作業を行うために取得:)

Answer 2

文(a, (a, a))を見てください。どちらの右辺（RHS）に一致する可能性がありますか？最初のもの、S ← (L)。したがって、ツリーのルートは、 - ノード、L - ノード、) - ノードの3つの子を持つS - ノードのノードになります。

Lノードの子が何であるか把握し、残りの入力：a,(a,a)と一致させる必要があります。だから、LHSのLの規則を見てください。これらの規則のうち、一致する可能性のあるRHSはどれですか？a,(a,a)？ここで

Answer 3

(a,(a,a))のための解析ツリーがの左端の導出から得られます(a,(a,a))：

S => (L)  [S -> (L)] 
    => (L,S)  [L -> L,S] 
    => (S,S)  [L -> S ] 
    => (a,S)  [S -> a ] 
    => (a,(L)) [S -> (L)] 
    => (a,(L,S)) [L -> L,S] 
    => (a,(S,S)) [L -> S ] 
    => (a,(a,S)) [S -> a ] 
    => (a,(a,a)) [S -> a ] 

あなたのパースツリーのルートはSです。派生物の非終端記号の書き換えごとに、適切なノードを解析ツリーに描画します。また、あなたの文法は最適ではなく、とりわけ連鎖規則を含んでいます。それらを削除すると、aを得るためにをLから派生させる必要がなくなります。