Синтаксические анализаторы следуют производственным правилам, определенным посредством контекстно-свободной грамматики. Способ реализации правил производства (деривация) разделяет разбор на два типа: разбор сверху вниз и разбор снизу вверх.
Разбор сверху вниз
Когда синтаксический анализатор начинает конструировать дерево анализа из начального символа, а затем пытается преобразовать начальный символ во входные данные, это называется синтаксическим анализом сверху вниз.
-
Разбор рекурсивного спуска : это распространенная форма синтаксического анализа сверху вниз. Он называется рекурсивным, поскольку он использует рекурсивные процедуры для обработки ввода. При рекурсивном разборе страдает откат назад.
-
Возврат . Это означает, что в случае сбоя одного производного процесса анализатор синтаксиса перезапускает процесс, используя разные правила одного и того же производства. Этот метод может обрабатывать входную строку более одного раза, чтобы определить правильную продукцию.
Разбор рекурсивного спуска : это распространенная форма синтаксического анализа сверху вниз. Он называется рекурсивным, поскольку он использует рекурсивные процедуры для обработки ввода. При рекурсивном разборе страдает откат назад.
Возврат . Это означает, что в случае сбоя одного производного процесса анализатор синтаксиса перезапускает процесс, используя разные правила одного и того же производства. Этот метод может обрабатывать входную строку более одного раза, чтобы определить правильную продукцию.
Анализ снизу вверх
Как следует из названия, анализ снизу вверх начинается с входных символов и пытается построить дерево разбора до начального символа.
Пример:
Входная строка: a + b * c
Правила производства:
S → E E → E + T E → E * T E → T T → id
Давайте начнем анализ снизу вверх
a + b * c
Прочитайте ввод и проверьте, совпадает ли какая-либо продукция с вводом: