注目★★★★★Lobsters
APLR(1): IELR(1)より簡潔・高性能なコンパクトLR(1)パーサ生成アルゴリズム
30秒で把握
- 1Hocc が APLR(1) を実装・LALR(1) の謎コンフリクトを排除したコンパクトパーサを生成
- 2非決定性・曖昧文法に対応し GLR 技法とも組み合わせ可能
- 3IELR⁺(1) と互換運用できサブグラフ同型探索ベースで概念的にシンプル
要約
Hemlock言語プロジェクトのパーサジェネレータHoccが、新しいLR(1)系アルゴリズム「APLR(1)（Adequacy Preservation LR(1)）」を実装した。APLR(1)は非決定性・曖昧文法にも対応しつつ、LR(1)相対的な不適切性を持たないコンパクトなパーサオートマトンを生成する。既存のLALR(1)が状態マージ時に生じる「謎のコンフリクト」を抱えるのに対し、APLR(1)は文法開発中にそのような問題が発生しない。
あなたへの影響
パーサジェネレータを自作・評価しているチームにとっては参考情報。
推奨：LALRの謎コンフリクトに悩んだ経験があれば、アルゴリズムの詳細を確認しておく程度で十分。