А.В. Ахо, М.С. Лам, Р. Сети, Дж. Д. Ульман - Компиляторы - принципы, технологии и инструментарий (1114947), страница 4
Текст из файла (страница 4)
Языки программирования эволюционировали и перед разработчиками возникли новые проблемы. Архитектура компьютеров предлагает массу различных вычислительных ресурсов, которые для получения наивысших результатов должен использовать разработчик компилятора. Пожалуй, наиболее интересно то, что методы оптимизации кода нашли применение не только в компиляторах.
В настоящее время они используются в инструментарии для поиска ошибок в программном обеспечении и, что особенно важно, при проверке безопасности существующего кода. Большинство других методов — грамматика, регулярные выражения, синтаксические анализаторы и синтаксически управляемые трансляторы — также широко используются не только прн разработке компиляторов. Таким образом, наш подход остался тем же, что и в предыдущих версиях книги. Мы отдаем себе отчет в том, что лишь малая доля наших читателей будет заниматься разработкой или хотя бы поддержкой компилятора для какого-то из основных языков программирования.
Однако модели, теория и алгоритмы, связанные с компиляторами, могут применяться для решения широкого диапазона задач проектирования и разработки программного обеспечения. Таким образом, мы уделяем особое внимание задачам, которые обычно встречаются при разработке языковых процессоров, независимо от исходного языка или целевой машины. Использование данной книги Требуется примерно два семестра, чтобы охватить весь (или, по крайней мере, ббльшую часть) материал данной книги.
Обычно первая половина книги служит предметом изучения студентов на первых курсах, в то время как вторая, посвященная оптимизации кода, изучается на старших курсах. Вот краткое содержание глав книги. В главе 1 содержится, в основном, мотивационный материал, и при этом раскрываются некоторые базовые вопросы архитектуры компьютера и принципов языков программирования. Предисловие 25 В главе 2 разрабатывается миниатюрный компилятор и вводится множество новых концепций, которые будут затем детально рассмотрены в последующих главах. Сам компилятор вы найдете в приложении А.
Глава 3 посвящена лексическому анализу, регулярным выражениям, конечным автоматам и инструментарию для создания сканеров входного потока. Материал зтой главы может быть широко использован при разработке текстовых редакторов. В главе 4 приведены различные методы синтаксического анализа, нисходящие (рекурсивного спуска, 1.Ь) и восходящие (ЬК и его варианты). В главе 5 вы познакомитесь с принципиальными идеями синтаксически управляемых определений и трансляции. В главе 6 показано, как теория из главы 5 применяется для генерации промежуточного кода в типичном языке программирования.
В главе 7 обсуждаются вопросы сред времени выполнения, в частности управление стеком и сборка мусора. Глава 8 посвящена генерации объектного кода. В ней рассматриваются построение базовых блоков, генерация кода из выражений и базовых блоков и методы распределения регистров. Глава 9 служит введением в методы оптимизации кода, включая потоковые графы, структуры потоков данных и итеративные алгоритмы для их разрешения. В главе 10 рассматривается оптимизация на уровне команд. Основной упор делается на поиск возможностей параллельного вычисления в небольших последовательностях команд и их диспетчеризация для процессоров, способных выполнять несколько команд одновременно.
Глава 11 посвящена поиску крупномасштабной параллельности вычислений н ее использованию. Здесь упор делается на числовой код, который содержит связанные циклы, работающие с многомерными массивами. В главе 12 речь идет о межпроцедурном анализе: анализе указателей, использовании псевдонимов и анализе потоков данных, которые принимают во внимание последовательность вызовов процедур, достигающих данной точки кода. Материал данной книги изучался в нескольких университетах — Колумбии, Гарварде и Стенфорде. В Колумбии в учебных курсах для первокурсников по языкам программирования н трансляторам регулярно использовался материал глав 1 — 8.
Основным заданием данного курса являлось написание курсовой работы, выполняющейся небольшими группами студентов и состоящей в реализации небольшого языка программирования, спроектированного ими самостоятельно. Разработанные таким образом языки ориентированы на применение в различных областях, включая квантовые вычисления, генерацию музыки, компьютерную графику, игры, операции с матрицами и многое другое.
В своей работе студенты использовали генераторы компонентов компиляторов, такие как АИТЬК, 1.ех и Тасс, и методы синтаксически управляемой трансляции, рассматривающнеся в главах 2 и 5. Курс для старшекурсников основывался на материале глав 9 — 12, и основ- 2б Предисловие ной упор делался на генерацию кода и оптимизацию для современных машин, включая сетевую и многопроцессорную архитектуры. В Стенфорде краткий вводный курс охватывал материал приблизительно глав 1 — 8, хотя в нем было и введение в вопросы глобальной оптимизации, основанное на материале главы 9.
Второй курс, посвященный компиляторам, охватывал главы 9 — 12, а также материал по сборке мусора из главы 7. Студенты использовали местную систему ЮоеЧ на основе Зача для реализации алгоритмов анализа потоков данных. Необходимые требования Читатель должен владеть определенными знаниями в области информатики, включая, по меньшей мере, курс по программированию и курсы по структурам данных и дискретной математике.
Полезно также знать несколько различных языков программирования, Упражнения Практически в каждом разделе книги содержится большое количество упражнений. Более сложные упражнения отмечены одним восклицательным знаком, а самые сложные — двумя. Поддержка в Интернете Начальная страница книги находится по адресу с1гадопЬоо)с.асапйогс).ес)ц Здесь вы можете найти список обнаруженных ошибок и исправлений (!тггр: //ими-с1Ь. всапйогс).ес!ц/-ц11вап/с)галоп/еггага.!тГт1) и дополнительные материалы к книге. Мы надеемся сделать общедоступной информацию по всем курсам, посвященным компиляторам, которые мы ведем, включая домашние задания, решения задач и экзаменационные вопросы.
Мы также планируем сделать доступной информацию о важных компиляторах, предоставленную нх разработчиками. Благодарности Благодарим дизайнера обложки — С.Д. Ульман (Б.П. 1)!!шип) из Ягалхе Тол!с Ргойисг/опз. Джон Бентли ()оп Веп1!еу) основательно помог своими комментариями ряда глав книги, когда она находилась еще на стадии черновика.
Полезные комментарии и исправления ошибок были сделаны следующими людьми. Предисловие 27 Доменико Бьянкулли (Остен!со В!апсп!!!), Питер Бош (РеГег ВозсЬ), Марцио Басс (Магсю Впзз), Марк Идди (Маге ЕагЫу), Стефен Эдвардс (БгерЬеп Ебччагбз), Вибхав Гарг (Ч!ЬЬач Оагй), Ким Хазельвуд (Кпп Нале!ччоод), Гурав Кц (Оацгач Кс), Вей Ли (чче! 1л), Майк Смит (Мйге Бш!!Ь), Арт Стамнесс (Агг Бгапшезз), Криста Свор (Кгузга Бчоге), Оливер Тардью (01!ч!ег Тагббец) и Джия Зенг (Ла Уепй).
Мы благодарим всех их за помощь. Все оставшиеся в книге ошибки остаются на нашей совести. Кроме того, Моника благодарит своих коллег по работе над компилятором ЯЛР за 18-летнее обучение. Это Джеральд Айнер (ОегаЫ А!йпег), Дзинтарс Авотс (Оьйп!агз Ачогз), Саман Амарасингх (шатап Атагаз!пйЬе), Дженнифер Андерсон (депп!Тег Апдегзоп), Майкл Карбин (М!сЬае! СагЬ!п), Джеральд Чинг (ОегаЫ СЬеопй), Амер Диван (Атег О!ччап), Роберт Френч (КоЬегГ РгепсЬ), Анвар Гулом (Апиаг ОЬц!ошп), Мери Холл (Магу Най), Джон Хеннеси (УоЬп Неппеззу), Девид Гейне (ОачЫ Неше), Ших-Вей Лао (БЫЬ-'чче! 1лао), Ами Лим (Ату 1.цп), Бенджамин Лившиц (Веп)агп!п 1лчзЬ!Гв), Майкл Мартин (М!сЬае! Магбп), Дрор Майдан (Огог Маубап), Тодд Моури (ТогЫ Моччгу), Брайан Мерфи (Впап МцгрЬу), Джеффри Оплингер (ЮеГТгеу Ор!!пйег), Карен Пипер (Кагеп Р!ерег), Мартин Ринард (Магбп К!пагд), Олатунджи Рувасе (О!ашп)! Кпччазе), Константине Сапунцакис (Сопзгапбпе ЯарцпгхаЫз), Патрик Сатьянатан (Рацзсй БагЬуапагЬап), Майкл Смит (М!сЬае! Бш!1Ь), Стивен Тжианг (8!ечеп Т1!апй), Чау-Вен Ценг (СЬап-'ччеп Тзепй), Кристофер Анкель (СЬзззГорЬег 1)пйе1), Джон Воли (зоЬп 'ччЬа!еу), Роберт Вильсон (КоЬегГ 1!(г!!зоп), Кристофер Вильсон (СЬ6зГорЬег чч!!зоп) и Майкл Вольф (МЫЬае1 'ччо!!).
А. Ъ'. А., Чатмен, Нью-Джерси М. Я. 1., Менло-Парк, Калифорния К. Б., Фар-Хилле, Нью-Джерси 1. П. (!., Стенфорд, Калифорния Июнь, 2006 28 Предисловие От издательства Вы, читатель этой книги, и есть главный ее критик и комментатор.
Мы ценим ваше мнение и хотим знать, что было сделано нами правильно, что можно было сделать лучше и что еще вы хотели бы увидеть изданным нами. Нам интересно услышать и любые другие замечания, которые вам хотелось бы высказать в наш адрес. Мы ждем ваших комментариев и надеемся на них. Вы можете прислать нам бумажное или электронное письмо, либо просто посетить наш %еЬ-сервер и оставить свои замечания там. Одним словом, любым удобным для вас способом дайте нам знать, нравится или нет вам эта книга, а также выскажите свое мнение о том, как сделать наши книги более интересными для вас. Посылая письмо или сообщение, не забудьте указать название книги и ее авторов, а также ваш обратный адрес. Мы внимательно ознакомимся с вашим мнением и обязательно учтем его при отборе и подготовке к изданию последующих книг. Наши координаты: Е-ща11: хпйойиз11хатври!э1ьвЬхпд.сов %%%: Ьсгр://ими.их11хаыри!э1хаЬхпд.сов Информация для писем из России: !!5419, Москва, а/я 783 из Украины: 03150, Киев, а/я 152 ГЛАВА 1 Введение в компиляцию Языки программирования представляют собой средство описания вычислений для людей и машин.
Современный мир зависит от языков программирования, поскольку все программное обеспечение на всех компьютерах мира написано на том или ином языке программирования. Однако, прежде чем запустить программу, ее необходимо преобразовать в форму, которая может выполняться иа компьютере. Программные системы, выполняющие такое преобразование, называются комн иляя орами. Эта книга о том, как разрабатывать и реализовывать компиляторы. Вы узнаете, что для построения трансляторов для широкого диапазона языков и машин могут использоваться всего несколько базовых идей.
![](https://s.studizba.com/z.php?f=/templates/si/i/noavatar.png&w=100&h=100&t=1"){kind=avatar}
