gl5_progのメモ

自分のためのメモとかまとめとか

構文解析用語集

説明は乱暴だしいろいろ間違っている思う。

用語 説明
BNF 文脈自由文法を定義するための記述法。
PEG 形式文法を定義するための文法(言語)。BNFとは違い、定義する文法には曖昧性が存在しないようになっている。また、PEGが定義する文法は文脈自由文法ではないらしい。「失敗したら」というのが文脈依存になるのかな。
文脈自由文法 すべての生成規則が文脈に依存せずに非終端記号を終端記号へ変換できるような形式文法のこと。
形式言語 文字列の集合。無限の集合の場合が多いと思う。
形式文法 変換規則の集合。形式言語の定義を記述できる。生成文法と分析的文法に分かれるらしいけど違いがわからない。非終端記号の集合、終端記号の集合、生成規則の集合、開始記号で構成される。
非終端記号 変換規則が含まれる生成規則
終端記号 変換規則が含まれない生成規則
生成規則 変換ルール
開始記号 開始地点
トップダウン構文解析 開始記号から導出を行う解析手法。LL法などがある。
ボトムアップ構文解析 終端記号から導出を行う解析手法。LR法などがある。
LL法 トップダウン構文解析の1種。入力文字列を左([L]eft)から解析していき、左端導出([L]eftmost Derivation)を行っていく。解析の実装方法として、再帰下降構文解析と表駆動構文解析があるらしい。
再帰下降構文解析 LL法の実装方法の1つ。各生成規則が1つの関数になり、その中で再び各生成規則(関数)を呼ぶことで構文解析を行う。初めて書いたとき美しさに感動した。
導出 生成規則を適用(展開)すること。あるいは生成規則から文字列を生成すること。同じ文字列を生成する過程が複数ある場合、その文法は曖昧な文法らしい。導出は真逆の用法も含んでいる気がする。つまり、「生成規則から文字列を生成する」の逆、「文字列から生成規則を見つけていく」という用法。LL法の左端導出はこっちの用法だと思う。
左端導出 生成規則を適用するとき左端の非終端記号から置き換えていく取り決めを持った導出のこと。

関連リンク