  |
はてなキーワード: DFAとは
http://tradenote.info/blog-entry-3.html
一般に、バッカスナウア記法は正規表現では処理できないネストの階層を記憶できるなどの根本的な差があります。
これは正規表現が有限決定性オートマトン（DFA）ないしε遷移と不特定の同種記号の遷移を用いる非決定性オートマトン（NFA）に基づいているのに対し、BNF記法での解析は必然的にスタックを内部状態に持つからです。
https://ja.wikipedia.org/wiki/LL%E6%B3%95
これは左からトークンを走査して、導出する非終端記号を左から決定していくアルゴリズムです。
例えばA→A Bという構文規則があった場合に、Aの還元内でAを還元できるかどうか判定し続けて無限ループに陥ってしまい、いつまで経ってもBの判定に辿り着けません。これを左再帰といい、LLでは左再帰を直接扱う事ができません。
非終端記号の間接的還元を考慮したはじめに現れる終端記号の集合（FIRST集合）を構築して上手く左再帰を回避しなければなりません。
マッチングに用いる規則をベタに関数内部に再帰させながら順番に書いていくだけなので実装は容易です。
https://ja.wikipedia.org/wiki/LR%E6%B3%95
https://ja.wikipedia.org/wiki/LALR%E6%B3%95
こちらは左からトークンを走査して、導出する非終端記号を右から構築するアルゴリズムです。
BNF構文規則から走査に相応するDFAを構築し、DFAの遷移を記憶しながらスタックに状態をpush/popし構文解析を行います。
なのでLL法にあるような左再帰を直接扱えないという欠点がなく、むしろスタックが簡潔になるため積極的に左再帰のBNF記述を行った方が効率よく処理を進められます。
LR法はDFAの大きさが巨大になるため、実用的ではないようです。
LALR法はLR法を改良したアルゴリズムで、扱える構文クラスの範囲はLRよりも少し小さくなりますが現実的な計算資源で構文解析を行う事ができます。
