Разработка компиляторов
Управляющая программа анализатора
Управляющая программа одинакова для всех LR-анализаторов, а таблица изменяется от одного анализатора к другому. Программа анализатора читает последовательно символы входной цепочки. Программа использует магазин для запоминания строки следующего вида s0X1s1X2…Xmsm, где s m - вершина магазина. Каждый Xi - символ грамматики, а si - символ, называемый состоянием. Каждое состояние суммирует информацию, cодержащуюся в стеке перед ним. Комбинация символа состояния на вершине магазина и текущего входного символа используется для индексирования управляющей таблицы и определения операции переноса-свертки. При реализации грамматические символы не обязательно располагаются в магазине; однако, мы будем использовать их при обсуждении для лучшего понимания поведения LR-анализатора.
Программа, управляющая LR-анализатором, ведет себя следующим образом. Рассматривается пара: s m - текущее состояние на вершине магазина, a i - текущий входной символ; после этого вычисляется action [s m, a i ]: , которое может иметь одно из четырех значений:
- shift s, где s - состояние,
- свертка по правилу A->? ,
- допуск (accept)
- ошибка.
Функция goto получает состояние и символ грамматики и выдает состояние. Функция goto , строящаяся по грамматике G , есть функция переходов детерминированного магазинного автомата, который распознает язык, порождаемый грамматикой G.
Управляющая программа выглядит следующим образом:
Установить ip на первый символ входной цепочки w$;
while (цепочка не закончилась) { Пусть s - состояние на вершине магазина, a - символ входной цепочки, на который указывает ip. if (action [s, a] == shift s') { push (a); push (s'); ip++; } else if (action [s, a] == reduce A->?) { for (i=1; i<=| ? |; i++) { pop (); pop (); } Пусть s' - состояние на вершине магазина; push (A); push (goto [s', A]); Вывод правила (A->?); } else if (action [s, a] == accept) { return success; } else { error (); } }
