文脈自由文法
ある文法において、開始記号からある文字列が導出される過程を記述する方法は二種類存在する。単純な方法は導出過程の途中の文字列を全て書き出していく方法である。つまり開始記号から始めて、生成規則を一回適用する度に文字列を書き出して、最後に目的の文字列になるまで列挙するのである。例えば「左端に最も近い非終端記号を最初に書き換える」という規則を適用したとすれば、文脈自由文法では適用する生成規則を列挙するだけで十分である。これを文字列の「左端導出」(Leftmost Derivation)と呼ぶ。例えば、以下の文法があるとする。
(1) S → S + S (2) S → 1 (3) S → a
文字列「1 + 1 + a」を導出する過程は [ (1), (1), (2), (2), (3) ] というリストになる。同様に「右端導出」も定義できる。この例の場合、右端導出での導出過程は [ (1), (3), (1), (2), (2)] というリストになる。
左端導出と右端導出のリストが異なるのは重要なポイントである。構文解析では、文法規則毎にそれを入力文字列に適用する小さなプログラムが存在する。したがって、構文解析が左端導出を行うのか右端導出を行うのかによってそれらのプログラムを適用する順番が変わってくるのである。