parse-tree - 文法構文木

Question

次の文法が与えられます

R → XRX|S

S → aT b|bT a

T → XT X|X|

X → a|b

そして、文字列「abab」の派生と解析ツリーを提供するように求められました

これがどのように機能するのか完全にはわかりません. R → S → aTb → abTab → abab を試してみました. mは、上記のGrammarの派生を書く際に書き込み方向に進みます

Answer 1

派生のいくつかのステップをスキップしたようです。以下は完全なもので、各ステップの左側が太字で強調表示されています。

• R [R→S]
• し[し→た]
• a T b [T → XTX]
• a X TXb [X → b]
• abT X b [X → a]
• ab T ab [T → ε]
• アバブ