А.В. Ахо, М.С. Лам, Р. Сети, Дж. Д. Ульман - Компиляторы - принципы, технологии и инструментарий (1114947), страница 5
Текст из файла (страница 5)
Принципы и методы проектирования компиляторов применимы в таком количестве многих других областей, что только редкий ученый-кибернетик не столкнется с ними множество раз в процессе своей деятельности. Изучение написания компиляторов требует обращения к таким темам, как языки программирования, архитектура компьютера, теория языков, алгоритмы, разработка программного обеспечения. В этой вступительной главе вы познакомитесь с различными видами трансляторов, структурой типичного компилятора и узнаете о тенденциях развития языков программирования и архитектуры вычислительных систем и их влиянии на компиляторы.
Здесь также рассматриваются вопросы взаимодействия проектирования компиляторов и теоретической информатики и применения методов разработки компиляторов, выходящих за рамки компиляции. Завершится этот краткий обзор рассмотрением ключевых концепций языков программирования, которые будут необходимы при изучении компиляторов. 1.1 Компиляторы Попросту говоря, компилятор — это программа, которая считывает текст программы, написанной на одном языке — исходном„и транслирует (переводит) его в эквивалентный текст на другом языке — целевом (рис.
1.1). Одна из важных ролей компилятора состоит в сообщении об ошибках в исходной программе, обнаруженных в процессе трансляции. 3О Глава!. Введение в компиляцию Если целевая программа представляет собой программу на машинном языке, она затем может быть вызвана пользователем для обработки некоторых входных данных и получения некоторых выходных данных (рис. 1.2). Исходная программа Входныедаиные Выходныеданные Целевая программа Рис.
1.1. Компилятор Рис. 1.2. Выполнение целевой программы Инглерлреглаглор представляет собой еще один распространенный вид языюэвого процессора. Вместо получения целевой программы, как в случае транслятора, интерпретатор непосредственно выполняет операции, указанные в исходной программе, над входными данными, предоставляемыми пользователем (рис. 1.3).
Исходная программа Входныедаиные Выходныеданные Рис. 1.3. Интерпретатор Целевая программа на машинном языке, производимая компилятором, обычно гораздо быстрее, чем интерпретатор, получает выходные данные на основании входных. Однако интерпретатор обычно обладает лучшими способностями к диагностике ошибок, чем компилятор, поскольку он выполняет исходную программу инструкция за инструкцией.! Пример 1.1.
Языковой процессор 1ача объединяет в себе и компиляцию, и интерпретацию (рис. 1.4). Исходная программа на )ача может сначала компилироваться в промежуточный вид, именуемый байт-кодом (Ьутесог)е). Затем байт-код интерпретируется виртуальной машиной. Преимущество такого решения в том, что скомпилированный на одной машине байт-код может быть выполнен на другой, например, будучи передан по сети. 'Обращаем ваше внимание на перевал термина вгагвтвт в данной книге. Дословно он означает высказывание, утверждение, однако в применении к компьютерной тематике это не совсем удачно. Обычно при переводе используется термин олератор, но в данной книге, посвященной формальным языкам, этот термин имеет собственное значение. Поэтому при переводе термина тагетвлг за редкими исключениями было использовано понятие инструкция — как наиболее близкое по смыслу, так и использовавшееся в переводе предыдущего издания книги (А.
Ахо, Р. Сети, Д. Ульман. Камлияяторы: лрилцилы, технологии и илструмелты. — Мэ Издательский дом "Вильямс", 2001).— Прим. лер. 1.1. Компиляторы Для более быстрой обработки входных данных некоторые компиляторы вача, именуемые1из1-тл-11лте-компиляторами, транслируют байт-код в машинный язык непосредственно перед запуском промежуточной программы для обработки входных данных. тт Исходная программа Промеиуточная программа Входные данные Выходные данные Рис. !.4. Гибридный компилятор Кроме компиляторов, потребовать создания выполнимой целевой программы могут и другие программы (рис. 1.5).
Исходная программа может быть разделена на модули, находящиеся в различных файлах. Сборка исходной программы иногда поручается отдельной программе, именуемой ирелроиессоролг. Препроцес- Исходная программа Модифицированная исходная программа Целевая ассемблерная программа Перемещаемый машинный код Библиотечные файлы Перемещаемые объектные файлы Целевой машинный код Рис. 1.5. Система обработки языка З2 Глава 1. Введение в компиляцию сор может также раскрывать сокращения, именуемые макросами, в инструкции исходного языка. Модифицированная исходная программа затем передается компилятору. Компилятор может выдать в качестве выходных данных программу на языке ассемблера, поскольку ассемблерный код легче создать и проще отлаживать.
Язык ассемблера затем обрабатывается программой, которая называется ассемблер, и дает в качестве выходных данных перемещаемый машинный код. Большие программы зачастую компилируются по частям, так что перемещаемый машинный код должен быть скомпонован совместно с другими перемещаемыми объектными файлами и библиотечными файлами в код, кпторый можно будет выполнять на данной машине. Компоновщик ("линкер") выполняет разрешение внешних адресов памяти, по которым код из одного файла может обращаться к информации из другого файла. Загрузчик затем помещает все выполнимые объектные файлы в память для выполнения. 1.1.1 Упражнения к разделу 1.1 Упражнение 1.1.1.
В чем заключается разница между компилятором и интерпре- татором? Упражнение 1.1.2. Каковы преимущества (а) компилятора перед интерпретато- ром и (б) интерпретатора перед компилятором? Упражнение 1.1.3. Каковы преимущества системы обработки языка, в которой компилятор дает выход на языке ассемблера, по сравнению с системой, в которой компилятор дает выход на машинном языке? Упражнение 1.1.4. Компилятор, который транслирует программу на высокоуровневом языке программирования в программу на другом высокоуровневом языке программирования, называется транслятором из исходного текста в исходный текст (зоцгсе-ю-зоцгсе).
Каковы преимущества использования языка программирования С в качестве целевого для такого компилятора? Упражнение 1.1.5. Опишите некоторые из задач, которые должен выполнять ас- семблер. 1.2 Структура компилятора Пока что мы рассматривали компилятор как "черный ящик", отображающий исходную программу в семантически эквивалентную ей целевую программу. Если мы немного приоткроем этот ящик, то увидим, что это отображение разделяется на две части: анализ и синтез.
Анализ разбивает исходную программу на составные части и накладывает на них грамматическую структуру. Затем он использует эту структуру для создания зз 1.2. Структура компилятора промежуточного представления исходной программы. Если анализ обнаруживает, что исходная программа неверно составлена синтаксически либо дефектна семантически, он должен выдать информативные сообщения об этом, чтобы пользователь мог исправить обнаруженные ошибки. Анализ также собирает информацию об исходной программе и сохраняет ее в структуре данных, именуемой таблицей сииволов, которая передается вместе с промежуточным представлением синтезу.
Синтез строит требуемую целевую программу на основе промежуточного представления и информации из таблицы символов. Анализ часто называют начальной стадией ((гоп1 епд), а синтез — заключительной (Ьас)г епд). Если рассмотреть процесс компиляции более детально, можно увидеть, что он представляет собой последовательность фаз, каждая из которых преобразует одно из представлений исходной программы в другое. Типичное разложение компилятора на фазы приведено на рис.
1.6. На практике некоторые фазы могут объединяться, а межфазное промежуточное представление может не строиться явно. Таблица символов, в которой хранится информация обо всей исходной программе. используется всеми фазами компилятора. Некоторые компиляторы содержат фазу машинно-независимой оптимизации между анализом и синтезом. Назначение этой оптимизации — преобразовать промежуточное представление, чтобы синтез мог получить более качественную целевую программу по сравнению с той, которая может быть получена из неоптимизированного промежуточного представления. Поскольку оптимизация необязательна, некоторые фазы оптимизации, показанные на рис.
1.6, в компиляторе могут отсутствовать. 1.2.1 Лексический анализ Первая фаза компиляции называется лексически.и анализол~ или сканированием. Лексический анализатор читает поток символов, составляющих исходную программу, и группирует эти символы в значащие последовательности, называющиеся лексемами. Для каждой лексемы анализатор строит выходной токен (Го)геп) вида (иия такена, значение атрибута) Он передается последующей фазе, синтаксическому анализу. Первый компонент токена, имя токена, представляет собой абстрактный символ, использующийся во время синтаксического анализа, а второй компонент, значение атриб>та, указывает на запись в таблице символов, соответствующую данному токену.
Информация из записи в таблице символов необходима для семантического анализа и генерации кода. Предположим, например, что исходная программа содержит инструкцию присваивания ровйхоп = зпх11а1 + га1е * 60 (1.!) 34 Глава 1. Введение в компиляцию Поток символов Поток токенов Синтаксическое дерево Синтаксическое дерево Промежуточное представление Промежуточное представление Код целевой машины Код целевой машины Рис. 1.б. Фазы компилятора Символы в этом присваивании могут быть сгруппированы в следующие лексемы и отображены в следующие токены, передаваемые синтаксическому анализатору. 1.