Введение
Тип анализатора для неоднозначных грамматик
В информатике, chart-анализатор (или анализатор на основе диаграммы) — это тип анализатора, подходящий для неоднозначных грамматик (включая грамматики естественных языков). Он использует подход динамического программирования: частичные гипотетические результаты хранятся в структуре, называемой диаграммой, и могут быть повторно использованы. Это устраняет возврат к предыдущим шагам (backtracking) и предотвращает комбинаторный взрыв. Разбору на основе диаграммы обычно приписывают авторство Мартина Кея.
Типы анализаторов диаграмм
Общий подход — использовать вариант алгоритма Витерби. Парсер Эрли — это тип анализатора диаграмм, который в основном используется для синтаксического анализа в вычислительной лингвистике и назван в честь своего изобретателя. Другим алгоритмом анализа диаграмм является алгоритм Кокке — Юнгер — Касами (CYK). Анализаторы диаграмм также могут использоваться для синтаксического анализа компьютерных языков. Парсеры Эрли, в частности, использовались в компиляторах, где их способность анализировать с использованием произвольных контекстно-свободных грамматик упрощает задачу написания грамматики для конкретного языка. Однако их меньшая эффективность привела к тому, что их избегают при большинстве работ по компиляции. В двунаправленном анализе диаграмм рёбра диаграммы маркируются направлением — либо вперёд, либо назад, — и правила применяются к направлению, в котором должны быть ориентированы рёбра, чтобы их можно было объединить в новые рёбра. При инкрементном анализе диаграмм диаграмма строится постепенно по мере редактирования текста пользователем, при этом каждое изменение текста приводит к минимально возможному соответствующему изменению диаграммы. Анализаторы диаграмм различаются по принципу построения — сверху вниз и снизу вверх, а также по типу — активные и пассивные.