Лекции по конструированию компиляторов. В.А. Серебряков (1134688), страница 8
Текст из файла (страница 8)
Тогда для каждого нетерминалапостроение диаграммы включает следующие шаги.Шаг 1. Вводим начальное и заключительное состояния.Шаг 2. Для каждого правила вывода A->X1X2...Xn строим путь изначального в конечное состояние с дугами, помеченными X1,...,Xn. Еслианализатор, построенный по диаграмме переходов, оказывается в46состоянии s и дуга, помеченная терминалом a, ведет в состояние t, то еслиочередной входной символ равен a, анализатор продвигает вход на однупозицию вправо и переходит в состояние t. Если же дуга помеченанетерминалом A, анализатор входит в начальное состояние для A безпродвижения входа. После того как он достигает заключительногосостояния для A, он переходит в состояние t, что означает "чтение" A извхода при переходе из состояния s в состояние t.
Наконец, если есть дугаиз s в t, помеченная e, то анализатор переходит из s в t, не читая входа.Если следовать программе рекурсивного спуска, то переход по eдолжен всегда выбираться в качестве последней альтернативы.Диаграммы переходов могут быть упрощены подстановкой одной вдругую. Рассмотрим, например, диаграммы для арифметическихвыражений на рис.
3.10.TE`+TE`E: 012E`: 3456eFT`89*F1112T`T:7T`:1013e(F:14E15)1617idРис. 3.10e+E`3TT4+5E`e34e6647e+E:0+T3T4E:3e46e66Рис. 3.11+*TE:0F:14eF36T:(E)15167e81317idРис. 3.12На рис 3.11 приведена эквивалентная диаграмма переходов для E'. Можноподставить диаграмму для E' рис.3.11 в диаграмму для E рис. 3.10.Получится диаграмма рис. 3.11 для E. Наконец, видно, что в этойдиаграмме нулевая и четвертая вершины эквивалентны и их можно слить.Так же можно поступить с диаграммами для T и T'. В результате получитсянабор диаграмм рис.
3.12.Такое преобразование эквивалентно описанию грамматикирасширенными формулами Бэкуса-Наура, в которых помимо собственнорекурсивных определений допускаются описания повторений. Припрограммировании рекурсивного спуска такая диаграмма для Eзаписывается очевидным образом:procedure E; repeat T; until InSym<>PLUS;483.2.9. Восстановление после синтаксических ошибокВ приведенных программах рекурсивного спуска использоваласьпроцедура реакции на синтаксические ошибки error(). В простейшемслучае эта процедура выдает диагностику и завершает работу анализатора.Но можно попытаться некоторым разумным образом продолжить работу.Для разбора сверху вниз можно предложить следующий простойалгоритм.Если в момент обнаружения ошибки на верхушке магазина оказалсянетерминальный символ N и для него нет правила, соответствующеговходному символу, то сканируем вход до тех пор, пока не встретим символлибо из FIRST(N), либо из FOLLOW(N).
В первом случае разворачиваем Nпо соответствующему правилу, во втором - удаляем N из магазина.Если на верхушке магазина терминальный символ, то можновыкинуть все терминальные символы с верхушки магазина вплоть допервого (сверху) нетерминального символа и продолжать так, как это былоописано выше.493.3. Разбор снизу-вверх типа сдвиг-свертка3.3.1. ОсноваВ процессе разбора снизу-вверх типа сдвиг-свертка строится дереворазбора входной строки, начиная с листьев (снизу) к корню (вверх). Этотпроцесс можно рассматривать как "свертку" строки w к начальномусимволу грамматики. На каждом шаге свертки подстрока, которую можносопоставить правой части некоторого правила вывода, заменяетсясимволом левой части этого правила вывода, и если на каждом шагевыбирается правильная подстрока, то в обратном порядке прослеживаетсяправосторонний вывод (рис.
3.13).SS/ | \X1 X2.../|............/|YY|/|\/|\Z/ .../ ... /|\a.........$ a...........$a.......b.......$а)Sб)в)Рис. 3.13Пример 3.5. Рассмотрим грамматику арифметических выражений,приведенную на рис. 3.14 а). Строка а+b*c может быть сведена к S, какпоказано на рис. 3.14.б). Дерево этой строки приведено на рис. 3.14 в).В строке a+b*c ищется подстрока, которую можно сопоставить справой частью некоторого правила вывода.
Этому удовлетворяютподстроки a, b и c. Если выбрать самое левое a и заменить его на F - левуючасть правила F->id, то получим строку F+b*c. Теперь правой части тогоже правила можно сопоставить подстроки b и c. Эти свертки представляютсобой в обратном порядке правосторонний вывод:E->E+T->E+T*F->E+T*c->E+F*c->E+b*c->T+b*c->F+b*c>a+b*c50EETTF->->->->->E + TTT*FFidа)а+b*cF+b*cT+b*cE+b*cE+F*cE+T*cE+T*FE+TEE/+\ET||\TT *|| \FFF||\id idid|||abcб)Рис. 3.14в)Подстрока сентенциальной формы, которая может быть сопоставленаправой части некоторого правила вывода, свертка по которому к левойчасти правила соответствует одному шагу в обращении правостороннеговывода, называется основой строки.
В приведенном выше выводе основывыделены. Самая левая подстрока, которая сопоставляется правой частинекоторого правила вывода A->v, не обязательно является основой,поскольку свертка по правилу A->v может дать строку, которая не можетбыть сведена к аксиоме. Если, скажем, в примере 3.5 заменить a на F и b наF, то получим строку F+F*c, которая не может быть сведена к S.Формально, основа правой сентенциальной формы z - это правиловывода A->v и позиция в z, в которой может быть найдена строка v такие,что в результате замены v на A получается предыдущая сентенциальнаяформа в правостороннем выводе z.
Таким образом, если S=>*uAw=>uvw,то A->v в позиции, следующей за u, это основа строки uvw. Строка wсправа от основы содержит только терминальные символы. Вообщеговоря, грамматика может быть неоднозначной, поэтому не единственнымможет быть правосторонний вывод uvw и не единственной может бытьоснова. Если грамматика однозначна, то каждая правая сентенциальнаяформа грамматики имеет в точности одну основу. Замена основы всентенциальной форме на нетерминал левой части называется отсечениемосновы.
Обращение правостороннего вывода может быть получено спомощью повторного применения отсечения основы, начиная сразбираемой строки w. Если w - слово в рассматриваемой грамматике, тоw=Zn, n-я правая сентенциальная форма еще неизвестного правого выводаS = Z0 => Z1 => Z2 => ... => Zn-1 => Zn =w.Чтобы восстановить этот вывод в обратном порядке, выделяем основу Vn вZn и заменяем Vn на левую часть некоторого правила вывода An -> Vn,получая (n-1)-ю правую сентенциальную форму Zn-1. Затем повторяем этот51процесс, т.е. выделяем основу Vn-1 в Zn-1 и сворачиваем эту основу,получая правую сентенциальную форму Zn-2. Если, повторяя этот процесс,мы получаем правую сентенциальную форму, состоящую только изначального символа S, то останавливаемся и сообщаем об успешномзавершенииразбора.Обращениепоследовательностиправил,использованных в свертках, есть правый вывод входной строки.Таким образом, главная задача анализатора типа сдвиг-свертка - этовыделение и отсечение основы.3.3.2.
LR(k)-анализаторыВ названии LR(k) символ L означает, что разбор осуществляется слеванаправо, R - что строится правый вывод в обратном порядке, k - числовходных символов, на которые заглядывает вперед анализатор приразборе. Когда k опущено, имеют в виду 1.LR-анализ привлекателен по нескольким причинам:- LR-анализ - наиболее мощный метод анализа без возвратов типа сдвигсвертка;- LR-анализ может быть реализован довольно эффективно;- практически LR-анализаторы могут быть построены для всехконструкций языков программирования;- класс грамматик, которые могут быть проанализированы LRметодом, строго включает класс грамматик, которые могут бытьанализированы предсказывающими анализаторами (сверху вниз типаLL).Схематически структура LR-анализатора изображена на рис.
3.15. Онсостоит из входа, выхода, магазина, управляющей программы и таблицыанализа, которая имеет две части - действий и переходов. Управляющаяпрограмма одна и та же для всех анализаторов, разные анализаторыразличаются таблицами анализа. Программа анализатора читает символыиз входного буфера по одному за шаг. В процессе анализа используетсямагазин, в котором хранятся строки вида S0X1S1X2S2...XmSm (Sm верхушка магазина).
Каждый Xi - символ грамматики (терминальный илинетерминальный), а Si - символ, называемый состоянием. Каждый символсостояния выражает информацию, содержащуюся в магазине ниже него, акомбинация символа состояния на верхушке магазина и текущеговходного символа используется для индексации таблицы анализа иопределяет решение о сдвиге или свертке. В реализации символы52состояния не обязательно должны размещаться в магазине. Однако ихиспользование удобно для упрощения понимания поведения LRанализатора.Входa1 .
. . ai . . . anМагазин SmXm$LRанализаторВыходSm-1Xm-1....S0actiongotoРис. 3.15Таблица анализа состоит из двух частей: действия (action) ипереходов (goto). Начальное состояние этого ДКА - это состояние,помещенное на верхушку магазина LR-анализатора в начале работы.Конфигурация-LR анализатора - это пара, первая компонентакоторой - содержимое магазина, а вторая - непросмотренный вход:(S0 X1 S1 X2 S2 ... Xm Sm, ai ai+1 ... an $)Эта конфигурация соответствует правой сентенциальной формеX1 X2 ...
Xm ai ai+1 ... anПрефиксы правых сентенциальных форм, которые могут появиться вмагазине анализатора, называются активными префиксами. Основасентенциальной формы всегда располагается на верхушке магазина. Такимобразом, активный префикс - это такой префикс правой сентенциальнойформы, который не переходит правую границу основы этой формы.Очередной шаг анализатора определяется текущим входнымсимволом ai и символом состояния на верхушке магазина Sm.
Элементтаблицы действий action[Sm,ai] для состояния Sm и входа ai, может иметьодно их четырех значений:1) shift S, сдвиг, где S - состояние,532) reduce A->w, свертка по правилу грамматики A -> w,3) accept, допуск,4) error, ошибка.Конфигурации, получающиеся после каждого из четырех типов шагов,следующие1. Если 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->w, то анализатор выполняет свертку,переходя в конфигурацию(S0 X1 S1 X2 S2 ... Xm-r Sm-r A S, ai ai+1 ... an $)где S=goto[Sm-r,A] и r - длина w, правой части правила вывода. Функцияgoto таблицы анализа, построенная по грамматике G, - это функцияпереходов детерминированного конечного автомата, распознающегоактивные префиксы G. Анализатор сначала удаляет из магазина 2rсимволов (r символов состояния и r символов грамматики), так что наверхушке оказывается состояние Sm-r. Затем анализатор помещает вмагазин как A - левую часть правила вывода, так и S - содержимоетаблицы goto[Sm-r,A].
![](https://s.studizba.com/z.php?f=/templates/si/i/noavatar.png&w=100&h=100&t=1"){kind=avatar}
