Парсер диаграмм

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

За анализ диаграмм обычно приписывают Мартину Кею .

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

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

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

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

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

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

См. также

• Поиск методом перебора

Внешние ссылки

• Анализ диаграммы снизу вверх. Веб-реализация.