Loading article…
自然言語処理において、決定論的構文解析とは、バックトラックを行わない構文解析アルゴリズムを指します。LRパーサーはその一例です。（「決定論的」と「非決定論的」という言葉の意味は、非決定論的アルゴリズムを説明する際に用いられる意味とは異なります。）
プログラミング言語のコンパイル においては、決定論的な動作が望まれ、期待される。自然言語処理においては、自然言語に内在する曖昧さ（多くの文には複数の妥当な構文が存在する）のため、決定論的な構文解析は不可能であると長らく考えられていた。そのため、チャートパーサーのような非決定論的な手法を用いる必要があった。しかし、ミッチ・マーカスは1978年に、曖昧さを扱いながらも決定論的な動作を維持できるパーシファル構文解析器を提案した。