LL法
構文解析器は特定の形式文法に従った文字列を扱う。
構文解析器は以下の要素から構成される。
入力バッファ: 入力トークン列を格納する。
スタック: 解析対象文法の終端記号と非終端記号を格納する。
構文解析表: スタックのトップにある記号と次の入力トークンに従って適用すべき文法規則を示す。
構文解析器はスタックのトップにある記号と入力バッファ上の現在の記号から適用すべき規則を決定する。
構文解析器が動作開始したとき、既に以下の2つの記号がスタックにある。
ここで、'$' は特殊な終端記号で、スタックの底と入力バッファの最後を示す。'S' はその文法の開始記号である。構文解析器はスタックの内容を入力バッファの内容に従って書き換えていく。しかし、書き換えが必要かどうかはスタック上の内容だけで決定される。
例が示すように、LL法の構文解析器はスタックのトップが終端記号の場合、非終端記号の場合、特殊記号 $ の場合の3種類のステップを実行する。
トップが非終端記号の場合、構文解析表を参照し、適用すべき文法規則を決定して実行し(スタックを書き換え)、適用した規則の番号を出力する。構文解析表において、その非終端記号と入力バッファ上のトークンの組み合わせで適用すべき規則が記されていない場合、エラーを通知して停止する。
トップが終端記号の場合、入力バッファとスタックの記号を比較し、それらが同じである場合に取り除く。違っていた場合、エラーを通知して停止する。
トップが $ の場合、入力バッファも $ なら、構文解析成功を通知する。入力がまだある場合、エラーを通知する。いずれの場合も構文解析器は停止する。
これらのステップは構文解析器が停止するまで繰り返され、構文解析が成功して左端導出を出力するか、さもなくばエラーを通知する。