А.В. Ахо, М.С. Лам, Р. Сети, Дж. Д. Ульман - Компиляторы - принципы, технологии и инструментарий (1114947), страница 86
Текст из файла (страница 86)
о Пример 5.24. Рассмотрим ту же конструкцию веЫ!е, но теперь трансляция генерирует код не "на лету", а как синтезируемый атрибут 5.соде. Чтобы лучше понять пояснения, приводимые в данном примере, желательно все время помнить следующий инвариант, который, как мы полагаем, выполняется для каждого нетерминала. ° Каждый нетерминал, который имеет связанный с ним код, оставляет его в виде строки в записи синтеза, находящейся в стеке непосредственно под ним. Полагая данное утверждение истинным, мы будем работать с трЫ1е-продукцией так, чтобы поддерживать это утверждение как инвариант. На рис.
5.35, а показана ситуация непосредственно перед развертыванием 5 с использованием продукции для конструкции юЫ!е. На вершине стека находится запись для Я; она содержит поле для своего наследуемого атрибута клех~, как в примере 5.23. Непосредственно под этой записью располагается запись синтеза для данного экземпляра Я. В ней имеется поле для Я.соде, как и у всех записей синтеза для Я. Показаны также некоторые другие поля для локальных данных и действий, поскольку СУТ для продукции иЫ1е на рис. 5.28, конечно же, является частью большей СУТ. Наше раскрытие 5 основано на СУТ, представленной на рис. 5.28, и показано на рис.
5.35, б. Для ускорения в процессе раскрытия мы полагаем, что наследуемый атрибут Я.пех~ присваивается непосредственно С~аЬе, а не размещается в первом действии и затем копируется в запись для С. Рассмотрим, что делает каждая запись, оказавшись на вершине стека.
Сначала запись для и Ьйе заставляет выполнить проверку соответствия токена и'й1!е входному символу (соответствие должно выполняться, иначе для раскрытия 5 будет использоваться другая продукция). После того как со стека будут сняты звЫ1е и (, 5.5. Реализация Ь-атрибутных СУО 433 Вершина стека Данные а1 оехт =х сове =? Действия Вершина стека Синтез Х сове соде =? Данные С уойе =? тсие =? иййе Д( действие 12 =? А! =? Действия Гс(аск1тоо — 11.соне = "1аЬе1" ~1 Л 1Ссоое 1~ "1аЬе1" Щ~соНе~ 61 Рис. 5.35.
Раскрытие Я с сиитезируемым атрибутом, конструируемым в стеке будет выполнен код записи действий. Он генерирует значения И и А2, и мы можем сократить вычисления, копируя их непосредственно в наследуемые атрибуты 51 щехг С.ггие. Два последних шага действия копируют значения Т,1 и Е2 в запись "Синтез Ят.сне".
Запись синтеза для 51 выполняет двойную функцию: она не только хранит синтезируемый атрибут Ят.сне, но и служит в качестве записи действий для завершения вычислений атрибутов всей продукции Я вЂ” иЫ!е (С) 51. В частности, когда эта запись оказывается на вершине стека, она вычисляет синтезируемый атрибут Я.соЫе и помещает его значение в запись синтеза для заголовка о. Когда С находится на вершине стека, оба его наследуемых атрибута оказываются вычисленными. В соответствии со сформулированным ранее инвариантом мы предполагаем, что при этом корректно сгеперирован код для вычисления условия с переходом к соответствующей метке. Мы также считаем, что действие, выполняемое при раскрытии С, корректно размещает этот код в записи ниже в стеке в качестве значения синтезируемого атрибута С.сне.
После снятия С со стека на его вершине оказывается запись синтеза для С.соде. Этот код необходим в записи синтеза для Ят.соде, поскольку именно в ней выполняется конкатенация всех элементов кода, образукицих Я.соде. Таким образом, запись синтеза для С.сне содержит действие, состоящее в копировании С.сне в запись синтеза для Ят.сне. После этого вершины стека достигает запись для токена ), что приводит к выполнению проверки наличия ) во входном потоке.
434 Глава 5. Синтаксически управляемая трансляция В предположении, что проверка выполнена успешно, на вершину стека поднимается запись для Яь Согласно инварианту этот нетерминал раскрыт, и в результате соответствующий код корректно генерируется и размещается в поле со Хе в записи синтеза для Яи Теперь все поля данных записи синтеза для 51 заполнены, так что, когда оно оказывается на вершине стека, выполнению его действий ничто не препятствует. Действие состоит в конкатенации меток и кода из С.сне и Бисовое в правильном порядке.
Получающаяся в результате строка размещается ниже, т.е. в записи синтеза для Я. Теперь у нас есть корректно вычисленный атрибут Я.сне, и, когда запись синтеза для 5 окажется на вершине стека, этот код будет доступен для размещения в другой записи ниже в стеке, где в конечном счете он будет собран в большей строке кода, реализующей элемент программы, частью которого является Я. а 5.5.4 Восходящий синтаксический анализ Ь-атрибутных СУО Любая трансляция, которая может быть выполнена в нисходящем направлении, может быть выполнена и при восходящем синтаксическом анализе. Точнее, для данных ).-атрибутного СУО и 1.1.-грамматики можно адаптировать грамматику для вычисления того же самого СУО над новой грамматикой в процессе 1,К- синтаксического анализа.
Этот "трюк" состоит из трех частей. 1. Начнем с СУТ, построенной, как в разделе 5.4.5, которая размещает перед каждым нетерминалом действия по вычислению его наследуемых атрибутов, а в конце продукции — действия по вычислению синтезируемых атрибутов. 2. Введем в грамматику нетерминалы-маркеры на месте каждого вставленного действия. В каждое такое место вставляется свой маркер; для каждого маркера М существует только одна продукция, а именно — ЛХ 3. Модифицируем действие а, заменяемое маркером М в некоторой продукции А — а 1а) )3, и связываем с продукцией ЛХ вЂ” г действие а', которое а) копирует в качестве наследуемых атрибутов М любые атрибуты А или символов из о, которые требуются действию а; б) вычисляет атрибуты таким же способом, что и а, но делает эти атрибуты синтезируемыми атрибутами М. Это изменение выглядит некорректным, поскольку получается, что действие, связанное с продукцией М вЂ” г, должно иметь доступ к атрибутам, 435 5.5.
Реализация !.-атрнбутных СУЮ Возможна ли обработка Ь-атрибутного СУО на основе ЬК-грамматики В разделе 5.4А мы видели, что каждое Б-атрибутное СУО на основе !.К- грамматики может быть реализовано в процессе восходящего синтаксического анализа. Из раздела 5.5.3 известно, что каждое Ь-атрибутное СУО на основе Ь -грамматики может быть проанализировано при помощи нисходящего синтаксического анализа.
Поскольку ЬЬ-грамматики являются истинным подмножеством ЬК-грамматик, а Я-атрибутные СУΠ— истинным подмножеством !.-атрибутных СУО, можно ли работать с любой ЬК-грамматикой и !.-атрибутным СУО в восходящем направлении? Нет, как показывают следующие интуитивно понятные доводы. Предположим, имеются продукция А — В С из !.К-грамматики и наследуемый атрибут В.г, который зависит от наследуемых атрибутов А. При выполнении свертки к В мы все еще не видели входного потока, генерируемого С, так что мы не можем быть уверены в том, что имеем дело с телом продукции А — В С.
Таким образом, мы все еще не можем вычислить значение В.г', поскольку нет гарантии, что следует использовать правило, связанное именно с данной продукцией. Возможно, решение состоит в том, чтобы подождать свертки к С и убедиться в том, что мы должны свернуть В С к А. Однако даже тогда мы не знаем наследуемых атрибутов А, поскольку даже после свертки может быть неизвестно, какое именно тело продукции содержит это А. Если опять воспользоваться откладыванием вычисления В.г', то в конечном итоге мы придем к тому, что мы не можем принять ни одного решения, пока не будет проанализирована вся входная строка. По сути, это означает применение стратегии "сначала построить дерево разбора, а затем выполнить трансляцию".
связанным с грамматическими символами, которые отсутствуют в данной продукции. Однако, так как мы реализуем действия с использованием стека ЬК-синтаксического анализа, необходимые атрибуты всегда будут доступны посредством известных позиций записей ниже в стеке. Пример 5.25. Предположим, имеется ЬЬ-грамматика с продукцией А — В С и наследуемый атрибут В.г' вычисляется с использованием наследуемого атрибуга Ад по формуле В.г' = !'(А.г).
Значит, интересующий нас фрагмент СУТ имеет вид А — (В.г' = ~ (А.г);) В С 436 Глава 5. Синтаксически управляемая трансляция Почему работают маркеры Маркеры — это нетерминалы, порождающие только г и встречающиеся толью один раз в телах всех продукций.
Мы не приводим здесь формального доказательства того, что нетерминалы-маркеры могут быть добавлены в любые позиции в телах продукций ЕЕ-грамматики и получившаяся в результате грамматика останется ЕК-грамматикой. Интуитивно это поясняется следующим образом. Если грамматика принадлежит классу Ы., то можно определить, что строка ш во входном потоке порождается нетерминалом А, в порождении, начинающемся с продукции А — о, просматривая только один первый символ щ (или следующий символ, если гц = г). Таким образом, при восходящем синтаксическом анализе в тот факт, что префикс ш должен быть свернут в о, а затем в В, становится известен, как только во входном потоке появляется начало строки и.
В частности„если мы вставим маркер где угодно в а, то ЕК- состояния включат тот факт, что в некотором месте должен иметься данный маркер, и выполнят свертку е в маркер в соответствующей точке входного потока. Введем маркер М с наследуемым атрибутом ЛХл' н синтезнруемым атрибутом М.а. Первый является копией А.г, а последний — В.г'. СУТ записывается как А- МВС М вЂ” + ~М.г = А.г; ЛХ.а = Х (ЛХ.г);) Заметим, что атрибут Ал не доступен правилу для ЛХ, но в действительности можно так расположить наследуемые атрибуты нетерминалов, таких как А, чтобы они находились в стеке непосредственно под тем местом, где позже будет выполнена свертка в А.
![](https://s.studizba.com/z.php?f=/templates/si/i/noavatar.png&w=100&h=100&t=1"){kind=avatar}
