博士

やあ、ロボ子！今日の話題はEarley parserじゃ。任意のcontext-free grammarを扱える、すごい奴なのじゃぞ！

ロボ子

Earley parserですか。確か、最悪の場合の計算量はO(n^3)だと聞きました。

博士

そうじゃ！でも、健全なgrammarならO(n)で済むし、右再帰があってもLeoの最適化でO(n)にできる場合があるんじゃ。

ロボ子

Leoの最適化、ですか。右再帰のパフォーマンスを改善するのですね。

博士

その通り！Earley parserは、入力位置に列を持つEarley chartを作るのが特徴じゃ。Elizabeth Scottって人が、同じ計算量でParse Forestも作れるって証明したんじゃぞ。

ロボ子

Parse Forestですか。構文解析の結果を効率的に表現できるのですね。

博士

C言語のdangling else fixみたいに、曖昧さを解消する規則がある場合は、SPPFを反転させるか、2回目のレイヤーが必要になるんじゃ。

ロボ子

曖昧さを解消するために、grammarやtoken streamを反転させることもあるんですね。

博士

そうそう！C言語のparserでは、typedef情報を得るために、曖昧さを解消したparse treeから情報を取得して、typedefの使用が無効なEarley stateを拒否するんじゃ。

ロボ子

typedefの情報を使って、構文解析の精度を上げているんですね。

博士

別の方法として、最初の認識とparsingの段階でstate pruningをすることで、2回目の認識とparsingを回避できる可能性があるんじゃ。

ロボ子

state pruningですか。不要な状態を早期に排除することで、効率化を図るのですね。

博士

Earley parserの競合としては、CYK、GLR、GLL、Parsing With Derivatives、Parsing With Zippersがあるんじゃ。それぞれ一長一短じゃな。

ロボ子

色々なparserがあるんですね。それぞれ得意なこと、不得意なことがあるのでしょうか。

博士

例えば、CYKは常にO(n^3)だけど、GLRは未解決のperformance edge caseがあるんじゃ。GLLは右再帰のfixがないからO(n^2)になっちゃうし。Parsing With Derivativesはperformanceに問題があるみたいじゃ。

ロボ子

なるほど。parserの選択は、grammarの特性や求められるパフォーマンスによって変わってくるんですね。

博士

そういうことじゃ！Parsing With Zippersは有望らしいけど、まだ広く記述/理解されていないみたいじゃな。…ところでロボ子、parserって、まるで私の部屋みたいじゃな。

ロボ子

どういうことですか、博士？

博士

複雑で、色々なものが詰まってて、最適化が必要…ってね！

ロボ子

…博士の部屋は、Earley parserよりもカオスな気がします。