В.А. Серебряков - Теория и реализация языков программирования (1114953), страница 2
Текст из файла (страница 2)
. . . . . . . . 21510.1. Система СУПЕР . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 21510.2. Система YACC . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 217П р и л о ж е н и е . Классы атрибутных грамматик . .
. . . . . . . .A.1. Атрибутированное дерево разбора . . . . . . . . . . . . . . . . . .A.2. Незацикленные атрибутные грамматики . . . . . . . . . . . . .A.3. Вычислительные последовательности и корректность.визита. . . . . . . . . . . . . . . . . . . . . . . . . . . .
. . . . . . . . . . .A.4. Чистые многовизитные грамматики . . . . . . . . . . . . . . . . .A.5. Абсолютно незацикленные атрибутные грамматики . . . . .A.6. Простые многовизитные атрибутные грамматики . . . . . . .A.7. Одновизитные атрибутные грамматики . . . .
. . . . . . . . . .A.8. Многопроходные грамматики. . . . . . . . . . . . . . . . . . . . . ...............................Определение............................................................220220220222223224227228229Список литературы . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
. . . . . . . 234ПРЕДИСЛОВИЕПредлагаемая вниманию читателя книга основана на курсе лекций, прочитанных на факультете вычислительной математики и кибернетики МГУим. М.В. Ломоносова и на факультете управления и прикладной математикиМосковского физико-технического института. Диапазон вопросов, затронутых в книге, достаточно широк — от свойств формальных языков и до техники трансляции.
Круг этих вопросов представляет собой базис знаний,необходимых квалифицированному специалисту в области методов трансляции. В книге представлены «классические» разделы теории разработкикомпиляторов: лексический и синтаксический анализ, организация памятикомпилятора (таблицы символов) и периода исполнения (магазина), генерациякода. Рассматриваются такие средства автоматизации процесса разработкитрансляторов, как LEX, YACC, СУПЕР, методы генерации оптимальногокода. На протяжении всего изложения проводится единая «атрибутная» точказрения на процесс разработки компилятора.
Бо́льшая часть алгоритмов, изложенных в книге, реализована в виде программ на языке Java. Эти программысоставляют программное приложение к книге, размещенное на сайте тряп.рф.В тексте книги важную роль играют формальные конструкции. В предложениях, их содержащих, обычные правила пунктуации иногда не соблюдаются.Книга рассчитана как на студентов и аспирантов программистских специальностей, так и на профессионалов в области программирования.Автор благодарит всех, кто способствовал выходу этой книги в свет,и с признательностью примет все конструктивные замечания по ее содержанию и оформлению.Глава 1ВВЕДЕНИЕ1.1.
Место компилятора в программном обеспеченииКомпиляторы составляют существенную часть программного обеспеченияЭВМ. Это связано с тем, что языки высокого уровня стали основным средством разработки программ. Сегодня только очень малая часть программногообеспечения, требующая особой эффективности, разрабатывается с помощьюассемблеров. В настоящее время имеют применение довольно много языковпрограммирования. Наряду с традиционными языками, такими, например, какФортран, широкое распространение получили так называемые «универсальные» языки (Паскаль, Си, Java и др.), а также некоторые специализированные(например, язык обработки списочных структур Лисп). Кроме того, большоераспространение получили языки, связанные с узкими предметными областями, такие, как входные языки пакетов прикладных программ.Для ряда названных языков имеется довольно много реализаций.
Так,на рынке программного обеспечения представлены десятки реализаций языков Паскаля, Java или Си. С другой стороны, постоянно растущая потребность в новых компиляторах связана с бурным развитием архитектур ЭВМ.Это развитие идет по различным направлениям. Наряду с возникновением новых архитектур совершенствуются старые архитектуры как в концептуальномотношении, так и по отдельным, конкретным параметрам.
Это можно проиллюстрировать на примере микропроцессора Intel. Последовательные версииэтого микропроцессора отличаются не только техническими характеристиками, но и, что более важно, новыми возможностями и, значит, изменением(расширением) системы команд. Естественно, это требует новых компиляторов (или модификации старых).
То же можно сказать о микропроцессорахMotorola.В рамках традиционных последовательных машин развивается большоечисло различных направлений архитектур. Примерами могут служить архитектуры CISC, RISC. Такие ведущие фирмы, как Intel, Motorola, Sun, начинают переходить на выпуск машин с RISC-архитектурами. Естественно, длякаждой новой системы команд требуется полный набор новых компиляторовс распространенных языков.8Глава 1. ВведениеНаконец, бурно развиваются различные параллельные архитектуры.
Срединих отметим векторные, многопроцессорные, с широким командным словомархитектуры (вариантом которых являются суперскалярные ЭВМ). На рынке уже имеются десятки типов ЭВМ с параллельной архитектурой, начиная от супер-ЭВМ (Cray, CDC и др.), через рабочие станции (например,IBM RS/6000) и кончая персональными компьютерами. Естественно, каждаяиз новых машин снабжается новыми компиляторами для многих языковпрограммирования. Здесь необходимо также отметить, что новые архитектурытребуют разработки совершенно новых подходов к созданию компиляторов,так что наряду с собственно разработкой компиляторов ведется и большаянаучная работа по созданию новых методов трансляции.1.2.
Структура компилятораОбобщенная структура компилятора и основные фазы компиляции показаны на рис. 1.1.На начальной фазе лексического анализа входная программа, представляющая собой поток литер, разбивается на лексемы — слова в соответствиис определениями языка. Основными формализмами, лежащими в основе реализации лексических анализаторов, являются конечные автоматы и регулярные выражения. Лексический анализатор может работать в двух основныхрежимах: либо как подпрограмма, вызываемая синтаксическим анализаторомдля получения очередной лексемы, либо как полный проход, результатомкоторого является файл лексем.В процессе выделения лексем лексический анализатор может как самостоятельно строить таблицы объектов (чисел, строк, идентификаторов и т. п.),так и выдавать значения для каждой лексемы при очередном к нему обращении.
В этом случае таблицы объектов строятся в последующих фазах(например, в процессе синтаксического анализа).На этапе лексического анализа обнаруживаются некоторые (простейшие)ошибки: недопустимые символы, неправильная запись чисел, идентификаторов и др.Центральная задача синтаксического анализа — разбор структуры программы. Как правило, под структурой понимается дерево, соответствующееразбору в контекстно-свободной грамматике языка. В настоящее время чащевсего используется либо LL(1)-анализ (и его вариант — рекурсивный спуск),либо LR(1)-анализ и его варианты (LR(0), SLR(1), LALR(1) и др.). Рекурсивный спуск чаще используется при ручном программировании синтаксическогоанализатора, LR(1) — при использовании систем автоматического построениясинтаксических анализаторов.1.2.
Структура компилятора9Рис. 1.1Результатом синтаксического анализа является синтаксическое дерево соссылками на таблицы объектов. Ошибки, связанные со структурой программы, также обнаруживаются в процессе синтаксического анализа.На этапе контекстного анализа выявляются зависимости между частямипрограммы, которые не могут быть описаны контекстно-свободным синтаксисом. Это в основном — связи «описание-использование», в частности,10Глава 1.
Введениеанализ типов объектов, анализ областей видимости, соответствие параметров,метки и др. В процессе контекстного анализа таблицы объектов пополняютсяинформацией об описаниях (свойствах) объектов.Основным формализмом, используемым при контекстном анализе, является аппарат атрибутных грамматик.
Результатом контекстного анализа является атрибутированное дерево программы. Информация об объектах можетбыть как рассредоточена в самом дереве, так и сосредоточена в отдельныхтаблицах объектов. В процессе контекстного анализа также могут быть обнаружены ошибки, связанные с неправильным использованием объектов.Затем программа может быть переведена во внутреннее представление.Это делается для целей оптимизации и/или удобства генерации кода. Ещеодной целью преобразования программы во внутреннее представление является желание иметь переносимый компилятор.
Тогда только последняяфаза (генерация кода) является машинно-зависимой. В качестве внутреннегопредставления могут использоваться префиксная или постфиксная запись,ориентированный граф, тройки, четверки и другие способы.Фаз оптимизации может быть несколько. Оптимизации обычно делятна машинно-зависимые и машинно-независимые, локальные и глобальные.Определенная часть машинно-зависимой оптимизации выполняется на фазегенерации кода. Глобальная оптимизация пытается принять во вниманиеструктуру всей программы, локальная — только небольших ее фрагментов.Глобальная оптимизация основывается на глобальном потоковом анализе, который выполняется на графе программы и представляет по существу преобразование этого графа.
![](https://s.studizba.com/z.php?f=/templates/si/i/noavatar.png&w=100&h=100&t=1"){kind=avatar}
