Adaptive LL(*) Parsing: The Power of Dynamic Analysis
最近のパーサ PEG, LL(*), GLR, GLL でもまだまだ解決できない問題がある。
例えば副作用を持つ動作をサポートすることや、パフォーマンスを予測できず、速度が遅くなってしまう、直感的ではない動作をしてしまう等々である。
この論文は簡潔で、効率よく、従来のLL(k)の様に予測でき、GLRの様に強いALL(*) を提案する。
今回の１番の改善点はパース時間である。
ALL(*) は非左再帰文脈自由文法を受理でき、オーダーはO(n4)である。(これはこの論文状の実験上の話であるが)
ANTLR4は ALL(*)パーサを作成することができると同時に左再帰に書き直すことができる。
世界中でとても使われているANTLR4によりALL(*)のアプリケーションへの有用性は証明される。
コンピュータ言語のパーサは長い歴史の中、研究され精錬されてきたのにも関わらずまだまだ問題がたくさんある。コンピュータの処理速度がそんなによくなかった頃、プログラマはLALR(k),またはLL(k)を使っており制約の中で開発をしていた。近年、処理速度が上がり研究者の開発は(お金がかかるものの)よりパワフルになった。LL下降構文解析,LR上降構文解析。
GLR,LL(*)がANTLR3から登場し、最近ではGLLというのも生まれた。
しかし上の解析手法はLALR(k),LL(k)よしとても使いやすいが、いくつか弱点があった。
1つ目に、非決定性構文解析は時々予期しない挙動をする。GLL,GLRは曖昧な文脈に対し複数の木を返す。(とは言えこれは仕方がない。自然言語を扱う様に設計されたのであえて曖昧なものを扱ええる様にしてある) これはコンピュータ言語としてはエラーを引き起こす。コンピュータが一つの処理を行うために木の曖昧性を消すには時間とメモリが必要である。
PEGは明確に定義されたものであるが、おかしな挙動をする。
rule
A -> a | ab
は、決してabには一致しない。なぜならPEGは最初の(左)ルールを選択するので残りは選ばれないからであす。これは再帰的なルールのデバッグをより難しいものとしている。
2つ目に、副作用のある動作は避けられているはず(連続的投機(PEG), 入力の複数解釈(GLL,GLR)。なぜかというとそれらの動作は多分実際に副作用のない動作にはできないからである。
動作は不変データへの緩衝材になりつつ、戻る動作を提供しないといけない。
副作用を避ける一般的な手法として後置処理として木を作るというものがある。しかし入力ファイルの長さがメモリによって制限される。
パーサはパースツリーを作るがとても大きいデータを解析したり、無限のストリーミングデータ(ネットワーク通信的な)ものは扱えない。
3つ目に、自分たちの実験で分かったがGLL,GLRは遅くなるのと使用する、メモリサイズ、処理時間が予測でいないという問題がある。複雑になると度々O(n3)やO(np+1)(pは最大ルール長)となる。理論的には文脈自由構文解析器は決定性構文解析を線形時間で行える。今回、私たちは特定のケースにおいて度々GLL,GLRがALL(*)より遅くなることを発見した。LL(*)は正規表現のような決定オートマトンを使い上の弱点を克服する。k個固定し先読みするのではなく(LL(K))、残り全てを先読みする。DFAを制限された先読みLL(*)に使うことで先読み言語は文脈自由文法だが他の先読み言語と差別化をする。しかし一番の問題はLL(*)は安定して文法を決定できないことに加えたまに失敗する。(一致する表現を見つけられない)。ANTLR'3は避けるべき決定できない状況を見つけている。バックトラックは決定できない不明瞭なものではない最初の要素を選択する。
A -> a | a
ここでaは文法列(LL(*)ではない
この論文ではAdaptive LL(*)(ALL(*))を紹介する。これはトップダウン構文解析の簡単さとGLRのような強さを持つ。特にLL構文解析は予測決定?(非終端)に到達すると止まり、やり直す。この仕組みは最適な文法を拡大するために選択をしていく。この選択はLL(*)の非決定文法を避けると同時に正しいパーサを非再帰性文脈自由文法のために生成する。
静的解析はすべての入力列の可能性について考慮しなければならない。動的解析は最終的にどの様な結果になればいいのかのみを考慮する。
考えとしてALL(*)は決定点でサブパーサを実行する。サブパーサは擬似平行に実行されすべての可能性のあるパスを探す。サブパーサは一致しないものに当たると
終了する。最小の深さで一つだけサブパーサが生き残るよう解析していく。
もし複数のサブパーサがファイルの終端に到達した場合は文法の短い方を選択しつつ、文脈の曖昧さを告知する。
ALL(*)は結果をメモ化する。先読みして予測される文法を動的に書き込んでいく。これにより他のパーサより早く予測することができる。見知らぬ入力文をとりいれてDFAが更新されていく。
指数関数的にサブパーサが増えることを防ぐため予測はgraph-structured stackを用いる。GLRの手法とALL(*)の方法はサブパーサを使う以外は同じであるがGLRは終端をGSSにセットしないといけないがALL(*)はしなくても良い