概要
この記事ではA.V.エイホとR.セシィ共著のコンパイラ 原理・技法・ツールでよく忘れてしまう単語を備忘録としてまとめます。
忘れやすい単語
再起下降構文解析
下向き解析の一種で、文法で用いる各非終端記号に対して一つの手続きを用意しておき、それらの手続きの実行によって入力記号列を処理する。
再帰が循環して括弧の中に入っている様子から再帰下降
この表現は分かりやすいかも。 https://qiita.com/7shi/items/64261a67081d49f941e3#%E6%8B%AC%E5%BC%A7
予約型構文解析
再起下降構文解析で、先読み記号によって次にどの非終端記号に対する手続きを呼び出せばよいかが一意に決まる。 例えば複数ある手続きの先頭がそれぞれ一意であれば、次の非終端記号の先頭を見ればすべてを見なくてもどの手続きをすれば良いかが分かる。 この本ではFIRSTという関数を作り、先頭文字を取り出している。
simple という手続きであれば、先頭がinteger,char,numのどれかなので
FIRST(simple) = {integer, char, num}
と書ける。
構文主導翻訳スキーム
入力の階層構造を利用して、出力を生成しようとする方式。
BNF (バッカスナウア記法)
この記事が分かりやすい。 https://qiita.com/7shi/items/64261a67081d49f941e3#bnf
表圧縮法
有限オートマトンで遷移関数を管理するために配列を使うアクセスは早いがメモリ空間を多く使用してしまう、逆にリスト構造を使用するとメモリ空間の使用率は抑えられるがアクセス速度が落ちてしまう。
表圧縮法はこの配列とリスト構造の良いところ取りをした管理方法である。