Disambiguating Context-Free Grammars by Selecting the Minimum-Cost Parse Tree

言語は、単純な要素から複雑な概念を構築することを可能にする規則の体系です。コンピュータの世界では、これらの規則は文法と呼ばれ、マシンに対してコードの文字列や文章をどのように理解すべきかを伝えます。理想的には、一連の規則は、与えられた入力に対して唯一の解釈をもたらすべきです。しかし、プログラミング言語を記述するために用いられる多くの文法は曖昧であり、一つのテキストの文字列が、複数の相反する解釈を生むことがあります。典型的な例は、足し算と掛け算のような二つの演算を含む文章です。明確な指示がなければ、コンピュータは、足し算を先に行うべきか、それとも掛け算を先に行うべきかを判断できません。同様に、一連の「if」文においては、コンピュータはどの条件に「else」の指示が属しているのかを判断できなくなることがあります。コンピュータが正しく機能するためには、必ず正確に一つの解釈を選択しなければなりませんが、規則自体はしばしば明確な勝者を提示してくれません。

数十年にわたり、この混乱に対処するための標準的な方法は、規則を手作業で書き換えたり、行き詰まった際にコンピュータが進むべき道を示す特別な宣言を追加したりすることで、規則を曖昧でないものへと強制的に修正することでした。これらの手法は特定の種類の問題にはうまく機能しますが、人間の介入を必要とし、時には言語の本来の構造を壊してしまうこともあります。ミナ・ヘマティカルィンカニ（Mina Hematikarimkhani）によって提案された新しいアプローチは、この問題を「規則を書き換えて解決すべきパズル」としてではなく、「最適化の課題」として扱います。この手法は、間違った答えを削除しようとするのではなく、あらゆる可能な解釈を評価し、特定の基準に従って最も「安価な」ものを選択するようにコンピュータに求めます。

核心となるアイデアは、コンピュータがテキストを理解するために構築する、あらゆる可能な木構造（ツリー構造）に対してコストを割り当てることです。このシステムにおいて、木は文章の一つの解析方法を表します。コストは金銭的な価値ではなく、三つの要因に基づくスコアです。第一に、システムは、ユーザーが好むパターン（例えば、どの演算を優先すべきかといった規則）に木が何度違反したかをカウントします。第二に、木のノードの数をカウントし、これによりコンピュータが無限ループに陥るのを防ぎます。最後に、もし二つの木が同じスコアを持っていた場合、一意の識別子がタイブレークを行い、コンピュータが常に全く同じ結果を選択することを保証します。コンピュータは、合計スコアが最も低い木を保持します。このシステムは、悪い選択を全面的に禁止するのではなく、ペナルティを課すことで、言語内のすべての有効な文章が、たとえその解釈に何らかの規則違反が含まれていたとしても、必ず正確に一つの解釈を受け取ることを保証します。

この最適な木を見つけ出すために、研究者たちは「動的計画法」と呼ばれる手法を用いています。これは、複雑な問題をより小さく、重なり合う断片に分解することで解決する方法です。コンピュータが文章を見つめ、その小さな断片の一つひとつを理解する最善の方法を考え、それらの断片を組み合わせて全体を理解しようとしている様子を想像してください。演算の順序を決めるような単純なケースでは、コンピュータは隣接する要素だけを見れば十分です。しかし、「dangling else（宙ぶらりんのelse）」問題のように、ある「else」節が近くの「if」に属するのか、あるいは遠くの「if」に属するのかという、より複雑な状況においては、コンピュータはさらに下の構造まで見る必要があります。これに対処するため、研究者たちは「プロファイル」という概念を導入しました。コンピュータが木の小さな断片を構築する際、その下にどのような構造があるのか（例えば、その枝が特定の種類の規則で終わっているかどうかなど）を親となる構造に伝える、簡潔な要約、すなわちプロファイルも同時に作成します。これにより、コンピュータは毎回ツリー全体を再構築することなく、文章の遠く離れた部分について情報に基づいた決定を下すことができます。

この手法は、空のステップや循環参照を含む規則であっても、あらゆる規則のセットに対して機能します。テストにおいて、研究者たちは、混合演算を含む数学的表現や、入れ子になった条件文を含む様々な例にこの技術を適用しました。あらゆるケースにおいて、システムは単一の最も適切な木を特定することに成功しました。例えば、足し算と掛け算の両方を含む文字列が提示されたとき、システムは標準的な数学的優先順位を尊重する木を正しく選択し、その規則に違反する木に対して高いコストを割り当てました。入れ子の「if」文に直面した際、システムは「else」を最も近い「if」に正しく結合させました。これはプログラミングにおける標準的な慣習です。また、特定の規則が提供されなかった場合でも、システムの構造に基づいた一貫性のある決定論的な選択を行うことで、ケースを処理できました。

この手法は強力ですが、著者自身もその限界を明らかにしています。入力が大きくなるにつれてアルゴリズムの実行時間は大幅に増大するため、毎秒数百万行のコードを処理する現代の高速なプロダクション・コンパイラの要求を満たすには、あまりに低速です。むしろ、研究者たちはこのアプローチが、言語エディタ、静的解析ツール、あるいは教育用ソフトウェアのように、生の速度よりも再現性や複雑で乱れた規則の扱いが重要となる、任意のユーザー定義文法を扱うツールに適していると考えています。結果の質はユーザーが提供するパターンに完全に依存します。もし規則が不完全であったり矛盾していたりする場合、システムは依然として結果を返しますが、それは人間が意図したものとは異なる可能性があります。この手法は、文法がそもそも曖昧であるかどうかを判定するという根本的な数学的問題を解決するものではありませんが、曖昧さに遭遇した際にそれを回避するための信頼できる方法を提供します。

この研究は、言語処理に対する私たちの考え方に転換をもたらしています。言語の規則をコンピュータが目にする前に完璧なものにしようとするのではなく、コンピュータがすべての可能性を探索し、明確で測定可能な基準に基づいて最善のものを選べるようにするのです。これは、曖昧さが自然言語および人工言語のいずれにおいても特徴の一つであることを認め、元の構造を失うことなくそれを管理する方法を提示しています。曖昧さを最小コストの探索として扱うことで、研究者たちは柔軟で堅牢であり、複雑な文法の乱雑な現実にも対応できる、あらゆる有効な文章に対して常に一つの明確で再現可能な回答を保証するツールを作り上げたのです。