А.В. Ахо, М.С. Лам, Р. Сети, Дж. Д. Ульман - Компиляторы - принципы, технологии и инструментарий (1114947), страница 81
Текст из файла (страница 81)
Соответствующий пример приведен в разделе 5.4.3. 407 5.4. Синтаксически управляемые схемы трансляции Обычно СУТ реализуется в процессе синтаксического анализа, без построения дерева разбора. В данном разделе мы остановимся на использовании СУТ для реализации двух важных классов СУО. 1. Грамматика поддается ЬК-синтаксическому анализу, а СУΠ— Б-атрибутное. 2. Грамматика поддается ЕЕ-синтаксическому анализу, а СУΠ— Е-атрибутное. Мы увидим, каким образом в обоих случаях семантические правила СУО могут быть преобразованы в СУТ с действиями, выполняемыми в нужный момент. В процессе синтаксического анализа действие в теле продукции выполняется, как только все грамматические символы слева от него сопоставлены входной строке.
СУТ, которые могут быть реализованы в процессе синтаксического анализа, можно охарактеризовать путем вставки вместо действий отличающихся друг от друга нетерминапов-маркеров; каждый маркер М имеет единственную продукцию М вЂ” г. Если синтаксический анализ грамматики с такими нетерминаламимаркерами может быть выполнен некоторым методом, то СУТ может быть реализована в процессе данного синтаксического анализа. 5.4.1 Постфиксные схемы трансляции Простейшая реализация СУТ имеет место в случае восходящего синтаксического анализа и 8-атрибутного СУО. В этом случае можно построить СУТ, в которой каждое действие размещается в конце продукции и выполняется вместе со сверткой тела продукции в заголовок. СУТ со всеми действиями, расположенными на правом конце тел продукций, называются постфиксными СУТ.
Пример 5.14. Постфиксная СУТ на рис. 5.18 реализует СУО настольного калькулятора, представленного на рис. 5.1, с единственным изменением: действие первой продукции выводит вычисленное значение. Поскольку лежащая в основе СУТ грамматика является ЕК-грамматикой, а СУΠ— В-атрибутное, эти действия могут корректно выполняться синтаксическим анализатором при свертках. 5.4.2 Реализация постфиксной СУТ с использованием стека синтаксического анализатора Постфиксная СУТ может быть реализована в процессе ЕК-синтаксического анализа путем выполнения действий при свертках.
Атрибут (или атрибуты) каждого грамматического символа может помещаться в стек в том месте, где он может быть обнаружен в процессе свертки. Лучше всего разместить атрибуты вместе с грамматическими символами (или ЕК-состояниями, представляющими эти символы) в записях стека.
408 Глава 5. Синтаксически управляемая трансляция (рНпг (Ела!) 1) (Ела! = Етла1+ Тла1;) (Ела1 = Тла!;) (Тла! = Тт ла! х ела!;) (Тла! = Ела!;) (Ела! = Ела!;) (Ела! = т1181С1ехра11) Š— Ет + Т Е- Т Т вЂ” ТтеЕ Т вЂ” ~Е К- (Е) К - м181к Рис. 5.18. Постфиксная СУТ, реализующая настольный калькулятор На рис. 5.19 стек синтаксического анализатора содержит записи с полем для грамматических символов (или состояний синтаксического анализатора), а под ним — поле для атрибутов.
На вершине стека находятся три грамматических символа — Х У х; возможно, они будут свернуты в соответствии с продукцией наподобие А — Х У е,. На рисунке показан атрибут Х.х грамматического символа Х и т.д. В общем случае могут иметься несколько атрибутов; в этом случае следует либо увеличить размер записи в стеке так, чтобы она могла содержать все атрибуты, либо поместить в стек указатели на соответствующие записи. В случае атрибутов небольшого размера и в небольшом количестве может оказаться проще увеличить размер записи в стеке, даже если некоторые поля будут время от времени пустовать. Но если один или несколько атрибутов имеют неограниченный размер — например, представляют собой строки, — то лучше помещать в стек указатель на значение атрибута, который хранится в некотором другом месте памяти, не являющейся частью стека.
Ссстсяние/Грамматический символ Синтеаируемые атрибуты Вершина стека Рис. 5.19. Стек синтаксического анализатора с полем лля сии- тезируемых атрибутов Если все атрибуты синтезируемые, а действия располагаются в конце продукций, то можно вычислять атрибуты заголовков при выполнении свертки тела продукции к заголовку. Если выполняется свертка в соответствии с продукцией, такой как А — Х У х,, то все атрибуты Х, У и Я оказываются доступны и находятся в известных позициях в стеке, как показано на рис. 5.19. После выполнения действия А и его атрибуты находятся на вершине стека, в позиции, которую занимала запись для Х.
409 5.4. Синтаксически управляемые схемы трансляции Пример 5Л5. Перепишем действия из СУТ настольного калькулятора из примера 5.14 так, чтобы они явно работали со стеком. Такая работа со стеком обычно выполняется синтаксическим анализатором автоматически. Предположим, что стек поддерживается в виде массива записей с именем з(асА, с курсором (ор, указывающим на вершину стека. Таким образом, к(асА [(ор] представляет собой запись на вершине стека, з(асА[(ор — 1] — запись под ней и т.д. Предположим также, что каждая запись имеет поле с именем уа1, в котором хранится атрибут грамматического символа, представленного данной записью. Таким образом, обратиться к атрибуту Ела1, находящемуся в третьей позиции стека, можно как к пасА [(ор — 2] ла1. Полностью СУТ показана на рис.
5.20. ПРОДУКЦИЯ ДЕЙСТВИЯ [ рпт[з(асА [(ор — 1]ла1); (ор = (ор — 1; ) Ь- Еп ] з(асА [(ор — 2]ла1 = з(асА [(ор — 2] ла1 + я(асА [(ор]ла1; (ор = (ор — 2; ) Š— Е( + Т Е- Т т Т*к [ з(асА [(ор — 2] ла1 = з(асА [(ор — 2] ла( х з(асА [(ор] ла1; (ор = (ор — 2; ) Т вЂ” Е Е- [Е) [ з(асА[(ор — 2]ла! = я(асА [(ор — 1]ла!; (ор = (ор — 2; ) Рис. 5.20. Реализация настольного калькулятора в стеке восходящего синтакси- ческого анализа Например, во второй продукции, Š— Е(+Т, значение Е( расположено на две позиции ниже вершины стека, в то время как значение Т находится на вершине стека. Вычисленная сумма помещается в то место, в котором после свертки находится заголовок Е, т.е. двумя позициями ниже текущей вершины стека. Причина этого в том, что после свертки три грамматических символа на вершине стека будут заменены одним.
После вычисления Ела1 со стека снимаются два символа, так что запись, в которую было помещено значение Ела!, после этого окажется на вершине стека. В третьей продукции Š— Т действие не является необходимым, поскольку размер стека не изменяется и значение атрибута Тла! на вершине стека просто станет значением Ела1. Те же самые рассуждения применимы и к продукциям 410 Глава 5. Синтаксически управляемая трансляция Т вЂ” Г и г — д!й)П Продукция Р— (Е) несколько отличается тем, что, хотя значение атрибута и не изменяется, при свертке со стека снимаются два элемента, так что значение атрибута надо перенести в позицию, которая окажется на вершине стека после свертки.
Заметим, что здесь опущены шаги, управляющие первым полем записей в стеке — полем, которое содержит 1.К-состояние илн представляет грамматический символ. При выполнении 1.К-синтаксического анализа таблица анализа говорит нам о том, в какое новое состояние будет выполнена свертка (см. алгоритм 4.44). Таким образом, можно просто поместить состояние в запись на новой вершине стека.
П 5.4.3 СУТ с действиями внутри продукций Действия могут находиться в любой позиции в теле продукции. Действие выполняется сразу же после того, как обработаны все символы слева от него. Таким образом, если у нас есть продукция  — Х 1а) У, то действие а выполняется после того, как распознан Х (если Х вЂ” терминал) или все терминалы, порожденные из Х (если Х вЂ” нетерминал). Говоря более точно, ° при восходящем синтаксическом анализе действие а выполняется, как только данный грамматический символ Х оказывается на вершине стека; ° при нисходящем синтаксическом анализе действие и выполняется непосредственно перед тем, как выполняется раскрытие данного У (если У— нетерминал) или проверяется его наличие во входной строке (если У— терминал). СУТ, которые могут быть реализованы в процессе синтаксического анализа, включают постфиксные СУТ и класс СУТ, рассматриваемый в разделе 5.5, который реализует 1.-атрибутные определения.
![](https://s.studizba.com/z.php?f=/templates/si/i/noavatar.png&w=100&h=100&t=1"){kind=avatar}
