Дизайн компилятора - типы парсинга

Синтаксические анализаторы следуют производственным правилам, определенным посредством контекстно-свободной грамматики. Способ реализации правил производства (деривация) разделяет разбор на два типа: разбор сверху вниз и разбор снизу вверх.

Типы парсера

Разбор сверху вниз

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

  • Разбор рекурсивного спуска : это распространенная форма синтаксического анализа сверху вниз. Он называется рекурсивным, поскольку он использует рекурсивные процедуры для обработки ввода. При рекурсивном разборе страдает откат назад.

  • Возврат : Это означает, что в случае сбоя одного производного процесса анализатор синтаксиса перезапускает процесс, используя разные правила одного и того же производства. Этот метод может обрабатывать входную строку более одного раза, чтобы определить правильную продукцию.

Анализ снизу вверх

Как следует из названия, анализ снизу вверх начинается с входных символов и пытается построить дерево разбора до начального символа.

Пример:

Входная строка: a + b * c

Правила производства:

S → E
E → E + T
E → E * T
E → T
T → id

Давайте начнем анализ снизу вверх

a + b * c

Прочитайте ввод и проверьте, совпадает ли какая-либо продукция с вводом:

a + b * c
T + b * c
E + b * c
E + T * c
E * c
E * T
E
S