Парсер диаграмм - Chart parser

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

Парсинг диаграммы обычно приписывается Мартин Кей.[1]

Типы парсеров диаграмм

Общий подход - использовать вариант Алгоритм Витерби. В Парсер Эрли это тип анализатора диаграмм, который в основном используется для анализа в компьютерная лингвистика, названный в честь его изобретателя. Другой алгоритм разбора диаграммы - это Кок-Янгер-Касами (CYK) алгоритм.

Парсеры диаграмм также можно использовать для анализа компьютерных языков. В частности, парсеры Эрли использовались в компиляторы компилятора где их способность разбирать произвольные Бесконтекстные грамматики облегчает задачу написания грамматики для определенного языка. Однако их более низкая эффективность привела к тому, что люди избегают их для большей части работы с компилятором.

При синтаксическом анализе двунаправленной диаграммы края диаграммы помечаются направлением, вперед или назад, и применяются правила в отношении направления, в котором должны указываться края, чтобы их можно было объединить в другие края.

При инкрементном анализе диаграммы диаграмма строится постепенно, по мере того как текст редактируется пользователем, причем каждое изменение текста приводит к минимально возможным соответствующим изменениям в диаграмме.

Парсеры диаграмм различают сверху вниз и вверх дном, а также активный и пассивный.

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

Рекомендации

  1. ^ «Анализ диаграммы» (PDF). Архивировано из оригинал (PDF) 21 февраля 2015 г.. Получено 20 ноября 2011.

внешняя ссылка