А.В. Ахо, М.С. Лам, Р. Сети, Дж. Д. Ульман - Компиляторы - принципы, технологии и инструментарий (1114947), страница 79
Текст из файла (страница 79)
В случае СУО нас интересует баланс между атрибутными грамматиками и схемами трансляции. Атрибутные грамматики не имеют побочных действий и допускают любой порядок вычислений, согласующийся с графом зависимостей. Схемы трансляции требуют вычислений слева направо и допускают семантические действия, содержащие произвольные программные фрагменты; схемы трансляции рассматриваются в разделе 5.4.
Мы будем контролировать побочные действия в СУО одним из следующих способов. ° Позволяя второстепенные побочные действия, не препятствующие вычислению атрибутов. Другими словами, побочные действия разрешаются, если вычисление атрибутов на основе любой топологической сортировки графа зависимостей дает "корректную" трансляцию, где "корректность" зависит от конкретного приложения. ° Ограничивая допустимые порядки вычисления так, что прн любом из разрешенных порядков вычисления получается одна и та же трансляция.
Ограничения могут рассматриваться как неявные ребра, добавленные к графу зависимостей. В качестве примера второстепенного побочного действия изменим калькулятор из примера 5. ! так, чтобы он выводил полученный результат. Вместо правила г,л а1 = Ел и1, которое сохраняет результат вычислений в синтезируемом атрибуте т,.га1, рассмотрим следующее правило: ПРОДУкЦиЯ СемАнтическОе ИРАВилО !) т' — Е н рпп! 1Е.га1) Семантические правила, выполнение которых сводится только к побочным действиям, будут рассматриваться как определения фиктивных синтезируемых атрибутов, связанных с заголовком продукции.
Данное модифицированное СУО дает ту же трансляцию при любой топологической сортировке, поскольку инструкция вывода выполняется в самом конце, после того как результат вычислений сохранен в Ела1. 397 5.2. Порядок вычисления в СУО Пример 5.10. СУО на рис.
5.8 получает простое объявление Р, состоящее из базового типа Т, за которым следует список идентификаторов Ь. Т может быть 1пт или йоак Для каждого идентификатора в списке тип вносится в запись таблицы символов для данного идентификатора. Мы считаем, что внесение типа в запись таблицы символов для данного идентификатора не влияет на записи таблицы символов для прочих идентификаторов. Таким образом, записи могут обновляться в произвольном порядке.
Это СУО не проверяет, не объявлен ли идентификатор более одного раза; для этого в СУО можно внести необходимые изменения. Рис. 5,8. Синтаксически управляемое определение лля простых обьявлеиий типов Нетерминал Р представляет объявление, которое в соответствии с продукцией 1 состоит из типа Т, за которым следует список идентификаторов Ь.
Т имеет один атрибут, Т.цре, который является типом объявления Р. Нетерминал Е также имеет один атрибут, который назван тЬ для того, чтобы подчеркнуть, что этот атрибут — наследуемый. Назначение Алла — передача объявленного типа вниз по списку идентификаторов, чтобы он мог быть добавлен в соответствующие записи таблицы символов. Каждая из продукций 2 и 3 вычисляет синтезируемый атрибут Тлуре, присваивая ему корректное значение — 1п1еяег или Йоак Этот тип передается атрибуту Алла в правиле для продукции 1. Продукция 4 передает Л.1лЬ вниз по дереву разбора, т.е.
значение Ь~.ий вычисляется в узле дерева разбора путем копирования значения ЬдлЬ из родительского по отношению к данному узлу; родительский узел соответствует заголовку продукции. Продукции 4 и 5 имеют также правило, в соответствии с которым вызывается функция а ЫТуре с двумя аргументами: 1. и$.епггу, лексическим значением, которое указывает на объект таблицы сим- волов; 2.
Ьлпл, типом, назначенным каждому идентификатору из списка. 398 Глава 5. Синтаксически управляемая трансляция Мы предполагаем, что функция агЫТуре корректно устанавливает тип з,.иЬ в качестве типа представленного идентификатора. Граф зависимостей для входной строки йоа! Ыы Ыз, Ыз показан на рис. 5.9. Числа от 1 до 10 представляют узлы графа зависимостей.
Узлы 1, 2 и 3 представляют атрибут елггу, связанный с каждым из листьев с метками!о, Узлы б, 8 и 10 являются фиктивными атрибутами, представляющими применение функции а~ЫТуре к типу и одному из упомянутых значений еппу. / тя 9 я 1О глот м~ ! елоу Рис. 5.9. Граф зависимостей для объявления йоа! Ип Из, Из Узел 4 представляет атрибут Т.гуре, и здесь действительно начинается вычисление атрибута. Этот тип затем передается узлам 5, 7 и 9, представляющим атрибут Т Злй, связанный с каждым появлением нетерминала Т,. о 5.2.6 Упражнения к разделу 5.2 Упражнение 5.2.1.
Приведите все возможные топологические сортировки для графа зависимостей на рис. 5.7. Упражнение 5.2.2. Изобразите аннотированные деревья разбора для СУО на рис. 5.8 для следующих выражений: а)зпба, Ь, с; б) й1оат. и, х, у, я. Упражнение 5.2.3. Предположим, что у нас есть продукция А — В С Р, Каждый из нетерминалов А, В, С и Р имеет два атрибута: синтезируемый атрибут в и наследуемый атрибут г. Для каждого из перечисленных ниже наборов правил 399 5.3. Применения синтаксически управляемой трансляции укажите, согласуются ли эти правила с 5- и 1,-атрибутным определениями и существует ли вообще какой-либо порядок вычисления атрибутов в соответствии с указанными правилами. а) А.в = В.и+ С.в б) А.в = В.г + С.в и 23л' = Ал + В.в в) А.в = В.в+ 13.в ! г) А.в = 23л', Вл = А.в + С.в, Сл = В.в и Рл' = Вл' + Сл ! Упражнение 5.2.4.
Приведенная грамматика генерирует бинарные числа с "десятичной" точкой: Я вЂ” Ь.Ь(Ь Ь вЂ” ЬВ(  — 0)1 Разработайте 1.-атрибутное СУО для вычисления Я.иа1, десятичного значения входной строки. Например, трансляция строки 101. 101 должна давать десятичное число 5.625. Указание: воспользуйтесь наследуемым атрибутом Ьллл, который говорит, с какой стороны от десятичной точки располагается бит. !! Упражнение 5.2.5. Разработайте Я-атрибутное СУО для грамматики и трансляции, описанных в упражнении 5.2.4. !! Упражнение 5.2.6. Реализуйте алгоритм 3.23, который преобразует регулярные выражения в недетерминированные конечные автоматы, как 1.-атрибутное СУО для грамматики, к которой применим нисходящий синтаксический анализ.
Считаем, что токен сваг представляет произвольный символ, а снагуел а! — символ, который он представляет. Вы можете также считать, что существует функция леи (), которая возвращает новое состояние, т.е. состояние, которое ранее этой функцией не возвращалось. Используйте любые подходящие обозначения для указания переходов НКА. 5.3 Применения синтаксически управляемой трансляции Синтаксически управляемые методы из данной главы будут применены в главе 6 к проверке типов и генерации промежуточного кода.
Здесь же мы рассмотрим избранные примеры, иллюстрирующие некоторые представительные СУО. Основное применение в этом разделе заключается в построении синтаксических деревьев. Поскольку некоторые компиляторы в качестве промежуточного представления используют синтаксические деревья, распространенным видом Глава 5. Синтаксически управляемая трансляция СУО является преобразование входной строки в дерево.
Для завершения трансляции в промежуточный код компилятор затем может обойти построенное синтаксическое дерево, используя другой набор правил. (В главе б рассматривается подход к построению промежуточного кода, при котором СУО применяется без явного построения дерева.) Мы рассмотрим два СУО для построения синтаксических деревьев для выражений. Первое Я-атрибутное определение может использоваться в процессе восходящего синтаксического анализа. Второе Ь-атрибутное определение подходит для использования во время нисходящего синтаксического анализа.
Заключительный пример в этой главе представляет собой Ь-атрибутное определение, работающее с базовыми типами и массивами. 5.3.1 Построение синтаксических деревьев Как говорилось в разделе 2.8.2, каждый узел синтаксического дерева представляет конструкцию; его дочерние узлы представляют значащие компоненты конструкции. Синтаксическое дерево, представляющее выражение Е~ + Ез, имеет метку + и два дочерних узла, представляющих подвыражения Е~ н Е.. Мы реализуем узлы синтаксического дерева при помощи объектов с соответствующим количеством полей. Каждый объект будет иметь поле ор, являющееся меткой узла.
У объектов будут следующие дополнительные поля. ° Если узел является листом, дополнительное поле хранит лексическое значение листа. Конструктор ЛеаДор, га!) создает объект листа. В качестве альтернативы, если узлы рассматриваются как записи, 1,еа)' возвращает указатель на новую запись для листа.
° Если узел — внутренний, то в нем имеется столько дополнительных полей, сколько у него дочерних узлов в синтаксическом дереве. Конструктор А!оИе получает два или больше аргументов: !Уо~(е (ор, сы сз,..., сь) создает объект с первым полем ор и Й дополнительными полями для й дочерних узлов сы...,сы Пример 5.11. Я-атрибутное определение на рис. 5.! О строит синтаксическое дерево для простой грамматики выражений, включающей только два бинарных оператора: + и —. Как обычно, эти операторы имеют один и тот же приоритет и совместно левоассоциативны. Все нетерминалы имеют один синтезируемый атрибут лопе, который представляет узел синтаксического дерева. Каждый раз при использовании первой продукции, Š— Е~ + Т, ее правило создает узел с *+' в качестве ор и двумя дочерними узлами Е!.лоЫе и Т.лойе для подвыражений. Вторая продукция имеет похожее правило.
В случае продукции 3, Š— Т, узел не создается, поскольку Е.поле имеет то же значение, что и Т.лойе. Аналогично не создается узел и при использовании 401 5.3. Применения синтаксически управляемой трансляции Рис. 5.10. Построение синтаксических деревьев для простых выражений продукции 4, Т вЂ” (Е). Значение Т.поде то же, что и значение Е.пог2е, поскольку скобки используются для группирования; они влияют на структуру дерева разбора и синтаксического дерева, но после выполнения своих функций их присутствие в синтаксическом дереве не является необходимым. Последние две Т-продукции имеют справа один терминал.
Мы используем конструктор Т,еаГ' для создания соответствующего узла, который становится значением Т.ног1е. На рис. 5.11 показано построение синтаксического дерева для выражения а — 4+ с. Узлы синтаксического дерева показаны как записи с первым полем ор. Здесь ребра синтаксического дерева показаны сплошными линиями, а лежащее в основе дерево разбора, построение которого в явном виде не требуется,— линиями, состоящими из точек.
![](https://s.studizba.com/z.php?f=/templates/si/i/noavatar.png&w=100&h=100&t=1"){kind=avatar}
