В.А. Серебряков, М.П. Галочкин - Основы конструирования компиляторов (1131395), страница 11
Текст из файла (страница 11)
В варианте 1.1 делается проверка, принадлежит ли следующий входной символ F OLLOW (A).Если нет – выдается ошибка. Во втором варианте этого не делается, такчто анализ ошибки откладывается на процедуру, вызвавшую A.void A(){ // A → u1 | u2 | ... | ukif (InSym ∈ F IRST (ui)) // только одному!if (parse(ui ))result("A → ui ");else error();else//Вариант 1:if (имеется правило A → ui такое, что ui ⇒∗ e)//Вариант 1.1if (InSym ∈ F OLLOW (A))result("A → ui ");else error();//Конец варианта 1.1//Вариант 1.2:result("A → ui ");//Конец варианта 1.2//Конец варианта 1//Вариант 2:if (нет правила A → ui такого, что u ⇒∗ e)error();//Конец варианта 2}boolean parse(u){ // из u не выводится e!v = u;while (v 6= e){ // v = Xzif (X - терминал a)if (InSym 6= a)return(false);else InSym = getInsym();4.4.
РАЗБОР СНИЗУ-ВВЕРХ ТИПА СДВИГ-СВЕРТКА67else // X - нетерминал BB;v = z;}return(true);}4.3.8Восстановление после синтаксических ошибокВ приведенных программах рекурсивного спуска использовалась процедура реакции на синтаксические ошибки error(). В простейшем случаеэта процедура выдает диагностику и завершает работу анализатора. Номожно попытаться некоторым разумным образом продолжить работу.Для разбора сверху вниз можно предложить следующий простой алгоритм.Если в момент обнаружения ошибки на верхушке магазина оказался нетерминальный символ A и для него нет правила, соответствующего входному символу, то сканируем вход до тех пор, пока не встретимсимвол либо из F IRST (A), либо из F OLLOW (A). В первом случае разворачиваем A по соответствующему правилу, во втором – удаляем A измагазина.Если на верхушке магазина терминальный символ, то можно удалить все терминальные символы с верхушки магазина вплоть до первого (сверху) нетерминального символа и продолжать так, как это былоописано выше.4.44.4.1Разбор снизу-вверх типа сдвиг-сверткаОсноваВ процессе разбора снизу-вверх типа сдвиг-свертка строится дерево разбора входной цепочки, начиная с листьев (снизу) к корню (вверх).
Этотпроцесс можно рассматривать как “свертку” цепочки w к начальномусимволу грамматики. На каждом шаге свертки подцепочка, которуюможно сопоставить правой части некоторого правила вывода, заменяется символом левой части этого правила вывода, и если на каждом шагевыбирается правильная подцепочка, то в обратном порядке прослеживается правосторонний вывод (рис. 4.7). Здесь ко входной цепочке, также как и при анализе LL(1)-грамматик, приписан концевой маркер $.Подцепочка сентенциальной формы, которая может быть сопоставлена правой части некоторого правила вывода, свертка по которому клевой части правила соответствует одному шагу в обращении правостороннего вывода, называется основой цепочки.
Самая левая подцепочка,которая сопоставляется правой части некоторого правила вывода A →ГЛАВА 4. СИНТАКСИЧЕСКИЙ АНАЛИЗ68666; ; D <<D =D E Рис. 4.7:γ, не обязательно является основой, поскольку свертка по правилу A →γ может дать цепочку, которая не может быть сведена к аксиоме.Формально, основа правой сентенциальной формы z – это правиловывода A → γ и позиция в z, в которой может быть найдена цепочкаγ такие, что в результате замены γ на A получается предыдущая сентенциальная форма в правостороннем выводе z.
Таким образом, еслиS ⇒∗r αAβ ⇒r αγβ, то A → γ в позиции, следующей за α, это основацепочки αγβ. Подцепочка β справа от основы содержит только терминальные символы.Вообще говоря, грамматика может быть неоднозначной, поэтому неединственным может быть правосторонний вывод αγβ и не единственной может быть основа. Если грамматика однозначна, то каждая правая сентенциальная форма грамматики имеет в точности одну основу.Замена основы в сентенциальной форме на нетерминал левой части называется отсечением основы. Обращение правостороннего вывода может быть получено с помощью повторного применения отсечения основы, начиная с исходной цепочки w.
Если w – слово в рассматриваемойграмматике, то w = αn , где αn – n-я правая сентенциальная форма ещенеизвестного правого вывода S = α0 ⇒r α1 ⇒r ... ⇒r αn−1 ⇒r αn = w.Чтобы восстановить этот вывод в обратном порядке, выделяем основу γn в αn и заменяем γn на левую часть некоторого правила выводаAn → γn , получая (n − 1)-ю правую сентенциальную форму αn−1 . Затемповторяем этот процесс, т.е.
выделяем основу γn−1 в αn−1 и сворачиваемэту основу, получая правую сентенциальную форму αn−2 . Если, повторяя этот процесс, мы получаем правую сентенциальную форму, состоящую только из начального символа S, то останавливаемся и сообщаемоб успешном завершении разбора. Обращение последовательности правил, использованных в свертках, есть правый вывод входной строки.4.4.
РАЗБОР СНИЗУ-ВВЕРХ ТИПА СДВИГ-СВЕРТКА69Таким образом, главная задача анализатора типа сдвиг-свертка – этовыделение и отсечение основы.4.4.2LR(1)-анализаторыВ названии LR(1) символ L указывает на то, что входная цепочка читается слева-направо, R – на то, что строится правый вывод, наконец, 1указывает на то, что анализатор видит один символ непрочитанной части входной цепочки.LR(1)-анализ привлекателен по нескольким причинам:– LR(1)-анализ – наиболее мощный метод анализа без возвратов типа сдвиг-свертка;– LR(1)-анализ может быть реализован довольно эффективно;– LR(1)-анализаторы могут быть построены для практически всех конструкций языков программирования;– класс грамматик, которые могут быть проанализированыLR(1)-методом, строго включает класс грамматик, которые могутбыть проанализированы предсказывающими анализаторами (сверхувниз типа LL(1)).Схематически структура LR(1)-анализатора изображена на рис.
4.8.Анализатор состоит из входной ленты, выходной ленты, магазина, управляющей программы и таблицы анализа (LR(1)-таблицы), которая имеет две части – функцию действий (Action) и функцию переходов (Goto).Управляющая программа одна и та же для всех LR(1)-анализаторов, разные анализаторы отличаются только таблицами анализа.Программа анализатора читает символы на входной ленте по одномуза шаг. В процессе анализа используется магазин, в котором хранятсястроки вида S0 X1 S1 X2 S2 ...
Xm Sm (Sm – верхушка магазина). КаждыйXi – символ грамматики (терминальный или нетерминальный), а Si –символ состояния.Заметим, что символы грамматики (либо символы состояний) не обязательно должны размещаться в магазине. Однако, их использованиеоблегчает понимание поведения LR-анализатора.Элемент функции действий Action[Sm , ai ] для символа состояния Smи входа ai ∈ T ∪ {$}, может иметь одно из четырех значений:1) shift S (сдвиг), где S – символ состояния,2) reduce A → γ (свертка по правилу грамматики A → γ),3) accept (допуск),4) error (ошибка).ГЛАВА 4. СИНТАКСИЧЕСКИЙ АНАЛИЗ70<oh^FZ]ZabgD DL DQ /5ZgZebaZlhj6P;P6P<uoh^;P$FWLRQ6*RWRРис.
4.8:Элемент функции переходов Goto[Sm , A] для символа состояния Sm ивхода A ∈ N , может иметь одно из двух значений:1) S, где S – символ состояния,2) error (ошибка).Конфигурацией LR(1)-анализатора называется пара, первая компонента которой – содержимое магазина, а вторая – непросмотренный вход:(S0 X1 S1 X2 S2 ...
Xm Sm , ai ai+1 ... an $)Эта конфигурация соответствует правой сентенциальной формеX1 X2 ... Xm ai ai+1 ... anПрефиксы правых сентенциальных форм, которые могут появитьсяв магазине анализатора, называются активными префиксами. Основасентенциальной формы всегда располагается на верхушке магазина. Таким образом, активный префикс – это такой префикс правой сентенциальной формы, который не переходит правую границу основы этой формы.В начале работы анализатора в магазине находится только символначального состояния S0 , на входной ленте – анализируемая цепочка смаркером конца.Очередной шаг анализатора определяется текущим входным символом ai и символом состояния на верхушке магазина Sm следующим образом.Пусть LR(1)-анализатор находится в конфигурации(S0 X1 S1 X2 S2 ...
Xm Sm , ai ai+1 ... an $)Анализатор может проделать один из следующих шагов:4.4. РАЗБОР СНИЗУ-ВВЕРХ ТИПА СДВИГ-СВЕРТКА711. Если Action[Sm , ai ] = shift S, то анализатор выполняет сдвиг, переходя в конфигурацию(S0 X1 S1 X2 S2 ... Xm Sm ai S, ai+1 ... an $)Таким образом, в магазин помещаются входной символ ai и символ состояния S, определяемый Action[Sm , ai ].
Текущим входнымсимволом становится ai+1 .2. Если Action[Sm , ai ] = reduce A → γ, то анализатор выполняет свертку, переходя в конфигурацию(S0 X1 S1 X2 S2 ... Xm−r Sm−r AS, ai ai+1 ... an $)где S = Goto[Sm−r , A] и r – длина γ, правой части правила вывода.Анализатор сначала удаляет из магазина 2r символов (r символовсостояния и r символов грамматики), так что на верхушке оказывается состояние Sm−r . Затем анализатор помещает в магазин A –левую часть правила вывода, и S – символ состояния, определяемый Goto[Sm−r , A]. На шаге свертки текущий входной символ неменяется. Для LR(1)-анализаторов Xm−r+1 ...
![](https://s.studizba.com/z.php?f=/templates/si/i/noavatar.png&w=100&h=100&t=1"){kind=avatar}
