Перейти к основному содержимому

Восходящий анализ

Восходящий анализатор пытается построить вывод в обратном порядке, выводя начальный символ из разбираемой строки.

Реализация такого парсера использует самый правый вывод (rightmost derivation). Строка разбирается путём чтения символов (shifting), пока не будет найдена подстрока, соответствующая правой части правила.

Часть формы предложения (sentential form), которая соответствует правой части правила вывода, называется дескриптором (handle). Как только дескриптор найден, подстрока в форме заменяется (reduce) на нетерминал в левой части правила.

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

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

Таким образом, парсер может выполнять следующие действия:

  • shift: чтение очередного символа из входной строки
  • reduce: замена в соответствии с одним из правил грамматики
  • accept: последовательность распознана
  • error: последовательность нераспознана и не соответсвует языку

Синтаксический анализатор, работающий по такому принципу называют анализатором сдвига-свёртки (shift-reduce parser).

Разрешение конфликтов​

Для неоднозначной грамматики существует проблема выбора действий. Такие ситуации называются конфликтами. Можно выделить несколько видов конфликтов:

  • shift/reduce: выбор между считыванием очередного символа и свёрткой
  • reduce/reduce: одни и те же символы могут быть заменены с использованием разных правил вывода

Чтобы справиться с такими проблемами, синтаксический анализатор может использовать два принципиально разных подхода:

  1. на этапе формирования таблицы действий сделать выбор в пользу одного из возможных вариантов
  2. на этапе анализа разобрать все варианты

В первом случае конфликт может быть разрешён банальным выбором первой попавшейся альтернативы, либо более осмысленным методом, например, через просмотр вперёд (lookahead).

Синтаксический анализ, при котором во время анализа разбираются несколько вариантов называется обобщённым (generalized parsing).