Анализ снизу вверх начинается с листовых узлов дерева и работает в направлении вверх, пока не достигнет корневого узла. Здесь мы начинаем с предложения, а затем применяем правила производства в обратном порядке, чтобы достичь начального символа. На приведенном ниже изображении показаны доступные парсеры снизу вверх.
Shift-Reduce Parsing
Разбор Shift-Reduce использует два уникальных шага для анализа снизу вверх. Эти шаги известны как шаг сдвига и шаг понижения.
-
Шаг сдвига: шаг сдвига относится к продвижению входного указателя к следующему входному символу, который называется смещенным символом. Этот символ помещается в стек. Смещенный символ обрабатывается как один узел дерева разбора.
-
Шаг сокращения : когда анализатор находит полное правило грамматики (RHS) и заменяет его на (LHS), это называется сокращением шага. Это происходит, когда вершина стека содержит дескриптор. Чтобы уменьшить, функция POP выполняется в стеке, который выскакивает из дескриптора и заменяет его нетерминальным символом LHS.
Шаг сдвига: шаг сдвига относится к продвижению входного указателя к следующему входному символу, который называется смещенным символом. Этот символ помещается в стек. Смещенный символ обрабатывается как один узел дерева разбора.
Шаг сокращения : когда анализатор находит полное правило грамматики (RHS) и заменяет его на (LHS), это называется сокращением шага. Это происходит, когда вершина стека содержит дескриптор. Чтобы уменьшить, функция POP выполняется в стеке, который выскакивает из дескриптора и заменяет его нетерминальным символом LHS.
LR Parser
Парсер LR — это нерекурсивный парсер снизу вверх. Он использует широкий класс контекстно-свободной грамматики, что делает его наиболее эффективным методом синтаксического анализа. Парсеры LR также известны как парсеры LR (k), где L обозначает сканирование входного потока слева направо; R обозначает построение крайнего правого вывода в обратном направлении, а k обозначает количество символов предпросмотра для принятия решений.
Существует три широко используемых алгоритма для создания парсера LR:
- SLR (1) — простой анализатор LR:
- Работает на наименьшем классе грамматики
- Несколько штатов, следовательно, очень маленькая таблица
- Простая и быстрая конструкция
- LR (1) — LR Parser:
- Работы по комплектации грамматики LR (1)
- Создает большую таблицу и большое количество состояний
- Медленное строительство
- LALR (1) — синтаксический анализатор LR:
- Работает на среднем уровне грамматики
- Количество состояний такое же, как в SLR (1)
Алгоритм синтаксического анализа LR
Здесь мы опишем скелетный алгоритм парсера LR: