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

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

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

Смотрите также

Ссылки

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