はじめに
文脈自由文法, LL(1), SLR(1) について書く
自分なりの理解を書きなぐってあります、間違ってたら教えて下さい。
文脈自由文法
A : B, C, d, e, F
みたいなのが並んだやつ, ただし大文字は非終端記号(自分で定義した記号)で、小文字は終端記号(文字列に含まれる記号)
また、空文字としてはεというものが一般的に使われる。これasciiに含まれてないから不便だと思うんですけど
重要なのは、左辺は非終端記号が1個ということ。右側はなんでもいい。
また、スタートを表す非終端記号を決めておく(大体S)。これ1個からスタート。
これをパースする方法を学ぼう！というわけ。
あとなんか計算量では記号の種類とかの構文のサイズ諸々は定数として扱われるっぽい。
また、解析した結果のものを構文木と呼ぶ。もちろん構文と入力によっては複数種類できることもある。
チョムスキーの標準系
これを解析する一番思考停止な方法は
dp[左][右][非終端記号] = [左, 右]を非終端記号にパースできるか
という区間DPである、計算量O(N3)で解析できるような気がする
が、よく考えたら
A : B B : A
とかで遷移にループが出来る。もちろんこのケースならどうせ何も入力できないので問題はないが、DPにおいてループが発生すると大体不幸なことになるので多分爆発炎上ケースが作れる。
なので、もうちょっと構文を制限したい。それがチョムスキーの標準系。
これは
A : BC A : a S : ε
の3種類に制限したもの。
実はどんな構文もこれに変換できる。
A : BC A : a A : ε
に変換するのは簡単。で、ここから変換するのはなんかεになりうる物を列挙してうまいことやれば除去できる。
で、チョムスキーの標準形にすると、ループが消えて区間DPが出来るようになる。やったね。
CYK法
実はこの区間DPにはこういう名前がついている
LL(1)
ICPCで普通に行う構文解析は 構文解析 Howto · GitHub がわかりやすい。
これは例えば
A : B c D
という規則があったら
void parse_A() {
parse_B();
consume('c');
parse_D();
}
という関数を作って、parse_S()を呼び出せば全部パースできてハッピーという話である。
ここで問題になるのが、
A : B C | D E
みたいにあった時に、どちらの生成規則を使うか決定する方法である。
ICPCだと、だいたいad-hocになんとか出来てしまう。
ここで、例えば
A : B | C B : "abc" C : "def"
だとすれば、次の文字を見て"a"だったらB、"d"だったらCとすればよい。
つまり、各生成規則ごとに"次に到達しうるconsumeで消費する文字の集合"を見て、次の文字が入ってるものをパースすれば良い。
これがLL(1)で、計算量はO(N)
なお、この集合はdirectorと呼ばれて、これの計算のためにfirst/followという関数が定義される
また、複数候補が生まれうるならばそれはLL(1)では解析できないということである
SLR(1)
LL(1)はつよいが、
A : B | C B : "abb" C : "abc"
という規則ですら解析できない。なのでLL(1)をちょっと強化したSLR(1)という物を考える。
やることは単純で、LL(1)で複数候補があるならば、全部試せばよい、という方法(だと思った)。
もちろん計算量が増大しては意味が無いため、O(N)で解析できるぐらいに留める。
具体的には、"次に使いうるconsume関数の集合"をもってparseする。
文字が入力されたら、その文字に対応するconsume関数を列挙して取り出して、それらを進め、また集合を再計算する。これはshift動作と呼ばれる。
もしparseの最後に到達しているものがあり、かつそのparseのLeftのfollow集合が入力された文字ならその関数は解析成功とする。入力された文字は消費せず、そのparseのLeftを入力する。
なんかこれらが複数同時に起こると衝突する。
これらを再帰関数でやるのは大変なので、スタックを直接操作する。表とかを作るのだが、集合を列挙することからもわかるように人間のやるものではない
