А.В. Ахо, М.С. Лам, Р. Сети, Дж. Д. Ульман - Компиляторы - принципы, технологии и инструментарий (1114947), страница 23
Текст из файла (страница 23)
Простой синтаксически управляемый транслятор Пример 2.13. Рассмотрим схему трансляции на рис. 2.21. Пусть А = ехрг а = + (епп ) рпп1(г+') ) (3 = — (егт ( рпп1('-') ) у = (егт В этом случае преобразование для устранения левой рекурсии приводит к схеме трансляции, показанной на рис. 2.23. Продукции для ехр«из рис. 2.21 преобразованы в одну продукцию для ехрг и продукции для нового нетерминала, который играет роль 22. Продукции для гегт те же, что и на рис. 2.21.
На рис. 2.24 показано, как выражение 9-5+2 транслируется с использованием грамматики, приведенной на рис. 2.23. и ехрг — (егт геяр ГЕХ( — г + ГЕ«т ( рПП(('+ ) ) ГЕХ( — Гегт ( рпп(('-') ) гехт Е (егт — г 0 1 рпп1(г0 ) ) 1 ( рпп(('1г) ) 9 ( рпп((г9г) ) Рис. 2.23. Схема трансляции гюсле устранения левой рекурсии ехрг 5 (рплю'59( + Геня (рпп1('+31 генг г 2 (рплю('23( е Рис. 2.24. Трансляция 9-5+2 в 95-2+ Устранение левой рекурсии должно выполняться очень аккуратно, чтобы гарантировать сохранение порядка семантических действий. Например, преобразованная схема на рис. 2.23 содержит действия ( рпп(('+') ) и ( рпп(('-') ) в средине )13 2.5. Транслятор простых выражений тела продукции, между нетерминалами 1егт и гека Если действие будет перемещено в конец тела продукции, после гет, трансляция станет некорректной. Читатель может самостоятельно убедиться, что в этом случае выражение 9-5+2 будет транслировано в 952+-, постфиксную запись для 9-(5+2), вместо корректной постфиксной записи 95-2+ выражения ( 9-5 ) +2.
2.5.3 Процедуры для нетерминалов Функции ехрг, гех1 и 1епл на рис. 2.25 реализуют схему синтаксически управляемой трансляции из рис. 2.23. Эти функции имитируют тела продукций соответствующих нетерминалов. Функция ехрг реализует продукцию ехрг — гегт гехт путем вызова 1егт () с последующим вызовом гехг(). чоИ ехрг() ( (егт(); гех1О; чоИ гех1() ( Ы ( 1ооййеаН = + ) ( та1сц'+'); 1егт()' рпп1('+')' гетО' е!яе и ( 1ооййеаИ = — '-' ) ( татски('-'); геттО; рпп1('-'); гех1() еие ( ) /ч Не делать ничего */; чав гегтО ( Ы( 1ооlайеай — цифра ) ( ~ =!оо)салеай; та1сл(1оо)салеа4; рпп1(1); е!ае герог1("ауп!ах епог"); Рнс.
2.25. Псевдокод для нетерминалов ехрг, ген и !епп Функция гет реализует три продукции для нетерминала гех1 на рис. 2.23. Она применяет первую продукцию, если сканируемый символ — знак "плюс", вторую — если это знак "минус", и продукцию гет — е во всех прочих случаях. Первые две продукции для «ех1 реализуются первыми двумя ветвями инструкции и в процедуре гея1. Если сканируемый символ — +, вызывается функция соответствия та1сЬ ('+ '), перемещающаяся по входной строке. После вызова депп () 114 Глава 2. Простой синтаксически управляемый транслятор реализуется семантическое действие путем печати символа "плюс".
Вторая продукция совершенно аналогична, только знак + заменяется знаком —. Поскольку третья продукция для гни в правой части содержит только е, последняя конструкция е1яе в функции ген не выполняет никаких действий. Десять продукций для депп генерируют десять цифр. Поскольку каждая из этих продукций генерирует цифру и печатает ее, один н тот же код на рис. 2.25 применим для всех них. При успешной проверке переменная 1 используется для хранения цифры, представленной переменной !оо)салеаЫ, поскольку последняя будет перезаписана вызовом татсЬ.
Вспомните, что эта функция изменяет текущий сканируемый символ, так что цифра должна быть сохранена для последующей печати.т 2.5.4 Упрощение транслятора Перед тем как показать вам полный текст программы, выполним два упрощающих преобразования кода на рис. 2.25. Эти упрощения приведут к переносу процедуры гетз в процедуру ехрг.
Такое упрощение позволяет уменьшить количество необходимых процедур при наличии многочисленных уровней приоритетов. Во-первых, некоторые рекурсивные вызовы можно заменить итерациями. Когда последней выполняемой инструкцией в теле процедуры является рекурсивный вызов той же самой процедуры, говорят, что такой вызов оконечно рекурсивен (1ай гесцга1уе). Например, в функции гек1 вызовы гела О для сканируемых символов + и — являются оконечно рекурсивными, поскольку рекурсивный вызов гш1 является последней инструкцией, выполняемой текущим вызовом гехп В случае процедуры без параметров оконечно рекурсивный вызов можно заменить простым безусловным переходом в начало процедуры. Код функции гех1 может быть переписан так, как показано в псевдокоде на рис.
2.26. Пока сканируемый символ представляет собой знак "плюс" нли "минус". процедура гехт вызывает функцию та~сБ для данного символа, затем вызывает функцию ~ели для цифры из входной строки и циклически продолжает этот процесс. В противном случае цикл тв1з11е прекращает работу и выполняется выход из функции гека Во-вторых, завершенная программа на языке программирования 3ата должна включать еще одно изменение. Поскольку оконечно рекурсивный вызов ген на рис. 2.25 заменен итерациями, единственный остающийся вызов гех~ остается внутри процедуры ехрг.
Таким образом, эти две процедуры могут быть объединены в одну путем замены вызова ген О телом процедуры гехп 7 В качестве небольшой оптимизации можно выполнить печать перед вызовом та~си, чтобы избежать необходимости хранения цифры. В общем же случае изменение порядка действий и граммвтических символов рискованно, поскольку при этом может измениться сама трансляция. 2.5. Транслятор простых выражений чоЫ гезго ! тчм!е( !гпе ) ! !1(!оо(галеаЫ == '+' ) ! та(сл('+'); (егто; рг1пг('+'); сопнппе; ене !! ! (ооАавеаг(== '-') ! та(си('-'); (егто; рг)п!!'-'); сопапне; Ьгеай; Рис. 2.26.
Устранение оконечной рекурсии в процедуре гез! из рис. 2.25 2.5.5 Завершенная программа Завершенная программа на языке программирования )ача показана на рис. 2.27. Первая строка на рис. 2.27, начинающаяся со слова 1врогг, предоставляет доступ к пакету 3 ача. 1о для системного ввода и вывода. Остальной код состоит из двух классов — Рагзег и Розггах. Класс Рагзег содержит переменную 1оо)са)зеаг! и функции Рагзег, ехрг, Гегв и васс)з.
Выполнение программы начинается с функции ва1п, определенной в классе Розгг1х. Функция вафп создает экземпляр рагзе класса Рагзег и вызывает его функцию ехрг для синтаксического анализа выражения. Функция Рагзег, имеющая то же имя, что и имя класса, является конструктором; она вызывается автоматически при создании объекта класса. Обратите внимание, что ее определение в начале класса Рагзег инициализирует переменную 1оо)са)таас! путем чтения токена. Токены, состоящие из отдельных символов, предоставляются системной подпрограммой геас), которая считывает очередной символ из входной строки.
Обратите внимание, что переменная 1оо)са)теаг! объявлена как целое число, а не символ. Это сделано для того, чтобы упредить возможное появление в дальнейшем дополнительных токенов, которые будут отличны от отдельных символов. Функция ехрг представляет собой результат применения упрощений, рассмотренных в разделе 2.5.4; она реализует нетермнналы ехрг и гезг из рис. 2.23. Код функции ехрг на рис. 2.27 вызывает гегв, за которым следует цикл тчМ!е, который бесконечно проверяет переменную 1ооЕа)теас! на равенство '+' или '-'.
Выход из цикла осуществляется по достижении инструкции геГигп. Внутри цикла для вывода символа используются средства класса Яузгев. Функция гегв использует подпрограмму 1зЫдфГ из класса С)тагасгег языка программирования )ача для проверки того, что сканируемый символ явля- 116 Глава 2. Простой синтаксически управляемый транслятор йврогс Эача.йо.*) с1азв Рагвег ( всасйс йпс 1оо)сайеаФ риЬ11с Рагзег() ГЬгомв 10Ехсерсйоп ( 1оо)сапеаб = Яузсев.йп.геас(()г ) чойс ехрг() ГЬгомв 10Ехсерсйоп ( гегв(); мЬ11е(сгпе) ( И( 1оо)сайеас( = '+' ) ( вагсЬ('+')) Гегв(); Яузсев.опт.иг1Ге('+')г ) е1зе 1Е( 1оо)саЬеас( == '-' ) вассЬ('-'); Гегв()Г Яузсев.оп( .мг1Ге('-'); ) е1ве гегпгпг чойс( сегв() ГЬгомз 10Ехсерсйоп 11( СЬагасгег.йзШд1Г((сйаг)1оо)сайеас() ) ( Яувсев.оиг.мгйсе((сйаг)1оо)саЬеаб); вассЬ(1оо)сайеас(); ) е1ве сйгом пем Еггог("пупсах еггог"); чойс( васой(йпГ Г) ГЬгомз 10Ехсерсйоп ( 11( 1оо)сайеас( == с ) 1оо)саЬеаб = Яувсев.йп.геас)(); е1ве Спгом пем Еггог("вупсах еггог"); риЪ11с с1авв РозГЕ1х ( рпЬ11с вгагйс чоЫ вайп(ЯГг1пд[) агдв) сЬгомв 10Ехсергйоп ( Рагвег рагзе = пеи Рагзег(); рагве.ехрг(); Яузтев.опт.мгйсе('тп')г ) Рис.
2.27. Программа на языке программирования 1ача для трансляции инфиксных выра- жений а постфиксную запись 117 2.5. Транслятор простых выражений Несколько выдающихся возможностей Лича Тем, кто не знаком с языком программирования Зача, при чтении кода на рис. 2.27 могут помочь следующие примечания. ° Класс в 1ача состоит из последовательности определений переменных и функций. ° Скобки вокруг списка параметров необходимы даже при отсутствии параметров; следовательно, надо писать ехрг ( ) и сего( ) . Эти функции в действительности являются процедурами, поскольку они не возвращают никаких значений, на что указывает ключевое слово чофс( перед именем функции. ° Функции обмениваются информацией посредством либо передачи параметров по значению, либо обращения к общим данным. Например, функции ехрг() и Геглз() получают информацию о сканируемом символе при помощи переменной класса 1ос)са)зеад, к которой они могут обратиться, являясь с ней членами одного класса Рагвег.
![](https://s.studizba.com/z.php?f=/templates/si/i/noavatar.png&w=100&h=100&t=1"){kind=avatar}
