決定論的解析

自然言語処理において、決定論的解析とは、バックトラックを行わない解析 アルゴリズムを指します。LRパーサーはその一例です。（「決定論的」と「非決定論的」という言葉の意味は、非決定論的アルゴリズムを説明する際に使用される意味とは異なります。）

プログラミング言語のコンパイル においては、決定論的な動作が求められ、期待されています。自然言語処理においては、自然言語に内在する曖昧性（多くの文には複数の妥当な構文解析が存在する）のために、決定論的な構文解析は不可能だと長らく考えられてきました。そのため、チャートパーサなどの非決定論的なアプローチを適用する必要がありました。しかし、ミッチ・マーカスは1978年に、決定論的な動作を維持しながら曖昧性に対処できるパーサ「パルジファル」を提案しました。

参照

• 決定論的文脈自由文法

参考文献

• Alfred V. Aho、Stephen C. Johnson、Jeffrey D. Ullman (1975): 「曖昧文法の決定論的解析」 Comm. ACM 18:8:441-452.
• ミッチェル・マーカス（1978）：「自然言語の統語認識理論」マサチューセッツ工科大学電気工学・コンピュータサイエンス学科博士論文。