А.В. Ахо, М.С. Лам, Р. Сети, Дж. Д. Ульман - Компиляторы - принципы, технологии и инструментарий (1114947), страница 82
Текст из файла (страница 82)
Как вы узнаете из приведенного ниже примера, не все СУТ могут быть реализованы в процессе синтаксического анализа. Пример 5.16. В качестве крайнего примера проблемной СУТ предположим, что мы преобразовали наш калькулятор в СУТ, которая печатает выражения в префиксном виде, а не вычисляет их значения. Продукции н действия такой СУТ показаны на рис. 5.21. К сожалению, эту СУТ невозможно реализовать в процессе нисходящего или восходящего синтаксического анализа, поскольку синтаксический анализатор должен выполнять критические действия, такие как вывод экземпляра * или +, задолго до того, как станет известно о его наличии во входном потоке. Использование нетерминалов-маркеров Мз и М4 для действий в продукциях соответственно 2 и 4 приводит к тому, что ПС-синтаксический анализатор (см.
411 5.4. Синтаксически управляемые схемы трансляции !) Ь вЂ” Еп 2) К вЂ” ~ (рггп1('+ ');) Е1 + Т 3) Е- Т 4) Т вЂ” ~ (рп'п1('а');) Т1 * Г 5) Т- Г б) Г- (Е) 7) à — ~ йфт )рнп~ (61р|Лехта!);) Рис. 5.21. Проблемная СУТ для трансляции инфиксных выражений в префиксные в процессе синтаксического анализа раздел 4.5.3) при входном символе, например, 3 обнаруживает конфликт между сверткой согласно Мз — е, сверткой согласно М4 — е и переносом обнаруженной во входном потоке цифры. и Любая СУТ может быть реализована следующим образом. 1. Игнорируя действия, выполняется синтаксический анализ входного потока и строится дерево разбора.
2. Проверяется каждый внутренний узел Х, скажем, для продукции А — ~п. Добавляем к Х дополнительные дочерние узлы для действий из гт таким образом, что дочерние узлы Х слева направо составляют символы и действия о. 3. Выполняется обход дерева в прямом порядке (см. раздел 2.3.4) и при посещении узла, помеченного действием, выполняется это действие. Например, на рис. 5.22 показано дерево разбора со вставленными действиями для выражения 3*5+4. При посещении узлов дерева в прямом порядке получается префиксная запись выражения: + * 3 5 4. 5.4.4 Устранение левой рекурсии из СУТ Поскольку ни одна грамматика с левой рекурсией не может быть детерминированно проанализирована нисходящим синтаксическим анализатором, нам надо устранять из грамматики левую рекурсию (с этим действием мы уже встречались в разделе 4.3.3).
Когда грамматика является частью СУТ, при устранении левой рекурсии необходимо побеспокоиться также и о действиях. Начнем с рассмотрения простого случая, в котором нас интересует только порядок выполнения действий в СУТ. Например, если каждое действие состоит в печати строки, то нас интересует только порядок, в котором будут напечатаны эти строки. В этом случае можно руководствоваться следующим принципом.
412 Глава 5. Синтаксически управляемая трансляция ( рппс('с-'); ) Е ( риссс(чр); ) Т г я(я(с ( рнрс(4); ) а(я(с ( рппс(5); ) а(я)с ( рппс(3); ) Рис. 5.22. Дерево разбора с добавленными действиями ° При внесении изменений в грамматику следует рассматривать действия так, как если бы они были терминальными символами. Этот принцип основан на той идее, что преобразования грамматики сохраняют порядок терминалов в генерируемой строке.
Действия, таким образом, выполняются в одном и том же порядке при любом синтаксическом анализе слева направо, как нисходящем, так и восходящем. "Трюк" устранения левой рекурсии состоит в том, что мы берем продукции А — Аа ()3 Они генерируют строки, состоящие из д и произвольного количества а, и заменяем их продукциями, которые генерируют те же строки с использованием нового нетерминала Л: А — (3Л Л вЂ” аЛ! е Если (3 не начинается с А, то А больше не имеет леворекурсивной продукции.
В терминах регулярных определений в обоих множествах продукций А определяется как (3 (а)*. Как справиться с ситуациями, когда А имеет больше рекурсивных или нерекурсивнсых продукций, описано в разделе 4.3.3. Пример 5.17. Рассмотрим следуюц(ие Е-продукции из СУТ лля преобразования инфиксных выражений в постфиксную запись: Š— ~ Е) + Т ~рг(п(('+ ');) Š— Т 413 5.4. Синтаксически управляемые схемы трансляции Если мы применим стандартное преобразование к Е, то остатком леворекурсивной продукции будет а = +Т (рппг ('+ ');) А Д, тело другой продукции, — Т. Если мы введем В как остаток Е, то получим следующее множество продукций: Л вЂ” ~ + Т (рггп1 (' + ');) гг — > г Если же действия СУО не просто выводят строки, но и вычисляют атрибуты, то следует быть более осторожным при устранении левой рекурсии из грамматики.
Однако, если СУО является $-атрибутным, то мы всегда можем построить СУТ путем размещения действий по вычислению атрибутов в соответствующих позициях в новых продукциях. Приведем общую схему для случая одной рекурсивной продукции, одной нерекурсивной продукции и одного атрибута леворекурсивного нетерминала; обобщение на случай многих продукций каждого типа не сложное, но весьма громоздкое. Предположим, что эти две продукции— А — ~ А1У (А.а=д(А1.а,Ку)) А — Х (А.а = ('(Хск)) Здесь А.а — синтезируемый атрибут леворекурсивного нетерминала А, а Х и У— отдельные грамматические символы с синтезируемыми атрибутами Х.х и У.у соответственно.
Они могут представлять строки из нескольких грамматических символов, каждый со своими атрибутами, поскольку схема содержит произвольную функцию д, вычисляющую А.а в рекурсивной продукции, и произвольную функцию г", вычисляющую А.а в другой продукции. В любом случае г" и д получают в качестве аргументов атрибуты, доступ к которым разрешен в случае Я- атрибутного СУО. Мы хотим преобразовать лежащую в основе грамматику в А — ХЛ Л вЂ” > УЙ~ е На рис.
5.23 показано, что должна делать СУТ на основе новой грамматики. На рис. 5.23, а мы видим результат работы постфиксной СУТ на основе исходной грамматики. Здесь один раз применяется функция )', соответствующая использованию продукции А — Х, а затем функция д применяется столько раз, сколько раз используется продукция А — А У. Поскольку В генерирует "остаток" строки из У, его трансляция зависит от строки слева от этого грамматического символа, т.е. 414 Глава 5. Синтаксически управляемая трансляция от строки вида ХУУ .
У. Каждое использование продукции Л вЂ” У Л приводит к применению функции д. В случае Л мы используем наследуемый атрибут Лл для накопления результата последовательного применения функций д, начиная со значения атрибута А.а. А.а = В(я(ДХх),?;.у), Уьу) /' Х Ми =Д(Х.х) А.а =В(/(Хх),гиу) У2 у, ЯА = я(Г(Х.х), Уау) ?", А.и =Д(Хх) ) ~ Я.! = В(я(ДХ.х), Уиу), Уьу) б) а) Рис. 5.23. Устранение левой рекурсии из постфиксной СУТ Кроме того, Л имеет синтезируемый атрибут Л.в, не показанный на рис.
5.23. Этот атрибут в первый раз вычисляется, когда Л завершает генерацию символов У, о чем свидетельствует использование продукции Л вЂ” е. Затем Л.в копируется вверх по дереву, так что он становится значением А.а для всего выражения ХУУ . У. На рис. 5.23 показана ситуация, когда А генерирует строку ХУУ, и видно, что значение А.а в корне дерева на рис. 5.23, а включает два использования функции д. То же самое можно сказать и о Л.г в нижней части дерева на рис. 5.23, б; это значение уже как значение Л.в затем копируется вверх по дереву.
Итак, для завершения трансляции используется следующая СУТ: А — ~ Х (Л.г' = )" (Х.х)) Л (А.а = Л.в) Л У (Л).г = д(Л.?',Уд)) Л) (Л.в = Л?.в) Л вЂ” е (Л.в = Л.г) Обратите внимание, что наследуемый атрибут Л.г' вычисляется непосредственно перед использованием Л в теле продукции, в то время как синтезируемые атрибуты А.а и Л.в вычисляются в конце продукций. Таким образом, все значения, необходимые для вычисления этих атрибутов, будут доступны из вычислений, проведенных в телах продукций слева. 5.4.5 СУТ для Ь-атрибутных определений В разделе 5.4.1 мы преобразовали Я-атрибутное СУО в постфиксную СУТ с действиями на правом конце продукций.
Поскольку лежащая в основе СУТ 415 5.4. Синтаксически управляемые схемы трансляции грамматика принадлежит классу ЬК, постфиксная СУТ может анализироваться и транслироваться снизу вверх. Рассмотрим теперь более общий случай Ь-атрибутного СУО.
Будем считать, что грамматика поддается нисходящему синтаксическому анализу, поскольку, если это не так, зачастую трансляцию невозможно выполнить ни ЬЬ-, ни ЬК-синтаксическим анализатором. Для произвольной грамматики применим метод, состоящий в присоединении действий к дереву разбора и выполнении их в процессе обхода дерева в прямом порядке. Вот правила, используемые при превращении 1.-атрибутного СУО в СУТ.
1. Вставить действие, которое вычисляет наследуемые атрибуты нетерминала А, непосредственно перед вхождением А в тело продукции. Если несколько наследуемых атрибутов А ациклически зависят друг от друга, следует упорядочить вычисление атрибутов с тем, чтобы сначала вычислялись те атрибуты, которые требуются первыми. 2. Поместить действия, вычисляющие синтезируемые атрибуты заголовка продукции, в конце тела соответствующей продукции. Проиллюстрируем эти принципы на двух расширенных примерах. Первый относится к области полиграфии и иллюстрирует, как методы компиляции могут использоваться в приложениях, далеких от того, что обычно представляется при словосочетании "язык программирования".
Второй пример связан с генерацией промежуточного кода для типичной конструкции языка программирования — цикла ткй)1е. Пример 5.18. Этот пример вдохновлен языками для набора математических формул. Одним из первых таких языков был язык Ес1п; ряд идей из Ес)п можно обнаружить и в системе ТЕХ, которая использовалась при подготовке данной книги. Мы сосредоточимся только на возможности определения нижних индексов, индексов у индексов и т.д., игнорируя верхние индексы, встроенные дроби и прочие особенности математических формул. В Ес)п строка а впЪ з впЪ э указывала на выражение а;,. Простейшей грамматикой для боксов (элементов текста, ограниченных прямоугольником) является  — В~ Вз ~ В~ япЬ Вз ~ (Вз) ~ 1ех1 В соответствии с приведенными четырьмя продукциями бокс может представлять собой одно из нижеперечисленного.
![](https://s.studizba.com/z.php?f=/templates/si/i/noavatar.png&w=100&h=100&t=1"){kind=avatar}
