Полезное:
Как сделать разговор полезным и приятным
Как сделать объемную звезду своими руками
Как сделать то, что делать не хочется?
Как сделать погремушку
Как сделать так чтобы женщины сами знакомились с вами
Как сделать идею коммерческой
Как сделать хорошую растяжку ног?
Как сделать наш разум здоровым?
Как сделать, чтобы люди обманывали меньше
Вопрос 4. Как сделать так, чтобы вас уважали и ценили?
Как сделать лучше себе и другим людям
Как сделать свидание интересным?
Категории:
АрхитектураАстрономияБиологияГеографияГеологияИнформатикаИскусствоИсторияКулинарияКультураМаркетингМатематикаМедицинаМенеджментОхрана трудаПравоПроизводствоПсихологияРелигияСоциологияСпортТехникаФизикаФилософияХимияЭкологияЭкономикаЭлектроника
|
Управляющая программа анализатора
Управляющая программа одинакова для всех LR-анализаторов, а таблица изменяется от одного анализатора к другому. Программа анализатора читает последовательно символы входной цепочки. Программа использует магазин для запоминания строки следующего вида s0X1s1X2…Xmsm, где sm – вершина магазина. Каждый Xi – символ грамматики, а si – символ, называемый состоянием. Каждое состояние суммирует информацию, cодержащуюся в стеке перед ним. Комбинация символа состояния на вершине магазина и текущего входного символа используется для индексирования управляющей таблицы и определения операции переноса-свертки. При реализации грамматические символы не обязательно располагаются в магазине; однако, мы будем использовать их при обсуждении для лучшего понимания поведения LR-анализатора.
Программа, управляющая LR-анализатором, ведет себя следующим образом. Рассматривается пара: sm – текущее состояние на вершине магазина, ai – текущий входной символ; после этого вычисляется action [ sm, ai ], которое может иметь одно из четырех значений:
Функция 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 (); } }
Управляющая таблица LR(0)-анализатора
Обсудим подробно алгоритм построения управляющей таблицы на примере LR(0)-анализаторов.
Заметим, что LR(0)-анализатор принимает решение о своих действиях только на основании содержимого магазина, не учитывая символы входной цепочки. Для иллюстрации построения таблиц LR(0)-анализатора мы будем использовать грамматику G0:
Определение. Пусть G = (VT, VN, P, S) – КС-грамматика. Пополненной грамматикой (augmented grammar) будем называть грамматику G' = (VT, VN+{S'}, P+{ S'→S }, S'), где Определение. Пусть G = (VT, VN, P, S) – КС-грамматика. Будем называть [A→w1.w2,, u] LR(k)-ситуацией (LR(k)-item), если A→w1w2 является правилом из P и u – цепочка терминалов, длина которой не превосходит k.
Понятно, что LR(0)-ситуации не должны содержать терминальной цепочки, то есть мы можем записывать их следующим образом: [A→w1.w2].
|