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

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

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

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

Recursive descent parsing: Это распространенная форма анализа сверху вниз. Он называется рекурсивным, поскольку он использует рекурсивные процедуры для обработки ввода. Синтаксический анализ с рекурсивным спуском страдает от возврата.
Backtracking: Это означает, что в случае сбоя одной производной продукции синтаксический анализатор перезапускает процесс, используя другие правила той же продукции. Этот метод может обрабатывать входную строку более одного раза, чтобы определить правильную продукцию.

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

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

Example:

Строка ввода: 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