 | Эта статья требует дополнительных ссылок для проверки . ( декабрь 2009 г. ) ( Узнайте, как и когда удалить этот шаблон сообщения ) |
В информатике , диаграмма анализатор представляет собой тип синтаксического анализа подходит для неоднозначных грамматик (включая грамматики естественных языков ). Он использует подход динамического программирования - частичные гипотетические результаты сохраняются в структуре, называемой диаграммой, и могут использоваться повторно. Это исключает возврат и предотвращает комбинаторный взрыв .
Парсинг диаграмм обычно возлагается на Мартина Кея . [1]
Типы парсеров диаграмм [ править ]
Распространенный подход - использовать вариант алгоритма Витерби . Анализатор Эрел является типом диаграммы синтаксического анализатора используется в основном для анализа в компьютерной лингвистике , названной в честь его изобретателя. Другой алгоритм анализа диаграммы - это алгоритм Кок-Янгера-Касами (CYK).
Анализаторы диаграмм также могут использоваться для анализа компьютерных языков. В частности, синтаксические анализаторы Эрли использовались в компиляторах компиляторов, где их способность выполнять синтаксический анализ с использованием произвольных контекстно-свободных грамматик упрощает задачу написания грамматики для конкретного языка. Однако их более низкая эффективность привела к тому, что люди избегают их для большей части работы с компилятором.
При синтаксическом анализе двунаправленной диаграммы края диаграммы помечаются направлением, вперед или назад, и применяются правила в отношении направления, в котором должны указываться края, чтобы их можно было объединить в другие края.
При инкрементальном анализе диаграммы диаграмма строится постепенно, по мере того как текст редактируется пользователем, причем каждое изменение текста приводит к минимально возможным соответствующим изменениям в диаграмме.
Парсеры диаграмм делятся на нисходящие и восходящие , а также активные и пассивные.
См. Также [ править ]
Ссылки [ править ]
- ^ "Анализ диаграммы" (PDF) . Архивировано из оригинального (PDF) 21 февраля 2015 года . Проверено 20 ноября 2011 года .
Внешние ссылки [ править ]
