Все статьи / Восходящий разбор по принципу сдвига и свёртки (shift-reduce)

При восходящем анализе по алгоритмам LL(k), LR(k), SLR(k), LALR разбор выполняется по единому принципу переноса-свёртки (shift-reduce). Конечный автомат в процессе движения по строке с помощью внутренней таблицы переходов выполняет всего два действия:

  • перенос — перенос терминального символа из входной строки или из входного списка токенов в стек, используемый объектом автомата как дополнительная память
  • свёртка — замещение цепочки терминальных или нетерминальных символов одним нетерминалом согласно какому-либо правилу

Общий цикл работы автомата выглядит следующим образом:

  • в цикле получаем терминальные символы из входного потока текста или из лексера
    • (shift) добавляем терминальные символ в стек автомата
    • (reduce) в цикле проверяем возможность однозначно согласно грамматике заменить некоторую цепочку символов с вершины стека в один нетерминальный символ, сворачиваем если возможность есть
  • в конце разбора проверяем, какой символ остался на стеке — должен был остаться символ верхнего уровня “единица трансляции”, эквивалентный одному файлу или модулю

Заметьте, что шаги reduce должны выполняться после каждого шага shift, до тех пор пока остаётся возможность однозначной свёртки. Но не всегда свёртка однозначна: например, в языке C есть как объявления переменных, так и объявления функции, и выбрать правильный вариант можно только после точки с запятой или открывающей сборки, которые вносят однозначность в выбор парсера:

// Если на стеке ["int" <identifier>], мы не можем однозначно выбрать правило для свёртки
// Если на стеке ["int" <identifier> "("], то можем
// Если на стеке ["int" <identifier> ";"], то также можем
int x;
int y(int a);

Трассировка восходящего разбора

Допустим, у нас есть текст “print 10 * 10 / 5.5” и набор правил для арифметических выражений, а также правило для инструкции print:

<statement> ::= <print_statement> | <variable_assignment>
<statement_list> ::= <statement> "\n" | <statement_list> <statement> "\n"
<print_statement> ::= "print" <expression>

Взгляните на трассировку работы автомата, разбирающего текст “print 10 * 10 / 5.5”:

Входной символ PRINT
Сдвиг, состояние 2
На стеке: [PRINT]
Входной символ NUMBER
Сдвиг, состояние 23
На стеке: [PRINT NUMBER]
Входной символ STAR
Свёртка по правилу [expression ::= NUMBER].
Сдвиг, состояние 13
На стеке: [PRINT expression]
Сдвиг, состояние 7
На стеке: [PRINT expression STAR]
Входной символ NUMBER
Сдвиг, состояние 23
На стеке: [PRINT expression STAR NUMBER]
Входной символ SLASH
Свёртка по правилу [expression ::= NUMBER].
Сдвиг, состояние 26
На стеке: [PRINT expression STAR expression]
Свёртка по правилу [expression ::= expression STAR expression].
Сдвиг, состояние 13
На стеке: [PRINT expression]
Сдвиг, состояние 6
На стеке: [PRINT expression SLASH]
Входной символ NUMBER
Сдвиг, состояние 23
На стеке: [PRINT expression SLASH NUMBER]
Входной символ NEWLINE
Свёртка по правилу [expression ::= NUMBER].
Сдвиг, состояние 25
На стеке: [PRINT expression SLASH expression]
Свёртка по правилу [expression ::= expression SLASH expression].
Сдвиг, состояние 13
На стеке: [PRINT expression]
Свёртка по правилу [statement ::= PRINT expression].
Сдвиг, состояние 20
На стеке: [statement]
Сдвиг, состояние 28
На стеке: [statement NEWLINE]

Ссылки