parsing - 文法構文木?

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 ). したがって、ツリーのルートは、-node、-node、および -nodeSという 3 つの子を持つ -node になります。(L)

次に、 -node の子が何であるかを把握する必要がありL、それらは残りの入力と一致する必要があります: a,(a,a). だからL、LHS にあるルールを見てください。これらのルールのうち、一致する 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。派生における非終端記号の書き換えごとに、解析ツリーに適切なノードを描画します。また、あなたの文法は最適ではなく、とりわけ連鎖規則が含まれています。それらを削除すると、から派生するS必要Lがなくなりますa。