Детерминированный анализ

В обработке естественного языка, детерминированный синтаксический анализ относится к синтаксическому анализу алгоритмам, которые не выполняют обратный поиск. LR-парсеры являются примером. (Это значение слов «детерминированный» и «недетерминированный» отличается от того, которое используется для описания недетерминированных алгоритмов.)

Детерминированное поведение желательно и ожидается в компиляции языков программирования. При обработке естественного языка долгое время считалось, что детерминированный анализ невозможен из-за двусмысленности, присущей естественным языкам (многие предложения имеют более одного правдоподобного анализа). Таким образом, пришлось применять недетерминированные подходы, такие как анализатор диаграмм . Однако в 1978 году был предложен синтаксический анализатор Парсифаля, который мог справляться с неоднозначностями, сохраняя при этом детерминированное поведение.

• Детерминированная контекстно-свободная грамматика

• Альфред В. Ахо, Стивен К. Джонсон, Джеффри Д. Уллман (1975): Детерминированный анализ неоднозначных грамматик. Comm. ACM 18: 8: 441-452.
• Митчелл Маркус (1978): Теория синтаксического распознавания естественного языка. Докторская диссертация, Департамент электротехники и информатики, Массачусетский технологический институт.