あいまいで曖昧でない文法のツリーを構文解析

Question

明瞭な文法では、左と右の両方の導出が同じ構文解析ツリーを生成しますか？ 2つ以上の解析木を持つ文法を読んだので、あいまいであると言われています。

Answer 1

文法が曖昧でない場合は、解析ツリーは1つのみです。 （定義によると）したがって、左端と右端の派生は同じ木を生成します。

派生をツリーウォークと考えることができます。与えられたツリーに対して、それを横断する可能性のあるさまざまな方法があります。左端および右端の導出は、それぞれ深度優先のプリトラクションおよびポストオーダートラバースです。