В.А. Серебряков, М.П. Галочкин - Основы конструирования компиляторов (1134643), страница 12
Текст из файла (страница 12)
Тогда после анализа того, что выводимо из α, можно развернуть по A0 → β1 или по A0 → β2 . Левофакторизованные правила принимают видA → αA0A0 → β1 | β2Алгоритм 4.8. Левая факторизация грамматики.Вход. КС-грамматика G.Выход. Левофакторизованная КС-грамматика G0 , эквивалентная G.Метод. Для каждого нетерминала A ищем самый длинный префиксα, общий для двух или более его альтернатив.
Если α 6= e, т.е. существует нетривиальный общий префикс, заменяем все A-правилаA → αβ1 | αβ2 | ... | αβn | z,где z обозначает все альтернативы, не начинающиеся с α, наA → αA0 | zA0 → β1 | β2 | ... | βnгде A0 – новый нетерминал. Повторно применяем это преобразование,пока никакие две альтернативы не будут иметь общего префикса.Пример 4.7. Рассмотрим вновь грамматику условных операторов из примера 4.6:S → if E then S | if E then S else S | aE→bПосле левой факторизации грамматика принимает видS → if E then SS 0 | aS 0 → else S | eE→bК сожалению, грамматика остается неоднозначной, а значит, и не LL(1).ГЛАВА 4.
СИНТАКСИЧЕСКИЙ АНАЛИЗ664.3.7Рекурсивный спускВыше был рассмотрен таблично-управляемый вариант предсказывающего анализа, когда магазин явно использовался в процессе работы анализатора. Можно предложить другой вариант предсказывающего анализа, в котором каждому нетерминалу сопоставляется процедура (вообще говоря, рекурсивная), и магазин образуется неявно при вызовах таких процедур. Процедуры рекурсивного спуска могут быть записаны,как показано ниже.В процедуре A для случая, когда имеется правило A → ui , такое, чтоui ⇒∗ e (напомним, что не может быть больше одного правила, из которого выводится e), приведены два варианта 1.1 и 1.2. В варианте 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 .
![](https://s.studizba.com/z.php?f=/templates/si/i/noavatar.png&w=100&h=100&t=1"){kind=avatar}
