Лекции по конструированию компиляторов глава 8 генерация кода


Основы конструирования компиляторов

Автор Серебряков В.А. Галочкин М.П.
Издательство Едиториал УРСС
Год 1999
Формат PDF

Предлагаемая вниманию читателя книга основана на курсе лекций, прочитанных на факультете вычислительной математики и кибернетики Московского государственного университета и факультете управления и прикладной математики Московского физико-технического института в 1991-1999 гг. Авторы надеются, что издание книги восполнит существенный пробел в литературе на русском языке по разработке компиляторов.

Содержание книги представляет собой «классические» разделы предмета: лексический и синтаксический анализ, организация памяти компилятора (таблицы символов) и периода исполнения (магазина), генерация кода. Рассматриваются некоторые средства автоматизации процесса разработки трансляторов, такие как LEX, YACC, СУПЕР, методы генерации оптимального кода. Сделана попытка на протяжении всего изложения провести единую «атрибутную» точку зрения на процесс разработки компилятора. В книге не затрагиваются чрезвычайно важные вопросы глобальной оптимизации и разработки компиляторов для машин с параллельной архитектурой. Авторы надеются восполнить эти пробелы в будущем.

Книга будет полезной как студентам и аспирантам программистских специальностей, так и профессионалам в этих областях.

Основы конструирования компиляторов. В.А.Серебряков, М.П.Галочкин

    Яков Алфимов 2 лет назад Просмотров:

1 Основы конструирования компиляторов В.А.Серебряков, М.П.Галочкин

2 2 Предисловие Предлагаемая вниманию читателя книга основана на курсе лекций, прочитанных на факультете вычислительной математики и кибернетики Московского государственного университета и факультете управления и прикладной математики Московского физико-технического института в гг. Авторы надеются, что издание книги восполнит существенный пробел в литературе на русском языке по разработке компиляторов. Содержание книги представляет собой классические разделы предмета: лексический и синтаксический анализ, организация памяти компилятора (таблицы символов) и периода исполнения (магазина), генерация кода. Рассматриваются некоторые средства автоматизации процесса разработки трансляторов, такие как LEX, YACC, СУПЕР, методы генерации оптимального кода. Сделана попытка на протяжении всего изложения провести единую атрибутную точку зрения на процесс разработки компилятора. В книге не затрагиваются чрезвычайно важные вопросы глобальной оптимизации и разработки компиляторов для машин с параллельной архитектурой. Авторы надеются восполнить эти пробелы в будущем. Книга будет полезной как студентам и аспирантам программистских специальностей, так и профессионалам в этих областях. Авторы с благодарностью примут все конструктивные замечания по содержанию книги. В.А.Серебряков, М.П.Галочкин,

3 Оглавление 1 Введение Место компилятора в программном обеспечении Структура компилятора Языки и их представление Алфавиты, цепочки и языки Представление языков Грамматики Формальное определение грамматики Типы грамматик и их свойства Лексический анализ Регулярные множества и выражения Конечные автоматы Алгоритмы построения конечных автоматов Построение недетерминированного конечного автомата по регулярному выражению Построение детерминированного конечного автомата по недетерминированному Построение детерминированного конечного автомата по регулярному выражению Построение детерминированного конечного автомата с минимальным числом состояний Регулярные множества и их представления Программирование лексического анализа Конструктор лексических анализаторов LEX Синтаксический анализ КС-грамматики и МП-автоматы Преобразования КС-грамматик Предсказывающий разбор сверху-вниз Алгоритм разбора сверху-вниз

4 4 ОГЛАВЛЕНИЕ Функции FIRST и F OLLOW Конструирование таблицы предсказывающего анализатора LL(1)-грамматики Удаление левой рекурсии Левая факторизация Рекурсивный спуск Восстановление после синтаксических ошибок Разбор снизу-вверх типа сдвиг-свертка Основа LR(1)-анализаторы Конструирование LR(1)-таблицы LR(1)-грамматики Восстановление после синтаксических ошибок Варианты LR-анализаторов Элементы теории перевода Преобразователи с магазинной памятью Синтаксически управляемый перевод Схемы синтаксически управляемого перевода Обобщенные схемы синтаксически управляемого перевода Атрибутные грамматики Определение атрибутных грамматик Классы атрибутных грамматик и их реализация Язык описания атрибутных грамматик Проверка контекстных условий Описание областей видимости и блочной структуры Занесение в среду и поиск объектов Организация таблиц символов Таблицы идентификаторов Таблицы расстановки Таблицы расстановки со списками Функции расстановки Таблицы на деревьях Реализация блочной структуры Сравнение методов реализации таблиц Промежуточное представление программы Представление в виде ориентированного графа Трехадресный код Линеаризованные представления Виртуальная машина Java Организация памяти

5 ОГЛАВЛЕНИЕ Набор команд виртуальной машины Организация информации в генераторе кода Уровень промежуточного представления Генерация кода Модельмашины Динамическая организация памяти Организация магазина со статической цепочкой Организация магазина с дисплеем Назначение адресов Трансляция переменных Трансляция целых выражений Трансляция арифметических выражений Трансляция логических выражений Выделение общих подвыражений Генерация оптимального кода методами синтаксического анализа Сопоставление образцов Синтаксический анализ для T-грамматик Выбор дерева вывода наименьшей стоимости Атрибутная схема для алгоритма сопоставления образцов Системы автоматизации построения трансляторов СистемаСУПЕР СистемаYacc

7 Глава 1 Введение 1.1 Место компилятора в программном обеспечении Компиляторы составляют существенную часть программного обеспечения ЭВМ. Это связано с тем, что языки высокого уровня стали основным средством разработки программ. Только очень незначительная часть программного обеспечения, требующая особой эффективности, программируется с помощью ассемблеров. В настоящее время распространено довольно много языков программирования. Наряду с традиционными языками, такими, как Фортран, широкое распространение получили так называемые универсальные языки (Паскаль, Си, Модула-2, Ада и другие), а также некоторые специализированные (например, язык обработки списочных структур Лисп). Кроме того, большое распространение получили языки, связанные с узкими предметными областями, такие, как входные языки пакетов прикладных программ. Для некоторых языков имеется довольно много реализаций. Например, реализаций Паскаля, Модулы-2 или Си для ЭВМ типа IBM PC на рынке десятки. С другой стороны, постоянно растущая потребность в новых компиляторах связана с бурным развитием архитектур ЭВМ. Это развитие идет по различным направлениям. Совершенствуются старые архитектуры как в концептуальном отношении, так и по отдельным, конкретным линиям. Это можно проиллюстрировать на примере микропроцессора Intel- 80X86. Последовательные версии этого микропроцессора 8086, 80186, 80286, 80386, 80486, отличаются не только техническими характеристиками, но и, что более важно, новыми возможностями и, значит, изменением (расширением) системы команд. Естественно, это требует новых компиляторов (или модификации старых). То же можно сказать о микропроцессорах Motorola 68010, 68020, 68030, В рамках традиционных последовательных машин возникает боль- 7

8 8 ГЛАВА 1. ВВЕДЕНИЕ шое число различных направлений архитектур. Примерами могут служить архитектуры CISC, RISC. Такие ведущие фирмы, как Intel, Motorola, Sun, начинают переходить на выпуск машин с RISC-архитектурами. Естественно, для каждой новой системы команд требуется полный набор новых компиляторов с распространенных языков. Наконец, бурно развиваются различные параллельные архитектуры. Среди них отметим векторные, многопроцессорные, с широким командным словом (вариантом которых являются суперскалярные ЭВМ). На рынке уже имеются десятки типов ЭВМ с параллельной архитектурой, начиная от супер-эвм (Cray, CDC и другие), через рабочие станции (например, IBM RS/6000) и кончая персональными (например, на основе микропроцессора I-860). Естественно, для каждой из машин создаются новые компиляторы для многих языков программирования. Здесь необходимо также отметить, что новые архитектуры требуют разработки совершенно новых подходов к созданию компиляторов, так что наряду с собственно разработкой компиляторов ведется и большая научная работа по созданию новых методов трансляции. 1.2 Структура компилятора Обобщенная структура компилятора и основные фазы компиляции показаны на рис На фазе лексического анализа входная программа, представляющая собой поток литер, разбивается на лексемы слова в соответствии с определениями языка. Основными формализмами, лежащим в основе реализации лексических анализаторов, являются конечные автоматы и регулярные выражения. Лексический анализатор может работать в двух основных режимах: либо как подпрограмма, вызываемая синтаксическим анализатором для получения очередной лексемы, либо как полный проход, результатом которого является файл лексем. В процессе выделения лексем лексический анализатор может как самостоятельно строить таблицы объектов (идентификаторов, строк, чисел и т.д.), так и выдавать значения для каждой лексемы при очередном к нему обращении. В этом случае таблицы объектов строятся в последующих фазах (например, в процессе синтаксического анализа). На этапе лексического анализа обнаруживаются некоторые (простейшие) ошибки (недопустимые символы, неправильная запись чисел, идентификаторов и др.). Основная задача синтаксического анализа разбор структуры программы. Как правило, под структурой понимается дерево, соответствующее разбору в контекстно-свободной грамматике языка. В настоящее время чаще всего используется либо LL(1)-анализ (и его вариант рекурсивный спуск), либо LR(1)-анализ и его варианты (LR(0), SLR(1), LALR(1) и другие). Рекурсивный спуск чаще используется при ручном программировании синтаксического анализатора, LR(1) при исполь-

9 1.2. СТРУКТУРА КОМПИЛЯТОРА 9 E_dkbq_kdbc ZgZeba Dhg_qgu_ Z\lhfZlu >bz]ghklbdz Ihlhde_dk_f lz[ebpuh[t_dlh\ KbglZdkbq_kdbc ZgZeba DK]jZffZlbdb >bz]ghklbdz >_j_\hjza[hjz lz[ebpuh[t_dlh\ Dhgl_dklguc ZgZeba :ljb[mlgu_ ]jzffzlbdb >bz]ghklbdz :ljb[mlbjh\zggh_^_j_\h lz[ebpuh[t_dlh\ =_g_jzpby ijhf_`mlhqgh]h ij_^klz\e_gby KMljZgkeypby Ijhf_`mlhqgZynhjfZ ij_nbdkgzyihkl nbdkgzyljhcdbb ^j HilbfbaZpby Ihlhdh\uc ZgZeba Ijhf_`mlhqgZynhjfZ hjb_glbjh\zgguc]jzn =_g_jzpbydh^z LZ[ebpuj_r_gbc ^bgzfbq_kdh_ ijh]jzffbjh\zgb_ H[t_dlgucfh^mev Рис. 1.1:

10 10 ГЛАВА 1. ВВЕДЕНИЕ зовании систем автоматического построения синтаксических анализаторов. Результатом синтаксического анализа является синтаксическое дерево со ссылками на таблицы объектов. В процессе синтаксического анализа также обнаруживаются ошибки, связанные со структурой программы. На этапе контекстного анализа выявляются зависимости между частями программы, которые не могут быть описаны контекстно-свободным синтаксисом. Это в основном связи описание-использование, в частности, анализ типов объектов, анализ областей видимости, соответствие параметров, метки и другие. В процессе контекстного анализа таблицы объектов пополняются информацией об описаниях (свойствах) объектов. Основным формализмом, использующимся при контекстном анализе, является аппарат атрибутных грамматик. Результатом контекстного анализа является атрибутированное дерево программы. Информация об объектах может быть как рассредоточена в самом дереве, так и сосредоточена в отдельных таблицах объектов. В процессе контекстного анализа также могут быть обнаружены ошибки, связанные с неправильным использованием объектов. Затем программа может быть переведена во внутреннее представление. Это делается для целей оптимизации и/или удобства генерации кода. Еще одной целью преобразования программы во внутреннее представление является желание иметь переносимый компилятор. Тогда только последняя фаза (генерация кода) является машинно-зависимой. В качестве внутреннего представления может использоваться префиксная или постфиксная запись, ориентированный граф, тройки, четверки и другие. Фаз оптимизации может быть несколько. Оптимизации обычно делят на машинно-зависимые и машинно-независимые, локальные и глобальные. Часть машинно-зависимой оптимизации выполняется на фазе генерации кода. Глобальная оптимизация пытается принять во внимание структуру всей программы, локальная только небольших ее фрагментов. Глобальная оптимизация основывается на глобальном потоковом анализе, который выполняется на графе программы и представляет по существу преобразование этого графа. При этом могут учитываться такие свойства программы, как межпроцедурный анализ, межмодульный анализ, анализ областей жизни переменных и т.д. Наконец, генерация кода последняя фаза трансляции. Результатом ее является либо ассемблерный модуль, либо объектный (или загрузочный) модуль. В процессе генерации кода могут выполняться некоторые локальные оптимизации, такие как распределение регистров, выбор длинных или коротких переходов, учет стоимости команд при выборе конкретной последовательности команд. Для генерации кода разработаны различные методы, такие как таблицы решений, сопоставление образцов, включающее динамическое программирование, различ-

11 1.2. СТРУКТУРА КОМПИЛЯТОРА 11 ные синтаксические методы. Конечно, те или иные фазы транслятора могут либо отсутствовать совсем, либо объединяться. В простейшем случае однопроходного транслятора нет явной фазы генерации промежуточного представления и оптимизации, остальные фазы объединены в одну, причем нет и явно построенного синтаксического дерева.

12 12 ГЛАВА 1. ВВЕДЕНИЕ

13 Глава 2 Языки и их представление 2.1 Алфавиты, цепочки и языки Алфавит, или словарь это конечное множество символов. Для обозначения символов мы будем пользоваться цифрами, латинскими буквами и специальными литерами типа #, $. Пусть V алфавит. Цепочка в алфавите V это любая строка конечной длины, составленная из символов алфавита V. Синонимом цепочки являются предложение, строка и слово. Пустая цепочка (обозначается e) это цепочка, в которую не входит ни один символ. Конкатенацией цепочек x и y называется цепочка xy. Заметим, что xe = ex = x для любой цепочки x. Пусть x, y, z произвольные цепочки в некотором алфавите. Цепочка y называется подцепочкой цепочки xyz. Цепочки x и y называются, соответственно, префиксом и суффиксом цепочки xy. Заметим, что любой префикс или суффикс цепочки является подцепочкой этой цепочки. Кроме того, пустая цепочка является префиксом, суффиксом и подцепочкой для любой цепочки. Пример 2.1. Для цепочки abbba префиксом является любая цепочка из множества L 1 = , суффиксом является любая цепочка из множества L 2 = , подцепочкой является любая цепочка из множества L 1 L 2. Длиной цепочки w (обозначается w ) называется число символов в ней. Например, abababa =7, а e =0. Язык в алфавите V это некоторое множество цепочек в алфавите V. Пример 2.2. Пусть дан алфавит V = . Вот некоторые языки в алфавите V : а) L 1 = пустой язык; 13

14 14 ГЛАВА 2. ЯЗЫКИ И ИХ ПРЕДСТАВЛЕНИЕ б) L 2 = язык, содержащий только пустую цепочку (заметим, что L 1 и L 2 различные языки); в) L 3 = язык, содержащий цепочки из a и b, длина которых не превосходит 2; г) L 4 язык, включающий всевозможные цепочки из a и b, содержащие четное число a и четное число b; д) L 5 = 0> язык цепочек из a, длины которых представляют собой квадраты натуральных чисел. Два последних языка содержат бесконечное число цепочек. Введем обозначение V для множества всех цепочек в алфавите V, включая пустую цепочку. Каждый язык в алфавите V является подмножеством V. Для обозначения множества всех цепочек в алфавите V, кроме пустой цепочки, будем использовать V +. Пример 2.3. Пусть V = <0, 1>. Тогда V = , V + = <0, 1, 00, 01, 10, 11, 000. >. Введем некоторые операции над языками. Пусть L 1 и L 2 языки в алфавите V. Конкатенацией языков L 1 и L 2 называется язык L 1 L 2 = . Пусть L язык в алфавите V. Итерацией языка L называется язык L, определяемый следующим образом: (1) L 0 = ; (2) L n = LL n 1, n 1; (3) L = n=0 L n. Пример 2.4. Пусть L 1 = и L 2 = . Тогда L 1L 2 = ,и L 1 = . Большинство языков, представляющих интерес, содержат бесконечное число цепочек. При этом возникают три важных вопроса. Во-первых, как представить язык (т.е. специфицировать входящие в него цепочки)? Если язык содержит только конечное множество цепочек, ответ прост. Можно просто перечислить его цепочки. Если язык бесконечен, необходимо найти для него конечное представление. Это конечное представление, в свою очередь, будет строкой символов над некоторым алфавитом вместе с некоторой интерпретацией, связывающей это представление с языком.

15 2.2. ПРЕДСТАВЛЕНИЕ ЯЗЫКОВ 15 Во-вторых, для любого ли языка существует конечное представление? Можно предположить, что ответ отрицателен. Мы увидим, что множество всех цепочек над алфавитом счетно. Язык это любое подмножество цепочек. Из теории множеств известно, что множество всех подмножеств счетного множества несчетно. Хотя мы и не дали строгого определения того, что является конечным представлением, интуитивно ясно, что любое разумное определение конечного представления ведет только к счетному множеству конечных представлений, поскольку нужно иметь возможность записать такое конечное представление в виде строки символов конечной длины. Поэтому языков значительно больше, чем конечных представлений. В-третьих, можно спросить, какова структура тех классов языков, для которых существует конечное представление? 2.2 Представление языков Процедура это конечная последовательность инструкций, которые могут быть механически выполнены. Примером может служить машинная программа. Процедура, которая всегда заканчивается, называется алгоритмом. Один из способов представления языка дать алгоритм, определяющий, принадлежит ли цепочка языку. Более общий способ состоит в том, чтобы дать процедуру, которая останавливается с ответом да для цепочек, принадлежащих языку, и либо останавливается с ответом нет, либо вообще не останавливается для цепочек, не принадлежащих языку. Говорят, что такая процедура или алгоритм распознает язык. Такой метод представляет язык с точки зрения распознавания. Язык можно также представить методом порождения. А именно, можно дать процедуру, которая систематически порождает в определенном порядке цепочки языка. Если мы можем распознать цепочки языка над алфавитом V либо с помощью процедуры, либо с помощью алгоритма, то мы можем и генерировать язык, поскольку мы можем систематически генерировать все цепочки из V, проверять каждую цепочку на принадлежность языку и выдавать список только цепочек языка. Но если процедура не всегда заканчивается при проверке цепочки, мы не сдвинемся дальше первой цепочки, на которой процедура не заканчивается. Эту проблему можно обойти, организовав проверку таким образом, чтобы процедура никогда не продолжала проверять одну цепочку бесконечно. Для этого введем следующую конструкцию. Предположим, что V имеет p символов. Мы можем рассматривать цепочки из V как числа, представленные в базисе p, плюс пустая цепочка e. Можно занумеровать цепочки в порядке возрастания длины и в числовом порядке для цепочек одинаковой длины. Такая нумерация для цепочек языка приведена на рис. 2.1, а.

16 16 ГЛАВА 2. ЯЗЫКИ И ИХ ПРЕДСТАВЛЕНИЕ Пусть P процедура для проверки принадлежности цепочки языку L. Предположим, что P может быть представлена дискретными шагами, так что имеет смысл говорить об i-ом шаге процедуры для любой данной цепочки. Прежде чем дать процедуру перечисления цепочек языка L, дадим процедуру нумерации пар положительных чисел. Все упорядоченные пары положительных чисел (x, y) можно отобразить на множество положительных чисел следующей формулой: z =(x + y 1)(x + y 2)/2+y Пары целых положительных чисел можно упорядочить в соответствии со значением z (рис. 2.1, б). 1 e 2 a 3 b 4 c 5 aa 6 ab 7 ac 8 ba 9 bb а y x z(x, y) б Рис. 2.1: Теперь можно дать процедуру перечисления цепочек L. Нумеруем упорядоченные пары целых положительных чисел (1,1), (2,1), (1,2), (3,1), (2,2). При нумерации пары (i, j) генерируем i-ю цепочку из V и применяем к цепочке первые j шагов процедуры P. Как только мы определили, что сгенерированная цепочка принадлежит L, добавляем цепочку к списку элементов L. Если цепочка i принадлежит L, это будет определено P за j шагов для некоторого конечного j. При перечислении (i, j) будет сгенерирована цепочку с номером i. Легко видеть, что эта процедура перечисляет все цепочки L. Если мы имеем процедуру генерации цепочек языка, то мы всегда можем построить процедуру распознавания предложений языка, но не всегда алгоритм. Для определения того, принадлежит ли x языку L, просто нумеруем предложения L и сравниваем x с каждым предложением. Если сгенерировано x, процедура останавливается, распознав, что x принадлежит L. Конечно, если x не принадлежит L, процедура никогда не закончится. Язык, предложения которого могут быть сгенерированы процедурой, называется рекурсивно перечислимым. Язык рекурсивно перечислим, если имеется процедура, распознающая предложения языка. Говорят,

17 2.3. ГРАММАТИКИ 17 что язык рекурсивен, если существует алгоритм для распознавания языка. Класс рекурсивных языков является собственным подмножеством класса рекурсивно перечислимых языков. Мало того, существуют языки, не являющиеся даже рекурсивно перечислимыми. 2.3 Грамматики Формальное определение грамматики Для нас наибольший интерес представляет одна из систем генерации языков грамматики. Понятие грамматики изначально было формализовано лингвистами при изучении естественных языков. Предполагалось, что это может помочь при их автоматической трансляции. Однако, наилучшие результаты в этом направлении достигнуты при описании не естественных языков, а языков программирования. Примером может служить способ описания синтаксиса языков программирования при помощи БНФ формы Бэкуса-Наура. Определение. Грамматика это четверка G =(N,T,P,S), где (1) N алфавит нетерминальных символов; (2) T алфавит терминальных символов, N T = ; (3) P конечное множество правил вида α β, где α (N T ) +, β (N T ) ; (4) S N начальный символ (или аксиома) грамматики. Мы будем использовать большие латинские буквы для обозначения нетерминальных символов, малые латинские буквы из начала алфавита для обозначения терминальных символов, малые латинские буквы из конца алфавита для обозначения цепочек из T и, наконец, малые греческие буквы для обозначения цепочек из (N T ). Будем использовать также сокращенную запись A α 1 α 2. α n для обозначения группы правил A α 1,A α 2. A α n. Определим на множестве (N T ) бинарное отношение выводимости следующим образом: если δ γ P,тоαδβ αγβ для всех α, β (N T ). Если α 1 α 2, то говорят, что цепочка α 2 непосредственно выводима из α 1. Мы будем использовать также рефлексивно-транзитивное и транзитивное замыкания отношения, а также его степень k 0 (обозначаемые соответственно, + и k ). Если α 1 α 2 (α 1 + α 2, α 1 k α 2 ), то говорят, что цепочка α 2 выводима (нетривиально выводима, выводима за k шагов)изα 1. Если α k β (k 0), то существует последовательность шагов γ 0 γ 1 γ 2. γ k 1 γ k

18 18 ГЛАВА 2. ЯЗЫКИ И ИХ ПРЕДСТАВЛЕНИЕ где α = γ 0 и β = γ k. Последовательность цепочек γ 0,γ 1,γ 2. γ k в этом случае называют выводом β из α. Сентенциальной формой грамматики G называется цепочка, выводимая из ее начального символа. Языком, порождаемым грамматикой G (обозначается L(G)), называется множество всех ее терминальных сентенциальных форм, т.е. L(G) = Грамматики G 1 и G 2 называются эквивалентными, если они порождают один и тот же язык, т.е. L(G 1 )=L(G 2 ). Пример 2.5. Грамматика G =(, , P, S), где P = , порождает язык L(G) =0>. Действительно, применяем n 1 раз правило 1 и получаем a n 1 S(BC) n 1, затем один раз правило 2 и получаем a n (BC) n, затем n(n 1)/2 раз правило 3 и получаем a n B n C n. Затем используем правило 4 и получаем a n bb n 1 C n. Затем применяем n 1 раз правило 5 и получаем a n b n C n. Затем применяем правило 6 и n 1 раз правило 7 и получаем a n b n c n. Можно показать, что язык L(G) состоит из цепочек только такого вида. Пример 2.6. Рассмотрим грамматику G =(, <0, 1>, , S). Легко видеть, что цепочка L(G), так как существует вывод S 0S1 00S Нетрудно показать, что грамматика порождает язык L(G) =<0 n 1>0>. Пример 2.7. Рассмотрим грамматику G = (, <0, 1>, ,S). Нетрудно показать, что грамматика порождает язык L(G) = <0 n 1 m n,>0> Типы грамматик и их свойства Рассмотрим классификацию грамматик (предложенную Н.Хомским), основанную на виде их правил. Определение. Пусть дана грамматика G =(N,T,P,S). Тогда (1) если правила грамматики не удовлетворяют никаким ограничениям, то ее называют грамматикой типа 0, или грамматикой без ограничений. (2) если а) каждое правило грамматики, кроме S e, имеет вид α β, где α β,и

19 2.3. ГРАММАТИКИ 19 б) в том случае, когда S e P, символ S не встречается в правых частях правил, то грамматику называют грамматикой типа 1, или неукорачивающей. (3) если каждое правило грамматики имеет вид A β, где A N, β (N T ), то ее называют грамматикой типа 2, или контекстносвободной (КС-грамматикой). (4) если каждое правило грамматики имеет вид либо A xb, либо A x, где A, B N, x T то ее называют грамматикой типа 3, или праволинейной. Легко видеть, что грамматика в примере 2.5 неукорачивающая, в примере 2.6 контекстно-свободная, в примере 2.7 праволинейная. Язык, порождаемый грамматикой типа i, называют языком типа i. Язык типа 0 называют также языком без ограничений, язык типа 1 контекстно-зависимым (КЗ), язык типа 2 контекстно-свободным (КС), язык типа 3 праволинейным. Теорема 2.1. Каждый контекстно-свободный язык может быть порожден неукорачивающей грамматикой. Доказательство. Пусть L контекстно-свободный язык. Тогда существует контекстно-свободная грамматика G = (N,T,P,S), порождающая L. Построим новую грамматику G =(N,T,P,S ) следующим образом: 1. Если в P есть правило вида A α 0 B 1 α 1. B k α k, где k 0, B i + e для 1 i k, и ни из одной цепочки α j (0 j k) не выводится e, то включить в P все правила (кроме A e) вида A α 0 X 1 α 1. X k α k где X i это либо B i, либо e. 2. Если S + e, то включить в P правила S S, S e и положить N = N . В противном случае положить N = N и S = S. Легко видеть, что G неукорачивающая грамматика. Можно показать по индукции, что L(G )=L(G). Пусть K i класс всех языков типа i. Доказано, что справедливо следующее (строгое) включение: K 3 K 2 K 1 K 0. Заметим, что если язык порождается некоторой грамматикой, это не означает, что он не может быть порожден грамматикой с более сильными ограничениями на правила. Приводимый ниже пример иллюстрирует этот факт.

20 20 ГЛАВА 2. ЯЗЫКИ И ИХ ПРЕДСТАВЛЕНИЕ Пример 2.8. Рассмотрим грамматику G = (, <0, 1>, , S). Эта грамматика является контекстносвободной. Легко показать, что L(G) = <0 n 1 m n,>0>. Однако, в примере 2.7 приведена праволинейная грамматика, порождающая тот же язык. Покажем что существует алгоритм, позволяющий для произвольного КЗ-языка L в алфавите T, и произвольной цепочки w T определить, принадлежит ли w языку L. Теорема 2.2. Каждый контекстно-зависимый язык является рекурсивным языком. Доказательство. Пусть L контекстно-зависимый язык. Тогда существует некоторая неукорачивающая грамматика G =(N, T, P, S), порождающая L. Пусть w T и w = n. Если n =0, т.е. w = e, то принадлежность w L проверяется тривиальным образом. Так что будем предполагать, что n>0. Определим множество T m как множество строк u (N T ) + длины не более n таких, что вывод S u имеет не более m шагов. Ясно, что T 0 = . Легко показать, что T m можно получить из T m 1 просматривая, какие строки с длиной, меньшей или равной n можно вывести из строк из T m 1 применением одного правила, т.е. T m = T m 1 . Если S u и u n, тоu T m для некоторого m. Если из S не выводится u или u >n,тоuне принадлежит T m ни для какого m. Очевидно, что T m T m 1 для всех m 1. Поскольку T m зависит только от T m 1, если T m = T m 1,тоT m = T m+1 = T m+2 =. Процедура будет вычислять T 1, T 2, T 3. пока для некоторого m не окажется T m = T m 1. Если w не принадлежит T m, то не принадлежит и L(G), поскольку для j>mвыполнено T j = T m. Если w T m,тоs w. Покажем, что существует такое m, что T m = T m 1. Поскольку для каждого i 1 справедливо T i T i 1, то если T i T i 1, то число элементов в T i по крайней мере на 1 больше, чем в T i 1. Пусть N T = k. Тогда число строк в (N T ) + длины меньшей или равной n равно k + k k n nk n. Только эти строки могут быть в любом T i. Значит, T m = T m 1 для некоторого m nk n. Таким образом, процедура, вычисляющая T i для всех i 1 до тех пор, пока не будут найдены два равных множества, гарантированно заканчивается, значит, это алгоритм.

21 Глава 3 Лексический анализ Основная задача лексического анализа разбить входной текст, состоящий из последовательности одиночных символов, на последовательность слов, или лексем, т.е. выделить эти слова из непрерывной последовательности символов. Все символы входной последовательности с этой точки зрения разделяются на символы, принадлежащие каким-либо лексемам, и символы, разделяющие лексемы (разделители). В некоторых случаях между лексемами может и не быть разделителей. С другой стороны, в некоторых языках лексемы могут содержать незначащие символы (например, символ пробела в Фортране). В Си разделительное значение символов-разделителей может блокироваться ( \ в конце строки внутри «. «). Обычно все лексемы делятся на классы. Примерами таких классов являются числа (целые, восьмеричные, шестнадцатиричные, действительные и т.д.), идентификаторы, строки. Отдельно выделяются ключевые слова и символы пунктуации (иногда их называют символы-ограничители). Как правило, ключевые слова это некоторое конечное подмножество идентификаторов. В некоторых языках (например, ПЛ/1) смысл лексемы может зависеть от ее контекста и невозможно провести лексический анализ в отрыве от синтаксического. С точки зрения дальнейших фаз анализа лексический анализатор выдает информацию двух сортов: для синтаксического анализатора, работающего вслед за лексическим, существенна информация о последовательности классов лексем, ограничителей и ключевых слов, а для контекстного анализа, работающего вслед за синтаксическим, важна информация о конкретных значениях отдельных лексем (идентификаторов, чисел и т.д.). Таким образом, общая схема работы лексического анализатора такова. Сначала выделяется отдельная лексема (возможно, используя символыразделители). Ключевые слова распознаются либо явным выделением непосредственно из текста, либо сначала выделяется идентификатор, а затем делается проверка на принадлежность его множеству ключевых 21

22 22 ГЛАВА 3. ЛЕКСИЧЕСКИЙ АНАЛИЗ слов. Если выделенная лексема является ограничителем, то он (точнее, некоторый его признак) выдается как результат лексического анализа. Если выделенная лексема является ключевым словом, то выдается признак соответствующего ключевого слова. Если выделенная лексема является идентификатором выдается признак идентификатора, а сам идентификатор сохраняется отдельно. Наконец, если выделенная лексема принадлежит какому-либо из других классов лексем (например, лексема представляет собой число, строку и т.д.), то выдается признак соответствующего класса, а значение лексемы сохраняется отдельно. Лексический анализатор может быть как самостоятельной фазой трансляции, так и подпрограммой, работающей по принципу дай лексему. В первом случае (рис. 3.1, а) выходом анализатора является файл лексем, во втором (рис. 3.1, б) лексема выдается при каждом обращении к анализатору (при этом, как правило, признак класса лексемы возвращается как результат функции лексический анализатор, а значение лексемы передается через глобальную переменную). С точки зрения обработки значений лексем, анализатор может либо просто выдавать значение каждой лексемы, и в этом случае построение таблиц объектов (идентификаторов, строк, чисел и т.д.) переносится на более поздние фазы, либо он может самостоятельно строить таблицы объектов. В этом случае в качестве значения лексемы выдается указатель на вход в соответствующую таблицу. LbiAgZq_gb_ KbglZgZebaZlhj Lbi e_dk_fu AgZq_gb_ LZ[ebpZ E_dkZgZebaZlhj Z [ Рис. 3.1: Работа лексического анализатора задается некоторым конечным автоматом. Однако, непосредственное описание конечного автомата неудобно с практической точки зрения. Поэтому для задания лексического анализатора, как правило, используется либо регулярное выражение, либо праволинейная грамматика. Все три формализма (конечных автоматов,

24 24 ГЛАВА 3. ЛЕКСИЧЕСКИЙ АНАЛИЗ (б) (pq) регулярное выражение, обозначающее регулярное множество PQ, (в) (p ) регулярное выражение, обозначающее регулярное множество P ; (5) ничто другое не является регулярным выражением в алфавите T. Мы будем опускать лишние скобки в регулярных выражениях, договорившись о том, что операция итерации имеет наивысший приоритет, затем идет операции конкатенации, наконец, операция объединения имеет наименьший приоритет. Кроме того, мы будем пользоваться записью p + для обозначения pp. Таким образом, запись (a ((ba)(a ))) эквивалентна a ba +. Наконец, мы будем использовать запись L(r) для регулярного множества, обозначаемого регулярным выражением r. Пример 3.1. Несколько примеров регулярных выражений и обозначаемых ими регулярных множеств: а) a(e a) b обозначает множество ; б) a(a b) обозначает множество всевозможных цепочек, состоящих из a и b, начинающихся с a; в) (a b) (a b)(a b) обозначает множество всех непустых цепочек, состоящих из a и b, т.е. множество + ; г) ((0 1)(0 1)(0 1)) обозначает множество всех цепочек, состоящих из нулей и единиц, длины которых делятся на 3. Ясно, что для каждого регулярного множества можно найти регулярное выражение, обозначающее это множество, и наоборот. Более того, для каждого регулярного множества существует бесконечно много обозначающих его регулярных выражений. Будем говорить, что регулярные выражения равны или эквивалентны (=), если они обозначают одно и то же регулярное множество. Существует ряд алгебраических законов, позволяющих осуществлять эквивалентное преобразование регулярных выражений. Лемма. Пусть p, q и r регулярные выражения. Тогда справедливы следующие соотношения: (1) p q = q p; (7) pe = ep = p; (2) = e; (8) p = p = ; (3) p (q r) =(p q) r; (9) p = p p ; (4) p(qr) =(pq)r; (10) (p ) = p ; (5) p(q r) = pq pr; (11) p p = p; (6) (p q)r = pr qr; (12) p = p. Следствие. Для любого регулярного выражения существует эквивалентное регулярное выражение, которое либо есть, либо не содержит в своей записи.

25 3.2. КОНЕЧНЫЕ АВТОМАТЫ 25 В дальнейшем будем рассматривать только регулярные выражения, не содержащие в своей записи. При практическом описании лексических структур бывает полезно сопоставлять регулярным выражениям некоторые имена, и ссылаться на них по этим именам. Для определения таких имен мы будем использовать запись вида d 1 = r 1 d 2 = r 2. d n = r n где d i различные имена, а каждое r i регулярное выражение над символами T , т.е. символами основного алфавита и ранее определенными символами (именами). Таким образом, для любого r i можно построить регулярное выражение над T, повторно заменяя имена регулярных выражений на обозначаемые ими регулярные выражения. Пример 3.2. Использование имен для регулярных выражений. а) Регулярное выражение для множества идентификаторов. Letter = a b c. x y z Digit = >

26 26 ГЛАВА 3. ЛЕКСИЧЕСКИЙ АНАЛИЗ (5) F Q множество заключительных состояний. Работа конечного автомата представляет собой некоторую последовательность шагов, или тактов. Такт определяется текущим состоянием управляющего устройства и входным символом, обозреваемым в данный момент входной головкой. Сам шаг состоит из изменения состояния и, возможно, сдвига входной головки на одну ячейку вправо (рис. 3.2). Khklhygb_ IjhqblZggZyqZklv \oh^ghcp_ihqdb D L_dmsbc \oh^ghc kbf\he G_ijhqblZggZyqZklv \oh^ghcp_ihqdb Рис. 3.2: Недетерминизм автомата заключается в том, что, во-первых, находясь в некотором состоянии и обозревая текущий символ, автомат может перейти в одно из, вообще говоря, нескольких возможных состояний, и во-вторых, автомат может делать переходы по e. Пусть M = (Q,T,D,q 0,F) НКА. Конфигурацией автомата M называется пара (q, w) Q T, где q текущее состояние управляющего устройства, а w цепочка символов на входной ленте, состоящая из символа под головкой и всех символов справа от него. Конфигурация (q 0,w) называется начальной, а конфигурация (q, e), где q F заключительной (или допускающей). Пусть M =(Q,T,D,q 0,F) НКА. Тактом автомата M называется бинарное отношение, определенное на конфигурациях M следующим образом: если p D(q, a), где a T , то(q, aw) (p, w) для всех w T. Будем обозначать символом + ( ) транзитивное (рефлексивнотранзитивное) замыкание отношения. Говорят, что автомат M допускает цепочку w, если (q 0,w) (q, e) для некоторого q F. Языком, допускаемым (распознаваемым, определяемым) автоматом M, (обозначается L(M)), называется множество входных цепочек, допускаемых автоматом M. Т.е. L(M) =.

27 3.2. КОНЕЧНЫЕ АВТОМАТЫ 27 Важным частным случаем недетерминированного конечного автомата является детерминированный конечный автомат, который на каждом такте работы имеет возможность перейти не более чем в одно состояние и не может делать переходы по e. Пусть M =(Q,T,D,q 0,F) НКА. Будем называть M детерминированным конечным автоматом (ДКА), если выполнены следующие два условия: (1) D(q, e) = для любого q Q,и (2) D(q, a) содержит не более одного элемента для любых q Q и a T. Так как функция переходов ДКА содержит не более одного элемента для любой пары аргументов, для ДКА мы будем пользоваться записью D(q, a) =p вместо D(q, a) =

. Конечный автомат может быть изображен графически в виде диаграммы, представляющей собой ориентированный граф, в котором каждому состоянию соответствует вершина, а дуга, помеченная символом a T , соединяет две вершины p и q, если p D(q, a). На диаграмме выделяются начальное и заключительные состояния (в примерах ниже, соответственно, входящей стрелкой и двойным контуром). Пример 3.3. Пусть L = L(r), где r =(a b) a(a b)(a b). а) Недетерминированный конечный автомат M, допускающий язык L: M = <<1, 2, 3, 4>, ,d,1, <4>>, где функция переходов D определяется так: D(1,a)=<1, 2>, D(3,a)=<4>, D(2,a)=<3>, D(3,b)=<4>, D(2,b)=<3>. Диаграмма автомата приведена на рис. 3.3, а. б) Детерминированный конечный автомат M, допускающий язык L: M = <<1, 2, 3, 4, 5, 6, 7, 8>, ,d,1, <3, 5, 6, 8>>, где функция переходов D определяется так: D(1,a)=2, D(5,a)=8, D(1,b)=1, D(5,b)=6, D(2,a)=4, D(6,a)=2, D(2,b)=7, D(6,b)=1, D(3,a)=3, D(7,a)=8, D(3,b)=5, D(7,b)=6, D(4,a)=3, D(8,a)=4, D(4,b)=5, D(8,b)=7. Диаграмма автомата приведена на рис. 3.3, б. Пример 3.4. Диаграмма ДКА, допускающего множество чисел в десятичной записи, приведена на рис. 3.4.

28 28 ГЛАВА 3. ЛЕКСИЧЕСКИЙ АНАЛИЗ E D D DE E DE D E E D D D D E E E D E D D E Z [ Рис. 3.3: Пример 3.5. Анализ цепочек. а) При анализе цепочки w = ababa автомат из примера 3.3, а, может сделать следующую последовательность тактов: (1, ababa) (1, baba) (1, aba) (2,ba) (3,a) (4,e). Состояние 4 является заключительным, следовательно, цепочка w допускается этим автоматом. б) При анализе цепочки w = ababab автомат из примера 3.3, б, должен сделать следующую последовательность тактов: (1, ababab) (2, babab) (7, abab) (8, bab) (7,ab) (8,b) (7,e). Так как состояние 7 не является заключительным, цепочка w не допускается этим автоматом. ( ‘LJLW ‘LJLW ‘LJLW ( ‘LJLW ‘LJLW ‘LJLW ‘LJLW Рис. 3.4:

29 3.3. АЛГОРИТМЫ ПОСТРОЕНИЯ КОНЕЧНЫХ АВТОМАТОВ Алгоритмы построения конечных автоматов Построение недетерминированного конечного автомата по регулярному выражению Рассмотрим алгоритм построения по регулярному выражению недетерминированного конечного автомата, допускающего тот же язык. Алгоритм 3.1. Построение недетерминированного конечного автомата по регулярному выражению. Вход. Регулярное выражение r в алфавите T. Выход. НКА M, такой что L(M) =L(r). Метод. Автомат для выражения строится композицией из автоматов, соответствующих подвыражениям. На каждом шаге построения строящийся автомат имеет в точности одно заключительное состояние, в начальное состояние нет переходов из других состояний и нет переходов из заключительного состояния в другие. 1. Для выражения e строится автомат L H I Рис. 3.5: 2. Для выражения a (a T ) строится автомат L D I Рис. 3.6: 3. Пусть M(s) и M(t) НКА для регулярных выражений s и t соответственно. а) Для выражения s t автомат M(s t) строится как показано на рис Здесь i новое начальное состояние и f новое заключительное состояние. Заметим, что имеет место переход по e из i в начальные состояния M(s) и M(t) и переход по e из заключительных состояний M(s) и M(t) в f. Начальное и заключительное состояния автоматов M(s) и M(t) не являются таковыми для автомата M(s t).

30 30 ГЛАВА 3. ЛЕКСИЧЕСКИЙ АНАЛИЗ H 0V H L I H 0W H Рис. 3.7: б) Для выражения st автомат M(st) строится следующим образом: L 0V 0W I Рис. 3.8: Начальное состояние M(s) становится начальным для нового автомата, а заключительное состояние M(t) становится заключительным для нового автомата. Начальное состояние M(t) и заключительное состояние M(s) сливаются, т.е. все переходы из начального состояния M(t) становятся переходами из заключительного состояния M(s). В новом автомате это объединенное состояние не является ни начальным, ни заключительным. в) Для выражения s автомат M(s ) строится следующим образом: L H H 0V H I H Рис. 3.9:

31 3.3. АЛГОРИТМЫ ПОСТРОЕНИЯ КОНЕЧНЫХ АВТОМАТОВ 31 Здесь i новое начальное состояние, а f новое заключительное состояние Построение детерминированного конечного автомата по недетерминированному Рассмотрим алгоритм построения по недетерминированному конечному автомату детерминированного конечного автомата, допускающего тот же язык. Алгоритм 3.2. Построение детерминированного конечного автомата по недетерминированному. Вход. НКА M =(Q,T,D,q 0,F). Выход. ДКА M =(Q,T,D,q 0,F ), такой что L(M) =L(M ). Метод. Каждое состояние результирующего ДКА это некоторое множество состояний исходного НКА. В алгоритме будут использоваться следующие функции: e-closure(r) (R Q) множество состояний НКА, достижимых из состояний, входящих в R, посредством только переходов по e, т.е. множество S =

q R move(r, a) (R Q) множество состояний НКА, в которые есть переход на входе a для состояний из R, т.е. множество S =

q R Вначале Q и D пусты. Выполнить шаги 1-4: (1) Определить q 0 = e-closure(). (2) Добавить q 0 в Q как непомеченное состояние. (3) Выполнить следующую процедуру: while (в Q есть непомеченное состояние R)< пометить R; for (каждого входного символа a T )< S = e-closure(move(r, a)); if (S )< if (S / Q ) добавить S в Q как непомеченное состояние; определить D (R, a) =S;

32 32 ГЛАВА 3. ЛЕКСИЧЕСКИЙ АНАЛИЗ > > > (4) Определить F = . Пример 3.6. Результат применения алгоритма 3.2 приведен на рис H H H D H H D E E H E H H D $ D % E D & D E D E ‘ E ( E Рис. 3.10: Построение детерминированного конечного автомата по регулярному выражению Приведем теперь алгоритм построения по регулярному выражению детерминированного конечного автомата, допускающего тот же язык [10]. Пусть дано регулярное выражение r в алфавите T. К регулярному выражению r добавим маркер конца: (r)#. Такое регулярное выражение будем называть пополненным. В процессе своей работы алгоритм будет использовать пополненное регулярное выражение.

33 3.3. АЛГОРИТМЫ ПОСТРОЕНИЯ КОНЕЧНЫХ АВТОМАТОВ 33 Алгоритм будет оперировать с синтаксическим деревом для пополненного регулярного выражения (r)#, каждый лист которого помечен символом a T , а каждая внутренняя вершина помечена знаком одной из операций: (конкатенация), (объединение), (итерация). Каждому листу дерева (кроме e-листьев) припишем уникальный номер, называемый позицией, и будем использовать его, с одной стороны, для ссылки на лист в дереве, и, с другой стороны, для ссылки на символ, соответствующий этому листу. Заметим, что если некоторый символ используется в регулярном выражении несколько раз, он имеет несколько позиций. Теперь, обходя дерево T снизу-вверх слева-направо, вычислим четыре функции: nullable, f irstpos, lastpos и f ollowpos. Функции nullable, firstpos и lastpos определены на узлах дерева, а followpos на множестве позиций. Значением всех функций, кроме nullable, является множество позиций. Функция f ollowpos вычисляется через три остальные функции. Функция f irstpos(n) для каждого узла n синтаксического дерева регулярного выражения дает множество позиций, которые соответствуют первым символам в подцепочках, генерируемых подвыражением с вершиной в n. Аналогично, lastpos(n) дает множество позиций, которым соответствуют последние символы в подцепочках, генерируемых подвыражениями с вершиной n. Для узла n, поддеревья которого (т.е. деревья, у которых узел n является корнем) могут породить пустое слово, определим nullable(n) =true, а для остальных узлов nullable(n)=f alse. Таблица для вычисления функций nullable, f irstpos и lastpos приведена на рис узел n nullable(n) firstpos(n) lastpos(n) лист e true лист i false (не e) nullable(u) /\ or f irstpos(u) f irstpos(v) lastpos(u) lastpos(v) uv nullable(v) nullable(u) if nullable(u) then if nullable(v) then /\ and f irstpos(u) f irstpos(v) lastpos(u) lastpos(v) u v nullable(v) else f irstpos(u) else lastpos(v) true f irstpos(v) lastpos(v) v Рис. 3.11: Пример 3.7. Синтаксическое дерево для пополненного регулярного выражения (a b) abb# с результатом вычисления функций firstpos и lastpos приведено

34 34 ГЛАВА 3. ЛЕКСИЧЕСКИЙ АНАЛИЗ ^` ^` ^` ^` ^` ^` ^` ^` ^`E ^` ^` ^` ^`E ^` ^`^` ^`D ^` ^` _ ^` ^`D ^` ^`E ^` Рис. 3.12: позиция f ollowpos 1 <1, 2, 3>2 <1, 2, 3>3 <4>4 <5>5 <6>6 Рис. 3.13: на рис Слева от каждого узла расположено значение firstpos, справа от узла значение lastpos. Заметим, что эти функции могут быть вычислены за один обход дерева. Если i позиция, то followpos(i) есть множество позиций j таких, что существует некоторая строка. cd. входящая в язык, описываемый регулярным выражением, такая, что позиция i соответствует этому вхождению c, а позиция j вхождению d. Функция f ollowpos может быть вычислена также за один обход дерева снизу-вверх по следующим двум правилам. 1. Пусть n внутренний узел с операцией (конкатенация), u и v его потомки. Тогда для каждой позиции i, входящей в lastpos(u), добавляем к множеству значений f ollowpos(i) множество f irstpos(v). 2. Пусть n внутренний узел с операцией (итерация), u его потомок. Тогда для каждой позиции i, входящей в lastpos(u), добавляем к множеству значений f ollowpos(i) множество f irstpos(u).

35 3.3. АЛГОРИТМЫ ПОСТРОЕНИЯ КОНЕЧНЫХ АВТОМАТОВ 35 Пример 3.8. Результат вычисления функции followpos для регулярного выражения из предыдущего примера приведен на рис Алгоритм 3.3. Прямое построение ДКА по регулярному выражению. Вход. Регулярное выражение r в алфавите T. Выход. ДКА M =(Q,T,D,q 0,F), такой что L(M) =L(r). Метод. Состояния ДКА соответствуют множествам позиций. Вначале Q и D пусты. Выполнить шаги 1-6: (1) Построить синтаксическое дерево для пополненного регулярного выражения (r)#. (2) Обходя синтаксическое дерево, вычислить значения функций nullable, f irstpos, lastpos и f ollowpos. (3) Определить q 0 = firstpos(root), где root корень синтаксического дерева. (4) Добавить q 0 в Q как непомеченное состояние. (5) Выполнить следующую процедуру: while (в Q есть непомеченное состояние R) < пометить R; for (каждого входного символа a T, такого, что в R имеется позиция, которой соответствует a)< пусть символ a в R соответствует позициям p 1. p n, и пусть S = followpos(p i ); 1 i n if (S )< if (S / Q) добавить S в Q как непомеченное состояние; определить D(R, a) =S; >> > (6) Определить F как множество всех состояний из Q, содержащих позиции, связанные с символом #. Пример 3.9. Результат применения алгоритма 3.3 для регулярного выражения (a b) abb приведен на рис

Системне програмне забезпечення / Методична література / Серебряков.Основы конструирования компиляторов

8.4. ВИРТУАЛЬНАЯ МАШИНА JAVA

8.4.1 Организация памяти

Машина имеет следующие регистры: pc – счетчик команд;

optop – указатель вершины стека операций;

frame – указатель на стек-фрейм исполняемого метода; vars – указатель на 0-ю переменную исполняемого метода.

Все регистры 32-разрядные. Стек-фрейм имеет три компоненты: локальные переменные, среду исполнения, стек операндов. Локальные переменные отсчитываются от адреса в регистре vars. Среда исполнения служит для поддержания самого стека. Она включает указатель на предыдущий фрейм, указатель на собственные локальные переменные, на базу стека операций и на верхушку стека. Кроме того, здесь же хранится некоторая дополнительная информация, например, для отладчика.

Куча сборки мусора содержит экземпляры объектов, которые создаются и уничтожаются автоматически. Область методов содержит коды, таблицы символов и т.д.

С каждым классом связана область констант. Она содержит имена полей, методов и другую подобную информацию, которая используется методами.

8.4.2 Набор команд виртуальной машины

Виртуальная Java-машина имеет следующие команды:

помещение констант на стек, помещение локальных переменных на стек,

запоминание значений из стека в локальных переменных, обработка массивов, управление стеком, арифметические команды, логические команды, преобразования типов, передача управления, возврат из функции, табличный переход, обработка полей объектов, вызов метода,

обработка исключительных ситуаций, прочие операции над объектами, мониторы, отладка.

Рассмотрим некоторые команды подробнее.

132 ГЛАВА 8. ПРОМЕЖУТОЧНОЕ ПРЕДСТАВЛЕНИЕ ПРОГРАММЫ

Помещение локальных переменных на стек

Команда iload – загрузить целое из локальной переменной. Операндом является смещение переменной в области локальных переменных. Указываемое значение копируется на верхушку стека операций. Имеются аналогичные команды для помещения плавающих, двойных целых, двойных плавающих и т.д.

Команда istore – сохранить целое в локальной переменной. Операндом операции является смещение переменной в области локальных переменных. Значение с верхушки стека операций копируется в указываемую область локальных переменных. Имеются аналогичные команды для помещения плавающих, двойных целых, двойных плавающих и т.д.

При трансляции объектно-ориентированных языков программирования из-за возможности перекрытия виртуальных методов, вообще говоря, нельзя статически протранслировать вызов метода объекта. Это связано с тем, что если метод перекрыт в производном классе, и вызывается метод объекта-переменной, то статически неизвестно, объект какого класса (базового или производного) хранится в переменной. Поэтому с каждым объектом связывается таблица всех его виртуальных методов: для каждого метода там помещается указатель на его реализацию в соответствии с принадлежностью самого объекта классу в иерархии классов.

В языке Java различные классы могут реализовывать один и тот же интерфейс. Если объявлена переменная или параметр типа интерфейс, то динамически нельзя определить объект какого класса присвоен переменной:

class C1 implements I; class C2 implements I; I O;

В этой точке программы, вообще говоря, нельзя сказать, какого типа значение хранится в переменной O. Кроме того, при работе программы на языке Java имеется возможность использования методов из других

8.4. ВИРТУАЛЬНАЯ МАШИНА JAVA

пакетов. Для реализации этого механизма в Java-машине используется динамическое связывание.

Предполагается, что стек операндов содержит handle объекта или массива и некоторое количество аргументов. Операнд операции используется для конструирования индекса в области констант текущего класса. Элемент по этому индексу в области констант содержит полную сигнатуру метода. Сигнатура метода описывает типы параметров и возвращаемого значения. Из handle объекта извлекается указатель на таблицу методов объекта. Просматривается сигнатура метода в таблице методов. Результатом этого просмотра является индекс в таблицу методов именованного класса, для которого найден указатель на блок метода. Блок метода указывает тип метода (native, synchronized и т.д.) и число аргументов, ожидаемых на стеке операндов.

Если метод помечен как synchronized, запускается монитор, связанный с handle. Базис массива локальных переменных для нового стекфрейма устанавливается так, что он указывает на handle на стеке. Определяется общее число локальных переменных, используемых методом, и после того, как отведено необходимое место для локальных переменных, окружение исполнения нового фрейма помещается на стек. База стека операндов для этого вызова метода устанавливается на первое слово после окружения исполнения. Затем исполнение продолжается с первой инструкции вызванного метода.

Обработка исключительных ситуаций

Команда athrow – возбудить исключительную ситуацию.

С каждым методом связан список операторов catch. Каждый оператор catch описывает диапазон инструкций, для которых он активен, тип исключения, который он обрабатывает. Кроме того, с оператором связан набор инструкций, которые его реализуют. При возникновении исключительной ситуации просматривается список операторов catch, чтобы установить соответствие. Исключительная ситуация соответствует оператору catch, если инструкция, вызвавшая исключительную ситуацию, находится в соответствующем диапазоне и исключительная ситуация принадлежит подтипу типа ситуации, которые обрабатывает оператор catch. Если соответствующий оператор catch найден, управление передается обработчику. Если нет, текущий стек-фрейм удаляется, и исключительная ситуация возбуждается вновь.

Порядок операторов catch в списке важен. Интерпретатор передает управление первому подходящему оператору catch.

134 ГЛАВА 8. ПРОМЕЖУТОЧНОЕ ПРЕДСТАВЛЕНИЕ ПРОГРАММЫ

8.5 Организация информации в генераторе кода

Синтаксическое дерево в чистом виде несет только информацию о структуре программы. На самом деле в процессе генерации кода требуется также информация о переменных (например, их адреса), процедурах (также адреса, уровни), метках и т.д. Для представления этой информации возможны различные решения. Наиболее распространены два:

– информация хранится в таблицах генератора кода;

– информация хранится в соответствующих вершинах дерева.

Рассмотрим, например, структуру таблиц, которые могут быть использованы в сочетании с Лидер-представлением. Поскольку Лидер-представление не содержит информации об адресах переменных, значит, эту информацию нужно формировать в процессе обработки объявлений и хранить в таблицах. Это касается и описаний массивов, записей и т.д. Кроме того, в таблицах также должна содержаться информация о процедурах (адреса, уровни, модули, в которых процедуры описаны, и т.д.).

При входе в процедуру в таблице уровней процедур заводится новый вход – указатель на таблицу описаний. При выходе указатель восстанавливается на старое значение. Если промежуточное представление – дерево, то информация может храниться в вершинах самого дерева.

8.6 Уровень промежуточного представления

Как видно из приведенных примеров, промежуточное представление программы может в различной степени быть близким либо к исходной программе, либо к машине. Например, промежуточное представление может содержать адреса переменных, и тогда оно уже не может быть перенесено на другую машину. С другой стороны, промежуточное представление может содержать раздел описаний программы, и тогда информацию об адресах можно извлечь из обработки описаний. В то же время ясно, что первое более эффективно, чем второе. Операторы управления

в промежуточном представлении могут быть представлены в исходном виде (в виде операторов языка if, for, while и т.д.), а могут содержаться

в виде переходов. В первом случае некоторая информация может быть извлечена из самой структуры (например, для оператора for – информация о переменной цикла, которую, может быть, разумно хранить на регистре, для оператора case – информация о таблице меток и т.д.). Во втором случае представление проще и унифицированней.

Некоторые формы промежуточного представления удобны для различного рода оптимизаций, некоторые – нет (например, косвенные тройки, в отличие от префиксной записи, позволяют эффективное перемещение кода).

Задача генератора кода – построение для программы на входном языке эквивалентной машинной программы. Обычно в качестве входа для генератора кода служит некоторое промежуточное представление программы.

Генерация кода включает ряд специфических, относительно независимых подзадач: распределение памяти (в частности, распределение регистров), выбор команд, генерацию объектного (или загрузочного) модуля. Конечно, независимость этих подзадач относительна: например, при выборе команд нельзя не учитывать схему распределения памяти, и, наоборот, схема распределения памяти (регистров, в частности) ведет к генерации той или иной последовательности команд. Однако удобно и практично эти задачи все же разделять, обращая при этом внимание на их взаимодействие.

Илон Маск рекомендует:  Что такое код swf_shapecurveto3

В какой-то мере схема генератора кода зависит от формы промежуточного представления. Ясно, что генерация кода из дерева отличается от генерации кода из троек, а генерация кода из префиксной записи отличается от генерации кода из ориентированного графа. В то же время все генераторы кода имеют много общего, и основные применяемые алгоритмы отличаются, как правило, только в деталях, связанных с используемым промежуточным представлением.

В дальнейшем в качестве промежуточного представления мы будем использовать префиксную нотацию. А именно, алгоритмы генерации кода будем излагать в виде атрибутных схем со входным языком Лидер.

9.1 Модель машины

При изложении алгоритмов генерации кода мы будем следовать некоторой модели машины, в основу которой положена система команд микропроцессора Motorola MC68020. В микропроцессоре имеется регистр

– счетчик команд PC, 8 регистров данных и 8 адресных регистров.

ГЛАВА 9. ГЕНЕРАЦИЯ КОДА

В системе команд используются следующие способы адресации: ABS – абсолютная: исполнительным адресом является значение ад-

IMM – непосредственный операнд: операндом команды является константа, заданная в адресном выражении.

D – прямая адресация через регистр данных, записывается как Хn, операнд находится в регистре Хn.

А – прямая адресация через адресный регистр, записывается как An, операнд находится в регистре An.

INDIRECT – записывается как (An), адрес операнда находится в адресном регистре An.

POST – пост-инкрементная адресация, записывается как (Аn)+, исполнительный адрес есть значение адресного регистра An и после исполнения команды значение этого регистра увеличивается на длину операнда.

PRE – пре-инкрементная адресация, записывается как -(Аn): перед исполнением операции содержимое адресного регистра An уменьшается на длину операнда, исполнительный адрес равен новому содержимому адресного регистра.

INDISP – косвенная адресация со смещением, записывается как (bd,An), исполнительный адрес вычисляется как (An)+d – содержимое An плюс d.

INDEX – косвенная адресация с индексом, записывается как (bd,An,Xn*sc), исполнительный адрес вычисляется как (An)+bd+(Xn)*sc – содержимое адресного регистра + адресное смещение + содержимое индексного регистра, умноженное на sc.

INDIRPC – косвенная через PC (счетчик команд), записывается как (bd,PC), исполнительный адрес определяется выражением (PC)+bd.

INDEXPC – косвенная через PC со смещением, записывается как (bd,PC,Xn*sc), исполнительный адрес определяется выражением (PC)+bd+(Xn)*sc.

INDPRE – пре-косвенная через память, записывается как ([bd,An,sc*Xn],od) (схема вычисления адресов для этого и трех последующих способов адресации приведена ниже).

INDPOST – пост-косвенная через память: ([bd,An],sc*Xn,od).

INDPREPC – пре-косвенная через PC: ([bd,PC,sc*Xn],od). INDPOSTPC – пост-косвенная через PC: ([bd,PC],Xn,od).

Здесь bd – это 16или 32-битная константа, называемая смещением , od – 16или 32-битная литеральная константа, называемая внешним смещением . Эти способы адресации могут использоваться в упрощенных формах без смещений bd и/или od и без регистров An или Xn. Следующие примеры иллюстрируют косвенную постиндексную адресацию:

9.1. МОДЕЛЬ МАШИНЫ

MOVE D0, ([$12345678,A0],D4,$FF000000)

Индексный регистр Xn может масштабироваться (умножаться) на 2,4,8, что записывается как sc*Xn. Например, в исполнительном адресе ([24,A0,4*D0]) содержимое квадратных скобок вычисляется как [A0] + 4 * [D0] + 24.

Эти способы адресации работают следующим образом. Каждый исполнительный адрес содержит пару квадратных скобок [. ] внутри пары круглых скобок, т.е. ([. ], . ). Сначала вычисляется содержимое квадратных скобок, в результате чего получается 32-битный указатель. Например, если используется постиндексная форма [20,A2], то исполнительный адрес – это 20 + [A2]. Аналогично, для преиндексной формы [12,A4,D5] исполнительный адрес – это 12 + [A4] + [D5].

Указатель, сформированный содержимым квадратных скобок, используется для доступа в память, чтобы получить новый указатель (отсюда термин косвенная адресация через память). К этому новому указателю добавляется содержимое внешних круглых скобок и таким образом формируется исполнительный адрес операнда.

В дальнейшем изложении будут использованы следующие команды (в частности, рассматриваются только арифметические команды с целыми операндами, но не с плавающими):

MOVEA ИА, А – загрузить содержимое по исполнительному адресу ИА на адресный регистр А.

MOVE ИА1, ИА2 – содержимое по исполнительному адресу ИА1 переписать по исполнительному адресу ИА2.

MOVEM список_регистров, ИА – сохранить указанные регистры в памяти, начиная с адреса ИА (регистры указываются маской в самой команде).

MOVEM ИА, список_регистров – восстановить указанные регистры из памяти, начиная с адреса ИА (регистры указываются маской в самой команде).

LEA ИА, А – загрузить исполнительный адрес ИА на адресный регистр

MUL ИА, D – умножить содержимое по исполнительному адресу ИА на содержимое регистра данных D и результат разместить в D (на самом деле в системе команд имеются две различные команды MULS и MULU для чисел со знаком и чисел без знака соответственно; для упрощения мы не будем принимать во внимание это различие).

DIV ИА, D – разделить содержимое регистра данных D на содержимое по исполнительному адресу ИА и результат разместить в D.

ADD ИА, D – сложить содержимое по исполнительному адресу ИА с содержимым регистра данных D и результат разместить в D.

SUB ИА, D – вычесть содержимое по исполнительному адресу ИА из содержимого регистра данных D и результат разместить в D.

Команды CMP и TST формируют разряды регистра состояний. Всего имеется 4 разряда: Z – признак нулевого результата, N – признак отри-

ГЛАВА 9. ГЕНЕРАЦИЯ КОДА

цательного результата, V – признак переполнения, C – признак переноса.

CMP ИА, D – из содержимого регистра данных D вычитается содержимое по исполнительному адресу ИА, при этом формируется все разряды регистра состояний, но содержимое регистра D не меняется.

TST ИА – выработать разряд Z регистра состояний по значению, находящемуся по исполнительному адресу ИА.

BNE ИА – условный переход по признаку Z = 1 (не равно) по исполнительному адресу ИА.

BEQ ИА – условный переход по признаку Z = 0 (равно) по исполнительному адресу ИА.

BLE ИА – условный переход по признаку N or Z (меньше или равно) по исполнительному адресу ИА.

BGT ИА – условный переход по признаку not N (больше) по исполнительному адресу ИА.

BLT ИА – условный переход по признаку N (меньше) по исполнительному адресу ИА.

BRA ИА – безусловный переход по адресу ИА.

JMP ИА – безусловный переход по исполнительному адресу.

RTD размер_локальных – возврат из подпрограммы с указанием размера локальных.

LINK A, размер_локальных – в стеке сохраняется значение регистра А, в регистр А заносится указатель на это место в стеке и указатель стека продвигается на размер локальных.


UNLK A – стек сокращается на размер локальных и регистр А восстанавливается из стека.

9.2 Динамическая организация памяти

Динамическая организация памяти — это организация памяти периода исполнения программы. Оперативная память программы обычно состоит из нескольких основных разделов: стек (магазин), куча, область статических данных (инициализированных и неинициализированных). Наиболее сложной является работа со стеком. Вообще говоря, стек периода исполнения необходим для программ не на всех языках программирования. Например, в ранних версиях Фортрана нет рекурсии, так что программа может исполняться без стека. С другой стороны, исполнение программы с рекурсией может быть реализовано и без стека (того же эффекта можно достичь, например, и с помощью списковых структур). Однако, для эффективной реализации пользуются стеком, который, как правило, поддерживается на уровне машинных команд.

Рассмотрим схему организации магазина периода выполнения для простейшего случая (как, например, в языке Паскаль), когда все переменные в магазине (фактические параметры и локальные переменные)

9.2. ДИНАМИЧЕСКАЯ ОРГАНИЗАЦИЯ ПАМЯТИ

имеют известные при трансляции смещения. Магазин служит для хранения локальных переменных (и параметров) и обращения к ним в языках, допускающих рекурсивные вызовы процедур. Еще одной задачей, которую необходимо решать при трансляции языков с блочной структурой – обеспечение реализации механизмов статической вложенности. Пусть имеется следующий фрагмент программы на Паскале:

В процессе выполнения этой программы, находясь в процедуре P2, мы должны иметь доступ к последнему экземпляру значений переменных процедуры P2 и к экземпляру значений переменных процедуры P1, из которой была вызвана P2. Кроме того, необходимо обеспечить восстановление состояния программы при завершении выполнения процедуры.

Мы рассмотрим две возможные схемы динамической организации памяти: схему со статической цепочкой и с дисплеем в памяти. В первом случае все статические контексты связаны в список, который называется статическойцепочкой ; в каждой записи для процедуры в магазине хранится указатель на запись статически охватывающей процедуры (помимо, конечно, указателя динамической цепочки – указателя на “базу” динамически предыдущей процедуры). Во втором случае для хранения ссылок на статические контексты используется массив, называемый дисплеем . Использование той или иной схемы определяется, помимо прочих условий, прежде всего числом адресных регистров.

9.2.1 Организация магазина со статической цепочкой

Итак, в случае статической цепочки магазин организован, как это изображено на рис. 9.1.

Таким образом, на запись текущей процедуры в магазине указывает регистр BP (Base Pointer), с которого начинается динамическая цепочка.

Основы компиляторов

Основные задачи компиляторов

Компьютеры сами по себе способны выполнять только очень ограниченный набор операций, называемых машинными кодами. В старые времена, когда появились первые компьютеры, программы писались в машинных кодах, представляющих собой последовательности двоичных чисел, однозначно воспринимаемых компьютером. В конце 50-х кодов прошлого века появились первые языки программирования, такие как язык ассемблера и Фортран. Для того, чтобы компьютер мог понять программу, написанную на каком-то языке программирования, необходим переводчик ( транслятор ) такой программы в машинные коды. Отметим, что, если оператор языка ассемблера отображается при трансляции чаще всего 1 Некоторые операторы языка ассемблера, например, такие, как операторы ввода/вывода, отображаются в несколько машинных команд. в одну машинную инструкцию, предложения языков более высокого уровня отображаются, вообще говоря, в несколько машинных инструкций.

Трансляторы бывают двух типов: компиляторы ( compiler ) и интерпретаторы ( interpreter ). Процесс компиляции состоит из двух частей: анализа ( analysis ) и синтеза ( synthesis ). Анализирующая часть компилятора разбивает исходную программу на составляющие ее элементы (конструкции языка) и создает промежуточное представление исходной программы. Синтезирующая часть из промежуточного представления создает новую программу, которую компьютер в состоянии понять. Такая программа называется объектной программой. Объектная программа может в дальнейшем выполняться без перетрансляции. В качестве промежуточного представления обычно используются деревья, в частности, так называемые деревья разбора. Под деревом разбора понимается дерево , каждый узел которого соответствует некоторой операции , а сыновья этого узла — операндам.

Интерпретатор

В отличие от компилятора, интерпретатор не создает никакой новой программы, а просто выполняет каждое предложение языка программирования. Можно сказать, что результатом работы интерпретатора является «число».

Вообще говоря, интерпретатор , так же, как и компилятор , анализирует программу на входном языке, создает промежуточное представление , а затем выполняет операции , содержащиеся в тексте этой программы. Например, интерпретатор может построить дерево разбора, а затем выполнить операции , которыми помечены узлы этого дерева.

В том случае, если исходный язык достаточно прост (например, если это язык ассемблера или Basic ), то никакое промежуточное представление не нужно, и тогда интерпретатор — это простой цикл . Он выбирает очередную инструкцию языка из входного потока, анализирует и выполняет ее. Затем выбирается следующая инструкция . Этот процесс продолжается до тех пор, пока не будут выполнены все инструкции, либо пока не встретится инструкция , означающая окончание процесса интерпретации.

Компилятор

Компилятор переводит программы с одного языка на другой. Входом компилятора служит цепочка символов , составляющая исходную программу на языке программирования . Выход компилятора (объектная программа ) также представляет собой цепочку символов, но принадлежащую другому языку , например, языку некоторого компьютера. При этом сам компилятор написан на языке , возможно, отличающемся от первых двух. Будем называть язык исходным языком, язык — целевым языком, а язык — языком реализации. Таким образом, можно говорить о компиляторе как об отображении множества в множество , т.е. .

Отметим, что далеко не всегда исходные программы корректны с точки зрения исходного языка. Более того, некорректные программы подаются на вход компилятору значительно чаще, чем корректные — таков уж современный процесс разработки программ. Поэтому крайне важной частью процесса трансляции является точная диагностика ошибок, допущенных во входной программе.

Существует огромное количество различных языков программирования, начиная с таких традиционных языков программирования как Fortran и Pascal и кончая современными объектно-ориентированными языками такими, как C# и Java . Практически каждый язык программирования имеет какие-то особенности с точки зрения создателя транслятора. Однако мы начнем с рассмотрения разнообразных целевых языков компиляторов.

Благодарности Глава Процесс компиляции

страница 1/16
Дата 14.07.2020
Размер 3.51 Mb.
Тип Задача
Робин Хантер

Основные концепции компиляторов

Глава 1. Процесс компиляции

  1. Вступление
  2. Основные понятия
  3. Процесс компиляции
  4. Этапы, фазы и проходы
  5. Интегрированные среды разработки
  6. Проектирование компилятора
  7. Использование инструментальных средств
  8. Резюме

Дополнительная литература Упражнения

Глава 2. Определение языка

  1. Вступление
  2. Определяя синтаксис
  3. Грамматики
  4. Отличия регулярных и контекстно-свободных языков
  5. Порождения
  6. Неоднозначные грамматики
  7. Ограничения контекстно-свободных грамматик
  8. Задача синтаксического анализа
  9. Определение семантики

2.10. Резюме

Дополнительная литература Упражнения

Глава 3. Лексический анализ

  1. Вступление
  2. Основные понятия
  3. Распознавание символов
  4. Lex
  5. Другие применения Lex
  6. Взаимодействие с YACC
  7. Лексические затруднения
  8. Резюме
Дополнительная литература 79 Упражнения 79 Глава 4, Нисходящий синтаксический анализ 81 4.1. Вступление 81 4.2. Критерии принятия решений 81 4.3. 1Х(1)-грамматики 84 4.4. Рекурсивный спуск 89 9 4.5. Преобразования грамматик 96 10 4.5.1. Удаление левой рекурсии 96 4.5.2. Факторизация 98 11 4.6. Достоинства и недостатки ЬЦ1)-анализа 101 11 4.7. Введение действий в грамматику 102 11 4.8. Резюме 105 12 Дополнительная литература 106 15 Упражнения 106 22 22 Глава 5. Восходящий синтаксический анализ 109 23 5.1. Вступление 109 25 5.2. Основные понятия 109 25 5.3. Использование таблицы синтаксического анализа 113 26 5.4. Создание таблицы синтаксического анализа 120 5.5. Особенности LR-анализа 132 27 • 5.6. Введение в YACC 135 27 5.7. Вычисление метрик 140 27 5.8. Использование YACC 143 31 5.9. Резюме . 153 39 Дополнительная литература 154 41 Упражнения 154 42 47 Глава 6. Семантический анализ 157 51 6.1. Вступление 157 52 6.2. Не-контекстно-свободные характеристики языка 157 53 6.3. Таблицы компилятора 162 53 6.3.1. Таблицы символов 162 54 6.3.2. Таблицы типов 167 6.3.3. Другие таблицы 168 57 6.4. Реализация наследования в C++ 169 57 6.5. Резюме 170 57 Дополнительная литература 171 58 Упражнения 171 62 71 Глава 7. Распределение памяти 173 75 7.1. Вступление 173 76 7.2. Память 173 78 7.3. Статическая и динамическая память 176
  1. Адреса времени компиляции
  2. Куча
  3. Резюме .
    Дополнительная литература
    Упражнения

Глава 8. Генерация кода

  1. Вступление
  2. Создание промежуточного кода
  1. Трехадресный код
  2. Р-код •
  3. Байт-код

8.3. Создание машинного кода

  1. Выбор инструкций
  2. Распределение регистров
  3. Распределение регистров путем раскрашивания графа
  1. Оптимизация кода
  2. Генераторы генераторов кода
  3. Резюме

Дополнительная литература Упражнения

Приложение А. Решения упражнений

Глава 1 Глава 2 Глава 3 Глава 4 Глава 5 Глава 6 Глава 7 Глава 8

Литература Предметный указатель

197 197 198 201 203 206 208 208 213 215 219 220 220 220

223 224 226 230

232 233 234 234

Изучение компиляторов является центральным и одним из наиболее вос­требованных аспектов компьютерных наук. Написание компилятора тре­бует знания исходного языка и целевой машины и обеспечения их взаи­мосвязи. Наличие современного инструментального обеспечения осво­бождает программиста от многих утомительных, подверженных ошибкам моментов при создании компилятора.

Мое первое знакомство с компиляторами произошло в 1967 году на лекциях создателя ранних моделей компиляторов для языка ALGOL 60 Питера Наура (Peter Naur) в Университете Ньюкасла. Позднее, в 1974 го­ду, мне посчастливилось прослушать расширенный курс по конструиро­ванию компиляторов в Техническом университете Мюнхена (отдел Ф. Л. Бауэра (F. L. Bauer)). С тех пор я, с некоторыми перерывами, работаю с компиляторами и инструментами для их разработки.

Большинство теоретических разработок и методов для конструирования компиляторов возникло в 1970-х, а некоторые из них даже раньше. В то же время развитие языков программирования постоянно ставило перед создате­лями компиляторов новые задачи: от определения языка ALGOL 60 (ранние работы Наура в Дании, а также Ренделла (Randell) и Рассела (Russell) в Вели­кобритании) до удовлетворения потребностей возникших позже языка Ada и языков объектно-ориентированного программирования. Современные требо­вания Java к сетевой безопасности, эффективности и переносимости вновь ставят перед создателями компиляторов новые проблемы. В то же время по­явление Java Virtual Machine дает великолепный пример промежуточного языка, позволяющего проиллюстрировать различные аспекты генерации кода и распределения памяти.

Процесс создания компилятора соединяет в себе как творческую, так и рутинную работу. Он требует хорошей инструментальной поддержки, что от­четливо видно при изучении истории развития компиляторов. В наше время доступно множество инструментальных средств для создания компиляторов. Некоторые из них можно получить бесплатно через Internet, но на данный момент наиболее используемыми и распространенными инструментальными средствами являются Unix Lex и YACC (сейчас они могут применяться и на других платформах). В Internet доступны также бесплатные версии Lex и YACC, известные как Flex и Bisson. Также можно получить существующие версии turbo Pascal (изначально основанные на С).

Во многих книгах по компиляторам описываются средства Lex и YACC с примерами их использования, но лишь в немногих из них со­держится достаточно информации для того, чтобы читатель сам смог воспользоваться этими инструментами для решения своих задач. Именно поэтому одной из задач, поставленных при написании данной книги, яв-

Основным языком при написании различных алгоритмов на базе Lex и YACC является С. Данная книга прежде всего посвящена компиляции императивных языков, поэтому язык С также будет применяться в каче­стве исходного языка во многих примерах, описывающих различные ас­пекты компиляции. В то же время многие свойства языка, компиляцию которого мы желаем рассмотреть, не связаны с С, поэтому в таких случа­ях будут использоваться другие, более подходящие языки — FORTRAN, Pascal, Ada, ALGOL 68, C++, Java.

Первая часть книги посвящена этапу анализа процесса компиляции. После введения в процесс компиляции (глаю 1) следуют главы по опре­делению языка, лексическому анализу, нисходящему и восходящему син­таксическому анализу и семантическому анализу (главы 2—6). Более ко­роткая вторая часть книги посвящена этапу синтеза процесса компиля­ции. Она содержит две главы, в которых рассмотрено распределение памяти и генерация кода (главы 7—8). Каждая глава завершается серией упражнений, ответы на которые приведены в конце книги. Кроме того, в конце каждой главы помещен список литературы, рекомендуемой для дальнейшего изучения. Значение большинства технических терминов, используемых в книге, можно найти в глоссарии.

Данная книга рассчитана на односеместровый курс по компиляторам и их инструментальным средствам, подобный читаемому в Университете Стратк-лайда (University of Stratchclyde). Названный университетский курс также включает практические занятия, на которых студенты закрепляют навыки по использованию Lex и YACC. Как и другие книги серии «Основы вычисли­тельных систем», эта книга стремится подать все необходимые аспекты про­цесса компиляции, не пытаясь охватить всю область.

С особым удовольствием я выражаю свою признательность издательству Prentice Hall за помощь и поддержку в создании настоящей книги. Необ­ходимо также поблагодарить Бориса Когана (Boris Cogan) и Тамару Мат­вееву (Tamara Mafveeva) за их полезные комментарии к тексту. Благода­рю свою жену Кейт (Kate) за ее поддержку и терпение, а также за про­верку всей рукописи, которую она охотно выполнила. Благодарю рецензентов издательства и редактора серии Рея Велланда (Rey Welland) за их конструктивные замечания на разных этапах создания книги.

Робин Хан тер (Robin Hunter)

В этой главе будут определены основные понятия компилятора языка, его структура, функции и реализация. В частности, будут рассмотрены следующие вопросы.

« Взаимосвязь между различными языками, задействованными в ти­пичном компиляторе.

  • Типичная структура компиляторов.
  • Функции основных фаз компиляции.
  • Цели, которые ставятся при разработке компиляторов.
  • Роль инструментальных средств при разработке компилятора.
  • Возможная степень автоматизации разработки компилятора.

1.2. Основные понития

Программное обеспечение можно создавать с помощью множества язы­ков программирования. Ими могут быть традиционные императивные языки (COBOL, FORTRAN, Pascal, С), объектно-ориентированные язы­ки (C++, Smalltalk, Java), функциональные или логические языки (LISP, Prolog), языки четвертого поколения или визуальные языки (Visual C++, Visual Basic, Delphi). Задача компилятора состоит в преобразовании ори­ентированного на пользователя представления программного обеспече­ния в машинно-ориентированное (в котором происходит непосредствен­ное выполнение программы компьютером). Компиляторы — это изна­чально изощренные системы обработки текста, которые имеют много общего с другими инструментальными средствами обработки текста, на­писанными на языке программирования либо на естественном языке. Обрабатываемый ими текст может быть написан как вручную на обыч­ном языке, так и полуавтоматическим способом при использовании ви­зуальных языков или языков четвертого поколения.

Задача компилятора обычно рассматривается на двух этапах.

W

1, Этап анализа, на котором анализируется исходный текст.

2. Этап синтеза, на котором генерируется машинно-ориентированное
представление,

В дальнейшем вход этапа анализа будем называть исходным текстом или исходным кодом, а выход этапа синтеза — целевым текстом или целе­вым кодом. Преобразование исходного кода в целевой обычно называется процессом компиляции. Процесс компиляции осуществляет компилятор. Компилятор языка можно также назвать реализацией языка. Произведен­ный компилятором целевой код может иметь вид машинного кода для некоторой машины (компьютера) или ассемблерного кода, или некото­рого промежуточного кода, который в дальнейшем будет преобразован (уже с помощью других инструментальных средств) или в ассемблерный код, или л машинный код для некоторой машины. Возможен также ва­риант, когда промежуточный код непосредственно используется посред­ством интерпретатора,

Несмотря на то, что предлагаемая книга посвящена процессу компи­ляции, при случае будут рассматриваться и другие возможности приме­нения текстуального анализа. Следует отметить, что при рассмотрении компиляции большее внимание будет уделяться вопросам анализа, чем синтеза. Это связано с тем, что понятия стадии анализа обладают боль­шей степенью общности и применимости по сравнению с частными, за­висимыми от машины понятиями стадии синтеза.

Технологии компиляторов значительно развились со времени появле­ния компьютеров, и теперь стала возможной автоматизация многих ас­пектов процесса создания компилятора. Существующие инструменталь­ные средства позволяют автоматизировать создание анализаторов, хотя успехи по автоматизации создания генераторов кода намного скромнее. Вопросы возможной степени автоматизации будут рассматриваться в по­следующих главах, где с этой целью будут широко использованы средства генерации анализаторов Lex и YACC.

В основном языком создания компиляторов с помощью Lex и YACC является С. Поэтому в дальнейшем в качестве языка реализации (языка написания компилятора) будет подразумеваться именно С, и требуемые алгоритмы будут описываться на нем. Чтобы избежать частого перехода от одного языка к другому, реализуемым языком также будет считаться С. Впрочем, для описания отдельных моментов будут использоваться и другие языки, более удобные в этих конкретных случаях.

1.3. Процесс компиляции

Процесс компиляции представляет собой преобразование одного языка в другой, переход от исходного кода, на котором работает программист или который автоматически генерируется из некоторого высокоуровневого представления, к целевому коду, который выполняется на машине, воз-

можно, после некоторых преобразований. Схематически этот процесс изображен на рис. 1.1

Исходный Целевой
код Процесс компиляции код

Рис. 1.1.

Как уже упоминалось, процесс компиляции также включает третий язык — язык реализации. Им может быть тот же язык, что и исходный или целевой код, но это необязательно. По возможности, в качестве язы­ка написания компилятора выбирается наиболее удобный — либо с точ­ки зрения внутренних характеристик (например, подверженность ошиб­кам), либо с точки зрения доступности и совместимости с инструмен­тальными средствами.

Три языка, задействованных в реализации, удобно представить с помо­щью Т-диаграммы, содержащей каждый язык в отдельной ветви. На рис. 1.2 изображен компилятор, который написан на С и преобразует Java в байт-код (язык, интерпретируемый посредством Java Virtual Machine).

Java Байт-код

Рис. 1.2.

На рис. 1.3 изображен компилятор, который написан на машинном коде (М-код) и преобразует Pascal в машинный код. Данный пример яв­ляется иллюстрацией того факта, что операционный компилятор обычно

пишется (и производит код) на том же языке, на котором работает ма­шина, где планируется выполнять данный код. Однако, если часть про­граммного обеспечения (возможно, для встроенных систем) компилиру­ется на машине, отличной от той, на которой это обеспечение будет ис­пользоваться, то потребуется задействовать два машинных кода. Один из них предназначен для машины, на которой запушен компилятор (язык, на котором компилятор написан), а второй — для машины, на которой будет использоваться данное, программное обеспечение (язык, который генерирует компилятор). Для примера на рис. 1.4 изображен компилятор для компилирования программного обеспечения встроенных систем.

Чтобы компилятор мог функционировать, он должен быть написан на коде той машины, на которой будет установлен. Однако, этот код может оказаться неудобным для написания программы компилятора по причи­не его низкого уровня.

Глава 1. Процесс компиляции

1.3. Процесс компиляции

13

и

Pascal

Рис, 1.3.

C++

Рис. 1.4.

Часто эту проблему решают следующим образом: вместо того, чтобы пи­сать программу на языке низкого уровня, ее получают путем компиляции программы, написанной на языке высокого уровня. Поэтому сами по се­бе компиляторы изначально пишутся на языке высокого уровня, а затем с помощью уже существующих компиляторов преобразуются к виду, ко­торый воспринимает машина. Данную ситуацию можно изобразить с по­мощью трех расположенных рядом Т-диаграмм (рис. 1.5).

C++ М-код C++ М-код
Vi-етд М-код

Р ис. 15.

В левом верхнем углу рисунка расположен компилятор, изначально написанный на C++, а в правом верхнем углу — исполняемый компиля­тор, полученный после компиляции компилятором, помещенным внизу рисунка. Эти три Т-диаграммы можно объединить, что позволит обнару­жить некоторые закономерности получения одного компилятора из дру­гого. Например, два языка в соответствующих двух верхних частях верх-

них диаграмм должны быть одинаковыми, а два соседствующих появле­ния языка C++ и машинного кода должны относиться к одному языку. Изображенный внизу М-код мог, по сути, быть любым языком, опреде­ляемым машиной, на которой компилируется компилятор.

С помощью Т-диаграммы легко показать, как перенести компилятор, написанный для одной машины, на другую. Пусть имеется компилятор, созданный для машины А, тогда при его переносе на машину В нужно, по меньшей мере, изменить язык реализации. Чем пытаться преобразо­вать код одной машины в код другой, намного проще вернуться к перво­начальной версии компилятора, написанной на языке высокого уровня, и откомпилировать ее в код машины В.

Во многих случаях необходимо преобразовать выход кода с помощью
компилятора (например, в код машины В). Это уже совсем другая задача,
и ее сложность будет зависеть от иных факторов, например, от „того, на­
сколько автономно производство кода. *

1,4. Этапы5 фазы и прожоды

Хорошо написанный компилятор имеет модульную структуру и должен представлять пример хорошо сконструированной программы. Логически процесс компиляции разделяется на этапы, которые, в свою очередь, разделяются на фазы. Физически компилятор разделяется на проходы. Остановимся на этих вопросах более детально.

Как уже говорилось, основными (и часто единственными) этапами компиляции являются анализ (определение структуры и значения исход­ного кода) и синтез (построение целевого кода). Кроме того, может быть этап предварительной обработки, в которой происходит присоединение исходных файлов, развертывание макросов и т.п. Этот этап достаточно прост и в основном связан с языками С и C++. Подробно данный этап рассматриваться не будет.

Типичные фазы процесса компиляции показаны на рис 1.6.

Этап анализа принято разделять на три отдельных фазы.

  1. Лексический анализ.
  2. Синтаксический анализ.
  3. Семантический анализ.

Этап синтеза состоит из следующих (всех или нескольких) фаз.

  • Генерация машинно-независимого кода.
  • Оптимизация машинно-независимого кода.
  • Распределение памяти.
  • Генерация машинного кода.
  • Оптимизация машинного кода.

i i

.Глава 1. Процесс компиляции

1.4. Этапы, фазы и проходы

Лексический анализ Синтаксический анализ Семантический анализ
Генерация машинно-независимого кода > Оптимизация

кода

>. Распре­деление памяти ■► Генерация

> Оптимизация машинного кода Синтез

Р ис. 1.6.

Лексический анализ — это относительно простая фаза, в которой формируются символы (или токены) языка. Слова языка, например,

или пользовательские идентификаторы, например,

или последовательности знаков, например,

удобно воспринимать как один символ, как это делается на этапе анали­за. Задачей фазы лексического анализа или лексического анализатора яв­ляется переход от последовательности знаков к символам языка, с кото­рыми в дальнейшем будут работать синтаксическая и семантическая фа­зы. Такой подход копирует поведение человека при чтении программы. В конечном счете, мы ведь воспринимаем текст программы не как простой набор знаков, а как набор символов, состоящих из этих знаков.

Наряду с преобразованием последовательности знаков в символы, лексический анализатор также обрабатывает пробелы и удаляет коммен­тарии и любые другие символы, не имеющие смысловой нагрузки для последующих этапов анализа. Важно отметить, что лексический анализа­тор всего лишь формирует символы — их последовательность не имеет для него никакого значения, т.е., если бы программа, допустим написан­ная на С, начиналась с

то лексический анализатор просто бы передал этот текст в символьном виде синтаксическому анализатору. Другими словами, лексический ана-

лизатор обычно не работает с контекстом. Если он обрабатывает один символ, для него совершенно не важно, что предшествовало этому сим­волу или что последует за ним.

Сравнительная простота и четкая формулировка лексического анализа позволяют легко автоматизировать создание лексических анализаторов, и в настоящее время существует множество инструментальных средств, по­зволяющих генерировать лексические анализаторы для языка, исходя только из его лексической (т.е. локальной) структуры. О том, как исполь­зовать эти инструменты, будет рассказано в главе 3.

Несмотря на сравнительную простоту лексического анализатора, его выполнение может занимать значительное время в процессе компиля­ции. Это не должно удивлять, если учесть, что лексический анализ — единственная фаза компиляции, которая имеет дело со знаками, которых значительно больше языковых символов. Если же работа лексического анализатора не занимает значительную часть времени компиляции, то стоит задуматься об эффективности остальных фаз процесса.

В процессе синтаксического анализа определяется общая структура программы, что включает понимание порядка следования символов в программе. Это означает, что синтаксический анализатор должен обла­дать информацией о контексте, в котором он работает, т.е. учитывать уже прочитанные символы. Результатом работы синтаксического анализатора является представление программы в древовидной форме, которую назы­вают синтаксическим деревом. К примеру, выражение

(а + Ь) * (с + d) может быть представлено в виде, показанном на рис. 1.7.

Это представление называется абстрактным синтаксическим деревом. Следует отметить, что в данном представлении нет необходимости показы­вать скобки, поскольку структура, задаваемая ими в первоначальном выра­жении, представляется структурой дерева. Таким же образом вся программа может быть представдена с помощью абстрактных сишаксических деревьев.

Глава 1. Процесс компиляции


1.4. Этапы, фазы и проходы

17

Синтаксический анализатор считывает символы в программе слева направо (привычным способом). В процессе считывания он должен уметь определять, является ли последовательность уже считанных симво­лов началом программы. Например, первые десять входных символов могут быть началом некоторой программы, а первые одиннадцать — нет. В этом случае последующие действия компилятора будут зависеть от принятого способа восстановления после ошибок. По крайней мере, ком­пилятор должен указать на одиннадцатый символ и сообщить, что в этой точке вход стал некорректным. Многие компиляторы имеют более широ­кие возможности, например, могут выводить (предположительно полез­ные) сообщения следующего характера:

Стоит отметить, что иногда подобные сообщения не помогают, а наобо­рот, еще больше запутывают.

Возникновение ошибки при считывании одиннадцатого символа мо­жет быть связано как с некорректностью настоящего символа, так и с ошибкой в предыдущих символах программы, и это — одна из причин того, что сообщения об ошибках могут причинять неудобства. Это не оз­начает, что компилятор может выдать сообщение об отсутствующей ошибке, он просто может указать неверное место ее нахождения и из-за этого неправильно ее охарактеризовать. Вопросы правильной диагности­ки ошибок и стратегии их устранения чрезьычайно важны, но в данной книге они не рассматриваются, дабы не отклоняться от главной темы и общих принципов книг серии «Основы вычислительных систем».

Синтаксические анализаторы для проверки синтаксиса могут быть по­строены автоматически (с использованием соответствующих инструмен­тальных средств) из определения языка, хотя при этом требуется писать код для формирования абстрактного синтаксического дерева. Об исполь­зовании таких инструментов рассказывается в главах 4 и 5.

Фаза синтаксического анализа является ключевой на этапе анализа. Она непосредственно взаимодействует с лексической фазой, а результаты ее работы в дальнейшем будут использоваться семантической фазой. Кроме того, фаза синтаксического анализа создает основу для работы компилятора в целом, коды этапа синтеза образуются именно благодаря взаимодействию со структурой, которую образует фаза синтаксического анализа. К тому же, синтаксический анализ создает основу для работы большого количества инструментальных средств анализа исходного кода, например, различных инструментов измерений, перекрестных ссылок, компоновки и т.д. Все упомянутые типы анализа являются частными случаями статического анализа, т.е. анализа, который осуществляется над исходным кодом без его выполнения. Анализ кода, связанный с вы­полнением команд исходного кода, называется динамическим.

Методы синтаксического анализа требуют интенсивного изучения. Некоторые из них обладают большей общностью, чем другие (в смысле применимости к более широкому классу языков), некоторые легче авто-

матизировать, а некоторые более эффективны. Далее в главах 4 и 5 будут подробно рассмотрены два ведущих метода — метод рекурсивного спуска,^ являющийся наглядным и простым при кодировании, и синтаксический анализ SLR(1), который легко автоматизируется и пригоден для большого диапазона языков.

Некоторые свойства языков программирования не могут быть прове­рены простым сканированием слева направо без создания таблиц произ­вольного размера для обеспечения доступа к информации на некотором расстоянии (с точки зрения символов исходного кода). В эту категорию, к примеру, попадает информация о типах переменных и области их ви­димости. Проверка этих типов свойств языков программирования (называющихся статической семантикой) выполняется не в синтаксиче­ской, а в семантической фазе анализа. Это означает, что синтаксический анализатор не заметит несовместимости используемых типов. Проблема такого рода будет исследоваться в семантической фазе анализа.

Семантический анализ обычно инициируется синтаксическим анали­затором для создания и получения доступа к соответствующим таблицам. То, что семантический анализ может не производиться автоматически синтаксическим анализатором, имеет свои положительные стороны; ошибки статической семантики легко обнаруживаются, и после них лег­ко производится восстановление,

Как уже говорилось, этап синтеза процесса компиляции состоит из следующих основных фаз.

  • Генерация машинно-независимого кода.
  • Оптимизация машинно-независимого кода.
  • Распределение памяти.
  • Генерация машинного кода.
  • Оптимизация машинного кода.

В частных случаях некоторые из этих фаз могут отсутствовать. Например, если компилятор непосредственно компилирует в машинный код, пер­вые две фазы могут пропускаться. Оптимизация кода может происходить на уровне машинно-независимого кода, на уровне машинного кода, на

обоих уровнях или ни на одном. Распределение памяти является ключе­вой фазой, которая управляется одной из фаз генерации кода.

Существуют причины, по которым вначале необходимо создавать ма­шинно-независимый код; это способствует переносимости компилятора

и служит для обособления зависимости от языка и зависимости от ма­шины. Многие компиляторы также производят некоторые промежуточ­ные коды, которые могут быть независимы от исходного языка, машин­ного языка или от обоих.

В свое время были приложены значительные усилия для создания так на­зываемого Универсального промежуточного языка (Universal Intermediate Language — UIL), удобного для использования в качестве промежуточного языка для компиляции всех, или почти всех, языков на любую машину. К \

18

Глава 1. Процесс компиляции

1.4. Этапы, фазы и проходы

19

сожалению, эта великолепная идея оказалась неосуществимой. Однако, на данный момент существуют хорошо разработанные промежуточные языки для компиляции исходных языков, например, Р-код для Pascal, Diana для Ada, байт-код для Java. Также существуют промежуточные языки для компи­ляции на определенные машины, например, CTL для машины Manchester MU5. Если бы существовал удачный язык UIL, то проблема использования т языков на п машинах решалась бы созданием т препроцессоров (front end) (каждый из них состоял бы из соответствующего анализатора одного из язы­ков и генератора UIL) и л постпроцессоров (back end) (каждый из них состоял бы из соответствующего транслятора с UIL в один из машинных кодов). Сказанное выше иллюстрируется на рис. 1.8. С другой стороны, независимая реализация каждого компилятора потребует создания т* п программных блоков, отображающих каждый язык на каждую машину.

Одной из проблем при создании LJIL является проблема выбора уровня языка: UIL может оказаться либо слишком высокоуровневым для некоторых языков, либо слишком низкоуровневым для некоторых машин. Несмотря на это, существует множество примеров компиляторов с одним исходным язы­ком, который преобразуется в коды нескольких машин, и компиляторов, ко­торые преобразуют различные исходные языки в один и тот же машинный.

Рассмотрим вопрос оптимизации кода. Потребность в ней может быть различной. Если требуется очень эффективный код, то компилятор обязан обеспечить значительную оптимизацию. В то же время во многих средах скорость работы программного обеспечения не является критическим пара­метром, следовательно, необходима всего лишь незначительная оптимизация. Некоторые типы оптимизации реализовать просто, и поэтому их часто вклю­чают в компиляторы, тогда как другие формы оптимизации, в особенности глобальные (в отличие от локальных), трудоемки и требуют значительных за­трат времени при компиляции, а посему употребляются редко. Многие ком­пиляторы позволяют пользователю самому определить, требуется ли исчер- ■ пывающая (а следовательно, дорогая) оптимизация.

В фазе распределения памяти каждая константа и переменная, фигу­рирующие в программе, получают зарезервированное место в памяти для хранения своего значения. Данная область памяти может иметь один из следующих типов.

  • Статическая память, если время жизни переменной равно време­
    ни жизни программы. Не может быть освобождена до завершения
    выполнения программы.
  • Динамическая память, если время жизни переменной равно времени
    жизни определенного блока, функции или процедуры. Может быть
    освобождена после выполнения данного фрагмента программы.
  • Глобальная память, если на момент компиляции время жизни неиз­
    вестно, а память должна выделяться и освобождаться в процессе вы­
    полнения. Эффективный контроль подобной памяти обычно подразу­
    мевает определенные служебные издержки времени выполнения.

Результатом работы фазы распределения памяти является создание

адреса, в котором содержится полная информация о локализации памяти. В дальнейшем адрес передается генератору кода.

Этап синтеза процесса компиляции (в отличие от этапа анализа) не очень поддается автоматизации, поэтому нельзя сказать, что средства его инструментальной поддержки весьма широко распространены. Ранняя идея создания компилятора компиляторов (compiler-compiler), програм­мы, вход которой являлся бы спецификацией языка и машины, а вы­ход — реализацией языка на машине, была в значительной степени осу­ществлена для этапа анализа и в меньшей степени — для этапа синтеза.

Если в логических терминах компилятор рассматривается как состоя­щий из этапов и фаз, физически он составлен из проходов (pass). Компи­лятор осуществляет проход каждый раз при считывании исходного кода или его представления. Многие компиляторы являются однопроходными, т.е. полный процесс компиляции полностью выполняется при однократ­ном чтении кода. В этом случае различные описанные фазы будут вы­полняться параллельно (что, как правило, является наиболее удобным), что устраняет необходимость сложной связи между различными прохо­дами. Ранние компиляторы были многопроходными (обычно 7-8 прохо­дов) по причине недостаточного объема памяти машин того времени. Для современных компиляторов проблем с объемом памяти уже (как правило) не существует, поэтому большинство из них являются однопро­ходными. В то же время некоторые языки, такие как ALGOL 68, невоз­можно откомпилировать за один проход. Это связано с тем, что инфор­мация, необходимая какой-то конкретной фазе, недоступна в той части исходного кода, в которой она используется. Требуемые многопроходные компиляторы можно легко описать как компиляторы с несколькими предварительными проходами, в течение которых информация собирает­ся и записывается в таблицы с последующим использованием на этапах анализа и синтеза.

Глава I. Процесс компиляции

1.5. Интегрированные среды разработки

Современные компиляторы часто являются не отдельными, автономны­ми инструментальными средствами, а представляют собой часть интегри­рованных сред разработки (Integrated Development Environment — IDE), которые иногда называют средами программирования. Помимо предос­тавления средства компиляции, современная среда IDE предлагает сред­ства языково-ориентированного редактирования, отладки, определения рабочих профилей программы, управления конфигурацией и т.д. Хоро­ший пример такой среды — Borland IDE для C/C++, которая в среде Windows предлагает средства для выполнения множества различных опе­раций, часть из которых выделена в перечисленные ниже группы.

  • Редактированиесо средствамивырезания, вставки, отмены опера­
    ции
    и т.п.
  • Поиск со средствами поиска текста, замены текста и локализации

функций в процессе отладки.

  • Обзорразличных окон, содержащих средства диагностики и другую
    информацию, связанную с текущим проектом, включая информа­
    цию по иерархии вызовов, расположению точек прерывания про­
    граммы, содержимого регистров, расположению переменных, ис­
    пользованию классов и т.д.
  • Управление проектом, включая запуск новых проектов, компиля­
    цию и связывание различных компонентов проекта при раздель­
    ном контроле средств компиляции и сборочных файлов.
  • Отладку для возможности запуска программы в обычном режиме
    или режиме отладки со средствами пошагового выполнения, уста­
    новки точек прерывания, отслеживания значений выражений,
    просмотра таблиц символов и т.д.
  • Средства выполнения, связанные с IDE.

Borland Pascal IDE для Windows предлагает подобный интерфейс, что по­зволяет легко переходить^ одного языка на другой. Хотя подробный об­зор сред IDE выходит за круг рассматриваемых в книге вопросов, в даль­нейшем, время от времени, мы будем обращаться к инструментальным

Общая структура компилятора во многом зависит от его фазоюй структуры и структуры синтаксического анализатора, создающего основу большинства фаз, а структура синтаксического анализатора отражает свойства исходного языка. Обычно при проектировании компилятора необходимо руководство­ваться следующими нефункциональными требованиями.

  • Эффективная компиляция.
  • Минимальный размер компилятора.
  • Минимальная длина целевого кода.
  • Создание эффективного целевого кода.
  • Легкость переносимости.
  • Простота использования.
  • Практичность, что включает хорошие средства диагностики оши­
    бок и восстановления после ошибок.

Безусловно, одновременно удовлетворить всем вышеперечисленным

требованиям практически невозможно, поэтому некоторым из них при­ходится отдавать предпочтение. К примеру, легкость переносимости и простота использования может не согласовываться с требованием мини­мального размера компилятора, а создание эффективного целевого ко­да—с требованием эффективной компиляции.

В обучающих средах, например, эффективность компиляции и хоро­шие средства диагностики могут быть важнее создания эффективного це­левого кода,, тогда как для встроенных систем первоочередное значение имеет размер и эффективность целевого кода. Многие компиляторы раз­решают пользователю самому определять режим работы компилятора — степень оптимизации, выполнение проверок времени выполнения и т.д.

1.7. Использование инструментальных средств

При создании компиляторов используются два основных типа инстру­ментальных средств.

  • Генераторы лексическиханализаторов(lexical analyser generator).
  • Генераторы синтаксических анализаторов (syntax analyser generator,
    или parser generator).

На вход инструментального средства, которое создает лексический анализатор, поступает информация о лексической структуре языка (как из знаков составляются токены языка), а результатом его работы являет­ся лексический анализатор (например, программа на С) этого языка.

Графически данный процесс представлен на рис. 1.9.

На вход инструментального средства, создающего синтаксический анализатор, поступает синтаксическое определение языка, а результатом его работы является синтаксический анализатор (например, программа на С) этого языка. Графически этот процесс представлен на рис. 1.10.

В настоящее время разработаны генераторы синтаксических анализа­торов, поддерживающие наиболее распространенные методы грамматиче­ского разбора. Самым известным из генераторов синтаксических анали­заторов разбора является YACC на основе Unix, который обычно исполь­зуется совместно с генератором лексических анализаторов Unix,

Основы конструирования компиляторов. В.А.Серебряков, М.П.Галочкин

    Яков Алфимов 2 лет назад Просмотров:

1 Основы конструирования компиляторов В.А.Серебряков, М.П.Галочкин

2 2 Предисловие Предлагаемая вниманию читателя книга основана на курсе лекций, прочитанных на факультете вычислительной математики и кибернетики Московского государственного университета и факультете управления и прикладной математики Московского физико-технического института в гг. Авторы надеются, что издание книги восполнит существенный пробел в литературе на русском языке по разработке компиляторов. Содержание книги представляет собой классические разделы предмета: лексический и синтаксический анализ, организация памяти компилятора (таблицы символов) и периода исполнения (магазина), генерация кода. Рассматриваются некоторые средства автоматизации процесса разработки трансляторов, такие как LEX, YACC, СУПЕР, методы генерации оптимального кода. Сделана попытка на протяжении всего изложения провести единую атрибутную точку зрения на процесс разработки компилятора. В книге не затрагиваются чрезвычайно важные вопросы глобальной оптимизации и разработки компиляторов для машин с параллельной архитектурой. Авторы надеются восполнить эти пробелы в будущем. Книга будет полезной как студентам и аспирантам программистских специальностей, так и профессионалам в этих областях. Авторы с благодарностью примут все конструктивные замечания по содержанию книги. В.А.Серебряков, М.П.Галочкин,

3 Оглавление 1 Введение Место компилятора в программном обеспечении Структура компилятора Языки и их представление Алфавиты, цепочки и языки Представление языков Грамматики Формальное определение грамматики Типы грамматик и их свойства Лексический анализ Регулярные множества и выражения Конечные автоматы Алгоритмы построения конечных автоматов Построение недетерминированного конечного автомата по регулярному выражению Построение детерминированного конечного автомата по недетерминированному Построение детерминированного конечного автомата по регулярному выражению Построение детерминированного конечного автомата с минимальным числом состояний Регулярные множества и их представления Программирование лексического анализа Конструктор лексических анализаторов LEX Синтаксический анализ КС-грамматики и МП-автоматы Преобразования КС-грамматик Предсказывающий разбор сверху-вниз Алгоритм разбора сверху-вниз

4 4 ОГЛАВЛЕНИЕ Функции FIRST и F OLLOW Конструирование таблицы предсказывающего анализатора LL(1)-грамматики Удаление левой рекурсии Левая факторизация Рекурсивный спуск Восстановление после синтаксических ошибок Разбор снизу-вверх типа сдвиг-свертка Основа LR(1)-анализаторы Конструирование LR(1)-таблицы LR(1)-грамматики Восстановление после синтаксических ошибок Варианты LR-анализаторов Элементы теории перевода Преобразователи с магазинной памятью Синтаксически управляемый перевод Схемы синтаксически управляемого перевода Обобщенные схемы синтаксически управляемого перевода Атрибутные грамматики Определение атрибутных грамматик Классы атрибутных грамматик и их реализация Язык описания атрибутных грамматик Проверка контекстных условий Описание областей видимости и блочной структуры Занесение в среду и поиск объектов Организация таблиц символов Таблицы идентификаторов Таблицы расстановки Таблицы расстановки со списками Функции расстановки Таблицы на деревьях Реализация блочной структуры Сравнение методов реализации таблиц Промежуточное представление программы Представление в виде ориентированного графа Трехадресный код Линеаризованные представления Виртуальная машина Java Организация памяти

5 ОГЛАВЛЕНИЕ Набор команд виртуальной машины Организация информации в генераторе кода Уровень промежуточного представления Генерация кода Модельмашины Динамическая организация памяти Организация магазина со статической цепочкой Организация магазина с дисплеем Назначение адресов Трансляция переменных Трансляция целых выражений Трансляция арифметических выражений Трансляция логических выражений Выделение общих подвыражений Генерация оптимального кода методами синтаксического анализа Сопоставление образцов Синтаксический анализ для T-грамматик Выбор дерева вывода наименьшей стоимости Атрибутная схема для алгоритма сопоставления образцов Системы автоматизации построения трансляторов СистемаСУПЕР СистемаYacc

7 Глава 1 Введение 1.1 Место компилятора в программном обеспечении Компиляторы составляют существенную часть программного обеспечения ЭВМ. Это связано с тем, что языки высокого уровня стали основным средством разработки программ. Только очень незначительная часть программного обеспечения, требующая особой эффективности, программируется с помощью ассемблеров. В настоящее время распространено довольно много языков программирования. Наряду с традиционными языками, такими, как Фортран, широкое распространение получили так называемые универсальные языки (Паскаль, Си, Модула-2, Ада и другие), а также некоторые специализированные (например, язык обработки списочных структур Лисп). Кроме того, большое распространение получили языки, связанные с узкими предметными областями, такие, как входные языки пакетов прикладных программ. Для некоторых языков имеется довольно много реализаций. Например, реализаций Паскаля, Модулы-2 или Си для ЭВМ типа IBM PC на рынке десятки. С другой стороны, постоянно растущая потребность в новых компиляторах связана с бурным развитием архитектур ЭВМ. Это развитие идет по различным направлениям. Совершенствуются старые архитектуры как в концептуальном отношении, так и по отдельным, конкретным линиям. Это можно проиллюстрировать на примере микропроцессора Intel- 80X86. Последовательные версии этого микропроцессора 8086, 80186, 80286, 80386, 80486, отличаются не только техническими характеристиками, но и, что более важно, новыми возможностями и, значит, изменением (расширением) системы команд. Естественно, это требует новых компиляторов (или модификации старых). То же можно сказать о микропроцессорах Motorola 68010, 68020, 68030, В рамках традиционных последовательных машин возникает боль- 7

8 8 ГЛАВА 1. ВВЕДЕНИЕ шое число различных направлений архитектур. Примерами могут служить архитектуры CISC, RISC. Такие ведущие фирмы, как Intel, Motorola, Sun, начинают переходить на выпуск машин с RISC-архитектурами. Естественно, для каждой новой системы команд требуется полный набор новых компиляторов с распространенных языков. Наконец, бурно развиваются различные параллельные архитектуры. Среди них отметим векторные, многопроцессорные, с широким командным словом (вариантом которых являются суперскалярные ЭВМ). На рынке уже имеются десятки типов ЭВМ с параллельной архитектурой, начиная от супер-эвм (Cray, CDC и другие), через рабочие станции (например, IBM RS/6000) и кончая персональными (например, на основе микропроцессора I-860). Естественно, для каждой из машин создаются новые компиляторы для многих языков программирования. Здесь необходимо также отметить, что новые архитектуры требуют разработки совершенно новых подходов к созданию компиляторов, так что наряду с собственно разработкой компиляторов ведется и большая научная работа по созданию новых методов трансляции. 1.2 Структура компилятора Обобщенная структура компилятора и основные фазы компиляции показаны на рис На фазе лексического анализа входная программа, представляющая собой поток литер, разбивается на лексемы слова в соответствии с определениями языка. Основными формализмами, лежащим в основе реализации лексических анализаторов, являются конечные автоматы и регулярные выражения. Лексический анализатор может работать в двух основных режимах: либо как подпрограмма, вызываемая синтаксическим анализатором для получения очередной лексемы, либо как полный проход, результатом которого является файл лексем. В процессе выделения лексем лексический анализатор может как самостоятельно строить таблицы объектов (идентификаторов, строк, чисел и т.д.), так и выдавать значения для каждой лексемы при очередном к нему обращении. В этом случае таблицы объектов строятся в последующих фазах (например, в процессе синтаксического анализа). На этапе лексического анализа обнаруживаются некоторые (простейшие) ошибки (недопустимые символы, неправильная запись чисел, идентификаторов и др.). Основная задача синтаксического анализа разбор структуры программы. Как правило, под структурой понимается дерево, соответствующее разбору в контекстно-свободной грамматике языка. В настоящее время чаще всего используется либо LL(1)-анализ (и его вариант рекурсивный спуск), либо LR(1)-анализ и его варианты (LR(0), SLR(1), LALR(1) и другие). Рекурсивный спуск чаще используется при ручном программировании синтаксического анализатора, LR(1) при исполь-

9 1.2. СТРУКТУРА КОМПИЛЯТОРА 9 E_dkbq_kdbc ZgZeba Dhg_qgu_ Z\lhfZlu >bz]ghklbdz Ihlhde_dk_f lz[ebpuh[t_dlh\ KbglZdkbq_kdbc ZgZeba DK]jZffZlbdb >bz]ghklbdz >_j_\hjza[hjz lz[ebpuh[t_dlh\ Dhgl_dklguc ZgZeba :ljb[mlgu_ ]jzffzlbdb >bz]ghklbdz :ljb[mlbjh\zggh_^_j_\h lz[ebpuh[t_dlh\ =_g_jzpby ijhf_`mlhqgh]h ij_^klz\e_gby KMljZgkeypby Ijhf_`mlhqgZynhjfZ ij_nbdkgzyihkl nbdkgzyljhcdbb ^j HilbfbaZpby Ihlhdh\uc ZgZeba Ijhf_`mlhqgZynhjfZ hjb_glbjh\zgguc]jzn =_g_jzpbydh^z LZ[ebpuj_r_gbc ^bgzfbq_kdh_ ijh]jzffbjh\zgb_ H[t_dlgucfh^mev Рис. 1.1:

10 10 ГЛАВА 1. ВВЕДЕНИЕ зовании систем автоматического построения синтаксических анализаторов. Результатом синтаксического анализа является синтаксическое дерево со ссылками на таблицы объектов. В процессе синтаксического анализа также обнаруживаются ошибки, связанные со структурой программы. На этапе контекстного анализа выявляются зависимости между частями программы, которые не могут быть описаны контекстно-свободным синтаксисом. Это в основном связи описание-использование, в частности, анализ типов объектов, анализ областей видимости, соответствие параметров, метки и другие. В процессе контекстного анализа таблицы объектов пополняются информацией об описаниях (свойствах) объектов. Основным формализмом, использующимся при контекстном анализе, является аппарат атрибутных грамматик. Результатом контекстного анализа является атрибутированное дерево программы. Информация об объектах может быть как рассредоточена в самом дереве, так и сосредоточена в отдельных таблицах объектов. В процессе контекстного анализа также могут быть обнаружены ошибки, связанные с неправильным использованием объектов. Затем программа может быть переведена во внутреннее представление. Это делается для целей оптимизации и/или удобства генерации кода. Еще одной целью преобразования программы во внутреннее представление является желание иметь переносимый компилятор. Тогда только последняя фаза (генерация кода) является машинно-зависимой. В качестве внутреннего представления может использоваться префиксная или постфиксная запись, ориентированный граф, тройки, четверки и другие. Фаз оптимизации может быть несколько. Оптимизации обычно делят на машинно-зависимые и машинно-независимые, локальные и глобальные. Часть машинно-зависимой оптимизации выполняется на фазе генерации кода. Глобальная оптимизация пытается принять во внимание структуру всей программы, локальная только небольших ее фрагментов. Глобальная оптимизация основывается на глобальном потоковом анализе, который выполняется на графе программы и представляет по существу преобразование этого графа. При этом могут учитываться такие свойства программы, как межпроцедурный анализ, межмодульный анализ, анализ областей жизни переменных и т.д. Наконец, генерация кода последняя фаза трансляции. Результатом ее является либо ассемблерный модуль, либо объектный (или загрузочный) модуль. В процессе генерации кода могут выполняться некоторые локальные оптимизации, такие как распределение регистров, выбор длинных или коротких переходов, учет стоимости команд при выборе конкретной последовательности команд. Для генерации кода разработаны различные методы, такие как таблицы решений, сопоставление образцов, включающее динамическое программирование, различ-

11 1.2. СТРУКТУРА КОМПИЛЯТОРА 11 ные синтаксические методы. Конечно, те или иные фазы транслятора могут либо отсутствовать совсем, либо объединяться. В простейшем случае однопроходного транслятора нет явной фазы генерации промежуточного представления и оптимизации, остальные фазы объединены в одну, причем нет и явно построенного синтаксического дерева.

12 12 ГЛАВА 1. ВВЕДЕНИЕ

13 Глава 2 Языки и их представление 2.1 Алфавиты, цепочки и языки Алфавит, или словарь это конечное множество символов. Для обозначения символов мы будем пользоваться цифрами, латинскими буквами и специальными литерами типа #, $. Пусть V алфавит. Цепочка в алфавите V это любая строка конечной длины, составленная из символов алфавита V. Синонимом цепочки являются предложение, строка и слово. Пустая цепочка (обозначается e) это цепочка, в которую не входит ни один символ. Конкатенацией цепочек x и y называется цепочка xy. Заметим, что xe = ex = x для любой цепочки x. Пусть x, y, z произвольные цепочки в некотором алфавите. Цепочка y называется подцепочкой цепочки xyz. Цепочки x и y называются, соответственно, префиксом и суффиксом цепочки xy. Заметим, что любой префикс или суффикс цепочки является подцепочкой этой цепочки. Кроме того, пустая цепочка является префиксом, суффиксом и подцепочкой для любой цепочки. Пример 2.1. Для цепочки abbba префиксом является любая цепочка из множества L 1 = , суффиксом является любая цепочка из множества L 2 = , подцепочкой является любая цепочка из множества L 1 L 2. Длиной цепочки w (обозначается w ) называется число символов в ней. Например, abababa =7, а e =0. Язык в алфавите V это некоторое множество цепочек в алфавите V. Пример 2.2. Пусть дан алфавит V = . Вот некоторые языки в алфавите V : а) L 1 = пустой язык; 13

14 14 ГЛАВА 2. ЯЗЫКИ И ИХ ПРЕДСТАВЛЕНИЕ б) L 2 = язык, содержащий только пустую цепочку (заметим, что L 1 и L 2 различные языки); в) L 3 = язык, содержащий цепочки из a и b, длина которых не превосходит 2; г) L 4 язык, включающий всевозможные цепочки из a и b, содержащие четное число a и четное число b; д) L 5 = 0> язык цепочек из a, длины которых представляют собой квадраты натуральных чисел. Два последних языка содержат бесконечное число цепочек. Введем обозначение V для множества всех цепочек в алфавите V, включая пустую цепочку. Каждый язык в алфавите V является подмножеством V. Для обозначения множества всех цепочек в алфавите V, кроме пустой цепочки, будем использовать V +. Пример 2.3. Пусть V = <0, 1>. Тогда V = , V + = <0, 1, 00, 01, 10, 11, 000. >. Введем некоторые операции над языками. Пусть L 1 и L 2 языки в алфавите V. Конкатенацией языков L 1 и L 2 называется язык L 1 L 2 = . Пусть L язык в алфавите V. Итерацией языка L называется язык L, определяемый следующим образом: (1) L 0 = ; (2) L n = LL n 1, n 1; (3) L = n=0 L n. Пример 2.4. Пусть L 1 = и L 2 = . Тогда L 1L 2 = ,и L 1 = . Большинство языков, представляющих интерес, содержат бесконечное число цепочек. При этом возникают три важных вопроса. Во-первых, как представить язык (т.е. специфицировать входящие в него цепочки)? Если язык содержит только конечное множество цепочек, ответ прост. Можно просто перечислить его цепочки. Если язык бесконечен, необходимо найти для него конечное представление. Это конечное представление, в свою очередь, будет строкой символов над некоторым алфавитом вместе с некоторой интерпретацией, связывающей это представление с языком.

15 2.2. ПРЕДСТАВЛЕНИЕ ЯЗЫКОВ 15 Во-вторых, для любого ли языка существует конечное представление? Можно предположить, что ответ отрицателен. Мы увидим, что множество всех цепочек над алфавитом счетно. Язык это любое подмножество цепочек. Из теории множеств известно, что множество всех подмножеств счетного множества несчетно. Хотя мы и не дали строгого определения того, что является конечным представлением, интуитивно ясно, что любое разумное определение конечного представления ведет только к счетному множеству конечных представлений, поскольку нужно иметь возможность записать такое конечное представление в виде строки символов конечной длины. Поэтому языков значительно больше, чем конечных представлений. В-третьих, можно спросить, какова структура тех классов языков, для которых существует конечное представление? 2.2 Представление языков Процедура это конечная последовательность инструкций, которые могут быть механически выполнены. Примером может служить машинная программа. Процедура, которая всегда заканчивается, называется алгоритмом. Один из способов представления языка дать алгоритм, определяющий, принадлежит ли цепочка языку. Более общий способ состоит в том, чтобы дать процедуру, которая останавливается с ответом да для цепочек, принадлежащих языку, и либо останавливается с ответом нет, либо вообще не останавливается для цепочек, не принадлежащих языку. Говорят, что такая процедура или алгоритм распознает язык. Такой метод представляет язык с точки зрения распознавания. Язык можно также представить методом порождения. А именно, можно дать процедуру, которая систематически порождает в определенном порядке цепочки языка. Если мы можем распознать цепочки языка над алфавитом V либо с помощью процедуры, либо с помощью алгоритма, то мы можем и генерировать язык, поскольку мы можем систематически генерировать все цепочки из V, проверять каждую цепочку на принадлежность языку и выдавать список только цепочек языка. Но если процедура не всегда заканчивается при проверке цепочки, мы не сдвинемся дальше первой цепочки, на которой процедура не заканчивается. Эту проблему можно обойти, организовав проверку таким образом, чтобы процедура никогда не продолжала проверять одну цепочку бесконечно. Для этого введем следующую конструкцию. Предположим, что V имеет p символов. Мы можем рассматривать цепочки из V как числа, представленные в базисе p, плюс пустая цепочка e. Можно занумеровать цепочки в порядке возрастания длины и в числовом порядке для цепочек одинаковой длины. Такая нумерация для цепочек языка приведена на рис. 2.1, а.

16 16 ГЛАВА 2. ЯЗЫКИ И ИХ ПРЕДСТАВЛЕНИЕ Пусть P процедура для проверки принадлежности цепочки языку L. Предположим, что P может быть представлена дискретными шагами, так что имеет смысл говорить об i-ом шаге процедуры для любой данной цепочки. Прежде чем дать процедуру перечисления цепочек языка L, дадим процедуру нумерации пар положительных чисел. Все упорядоченные пары положительных чисел (x, y) можно отобразить на множество положительных чисел следующей формулой: z =(x + y 1)(x + y 2)/2+y Пары целых положительных чисел можно упорядочить в соответствии со значением z (рис. 2.1, б). 1 e 2 a 3 b 4 c 5 aa 6 ab 7 ac 8 ba 9 bb а y x z(x, y) б Рис. 2.1: Теперь можно дать процедуру перечисления цепочек L. Нумеруем упорядоченные пары целых положительных чисел (1,1), (2,1), (1,2), (3,1), (2,2). При нумерации пары (i, j) генерируем i-ю цепочку из V и применяем к цепочке первые j шагов процедуры P. Как только мы определили, что сгенерированная цепочка принадлежит L, добавляем цепочку к списку элементов L. Если цепочка i принадлежит L, это будет определено P за j шагов для некоторого конечного j. При перечислении (i, j) будет сгенерирована цепочку с номером i. Легко видеть, что эта процедура перечисляет все цепочки L. Если мы имеем процедуру генерации цепочек языка, то мы всегда можем построить процедуру распознавания предложений языка, но не всегда алгоритм. Для определения того, принадлежит ли x языку L, просто нумеруем предложения L и сравниваем x с каждым предложением. Если сгенерировано x, процедура останавливается, распознав, что x принадлежит L. Конечно, если x не принадлежит L, процедура никогда не закончится. Язык, предложения которого могут быть сгенерированы процедурой, называется рекурсивно перечислимым. Язык рекурсивно перечислим, если имеется процедура, распознающая предложения языка. Говорят,

17 2.3. ГРАММАТИКИ 17 что язык рекурсивен, если существует алгоритм для распознавания языка. Класс рекурсивных языков является собственным подмножеством класса рекурсивно перечислимых языков. Мало того, существуют языки, не являющиеся даже рекурсивно перечислимыми. 2.3 Грамматики Формальное определение грамматики Для нас наибольший интерес представляет одна из систем генерации языков грамматики. Понятие грамматики изначально было формализовано лингвистами при изучении естественных языков. Предполагалось, что это может помочь при их автоматической трансляции. Однако, наилучшие результаты в этом направлении достигнуты при описании не естественных языков, а языков программирования. Примером может служить способ описания синтаксиса языков программирования при помощи БНФ формы Бэкуса-Наура. Определение. Грамматика это четверка G =(N,T,P,S), где (1) N алфавит нетерминальных символов; (2) T алфавит терминальных символов, N T = ; (3) P конечное множество правил вида α β, где α (N T ) +, β (N T ) ; (4) S N начальный символ (или аксиома) грамматики. Мы будем использовать большие латинские буквы для обозначения нетерминальных символов, малые латинские буквы из начала алфавита для обозначения терминальных символов, малые латинские буквы из конца алфавита для обозначения цепочек из T и, наконец, малые греческие буквы для обозначения цепочек из (N T ). Будем использовать также сокращенную запись A α 1 α 2. α n для обозначения группы правил A α 1,A α 2. A α n. Определим на множестве (N T ) бинарное отношение выводимости следующим образом: если δ γ P,тоαδβ αγβ для всех α, β (N T ). Если α 1 α 2, то говорят, что цепочка α 2 непосредственно выводима из α 1. Мы будем использовать также рефлексивно-транзитивное и транзитивное замыкания отношения, а также его степень k 0 (обозначаемые соответственно, + и k ). Если α 1 α 2 (α 1 + α 2, α 1 k α 2 ), то говорят, что цепочка α 2 выводима (нетривиально выводима, выводима за k шагов)изα 1. Если α k β (k 0), то существует последовательность шагов γ 0 γ 1 γ 2. γ k 1 γ k

18 18 ГЛАВА 2. ЯЗЫКИ И ИХ ПРЕДСТАВЛЕНИЕ где α = γ 0 и β = γ k. Последовательность цепочек γ 0,γ 1,γ 2. γ k в этом случае называют выводом β из α. Сентенциальной формой грамматики G называется цепочка, выводимая из ее начального символа. Языком, порождаемым грамматикой G (обозначается L(G)), называется множество всех ее терминальных сентенциальных форм, т.е. L(G) = Грамматики G 1 и G 2 называются эквивалентными, если они порождают один и тот же язык, т.е. L(G 1 )=L(G 2 ). Пример 2.5. Грамматика G =(, , P, S), где P = , порождает язык L(G) =0>. Действительно, применяем n 1 раз правило 1 и получаем a n 1 S(BC) n 1, затем один раз правило 2 и получаем a n (BC) n, затем n(n 1)/2 раз правило 3 и получаем a n B n C n. Затем используем правило 4 и получаем a n bb n 1 C n. Затем применяем n 1 раз правило 5 и получаем a n b n C n. Затем применяем правило 6 и n 1 раз правило 7 и получаем a n b n c n. Можно показать, что язык L(G) состоит из цепочек только такого вида. Пример 2.6. Рассмотрим грамматику G =(, <0, 1>, , S). Легко видеть, что цепочка L(G), так как существует вывод S 0S1 00S Нетрудно показать, что грамматика порождает язык L(G) =<0 n 1>0>. Пример 2.7. Рассмотрим грамматику G = (, <0, 1>, ,S). Нетрудно показать, что грамматика порождает язык L(G) = <0 n 1 m n,>0> Типы грамматик и их свойства Рассмотрим классификацию грамматик (предложенную Н.Хомским), основанную на виде их правил. Определение. Пусть дана грамматика G =(N,T,P,S). Тогда (1) если правила грамматики не удовлетворяют никаким ограничениям, то ее называют грамматикой типа 0, или грамматикой без ограничений. (2) если а) каждое правило грамматики, кроме S e, имеет вид α β, где α β,и

19 2.3. ГРАММАТИКИ 19 б) в том случае, когда S e P, символ S не встречается в правых частях правил, то грамматику называют грамматикой типа 1, или неукорачивающей. (3) если каждое правило грамматики имеет вид A β, где A N, β (N T ), то ее называют грамматикой типа 2, или контекстносвободной (КС-грамматикой). (4) если каждое правило грамматики имеет вид либо A xb, либо A x, где A, B N, x T то ее называют грамматикой типа 3, или праволинейной. Легко видеть, что грамматика в примере 2.5 неукорачивающая, в примере 2.6 контекстно-свободная, в примере 2.7 праволинейная. Язык, порождаемый грамматикой типа i, называют языком типа i. Язык типа 0 называют также языком без ограничений, язык типа 1 контекстно-зависимым (КЗ), язык типа 2 контекстно-свободным (КС), язык типа 3 праволинейным. Теорема 2.1. Каждый контекстно-свободный язык может быть порожден неукорачивающей грамматикой. Доказательство. Пусть L контекстно-свободный язык. Тогда существует контекстно-свободная грамматика G = (N,T,P,S), порождающая L. Построим новую грамматику G =(N,T,P,S ) следующим образом: 1. Если в P есть правило вида A α 0 B 1 α 1. B k α k, где k 0, B i + e для 1 i k, и ни из одной цепочки α j (0 j k) не выводится e, то включить в P все правила (кроме A e) вида A α 0 X 1 α 1. X k α k где X i это либо B i, либо e. 2. Если S + e, то включить в P правила S S, S e и положить N = N . В противном случае положить N = N и S = S. Легко видеть, что G неукорачивающая грамматика. Можно показать по индукции, что L(G )=L(G). Пусть K i класс всех языков типа i. Доказано, что справедливо следующее (строгое) включение: K 3 K 2 K 1 K 0. Заметим, что если язык порождается некоторой грамматикой, это не означает, что он не может быть порожден грамматикой с более сильными ограничениями на правила. Приводимый ниже пример иллюстрирует этот факт.

20 20 ГЛАВА 2. ЯЗЫКИ И ИХ ПРЕДСТАВЛЕНИЕ Пример 2.8. Рассмотрим грамматику G = (, <0, 1>, , S). Эта грамматика является контекстносвободной. Легко показать, что L(G) = <0 n 1 m n,>0>. Однако, в примере 2.7 приведена праволинейная грамматика, порождающая тот же язык. Покажем что существует алгоритм, позволяющий для произвольного КЗ-языка L в алфавите T, и произвольной цепочки w T определить, принадлежит ли w языку L. Теорема 2.2. Каждый контекстно-зависимый язык является рекурсивным языком. Доказательство. Пусть L контекстно-зависимый язык. Тогда существует некоторая неукорачивающая грамматика G =(N, T, P, S), порождающая L. Пусть w T и w = n. Если n =0, т.е. w = e, то принадлежность w L проверяется тривиальным образом. Так что будем предполагать, что n>0. Определим множество T m как множество строк u (N T ) + длины не более n таких, что вывод S u имеет не более m шагов. Ясно, что T 0 = . Легко показать, что T m можно получить из T m 1 просматривая, какие строки с длиной, меньшей или равной n можно вывести из строк из T m 1 применением одного правила, т.е. T m = T m 1 . Если S u и u n, тоu T m для некоторого m. Если из S не выводится u или u >n,тоuне принадлежит T m ни для какого m. Очевидно, что T m T m 1 для всех m 1. Поскольку T m зависит только от T m 1, если T m = T m 1,тоT m = T m+1 = T m+2 =. Процедура будет вычислять T 1, T 2, T 3. пока для некоторого m не окажется T m = T m 1. Если w не принадлежит T m, то не принадлежит и L(G), поскольку для j>mвыполнено T j = T m. Если w T m,тоs w. Покажем, что существует такое m, что T m = T m 1. Поскольку для каждого i 1 справедливо T i T i 1, то если T i T i 1, то число элементов в T i по крайней мере на 1 больше, чем в T i 1. Пусть N T = k. Тогда число строк в (N T ) + длины меньшей или равной n равно k + k k n nk n. Только эти строки могут быть в любом T i. Значит, T m = T m 1 для некоторого m nk n. Таким образом, процедура, вычисляющая T i для всех i 1 до тех пор, пока не будут найдены два равных множества, гарантированно заканчивается, значит, это алгоритм.

21 Глава 3 Лексический анализ Основная задача лексического анализа разбить входной текст, состоящий из последовательности одиночных символов, на последовательность слов, или лексем, т.е. выделить эти слова из непрерывной последовательности символов. Все символы входной последовательности с этой точки зрения разделяются на символы, принадлежащие каким-либо лексемам, и символы, разделяющие лексемы (разделители). В некоторых случаях между лексемами может и не быть разделителей. С другой стороны, в некоторых языках лексемы могут содержать незначащие символы (например, символ пробела в Фортране). В Си разделительное значение символов-разделителей может блокироваться ( \ в конце строки внутри «. «). Обычно все лексемы делятся на классы. Примерами таких классов являются числа (целые, восьмеричные, шестнадцатиричные, действительные и т.д.), идентификаторы, строки. Отдельно выделяются ключевые слова и символы пунктуации (иногда их называют символы-ограничители). Как правило, ключевые слова это некоторое конечное подмножество идентификаторов. В некоторых языках (например, ПЛ/1) смысл лексемы может зависеть от ее контекста и невозможно провести лексический анализ в отрыве от синтаксического. С точки зрения дальнейших фаз анализа лексический анализатор выдает информацию двух сортов: для синтаксического анализатора, работающего вслед за лексическим, существенна информация о последовательности классов лексем, ограничителей и ключевых слов, а для контекстного анализа, работающего вслед за синтаксическим, важна информация о конкретных значениях отдельных лексем (идентификаторов, чисел и т.д.). Таким образом, общая схема работы лексического анализатора такова. Сначала выделяется отдельная лексема (возможно, используя символыразделители). Ключевые слова распознаются либо явным выделением непосредственно из текста, либо сначала выделяется идентификатор, а затем делается проверка на принадлежность его множеству ключевых 21

22 22 ГЛАВА 3. ЛЕКСИЧЕСКИЙ АНАЛИЗ слов. Если выделенная лексема является ограничителем, то он (точнее, некоторый его признак) выдается как результат лексического анализа. Если выделенная лексема является ключевым словом, то выдается признак соответствующего ключевого слова. Если выделенная лексема является идентификатором выдается признак идентификатора, а сам идентификатор сохраняется отдельно. Наконец, если выделенная лексема принадлежит какому-либо из других классов лексем (например, лексема представляет собой число, строку и т.д.), то выдается признак соответствующего класса, а значение лексемы сохраняется отдельно. Лексический анализатор может быть как самостоятельной фазой трансляции, так и подпрограммой, работающей по принципу дай лексему. В первом случае (рис. 3.1, а) выходом анализатора является файл лексем, во втором (рис. 3.1, б) лексема выдается при каждом обращении к анализатору (при этом, как правило, признак класса лексемы возвращается как результат функции лексический анализатор, а значение лексемы передается через глобальную переменную). С точки зрения обработки значений лексем, анализатор может либо просто выдавать значение каждой лексемы, и в этом случае построение таблиц объектов (идентификаторов, строк, чисел и т.д.) переносится на более поздние фазы, либо он может самостоятельно строить таблицы объектов. В этом случае в качестве значения лексемы выдается указатель на вход в соответствующую таблицу. LbiAgZq_gb_ KbglZgZebaZlhj Lbi e_dk_fu AgZq_gb_ LZ[ebpZ E_dkZgZebaZlhj Z [ Рис. 3.1: Работа лексического анализатора задается некоторым конечным автоматом. Однако, непосредственное описание конечного автомата неудобно с практической точки зрения. Поэтому для задания лексического анализатора, как правило, используется либо регулярное выражение, либо праволинейная грамматика. Все три формализма (конечных автоматов,

24 24 ГЛАВА 3. ЛЕКСИЧЕСКИЙ АНАЛИЗ (б) (pq) регулярное выражение, обозначающее регулярное множество PQ, (в) (p ) регулярное выражение, обозначающее регулярное множество P ; (5) ничто другое не является регулярным выражением в алфавите T. Мы будем опускать лишние скобки в регулярных выражениях, договорившись о том, что операция итерации имеет наивысший приоритет, затем идет операции конкатенации, наконец, операция объединения имеет наименьший приоритет. Кроме того, мы будем пользоваться записью p + для обозначения pp. Таким образом, запись (a ((ba)(a ))) эквивалентна a ba +. Наконец, мы будем использовать запись L(r) для регулярного множества, обозначаемого регулярным выражением r. Пример 3.1. Несколько примеров регулярных выражений и обозначаемых ими регулярных множеств: а) a(e a) b обозначает множество ; б) a(a b) обозначает множество всевозможных цепочек, состоящих из a и b, начинающихся с a; в) (a b) (a b)(a b) обозначает множество всех непустых цепочек, состоящих из a и b, т.е. множество + ; г) ((0 1)(0 1)(0 1)) обозначает множество всех цепочек, состоящих из нулей и единиц, длины которых делятся на 3. Ясно, что для каждого регулярного множества можно найти регулярное выражение, обозначающее это множество, и наоборот. Более того, для каждого регулярного множества существует бесконечно много обозначающих его регулярных выражений. Будем говорить, что регулярные выражения равны или эквивалентны (=), если они обозначают одно и то же регулярное множество. Существует ряд алгебраических законов, позволяющих осуществлять эквивалентное преобразование регулярных выражений. Лемма. Пусть p, q и r регулярные выражения. Тогда справедливы следующие соотношения: (1) p q = q p; (7) pe = ep = p; (2) = e; (8) p = p = ; (3) p (q r) =(p q) r; (9) p = p p ; (4) p(qr) =(pq)r; (10) (p ) = p ; (5) p(q r) = pq pr; (11) p p = p; (6) (p q)r = pr qr; (12) p = p. Следствие. Для любого регулярного выражения существует эквивалентное регулярное выражение, которое либо есть, либо не содержит в своей записи.

25 3.2. КОНЕЧНЫЕ АВТОМАТЫ 25 В дальнейшем будем рассматривать только регулярные выражения, не содержащие в своей записи. При практическом описании лексических структур бывает полезно сопоставлять регулярным выражениям некоторые имена, и ссылаться на них по этим именам. Для определения таких имен мы будем использовать запись вида d 1 = r 1 d 2 = r 2. d n = r n где d i различные имена, а каждое r i регулярное выражение над символами T , т.е. символами основного алфавита и ранее определенными символами (именами). Таким образом, для любого r i можно построить регулярное выражение над T, повторно заменяя имена регулярных выражений на обозначаемые ими регулярные выражения. Пример 3.2. Использование имен для регулярных выражений. а) Регулярное выражение для множества идентификаторов. Letter = a b c. x y z Digit = >

26 26 ГЛАВА 3. ЛЕКСИЧЕСКИЙ АНАЛИЗ (5) F Q множество заключительных состояний. Работа конечного автомата представляет собой некоторую последовательность шагов, или тактов. Такт определяется текущим состоянием управляющего устройства и входным символом, обозреваемым в данный момент входной головкой. Сам шаг состоит из изменения состояния и, возможно, сдвига входной головки на одну ячейку вправо (рис. 3.2). Khklhygb_ IjhqblZggZyqZklv \oh^ghcp_ihqdb D L_dmsbc \oh^ghc kbf\he G_ijhqblZggZyqZklv \oh^ghcp_ihqdb Рис. 3.2: Недетерминизм автомата заключается в том, что, во-первых, находясь в некотором состоянии и обозревая текущий символ, автомат может перейти в одно из, вообще говоря, нескольких возможных состояний, и во-вторых, автомат может делать переходы по e. Пусть M = (Q,T,D,q 0,F) НКА. Конфигурацией автомата M называется пара (q, w) Q T, где q текущее состояние управляющего устройства, а w цепочка символов на входной ленте, состоящая из символа под головкой и всех символов справа от него. Конфигурация (q 0,w) называется начальной, а конфигурация (q, e), где q F заключительной (или допускающей). Пусть M =(Q,T,D,q 0,F) НКА. Тактом автомата M называется бинарное отношение, определенное на конфигурациях M следующим образом: если p D(q, a), где a T , то(q, aw) (p, w) для всех w T. Будем обозначать символом + ( ) транзитивное (рефлексивнотранзитивное) замыкание отношения. Говорят, что автомат M допускает цепочку w, если (q 0,w) (q, e) для некоторого q F. Языком, допускаемым (распознаваемым, определяемым) автоматом M, (обозначается L(M)), называется множество входных цепочек, допускаемых автоматом M. Т.е. L(M) =.

27 3.2. КОНЕЧНЫЕ АВТОМАТЫ 27 Важным частным случаем недетерминированного конечного автомата является детерминированный конечный автомат, который на каждом такте работы имеет возможность перейти не более чем в одно состояние и не может делать переходы по e. Пусть M =(Q,T,D,q 0,F) НКА. Будем называть M детерминированным конечным автоматом (ДКА), если выполнены следующие два условия: (1) D(q, e) = для любого q Q,и (2) D(q, a) содержит не более одного элемента для любых q Q и a T. Так как функция переходов ДКА содержит не более одного элемента для любой пары аргументов, для ДКА мы будем пользоваться записью D(q, a) =p вместо D(q, a) =

. Конечный автомат может быть изображен графически в виде диаграммы, представляющей собой ориентированный граф, в котором каждому состоянию соответствует вершина, а дуга, помеченная символом a T , соединяет две вершины p и q, если p D(q, a). На диаграмме выделяются начальное и заключительные состояния (в примерах ниже, соответственно, входящей стрелкой и двойным контуром). Пример 3.3. Пусть L = L(r), где r =(a b) a(a b)(a b). а) Недетерминированный конечный автомат M, допускающий язык L: M = <<1, 2, 3, 4>, ,d,1, <4>>, где функция переходов D определяется так: D(1,a)=<1, 2>, D(3,a)=<4>, D(2,a)=<3>, D(3,b)=<4>, D(2,b)=<3>. Диаграмма автомата приведена на рис. 3.3, а. б) Детерминированный конечный автомат M, допускающий язык L: M = <<1, 2, 3, 4, 5, 6, 7, 8>, ,d,1, <3, 5, 6, 8>>, где функция переходов D определяется так: D(1,a)=2, D(5,a)=8, D(1,b)=1, D(5,b)=6, D(2,a)=4, D(6,a)=2, D(2,b)=7, D(6,b)=1, D(3,a)=3, D(7,a)=8, D(3,b)=5, D(7,b)=6, D(4,a)=3, D(8,a)=4, D(4,b)=5, D(8,b)=7. Диаграмма автомата приведена на рис. 3.3, б. Пример 3.4. Диаграмма ДКА, допускающего множество чисел в десятичной записи, приведена на рис. 3.4.

28 28 ГЛАВА 3. ЛЕКСИЧЕСКИЙ АНАЛИЗ E D D DE E DE D E E D D D D E E E D E D D E Z [ Рис. 3.3: Пример 3.5. Анализ цепочек. а) При анализе цепочки w = ababa автомат из примера 3.3, а, может сделать следующую последовательность тактов: (1, ababa) (1, baba) (1, aba) (2,ba) (3,a) (4,e). Состояние 4 является заключительным, следовательно, цепочка w допускается этим автоматом. б) При анализе цепочки w = ababab автомат из примера 3.3, б, должен сделать следующую последовательность тактов: (1, ababab) (2, babab) (7, abab) (8, bab) (7,ab) (8,b) (7,e). Так как состояние 7 не является заключительным, цепочка w не допускается этим автоматом. ( ‘LJLW ‘LJLW ‘LJLW ( ‘LJLW ‘LJLW ‘LJLW ‘LJLW Рис. 3.4:

29 3.3. АЛГОРИТМЫ ПОСТРОЕНИЯ КОНЕЧНЫХ АВТОМАТОВ Алгоритмы построения конечных автоматов Построение недетерминированного конечного автомата по регулярному выражению Рассмотрим алгоритм построения по регулярному выражению недетерминированного конечного автомата, допускающего тот же язык. Алгоритм 3.1. Построение недетерминированного конечного автомата по регулярному выражению. Вход. Регулярное выражение r в алфавите T. Выход. НКА M, такой что L(M) =L(r). Метод. Автомат для выражения строится композицией из автоматов, соответствующих подвыражениям. На каждом шаге построения строящийся автомат имеет в точности одно заключительное состояние, в начальное состояние нет переходов из других состояний и нет переходов из заключительного состояния в другие. 1. Для выражения e строится автомат L H I Рис. 3.5: 2. Для выражения a (a T ) строится автомат L D I Рис. 3.6: 3. Пусть M(s) и M(t) НКА для регулярных выражений s и t соответственно. а) Для выражения s t автомат M(s t) строится как показано на рис Здесь i новое начальное состояние и f новое заключительное состояние. Заметим, что имеет место переход по e из i в начальные состояния M(s) и M(t) и переход по e из заключительных состояний M(s) и M(t) в f. Начальное и заключительное состояния автоматов M(s) и M(t) не являются таковыми для автомата M(s t).

30 30 ГЛАВА 3. ЛЕКСИЧЕСКИЙ АНАЛИЗ H 0V H L I H 0W H Рис. 3.7: б) Для выражения st автомат M(st) строится следующим образом: L 0V 0W I Рис. 3.8: Начальное состояние M(s) становится начальным для нового автомата, а заключительное состояние M(t) становится заключительным для нового автомата. Начальное состояние M(t) и заключительное состояние M(s) сливаются, т.е. все переходы из начального состояния M(t) становятся переходами из заключительного состояния M(s). В новом автомате это объединенное состояние не является ни начальным, ни заключительным. в) Для выражения s автомат M(s ) строится следующим образом: L H H 0V H I H Рис. 3.9:

31 3.3. АЛГОРИТМЫ ПОСТРОЕНИЯ КОНЕЧНЫХ АВТОМАТОВ 31 Здесь i новое начальное состояние, а f новое заключительное состояние Построение детерминированного конечного автомата по недетерминированному Рассмотрим алгоритм построения по недетерминированному конечному автомату детерминированного конечного автомата, допускающего тот же язык. Алгоритм 3.2. Построение детерминированного конечного автомата по недетерминированному. Вход. НКА M =(Q,T,D,q 0,F). Выход. ДКА M =(Q,T,D,q 0,F ), такой что L(M) =L(M ). Метод. Каждое состояние результирующего ДКА это некоторое множество состояний исходного НКА. В алгоритме будут использоваться следующие функции: e-closure(r) (R Q) множество состояний НКА, достижимых из состояний, входящих в R, посредством только переходов по e, т.е. множество S =

q R move(r, a) (R Q) множество состояний НКА, в которые есть переход на входе a для состояний из R, т.е. множество S =

q R Вначале Q и D пусты. Выполнить шаги 1-4: (1) Определить q 0 = e-closure(). (2) Добавить q 0 в Q как непомеченное состояние. (3) Выполнить следующую процедуру: while (в Q есть непомеченное состояние R)< пометить R; for (каждого входного символа a T )< S = e-closure(move(r, a)); if (S )< if (S / Q ) добавить S в Q как непомеченное состояние; определить D (R, a) =S;

32 32 ГЛАВА 3. ЛЕКСИЧЕСКИЙ АНАЛИЗ > > > (4) Определить F = . Пример 3.6. Результат применения алгоритма 3.2 приведен на рис H H H D H H D E E H E H H D $ D % E D & D E D E ‘ E ( E Рис. 3.10: Построение детерминированного конечного автомата по регулярному выражению Приведем теперь алгоритм построения по регулярному выражению детерминированного конечного автомата, допускающего тот же язык [10]. Пусть дано регулярное выражение r в алфавите T. К регулярному выражению r добавим маркер конца: (r)#. Такое регулярное выражение будем называть пополненным. В процессе своей работы алгоритм будет использовать пополненное регулярное выражение.

33 3.3. АЛГОРИТМЫ ПОСТРОЕНИЯ КОНЕЧНЫХ АВТОМАТОВ 33 Алгоритм будет оперировать с синтаксическим деревом для пополненного регулярного выражения (r)#, каждый лист которого помечен символом a T , а каждая внутренняя вершина помечена знаком одной из операций: (конкатенация), (объединение), (итерация). Каждому листу дерева (кроме e-листьев) припишем уникальный номер, называемый позицией, и будем использовать его, с одной стороны, для ссылки на лист в дереве, и, с другой стороны, для ссылки на символ, соответствующий этому листу. Заметим, что если некоторый символ используется в регулярном выражении несколько раз, он имеет несколько позиций. Теперь, обходя дерево T снизу-вверх слева-направо, вычислим четыре функции: nullable, f irstpos, lastpos и f ollowpos. Функции nullable, firstpos и lastpos определены на узлах дерева, а followpos на множестве позиций. Значением всех функций, кроме nullable, является множество позиций. Функция f ollowpos вычисляется через три остальные функции. Функция f irstpos(n) для каждого узла n синтаксического дерева регулярного выражения дает множество позиций, которые соответствуют первым символам в подцепочках, генерируемых подвыражением с вершиной в n. Аналогично, lastpos(n) дает множество позиций, которым соответствуют последние символы в подцепочках, генерируемых подвыражениями с вершиной n. Для узла n, поддеревья которого (т.е. деревья, у которых узел n является корнем) могут породить пустое слово, определим nullable(n) =true, а для остальных узлов nullable(n)=f alse. Таблица для вычисления функций nullable, f irstpos и lastpos приведена на рис узел n nullable(n) firstpos(n) lastpos(n) лист e true лист i false (не e) nullable(u) /\ or f irstpos(u) f irstpos(v) lastpos(u) lastpos(v) uv nullable(v) nullable(u) if nullable(u) then if nullable(v) then /\ and f irstpos(u) f irstpos(v) lastpos(u) lastpos(v) u v nullable(v) else f irstpos(u) else lastpos(v) true f irstpos(v) lastpos(v) v Рис. 3.11: Пример 3.7. Синтаксическое дерево для пополненного регулярного выражения (a b) abb# с результатом вычисления функций firstpos и lastpos приведено

34 34 ГЛАВА 3. ЛЕКСИЧЕСКИЙ АНАЛИЗ ^` ^` ^` ^` ^` ^` ^` ^` ^`E ^` ^` ^` ^`E ^` ^`^` ^`D ^` ^` _ ^` ^`D ^` ^`E ^` Рис. 3.12: позиция f ollowpos 1 <1, 2, 3>2 <1, 2, 3>3 <4>4 <5>5 <6>6 Рис. 3.13: на рис Слева от каждого узла расположено значение firstpos, справа от узла значение lastpos. Заметим, что эти функции могут быть вычислены за один обход дерева. Если i позиция, то followpos(i) есть множество позиций j таких, что существует некоторая строка. cd. входящая в язык, описываемый регулярным выражением, такая, что позиция i соответствует этому вхождению c, а позиция j вхождению d. Функция f ollowpos может быть вычислена также за один обход дерева снизу-вверх по следующим двум правилам. 1. Пусть n внутренний узел с операцией (конкатенация), u и v его потомки. Тогда для каждой позиции i, входящей в lastpos(u), добавляем к множеству значений f ollowpos(i) множество f irstpos(v). 2. Пусть n внутренний узел с операцией (итерация), u его потомок. Тогда для каждой позиции i, входящей в lastpos(u), добавляем к множеству значений f ollowpos(i) множество f irstpos(u).

35 3.3. АЛГОРИТМЫ ПОСТРОЕНИЯ КОНЕЧНЫХ АВТОМАТОВ 35 Пример 3.8. Результат вычисления функции followpos для регулярного выражения из предыдущего примера приведен на рис Алгоритм 3.3. Прямое построение ДКА по регулярному выражению. Вход. Регулярное выражение r в алфавите T. Выход. ДКА M =(Q,T,D,q 0,F), такой что L(M) =L(r). Метод. Состояния ДКА соответствуют множествам позиций. Вначале Q и D пусты. Выполнить шаги 1-6: (1) Построить синтаксическое дерево для пополненного регулярного выражения (r)#. (2) Обходя синтаксическое дерево, вычислить значения функций nullable, f irstpos, lastpos и f ollowpos. (3) Определить q 0 = firstpos(root), где root корень синтаксического дерева. (4) Добавить q 0 в Q как непомеченное состояние. (5) Выполнить следующую процедуру: while (в Q есть непомеченное состояние R) < пометить R; for (каждого входного символа a T, такого, что в R имеется позиция, которой соответствует a)< пусть символ a в R соответствует позициям p 1. p n, и пусть S = followpos(p i ); 1 i n if (S )< if (S / Q) добавить S в Q как непомеченное состояние; определить D(R, a) =S; >> > (6) Определить F как множество всех состояний из Q, содержащих позиции, связанные с символом #. Пример 3.9. Результат применения алгоритма 3.3 для регулярного выражения (a b) abb приведен на рис

Благодарности Глава Процесс компиляции

страница 1/16
Дата 14.07.2020
Размер 3.51 Mb.
Тип Задача
Робин Хантер

Основные концепции компиляторов

Глава 1. Процесс компиляции

  1. Вступление
  2. Основные понятия
  3. Процесс компиляции
  4. Этапы, фазы и проходы
  5. Интегрированные среды разработки
  6. Проектирование компилятора
  7. Использование инструментальных средств
  8. Резюме

Дополнительная литература Упражнения

Глава 2. Определение языка

  1. Вступление
  2. Определяя синтаксис
  3. Грамматики
  4. Отличия регулярных и контекстно-свободных языков
  5. Порождения
  6. Неоднозначные грамматики
  7. Ограничения контекстно-свободных грамматик
  8. Задача синтаксического анализа
  9. Определение семантики

2.10. Резюме

Дополнительная литература Упражнения

Глава 3. Лексический анализ

  1. Вступление
  2. Основные понятия
  3. Распознавание символов
  4. Lex
  5. Другие применения Lex
  6. Взаимодействие с YACC
  7. Лексические затруднения
  8. Резюме
Дополнительная литература 79 Упражнения 79 Глава 4, Нисходящий синтаксический анализ 81 4.1. Вступление 81 4.2. Критерии принятия решений 81 4.3. 1Х(1)-грамматики 84 4.4. Рекурсивный спуск 89 9 4.5. Преобразования грамматик 96 10 4.5.1. Удаление левой рекурсии 96 4.5.2. Факторизация 98 11 4.6. Достоинства и недостатки ЬЦ1)-анализа 101 11 4.7. Введение действий в грамматику 102 11 4.8. Резюме 105 12 Дополнительная литература 106 15 Упражнения 106 22 22 Глава 5. Восходящий синтаксический анализ 109 23 5.1. Вступление 109 25 5.2. Основные понятия 109 25 5.3. Использование таблицы синтаксического анализа 113 26 5.4. Создание таблицы синтаксического анализа 120 5.5. Особенности LR-анализа 132 27 • 5.6. Введение в YACC 135 27 5.7. Вычисление метрик 140 27 5.8. Использование YACC 143 31 5.9. Резюме . 153 39 Дополнительная литература 154 41 Упражнения 154 42 47 Глава 6. Семантический анализ 157 51 6.1. Вступление 157 52 6.2. Не-контекстно-свободные характеристики языка 157 53 6.3. Таблицы компилятора 162 53 6.3.1. Таблицы символов 162 54 6.3.2. Таблицы типов 167 6.3.3. Другие таблицы 168 57 6.4. Реализация наследования в C++ 169 57 6.5. Резюме 170 57 Дополнительная литература 171 58 Упражнения 171 62 71 Глава 7. Распределение памяти 173 75 7.1. Вступление 173 76 7.2. Память 173 78 7.3. Статическая и динамическая память 176
  1. Адреса времени компиляции
  2. Куча
  3. Резюме .
    Дополнительная литература
    Упражнения

Глава 8. Генерация кода

  1. Вступление
  2. Создание промежуточного кода
  1. Трехадресный код
  2. Р-код •
  3. Байт-код

8.3. Создание машинного кода

  1. Выбор инструкций
  2. Распределение регистров
  3. Распределение регистров путем раскрашивания графа
  1. Оптимизация кода
  2. Генераторы генераторов кода
  3. Резюме

Дополнительная литература Упражнения

Приложение А. Решения упражнений

Глава 1 Глава 2 Глава 3 Глава 4 Глава 5 Глава 6 Глава 7 Глава 8

Литература Предметный указатель

197 197 198 201 203 206 208 208 213 215 219 220 220 220

223 224 226 230

232 233 234 234

Изучение компиляторов является центральным и одним из наиболее вос­требованных аспектов компьютерных наук. Написание компилятора тре­бует знания исходного языка и целевой машины и обеспечения их взаи­мосвязи. Наличие современного инструментального обеспечения осво­бождает программиста от многих утомительных, подверженных ошибкам моментов при создании компилятора.

Мое первое знакомство с компиляторами произошло в 1967 году на лекциях создателя ранних моделей компиляторов для языка ALGOL 60 Питера Наура (Peter Naur) в Университете Ньюкасла. Позднее, в 1974 го­ду, мне посчастливилось прослушать расширенный курс по конструиро­ванию компиляторов в Техническом университете Мюнхена (отдел Ф. Л. Бауэра (F. L. Bauer)). С тех пор я, с некоторыми перерывами, работаю с компиляторами и инструментами для их разработки.

Большинство теоретических разработок и методов для конструирования компиляторов возникло в 1970-х, а некоторые из них даже раньше. В то же время развитие языков программирования постоянно ставило перед создате­лями компиляторов новые задачи: от определения языка ALGOL 60 (ранние работы Наура в Дании, а также Ренделла (Randell) и Рассела (Russell) в Вели­кобритании) до удовлетворения потребностей возникших позже языка Ada и языков объектно-ориентированного программирования. Современные требо­вания Java к сетевой безопасности, эффективности и переносимости вновь ставят перед создателями компиляторов новые проблемы. В то же время по­явление Java Virtual Machine дает великолепный пример промежуточного языка, позволяющего проиллюстрировать различные аспекты генерации кода и распределения памяти.

Процесс создания компилятора соединяет в себе как творческую, так и рутинную работу. Он требует хорошей инструментальной поддержки, что от­четливо видно при изучении истории развития компиляторов. В наше время доступно множество инструментальных средств для создания компиляторов. Некоторые из них можно получить бесплатно через Internet, но на данный момент наиболее используемыми и распространенными инструментальными средствами являются Unix Lex и YACC (сейчас они могут применяться и на других платформах). В Internet доступны также бесплатные версии Lex и YACC, известные как Flex и Bisson. Также можно получить существующие версии turbo Pascal (изначально основанные на С).

Во многих книгах по компиляторам описываются средства Lex и YACC с примерами их использования, но лишь в немногих из них со­держится достаточно информации для того, чтобы читатель сам смог воспользоваться этими инструментами для решения своих задач. Именно поэтому одной из задач, поставленных при написании данной книги, яв-

Основным языком при написании различных алгоритмов на базе Lex и YACC является С. Данная книга прежде всего посвящена компиляции императивных языков, поэтому язык С также будет применяться в каче­стве исходного языка во многих примерах, описывающих различные ас­пекты компиляции. В то же время многие свойства языка, компиляцию которого мы желаем рассмотреть, не связаны с С, поэтому в таких случа­ях будут использоваться другие, более подходящие языки — FORTRAN, Pascal, Ada, ALGOL 68, C++, Java.

Первая часть книги посвящена этапу анализа процесса компиляции. После введения в процесс компиляции (глаю 1) следуют главы по опре­делению языка, лексическому анализу, нисходящему и восходящему син­таксическому анализу и семантическому анализу (главы 2—6). Более ко­роткая вторая часть книги посвящена этапу синтеза процесса компиля­ции. Она содержит две главы, в которых рассмотрено распределение памяти и генерация кода (главы 7—8). Каждая глава завершается серией упражнений, ответы на которые приведены в конце книги. Кроме того, в конце каждой главы помещен список литературы, рекомендуемой для дальнейшего изучения. Значение большинства технических терминов, используемых в книге, можно найти в глоссарии.

Данная книга рассчитана на односеместровый курс по компиляторам и их инструментальным средствам, подобный читаемому в Университете Стратк-лайда (University of Stratchclyde). Названный университетский курс также включает практические занятия, на которых студенты закрепляют навыки по использованию Lex и YACC. Как и другие книги серии «Основы вычисли­тельных систем», эта книга стремится подать все необходимые аспекты про­цесса компиляции, не пытаясь охватить всю область.

С особым удовольствием я выражаю свою признательность издательству Prentice Hall за помощь и поддержку в создании настоящей книги. Необ­ходимо также поблагодарить Бориса Когана (Boris Cogan) и Тамару Мат­вееву (Tamara Mafveeva) за их полезные комментарии к тексту. Благода­рю свою жену Кейт (Kate) за ее поддержку и терпение, а также за про­верку всей рукописи, которую она охотно выполнила. Благодарю рецензентов издательства и редактора серии Рея Велланда (Rey Welland) за их конструктивные замечания на разных этапах создания книги.

Робин Хан тер (Robin Hunter)

В этой главе будут определены основные понятия компилятора языка, его структура, функции и реализация. В частности, будут рассмотрены следующие вопросы.

« Взаимосвязь между различными языками, задействованными в ти­пичном компиляторе.

  • Типичная структура компиляторов.
  • Функции основных фаз компиляции.
  • Цели, которые ставятся при разработке компиляторов.
  • Роль инструментальных средств при разработке компилятора.
  • Возможная степень автоматизации разработки компилятора.

1.2. Основные понития

Программное обеспечение можно создавать с помощью множества язы­ков программирования. Ими могут быть традиционные императивные языки (COBOL, FORTRAN, Pascal, С), объектно-ориентированные язы­ки (C++, Smalltalk, Java), функциональные или логические языки (LISP, Prolog), языки четвертого поколения или визуальные языки (Visual C++, Visual Basic, Delphi). Задача компилятора состоит в преобразовании ори­ентированного на пользователя представления программного обеспече­ния в машинно-ориентированное (в котором происходит непосредствен­ное выполнение программы компьютером). Компиляторы — это изна­чально изощренные системы обработки текста, которые имеют много общего с другими инструментальными средствами обработки текста, на­писанными на языке программирования либо на естественном языке. Обрабатываемый ими текст может быть написан как вручную на обыч­ном языке, так и полуавтоматическим способом при использовании ви­зуальных языков или языков четвертого поколения.

Задача компилятора обычно рассматривается на двух этапах.

W

1, Этап анализа, на котором анализируется исходный текст.

2. Этап синтеза, на котором генерируется машинно-ориентированное
представление,

В дальнейшем вход этапа анализа будем называть исходным текстом или исходным кодом, а выход этапа синтеза — целевым текстом или целе­вым кодом. Преобразование исходного кода в целевой обычно называется процессом компиляции. Процесс компиляции осуществляет компилятор. Компилятор языка можно также назвать реализацией языка. Произведен­ный компилятором целевой код может иметь вид машинного кода для некоторой машины (компьютера) или ассемблерного кода, или некото­рого промежуточного кода, который в дальнейшем будет преобразован (уже с помощью других инструментальных средств) или в ассемблерный код, или л машинный код для некоторой машины. Возможен также ва­риант, когда промежуточный код непосредственно используется посред­ством интерпретатора,

Несмотря на то, что предлагаемая книга посвящена процессу компи­ляции, при случае будут рассматриваться и другие возможности приме­нения текстуального анализа. Следует отметить, что при рассмотрении компиляции большее внимание будет уделяться вопросам анализа, чем синтеза. Это связано с тем, что понятия стадии анализа обладают боль­шей степенью общности и применимости по сравнению с частными, за­висимыми от машины понятиями стадии синтеза.

Технологии компиляторов значительно развились со времени появле­ния компьютеров, и теперь стала возможной автоматизация многих ас­пектов процесса создания компилятора. Существующие инструменталь­ные средства позволяют автоматизировать создание анализаторов, хотя успехи по автоматизации создания генераторов кода намного скромнее. Вопросы возможной степени автоматизации будут рассматриваться в по­следующих главах, где с этой целью будут широко использованы средства генерации анализаторов Lex и YACC.

В основном языком создания компиляторов с помощью Lex и YACC является С. Поэтому в дальнейшем в качестве языка реализации (языка написания компилятора) будет подразумеваться именно С, и требуемые алгоритмы будут описываться на нем. Чтобы избежать частого перехода от одного языка к другому, реализуемым языком также будет считаться С. Впрочем, для описания отдельных моментов будут использоваться и другие языки, более удобные в этих конкретных случаях.


1.3. Процесс компиляции

Процесс компиляции представляет собой преобразование одного языка в другой, переход от исходного кода, на котором работает программист или который автоматически генерируется из некоторого высокоуровневого представления, к целевому коду, который выполняется на машине, воз-

можно, после некоторых преобразований. Схематически этот процесс изображен на рис. 1.1

Исходный Целевой
код Процесс компиляции код

Рис. 1.1.

Как уже упоминалось, процесс компиляции также включает третий язык — язык реализации. Им может быть тот же язык, что и исходный или целевой код, но это необязательно. По возможности, в качестве язы­ка написания компилятора выбирается наиболее удобный — либо с точ­ки зрения внутренних характеристик (например, подверженность ошиб­кам), либо с точки зрения доступности и совместимости с инструмен­тальными средствами.

Три языка, задействованных в реализации, удобно представить с помо­щью Т-диаграммы, содержащей каждый язык в отдельной ветви. На рис. 1.2 изображен компилятор, который написан на С и преобразует Java в байт-код (язык, интерпретируемый посредством Java Virtual Machine).

Java Байт-код

Рис. 1.2.

На рис. 1.3 изображен компилятор, который написан на машинном коде (М-код) и преобразует Pascal в машинный код. Данный пример яв­ляется иллюстрацией того факта, что операционный компилятор обычно

пишется (и производит код) на том же языке, на котором работает ма­шина, где планируется выполнять данный код. Однако, если часть про­граммного обеспечения (возможно, для встроенных систем) компилиру­ется на машине, отличной от той, на которой это обеспечение будет ис­пользоваться, то потребуется задействовать два машинных кода. Один из них предназначен для машины, на которой запушен компилятор (язык, на котором компилятор написан), а второй — для машины, на которой будет использоваться данное, программное обеспечение (язык, который генерирует компилятор). Для примера на рис. 1.4 изображен компилятор для компилирования программного обеспечения встроенных систем.

Чтобы компилятор мог функционировать, он должен быть написан на коде той машины, на которой будет установлен. Однако, этот код может оказаться неудобным для написания программы компилятора по причи­не его низкого уровня.

Глава 1. Процесс компиляции

1.3. Процесс компиляции

13

и

Pascal

Рис, 1.3.

C++

Рис. 1.4.

Часто эту проблему решают следующим образом: вместо того, чтобы пи­сать программу на языке низкого уровня, ее получают путем компиляции программы, написанной на языке высокого уровня. Поэтому сами по се­бе компиляторы изначально пишутся на языке высокого уровня, а затем с помощью уже существующих компиляторов преобразуются к виду, ко­торый воспринимает машина. Данную ситуацию можно изобразить с по­мощью трех расположенных рядом Т-диаграмм (рис. 1.5).

C++ М-код C++ М-код
Vi-етд М-код

Р ис. 15.

В левом верхнем углу рисунка расположен компилятор, изначально написанный на C++, а в правом верхнем углу — исполняемый компиля­тор, полученный после компиляции компилятором, помещенным внизу рисунка. Эти три Т-диаграммы можно объединить, что позволит обнару­жить некоторые закономерности получения одного компилятора из дру­гого. Например, два языка в соответствующих двух верхних частях верх-

них диаграмм должны быть одинаковыми, а два соседствующих появле­ния языка C++ и машинного кода должны относиться к одному языку. Изображенный внизу М-код мог, по сути, быть любым языком, опреде­ляемым машиной, на которой компилируется компилятор.

С помощью Т-диаграммы легко показать, как перенести компилятор, написанный для одной машины, на другую. Пусть имеется компилятор, созданный для машины А, тогда при его переносе на машину В нужно, по меньшей мере, изменить язык реализации. Чем пытаться преобразо­вать код одной машины в код другой, намного проще вернуться к перво­начальной версии компилятора, написанной на языке высокого уровня, и откомпилировать ее в код машины В.

Во многих случаях необходимо преобразовать выход кода с помощью
компилятора (например, в код машины В). Это уже совсем другая задача,
и ее сложность будет зависеть от иных факторов, например, от „того, на­
сколько автономно производство кода. *

1,4. Этапы5 фазы и прожоды

Хорошо написанный компилятор имеет модульную структуру и должен представлять пример хорошо сконструированной программы. Логически процесс компиляции разделяется на этапы, которые, в свою очередь, разделяются на фазы. Физически компилятор разделяется на проходы. Остановимся на этих вопросах более детально.

Как уже говорилось, основными (и часто единственными) этапами компиляции являются анализ (определение структуры и значения исход­ного кода) и синтез (построение целевого кода). Кроме того, может быть этап предварительной обработки, в которой происходит присоединение исходных файлов, развертывание макросов и т.п. Этот этап достаточно прост и в основном связан с языками С и C++. Подробно данный этап рассматриваться не будет.

Типичные фазы процесса компиляции показаны на рис 1.6.

Этап анализа принято разделять на три отдельных фазы.

  1. Лексический анализ.
  2. Синтаксический анализ.
  3. Семантический анализ.

Этап синтеза состоит из следующих (всех или нескольких) фаз.

  • Генерация машинно-независимого кода.
  • Оптимизация машинно-независимого кода.
  • Распределение памяти.
  • Генерация машинного кода.
  • Оптимизация машинного кода.

i i

.Глава 1. Процесс компиляции

1.4. Этапы, фазы и проходы

Лексический анализ Синтаксический анализ Семантический анализ
Генерация машинно-независимого кода > Оптимизация

кода

>. Распре­деление памяти ■► Генерация

> Оптимизация машинного кода Синтез

Р ис. 1.6.

Лексический анализ — это относительно простая фаза, в которой формируются символы (или токены) языка. Слова языка, например,

или пользовательские идентификаторы, например,

или последовательности знаков, например,

удобно воспринимать как один символ, как это делается на этапе анали­за. Задачей фазы лексического анализа или лексического анализатора яв­ляется переход от последовательности знаков к символам языка, с кото­рыми в дальнейшем будут работать синтаксическая и семантическая фа­зы. Такой подход копирует поведение человека при чтении программы. В конечном счете, мы ведь воспринимаем текст программы не как простой набор знаков, а как набор символов, состоящих из этих знаков.

Наряду с преобразованием последовательности знаков в символы, лексический анализатор также обрабатывает пробелы и удаляет коммен­тарии и любые другие символы, не имеющие смысловой нагрузки для последующих этапов анализа. Важно отметить, что лексический анализа­тор всего лишь формирует символы — их последовательность не имеет для него никакого значения, т.е., если бы программа, допустим написан­ная на С, начиналась с

то лексический анализатор просто бы передал этот текст в символьном виде синтаксическому анализатору. Другими словами, лексический ана-

лизатор обычно не работает с контекстом. Если он обрабатывает один символ, для него совершенно не важно, что предшествовало этому сим­волу или что последует за ним.

Сравнительная простота и четкая формулировка лексического анализа позволяют легко автоматизировать создание лексических анализаторов, и в настоящее время существует множество инструментальных средств, по­зволяющих генерировать лексические анализаторы для языка, исходя только из его лексической (т.е. локальной) структуры. О том, как исполь­зовать эти инструменты, будет рассказано в главе 3.

Несмотря на сравнительную простоту лексического анализатора, его выполнение может занимать значительное время в процессе компиля­ции. Это не должно удивлять, если учесть, что лексический анализ — единственная фаза компиляции, которая имеет дело со знаками, которых значительно больше языковых символов. Если же работа лексического анализатора не занимает значительную часть времени компиляции, то стоит задуматься об эффективности остальных фаз процесса.

В процессе синтаксического анализа определяется общая структура программы, что включает понимание порядка следования символов в программе. Это означает, что синтаксический анализатор должен обла­дать информацией о контексте, в котором он работает, т.е. учитывать уже прочитанные символы. Результатом работы синтаксического анализатора является представление программы в древовидной форме, которую назы­вают синтаксическим деревом. К примеру, выражение

(а + Ь) * (с + d) может быть представлено в виде, показанном на рис. 1.7.

Это представление называется абстрактным синтаксическим деревом. Следует отметить, что в данном представлении нет необходимости показы­вать скобки, поскольку структура, задаваемая ими в первоначальном выра­жении, представляется структурой дерева. Таким же образом вся программа может быть представдена с помощью абстрактных сишаксических деревьев.

Глава 1. Процесс компиляции

1.4. Этапы, фазы и проходы

17

Синтаксический анализатор считывает символы в программе слева направо (привычным способом). В процессе считывания он должен уметь определять, является ли последовательность уже считанных симво­лов началом программы. Например, первые десять входных символов могут быть началом некоторой программы, а первые одиннадцать — нет. В этом случае последующие действия компилятора будут зависеть от принятого способа восстановления после ошибок. По крайней мере, ком­пилятор должен указать на одиннадцатый символ и сообщить, что в этой точке вход стал некорректным. Многие компиляторы имеют более широ­кие возможности, например, могут выводить (предположительно полез­ные) сообщения следующего характера:

Стоит отметить, что иногда подобные сообщения не помогают, а наобо­рот, еще больше запутывают.

Возникновение ошибки при считывании одиннадцатого символа мо­жет быть связано как с некорректностью настоящего символа, так и с ошибкой в предыдущих символах программы, и это — одна из причин того, что сообщения об ошибках могут причинять неудобства. Это не оз­начает, что компилятор может выдать сообщение об отсутствующей ошибке, он просто может указать неверное место ее нахождения и из-за этого неправильно ее охарактеризовать. Вопросы правильной диагности­ки ошибок и стратегии их устранения чрезьычайно важны, но в данной книге они не рассматриваются, дабы не отклоняться от главной темы и общих принципов книг серии «Основы вычислительных систем».

Синтаксические анализаторы для проверки синтаксиса могут быть по­строены автоматически (с использованием соответствующих инструмен­тальных средств) из определения языка, хотя при этом требуется писать код для формирования абстрактного синтаксического дерева. Об исполь­зовании таких инструментов рассказывается в главах 4 и 5.

Фаза синтаксического анализа является ключевой на этапе анализа. Она непосредственно взаимодействует с лексической фазой, а результаты ее работы в дальнейшем будут использоваться семантической фазой. Кроме того, фаза синтаксического анализа создает основу для работы компилятора в целом, коды этапа синтеза образуются именно благодаря взаимодействию со структурой, которую образует фаза синтаксического анализа. К тому же, синтаксический анализ создает основу для работы большого количества инструментальных средств анализа исходного кода, например, различных инструментов измерений, перекрестных ссылок, компоновки и т.д. Все упомянутые типы анализа являются частными случаями статического анализа, т.е. анализа, который осуществляется над исходным кодом без его выполнения. Анализ кода, связанный с вы­полнением команд исходного кода, называется динамическим.

Методы синтаксического анализа требуют интенсивного изучения. Некоторые из них обладают большей общностью, чем другие (в смысле применимости к более широкому классу языков), некоторые легче авто-

матизировать, а некоторые более эффективны. Далее в главах 4 и 5 будут подробно рассмотрены два ведущих метода — метод рекурсивного спуска,^ являющийся наглядным и простым при кодировании, и синтаксический анализ SLR(1), который легко автоматизируется и пригоден для большого диапазона языков.

Некоторые свойства языков программирования не могут быть прове­рены простым сканированием слева направо без создания таблиц произ­вольного размера для обеспечения доступа к информации на некотором расстоянии (с точки зрения символов исходного кода). В эту категорию, к примеру, попадает информация о типах переменных и области их ви­димости. Проверка этих типов свойств языков программирования (называющихся статической семантикой) выполняется не в синтаксиче­ской, а в семантической фазе анализа. Это означает, что синтаксический анализатор не заметит несовместимости используемых типов. Проблема такого рода будет исследоваться в семантической фазе анализа.

Семантический анализ обычно инициируется синтаксическим анали­затором для создания и получения доступа к соответствующим таблицам. То, что семантический анализ может не производиться автоматически синтаксическим анализатором, имеет свои положительные стороны; ошибки статической семантики легко обнаруживаются, и после них лег­ко производится восстановление,

Как уже говорилось, этап синтеза процесса компиляции состоит из следующих основных фаз.

  • Генерация машинно-независимого кода.
  • Оптимизация машинно-независимого кода.
  • Распределение памяти.
  • Генерация машинного кода.
  • Оптимизация машинного кода.

В частных случаях некоторые из этих фаз могут отсутствовать. Например, если компилятор непосредственно компилирует в машинный код, пер­вые две фазы могут пропускаться. Оптимизация кода может происходить на уровне машинно-независимого кода, на уровне машинного кода, на

обоих уровнях или ни на одном. Распределение памяти является ключе­вой фазой, которая управляется одной из фаз генерации кода.

Существуют причины, по которым вначале необходимо создавать ма­шинно-независимый код; это способствует переносимости компилятора

и служит для обособления зависимости от языка и зависимости от ма­шины. Многие компиляторы также производят некоторые промежуточ­ные коды, которые могут быть независимы от исходного языка, машин­ного языка или от обоих.

В свое время были приложены значительные усилия для создания так на­зываемого Универсального промежуточного языка (Universal Intermediate Language — UIL), удобного для использования в качестве промежуточного языка для компиляции всех, или почти всех, языков на любую машину. К \

18

Глава 1. Процесс компиляции

1.4. Этапы, фазы и проходы

19

сожалению, эта великолепная идея оказалась неосуществимой. Однако, на данный момент существуют хорошо разработанные промежуточные языки для компиляции исходных языков, например, Р-код для Pascal, Diana для Ada, байт-код для Java. Также существуют промежуточные языки для компи­ляции на определенные машины, например, CTL для машины Manchester MU5. Если бы существовал удачный язык UIL, то проблема использования т языков на п машинах решалась бы созданием т препроцессоров (front end) (каждый из них состоял бы из соответствующего анализатора одного из язы­ков и генератора UIL) и л постпроцессоров (back end) (каждый из них состоял бы из соответствующего транслятора с UIL в один из машинных кодов). Сказанное выше иллюстрируется на рис. 1.8. С другой стороны, независимая реализация каждого компилятора потребует создания т* п программных блоков, отображающих каждый язык на каждую машину.

Одной из проблем при создании LJIL является проблема выбора уровня языка: UIL может оказаться либо слишком высокоуровневым для некоторых языков, либо слишком низкоуровневым для некоторых машин. Несмотря на это, существует множество примеров компиляторов с одним исходным язы­ком, который преобразуется в коды нескольких машин, и компиляторов, ко­торые преобразуют различные исходные языки в один и тот же машинный.

Рассмотрим вопрос оптимизации кода. Потребность в ней может быть различной. Если требуется очень эффективный код, то компилятор обязан обеспечить значительную оптимизацию. В то же время во многих средах скорость работы программного обеспечения не является критическим пара­метром, следовательно, необходима всего лишь незначительная оптимизация. Некоторые типы оптимизации реализовать просто, и поэтому их часто вклю­чают в компиляторы, тогда как другие формы оптимизации, в особенности глобальные (в отличие от локальных), трудоемки и требуют значительных за­трат времени при компиляции, а посему употребляются редко. Многие ком­пиляторы позволяют пользователю самому определить, требуется ли исчер- ■ пывающая (а следовательно, дорогая) оптимизация.

В фазе распределения памяти каждая константа и переменная, фигу­рирующие в программе, получают зарезервированное место в памяти для хранения своего значения. Данная область памяти может иметь один из следующих типов.

  • Статическая память, если время жизни переменной равно време­
    ни жизни программы. Не может быть освобождена до завершения
    выполнения программы.
  • Динамическая память, если время жизни переменной равно времени
    жизни определенного блока, функции или процедуры. Может быть
    освобождена после выполнения данного фрагмента программы.
  • Глобальная память, если на момент компиляции время жизни неиз­
    вестно, а память должна выделяться и освобождаться в процессе вы­
    полнения. Эффективный контроль подобной памяти обычно подразу­
    мевает определенные служебные издержки времени выполнения.

Результатом работы фазы распределения памяти является создание

адреса, в котором содержится полная информация о локализации памяти. В дальнейшем адрес передается генератору кода.

Этап синтеза процесса компиляции (в отличие от этапа анализа) не очень поддается автоматизации, поэтому нельзя сказать, что средства его инструментальной поддержки весьма широко распространены. Ранняя идея создания компилятора компиляторов (compiler-compiler), програм­мы, вход которой являлся бы спецификацией языка и машины, а вы­ход — реализацией языка на машине, была в значительной степени осу­ществлена для этапа анализа и в меньшей степени — для этапа синтеза.

Если в логических терминах компилятор рассматривается как состоя­щий из этапов и фаз, физически он составлен из проходов (pass). Компи­лятор осуществляет проход каждый раз при считывании исходного кода или его представления. Многие компиляторы являются однопроходными, т.е. полный процесс компиляции полностью выполняется при однократ­ном чтении кода. В этом случае различные описанные фазы будут вы­полняться параллельно (что, как правило, является наиболее удобным), что устраняет необходимость сложной связи между различными прохо­дами. Ранние компиляторы были многопроходными (обычно 7-8 прохо­дов) по причине недостаточного объема памяти машин того времени. Для современных компиляторов проблем с объемом памяти уже (как правило) не существует, поэтому большинство из них являются однопро­ходными. В то же время некоторые языки, такие как ALGOL 68, невоз­можно откомпилировать за один проход. Это связано с тем, что инфор­мация, необходимая какой-то конкретной фазе, недоступна в той части исходного кода, в которой она используется. Требуемые многопроходные компиляторы можно легко описать как компиляторы с несколькими предварительными проходами, в течение которых информация собирает­ся и записывается в таблицы с последующим использованием на этапах анализа и синтеза.

Глава I. Процесс компиляции

1.5. Интегрированные среды разработки

Современные компиляторы часто являются не отдельными, автономны­ми инструментальными средствами, а представляют собой часть интегри­рованных сред разработки (Integrated Development Environment — IDE), которые иногда называют средами программирования. Помимо предос­тавления средства компиляции, современная среда IDE предлагает сред­ства языково-ориентированного редактирования, отладки, определения рабочих профилей программы, управления конфигурацией и т.д. Хоро­ший пример такой среды — Borland IDE для C/C++, которая в среде Windows предлагает средства для выполнения множества различных опе­раций, часть из которых выделена в перечисленные ниже группы.

  • Редактированиесо средствамивырезания, вставки, отмены опера­
    ции
    и т.п.
  • Поиск со средствами поиска текста, замены текста и локализации

функций в процессе отладки.

  • Обзорразличных окон, содержащих средства диагностики и другую
    информацию, связанную с текущим проектом, включая информа­
    цию по иерархии вызовов, расположению точек прерывания про­
    граммы, содержимого регистров, расположению переменных, ис­
    пользованию классов и т.д.
  • Управление проектом, включая запуск новых проектов, компиля­
    цию и связывание различных компонентов проекта при раздель­
    ном контроле средств компиляции и сборочных файлов.
  • Отладку для возможности запуска программы в обычном режиме
    или режиме отладки со средствами пошагового выполнения, уста­
    новки точек прерывания, отслеживания значений выражений,
    просмотра таблиц символов и т.д.
  • Средства выполнения, связанные с IDE.

Borland Pascal IDE для Windows предлагает подобный интерфейс, что по­зволяет легко переходить^ одного языка на другой. Хотя подробный об­зор сред IDE выходит за круг рассматриваемых в книге вопросов, в даль­нейшем, время от времени, мы будем обращаться к инструментальным

Общая структура компилятора во многом зависит от его фазоюй структуры и структуры синтаксического анализатора, создающего основу большинства фаз, а структура синтаксического анализатора отражает свойства исходного языка. Обычно при проектировании компилятора необходимо руководство­ваться следующими нефункциональными требованиями.

  • Эффективная компиляция.
  • Минимальный размер компилятора.
  • Минимальная длина целевого кода.
  • Создание эффективного целевого кода.
  • Легкость переносимости.
  • Простота использования.
  • Практичность, что включает хорошие средства диагностики оши­
    бок и восстановления после ошибок.

Безусловно, одновременно удовлетворить всем вышеперечисленным

требованиям практически невозможно, поэтому некоторым из них при­ходится отдавать предпочтение. К примеру, легкость переносимости и простота использования может не согласовываться с требованием мини­мального размера компилятора, а создание эффективного целевого ко­да—с требованием эффективной компиляции.

В обучающих средах, например, эффективность компиляции и хоро­шие средства диагностики могут быть важнее создания эффективного це­левого кода,, тогда как для встроенных систем первоочередное значение имеет размер и эффективность целевого кода. Многие компиляторы раз­решают пользователю самому определять режим работы компилятора — степень оптимизации, выполнение проверок времени выполнения и т.д.

1.7. Использование инструментальных средств

При создании компиляторов используются два основных типа инстру­ментальных средств.

  • Генераторы лексическиханализаторов(lexical analyser generator).
  • Генераторы синтаксических анализаторов (syntax analyser generator,
    или parser generator).

На вход инструментального средства, которое создает лексический анализатор, поступает информация о лексической структуре языка (как из знаков составляются токены языка), а результатом его работы являет­ся лексический анализатор (например, программа на С) этого языка.

Графически данный процесс представлен на рис. 1.9.

На вход инструментального средства, создающего синтаксический анализатор, поступает синтаксическое определение языка, а результатом его работы является синтаксический анализатор (например, программа на С) этого языка. Графически этот процесс представлен на рис. 1.10.

В настоящее время разработаны генераторы синтаксических анализа­торов, поддерживающие наиболее распространенные методы грамматиче­ского разбора. Самым известным из генераторов синтаксических анали­заторов разбора является YACC на основе Unix, который обычно исполь­зуется совместно с генератором лексических анализаторов Unix,

Лекции по конструированию компиляторов глава 8 генерация кода

Книга “Структура и интерпретация компьютерных программ” стала итогом многих лет преподавания функционального программирования на 1-м курсе MIT в качестве вводного курса программирования. В университет часто приходили молодые студенты, которые уже имели за плечами опыт программирования, но этот курс с нуля и с самых основ объяснял

  • почему и как в языки введены переменные, ключевые слова и другие инструкции
  • как и почему работают области видимости, вычисление выражений и вычисление программы
  • и так далее

Эта книга содержит чёткие требования к минимальному языку, на котором можно программировать. В последних главах рассматривается, как интерпретировать этот язык и как скомпилировать его для регистровой машины.

Книга Дракона

Книга “Компиляторы: принципы, технологии, инструментарий” появилась после сбора материалов из курса конструирования компиляторов в MIT, тысячи студентов применили её для своих проектов. Однако, несмотря на переиздание, часть книги успела устареть, а часть дана в не очень практичной форме: например, для разбора грамматик по LR-алгоритму вместо data-driven подхода, использующего простой движок и таблицу переходов, предлагается вручную кодировать правила грамматики.

Книга Engineering a Compiler

Эта книга может поэтапно показать минимальный набор теории и практики, достаточный для каждого компонента компилятора. Рассматриваются современные подходы, в том числе языки промежуточного представления, система типов языка, реализация возможностей современных процедурных и объектно-ориентированных языков. Каждая глава включает постановку проблемы, теоретические пути решения и несколько практических путей реализации.

Пошаговое руководство LLVM Kaleidoscope

Kaleidoscope — это вечно живой пример от проекта LLVM. Он демонстрирует, как использовать LLVM в виде библиотеки. API LLVM постепенно меняется, например, в LLVM 3.9 он на 3-5% отличается от LLVM 3.8. Пример входит в состав исходного кода LLVM и всегда показывает работу с актуальной версией API

Пример доступен в открытом доступе на странице llvm.org/docs/tutorial/. Лучше всего загрузить исходный код LLVM определённой версии, собрать LLVM с помощью CMake и начать изучать параллельно текст на сайте и исходники примера. На Windows можно сгенерировать проект командой cmake -G «Visual Studio 14» «..\path-to-llvm-src»

Сборник Mapping High Level Constructs To LLVM

Этот сборник рецептов, оформленный в один документ, содержит концентрат практических советов по реализации возможностей процедурных, объектно-ориентированных и функциональных языков на LLVM-IR.

Основы конструирования компиляторов

Владимир Серебряков, Максим Галочкин

ISBN: 5-8360-0242-8
Год издания: 2001
Издательство: Едиториал УРСС
Язык: Русский

Предлагаемая вниманию читателя книга основана на курсе лекций, прочитанных на факультете вычислительной математики и кибернетики Московского государственного университета и факультете управления и прикладной математики Московского физико-технического института в 1991-1999 гг. Авторы надеются, что издание книги восполнит существенный пробел в литературе на русском языке по разработке компиляторов. Содержание книги представляет собой `классические` разделы предмета: лексический и синтаксический анализ, организация памяти транслятора (таблицы символов) и периода исполнения (магазина), генерация кода, в частности генерация арифметических и логических выражений. Рассматриваются некоторые средства автоматизации процесса разработки трансляторов, такие как LEX, YACC, СУПЕР, методы генерации оптимального кода. Сделана попытка на протяжении всего изложения провести единую `атрибутную` точку зрения на процесс разработки компилятора. Книга будет полезна как студентам и аспирантам программистских специальностей, так ипрофессионалам в этих областях.

Мягкая обложка, 224 стр.
Тираж: 1000 экз.
Формат: 60×84/16 (145х200 мм)

Мягкая обложка, 224 стр.
Тираж: 1000 экз.
Формат: 60×84/16 (145х200 мм)

Издания и произведения

Эти книги тоже могут вас заинтересовать

Продолжая использовать наш сайт, вы даете согласие на обработку файлов cookie, пользовательских данных (сведения о местоположении; тип и версия ОС; тип и версия Браузера; тип устройства и разрешение его экрана; источник откуда пришел на сайт пользователь; с какого сайта или по какой рекламе; язык ОС и Браузера; какие страницы открывает и на какие кнопки нажимает пользователь; ip-адрес) в целях функционирования сайта, проведения ретаргетинга и проведения статистических исследований и обзоров. Если вы не хотите, чтобы ваши данные обрабатывались, покиньте сайт.

Благодарности Глава Процесс компиляции

страница 1/16
Дата 14.07.2020
Размер 3.51 Mb.
Тип Задача
Робин Хантер

Основные концепции компиляторов

Глава 1. Процесс компиляции

  1. Вступление
  2. Основные понятия
  3. Процесс компиляции
  4. Этапы, фазы и проходы
  5. Интегрированные среды разработки
  6. Проектирование компилятора
  7. Использование инструментальных средств
  8. Резюме

Дополнительная литература Упражнения

Глава 2. Определение языка

  1. Вступление
  2. Определяя синтаксис
  3. Грамматики
  4. Отличия регулярных и контекстно-свободных языков
  5. Порождения
  6. Неоднозначные грамматики
  7. Ограничения контекстно-свободных грамматик
  8. Задача синтаксического анализа
  9. Определение семантики

2.10. Резюме

Дополнительная литература Упражнения

Глава 3. Лексический анализ

  1. Вступление
  2. Основные понятия
  3. Распознавание символов
  4. Lex
  5. Другие применения Lex
  6. Взаимодействие с YACC
  7. Лексические затруднения
  8. Резюме
Дополнительная литература 79 Упражнения 79 Глава 4, Нисходящий синтаксический анализ 81


4.1. Вступление 81 4.2. Критерии принятия решений 81 4.3. 1Х(1)-грамматики 84 4.4. Рекурсивный спуск 89 9 4.5. Преобразования грамматик 96 10 4.5.1. Удаление левой рекурсии 96 4.5.2. Факторизация 98 11 4.6. Достоинства и недостатки ЬЦ1)-анализа 101 11 4.7. Введение действий в грамматику 102 11 4.8. Резюме 105 12 Дополнительная литература 106 15 Упражнения 106 22 22 Глава 5. Восходящий синтаксический анализ 109 23 5.1. Вступление 109 25 5.2. Основные понятия 109 25 5.3. Использование таблицы синтаксического анализа 113 26 5.4. Создание таблицы синтаксического анализа 120 5.5. Особенности LR-анализа 132 27 • 5.6. Введение в YACC 135 27 5.7. Вычисление метрик 140 27 5.8. Использование YACC 143 31 5.9. Резюме . 153 39 Дополнительная литература 154 41 Упражнения 154 42 47 Глава 6. Семантический анализ 157 51 6.1. Вступление 157 52 6.2. Не-контекстно-свободные характеристики языка 157 53 6.3. Таблицы компилятора 162 53 6.3.1. Таблицы символов 162 54 6.3.2. Таблицы типов 167 6.3.3. Другие таблицы 168 57 6.4. Реализация наследования в C++ 169 57 6.5. Резюме 170 57 Дополнительная литература 171 58 Упражнения 171 62 71 Глава 7. Распределение памяти 173 75 7.1. Вступление 173 76 7.2. Память 173 78 7.3. Статическая и динамическая память 176
  1. Адреса времени компиляции
  2. Куча
  3. Резюме .
    Дополнительная литература
    Упражнения

Глава 8. Генерация кода

  1. Вступление
  2. Создание промежуточного кода
  1. Трехадресный код
  2. Р-код •
  3. Байт-код

8.3. Создание машинного кода

  1. Выбор инструкций
  2. Распределение регистров
  3. Распределение регистров путем раскрашивания графа
  1. Оптимизация кода
  2. Генераторы генераторов кода
  3. Резюме

Дополнительная литература Упражнения

Приложение А. Решения упражнений

Глава 1 Глава 2 Глава 3 Глава 4 Глава 5 Глава 6 Глава 7 Глава 8

Литература Предметный указатель

197 197 198 201 203 206 208 208 213 215 219 220 220 220

223 224 226 230

232 233 234 234

Изучение компиляторов является центральным и одним из наиболее вос­требованных аспектов компьютерных наук. Написание компилятора тре­бует знания исходного языка и целевой машины и обеспечения их взаи­мосвязи. Наличие современного инструментального обеспечения осво­бождает программиста от многих утомительных, подверженных ошибкам моментов при создании компилятора.

Мое первое знакомство с компиляторами произошло в 1967 году на лекциях создателя ранних моделей компиляторов для языка ALGOL 60 Питера Наура (Peter Naur) в Университете Ньюкасла. Позднее, в 1974 го­ду, мне посчастливилось прослушать расширенный курс по конструиро­ванию компиляторов в Техническом университете Мюнхена (отдел Ф. Л. Бауэра (F. L. Bauer)). С тех пор я, с некоторыми перерывами, работаю с компиляторами и инструментами для их разработки.

Большинство теоретических разработок и методов для конструирования компиляторов возникло в 1970-х, а некоторые из них даже раньше. В то же время развитие языков программирования постоянно ставило перед создате­лями компиляторов новые задачи: от определения языка ALGOL 60 (ранние работы Наура в Дании, а также Ренделла (Randell) и Рассела (Russell) в Вели­кобритании) до удовлетворения потребностей возникших позже языка Ada и языков объектно-ориентированного программирования. Современные требо­вания Java к сетевой безопасности, эффективности и переносимости вновь ставят перед создателями компиляторов новые проблемы. В то же время по­явление Java Virtual Machine дает великолепный пример промежуточного языка, позволяющего проиллюстрировать различные аспекты генерации кода и распределения памяти.

Процесс создания компилятора соединяет в себе как творческую, так и рутинную работу. Он требует хорошей инструментальной поддержки, что от­четливо видно при изучении истории развития компиляторов. В наше время доступно множество инструментальных средств для создания компиляторов. Некоторые из них можно получить бесплатно через Internet, но на данный момент наиболее используемыми и распространенными инструментальными средствами являются Unix Lex и YACC (сейчас они могут применяться и на других платформах). В Internet доступны также бесплатные версии Lex и YACC, известные как Flex и Bisson. Также можно получить существующие версии turbo Pascal (изначально основанные на С).

Во многих книгах по компиляторам описываются средства Lex и YACC с примерами их использования, но лишь в немногих из них со­держится достаточно информации для того, чтобы читатель сам смог воспользоваться этими инструментами для решения своих задач. Именно поэтому одной из задач, поставленных при написании данной книги, яв-

Основным языком при написании различных алгоритмов на базе Lex и YACC является С. Данная книга прежде всего посвящена компиляции императивных языков, поэтому язык С также будет применяться в каче­стве исходного языка во многих примерах, описывающих различные ас­пекты компиляции. В то же время многие свойства языка, компиляцию которого мы желаем рассмотреть, не связаны с С, поэтому в таких случа­ях будут использоваться другие, более подходящие языки — FORTRAN, Pascal, Ada, ALGOL 68, C++, Java.

Первая часть книги посвящена этапу анализа процесса компиляции. После введения в процесс компиляции (глаю 1) следуют главы по опре­делению языка, лексическому анализу, нисходящему и восходящему син­таксическому анализу и семантическому анализу (главы 2—6). Более ко­роткая вторая часть книги посвящена этапу синтеза процесса компиля­ции. Она содержит две главы, в которых рассмотрено распределение памяти и генерация кода (главы 7—8). Каждая глава завершается серией упражнений, ответы на которые приведены в конце книги. Кроме того, в конце каждой главы помещен список литературы, рекомендуемой для дальнейшего изучения. Значение большинства технических терминов, используемых в книге, можно найти в глоссарии.

Данная книга рассчитана на односеместровый курс по компиляторам и их инструментальным средствам, подобный читаемому в Университете Стратк-лайда (University of Stratchclyde). Названный университетский курс также включает практические занятия, на которых студенты закрепляют навыки по использованию Lex и YACC. Как и другие книги серии «Основы вычисли­тельных систем», эта книга стремится подать все необходимые аспекты про­цесса компиляции, не пытаясь охватить всю область.

С особым удовольствием я выражаю свою признательность издательству Prentice Hall за помощь и поддержку в создании настоящей книги. Необ­ходимо также поблагодарить Бориса Когана (Boris Cogan) и Тамару Мат­вееву (Tamara Mafveeva) за их полезные комментарии к тексту. Благода­рю свою жену Кейт (Kate) за ее поддержку и терпение, а также за про­верку всей рукописи, которую она охотно выполнила. Благодарю рецензентов издательства и редактора серии Рея Велланда (Rey Welland) за их конструктивные замечания на разных этапах создания книги.

Робин Хан тер (Robin Hunter)

В этой главе будут определены основные понятия компилятора языка, его структура, функции и реализация. В частности, будут рассмотрены следующие вопросы.

« Взаимосвязь между различными языками, задействованными в ти­пичном компиляторе.

  • Типичная структура компиляторов.
  • Функции основных фаз компиляции.
  • Цели, которые ставятся при разработке компиляторов.
  • Роль инструментальных средств при разработке компилятора.
  • Возможная степень автоматизации разработки компилятора.

1.2. Основные понития

Программное обеспечение можно создавать с помощью множества язы­ков программирования. Ими могут быть традиционные императивные языки (COBOL, FORTRAN, Pascal, С), объектно-ориентированные язы­ки (C++, Smalltalk, Java), функциональные или логические языки (LISP, Prolog), языки четвертого поколения или визуальные языки (Visual C++, Visual Basic, Delphi). Задача компилятора состоит в преобразовании ори­ентированного на пользователя представления программного обеспече­ния в машинно-ориентированное (в котором происходит непосредствен­ное выполнение программы компьютером). Компиляторы — это изна­чально изощренные системы обработки текста, которые имеют много общего с другими инструментальными средствами обработки текста, на­писанными на языке программирования либо на естественном языке. Обрабатываемый ими текст может быть написан как вручную на обыч­ном языке, так и полуавтоматическим способом при использовании ви­зуальных языков или языков четвертого поколения.

Задача компилятора обычно рассматривается на двух этапах.

W

1, Этап анализа, на котором анализируется исходный текст.

2. Этап синтеза, на котором генерируется машинно-ориентированное
представление,

В дальнейшем вход этапа анализа будем называть исходным текстом или исходным кодом, а выход этапа синтеза — целевым текстом или целе­вым кодом. Преобразование исходного кода в целевой обычно называется процессом компиляции. Процесс компиляции осуществляет компилятор. Компилятор языка можно также назвать реализацией языка. Произведен­ный компилятором целевой код может иметь вид машинного кода для некоторой машины (компьютера) или ассемблерного кода, или некото­рого промежуточного кода, который в дальнейшем будет преобразован (уже с помощью других инструментальных средств) или в ассемблерный код, или л машинный код для некоторой машины. Возможен также ва­риант, когда промежуточный код непосредственно используется посред­ством интерпретатора,

Несмотря на то, что предлагаемая книга посвящена процессу компи­ляции, при случае будут рассматриваться и другие возможности приме­нения текстуального анализа. Следует отметить, что при рассмотрении компиляции большее внимание будет уделяться вопросам анализа, чем синтеза. Это связано с тем, что понятия стадии анализа обладают боль­шей степенью общности и применимости по сравнению с частными, за­висимыми от машины понятиями стадии синтеза.

Технологии компиляторов значительно развились со времени появле­ния компьютеров, и теперь стала возможной автоматизация многих ас­пектов процесса создания компилятора. Существующие инструменталь­ные средства позволяют автоматизировать создание анализаторов, хотя успехи по автоматизации создания генераторов кода намного скромнее. Вопросы возможной степени автоматизации будут рассматриваться в по­следующих главах, где с этой целью будут широко использованы средства генерации анализаторов Lex и YACC.

В основном языком создания компиляторов с помощью Lex и YACC является С. Поэтому в дальнейшем в качестве языка реализации (языка написания компилятора) будет подразумеваться именно С, и требуемые алгоритмы будут описываться на нем. Чтобы избежать частого перехода от одного языка к другому, реализуемым языком также будет считаться С. Впрочем, для описания отдельных моментов будут использоваться и другие языки, более удобные в этих конкретных случаях.

1.3. Процесс компиляции

Процесс компиляции представляет собой преобразование одного языка в другой, переход от исходного кода, на котором работает программист или который автоматически генерируется из некоторого высокоуровневого представления, к целевому коду, который выполняется на машине, воз-

можно, после некоторых преобразований. Схематически этот процесс изображен на рис. 1.1

Исходный Целевой
код Процесс компиляции код

Рис. 1.1.

Как уже упоминалось, процесс компиляции также включает третий язык — язык реализации. Им может быть тот же язык, что и исходный или целевой код, но это необязательно. По возможности, в качестве язы­ка написания компилятора выбирается наиболее удобный — либо с точ­ки зрения внутренних характеристик (например, подверженность ошиб­кам), либо с точки зрения доступности и совместимости с инструмен­тальными средствами.

Три языка, задействованных в реализации, удобно представить с помо­щью Т-диаграммы, содержащей каждый язык в отдельной ветви. На рис. 1.2 изображен компилятор, который написан на С и преобразует Java в байт-код (язык, интерпретируемый посредством Java Virtual Machine).

Java Байт-код

Рис. 1.2.

На рис. 1.3 изображен компилятор, который написан на машинном коде (М-код) и преобразует Pascal в машинный код. Данный пример яв­ляется иллюстрацией того факта, что операционный компилятор обычно

пишется (и производит код) на том же языке, на котором работает ма­шина, где планируется выполнять данный код. Однако, если часть про­граммного обеспечения (возможно, для встроенных систем) компилиру­ется на машине, отличной от той, на которой это обеспечение будет ис­пользоваться, то потребуется задействовать два машинных кода. Один из них предназначен для машины, на которой запушен компилятор (язык, на котором компилятор написан), а второй — для машины, на которой будет использоваться данное, программное обеспечение (язык, который генерирует компилятор). Для примера на рис. 1.4 изображен компилятор для компилирования программного обеспечения встроенных систем.

Чтобы компилятор мог функционировать, он должен быть написан на коде той машины, на которой будет установлен. Однако, этот код может оказаться неудобным для написания программы компилятора по причи­не его низкого уровня.

Глава 1. Процесс компиляции

1.3. Процесс компиляции

13

и

Pascal

Рис, 1.3.

C++

Рис. 1.4.

Часто эту проблему решают следующим образом: вместо того, чтобы пи­сать программу на языке низкого уровня, ее получают путем компиляции программы, написанной на языке высокого уровня. Поэтому сами по се­бе компиляторы изначально пишутся на языке высокого уровня, а затем с помощью уже существующих компиляторов преобразуются к виду, ко­торый воспринимает машина. Данную ситуацию можно изобразить с по­мощью трех расположенных рядом Т-диаграмм (рис. 1.5).

C++ М-код C++ М-код
Vi-етд М-код

Р ис. 15.

В левом верхнем углу рисунка расположен компилятор, изначально написанный на C++, а в правом верхнем углу — исполняемый компиля­тор, полученный после компиляции компилятором, помещенным внизу рисунка. Эти три Т-диаграммы можно объединить, что позволит обнару­жить некоторые закономерности получения одного компилятора из дру­гого. Например, два языка в соответствующих двух верхних частях верх-

них диаграмм должны быть одинаковыми, а два соседствующих появле­ния языка C++ и машинного кода должны относиться к одному языку. Изображенный внизу М-код мог, по сути, быть любым языком, опреде­ляемым машиной, на которой компилируется компилятор.

С помощью Т-диаграммы легко показать, как перенести компилятор, написанный для одной машины, на другую. Пусть имеется компилятор, созданный для машины А, тогда при его переносе на машину В нужно, по меньшей мере, изменить язык реализации. Чем пытаться преобразо­вать код одной машины в код другой, намного проще вернуться к перво­начальной версии компилятора, написанной на языке высокого уровня, и откомпилировать ее в код машины В.

Во многих случаях необходимо преобразовать выход кода с помощью
компилятора (например, в код машины В). Это уже совсем другая задача,
и ее сложность будет зависеть от иных факторов, например, от „того, на­
сколько автономно производство кода. *

1,4. Этапы5 фазы и прожоды

Хорошо написанный компилятор имеет модульную структуру и должен представлять пример хорошо сконструированной программы. Логически процесс компиляции разделяется на этапы, которые, в свою очередь, разделяются на фазы. Физически компилятор разделяется на проходы. Остановимся на этих вопросах более детально.

Как уже говорилось, основными (и часто единственными) этапами компиляции являются анализ (определение структуры и значения исход­ного кода) и синтез (построение целевого кода). Кроме того, может быть этап предварительной обработки, в которой происходит присоединение исходных файлов, развертывание макросов и т.п. Этот этап достаточно прост и в основном связан с языками С и C++. Подробно данный этап рассматриваться не будет.

Типичные фазы процесса компиляции показаны на рис 1.6.

Этап анализа принято разделять на три отдельных фазы.

  1. Лексический анализ.
  2. Синтаксический анализ.
  3. Семантический анализ.

Этап синтеза состоит из следующих (всех или нескольких) фаз.

  • Генерация машинно-независимого кода.
  • Оптимизация машинно-независимого кода.
  • Распределение памяти.
  • Генерация машинного кода.
  • Оптимизация машинного кода.

i i

.Глава 1. Процесс компиляции

1.4. Этапы, фазы и проходы

Лексический анализ Синтаксический анализ Семантический анализ
Генерация машинно-независимого кода > Оптимизация

кода

>. Распре­деление памяти ■► Генерация

> Оптимизация машинного кода Синтез

Р ис. 1.6.

Лексический анализ — это относительно простая фаза, в которой формируются символы (или токены) языка. Слова языка, например,

или пользовательские идентификаторы, например,

или последовательности знаков, например,

удобно воспринимать как один символ, как это делается на этапе анали­за. Задачей фазы лексического анализа или лексического анализатора яв­ляется переход от последовательности знаков к символам языка, с кото­рыми в дальнейшем будут работать синтаксическая и семантическая фа­зы. Такой подход копирует поведение человека при чтении программы. В конечном счете, мы ведь воспринимаем текст программы не как простой набор знаков, а как набор символов, состоящих из этих знаков.

Наряду с преобразованием последовательности знаков в символы, лексический анализатор также обрабатывает пробелы и удаляет коммен­тарии и любые другие символы, не имеющие смысловой нагрузки для последующих этапов анализа. Важно отметить, что лексический анализа­тор всего лишь формирует символы — их последовательность не имеет для него никакого значения, т.е., если бы программа, допустим написан­ная на С, начиналась с

то лексический анализатор просто бы передал этот текст в символьном виде синтаксическому анализатору. Другими словами, лексический ана-

лизатор обычно не работает с контекстом. Если он обрабатывает один символ, для него совершенно не важно, что предшествовало этому сим­волу или что последует за ним.

Сравнительная простота и четкая формулировка лексического анализа позволяют легко автоматизировать создание лексических анализаторов, и в настоящее время существует множество инструментальных средств, по­зволяющих генерировать лексические анализаторы для языка, исходя только из его лексической (т.е. локальной) структуры. О том, как исполь­зовать эти инструменты, будет рассказано в главе 3.

Несмотря на сравнительную простоту лексического анализатора, его выполнение может занимать значительное время в процессе компиля­ции. Это не должно удивлять, если учесть, что лексический анализ — единственная фаза компиляции, которая имеет дело со знаками, которых значительно больше языковых символов. Если же работа лексического анализатора не занимает значительную часть времени компиляции, то стоит задуматься об эффективности остальных фаз процесса.

В процессе синтаксического анализа определяется общая структура программы, что включает понимание порядка следования символов в программе. Это означает, что синтаксический анализатор должен обла­дать информацией о контексте, в котором он работает, т.е. учитывать уже прочитанные символы. Результатом работы синтаксического анализатора является представление программы в древовидной форме, которую назы­вают синтаксическим деревом. К примеру, выражение

(а + Ь) * (с + d) может быть представлено в виде, показанном на рис. 1.7.

Это представление называется абстрактным синтаксическим деревом. Следует отметить, что в данном представлении нет необходимости показы­вать скобки, поскольку структура, задаваемая ими в первоначальном выра­жении, представляется структурой дерева. Таким же образом вся программа может быть представдена с помощью абстрактных сишаксических деревьев.

Глава 1. Процесс компиляции

1.4. Этапы, фазы и проходы

17

Синтаксический анализатор считывает символы в программе слева направо (привычным способом). В процессе считывания он должен уметь определять, является ли последовательность уже считанных симво­лов началом программы. Например, первые десять входных символов могут быть началом некоторой программы, а первые одиннадцать — нет. В этом случае последующие действия компилятора будут зависеть от принятого способа восстановления после ошибок. По крайней мере, ком­пилятор должен указать на одиннадцатый символ и сообщить, что в этой точке вход стал некорректным. Многие компиляторы имеют более широ­кие возможности, например, могут выводить (предположительно полез­ные) сообщения следующего характера:

Стоит отметить, что иногда подобные сообщения не помогают, а наобо­рот, еще больше запутывают.

Возникновение ошибки при считывании одиннадцатого символа мо­жет быть связано как с некорректностью настоящего символа, так и с ошибкой в предыдущих символах программы, и это — одна из причин того, что сообщения об ошибках могут причинять неудобства. Это не оз­начает, что компилятор может выдать сообщение об отсутствующей ошибке, он просто может указать неверное место ее нахождения и из-за этого неправильно ее охарактеризовать. Вопросы правильной диагности­ки ошибок и стратегии их устранения чрезьычайно важны, но в данной книге они не рассматриваются, дабы не отклоняться от главной темы и общих принципов книг серии «Основы вычислительных систем».

Синтаксические анализаторы для проверки синтаксиса могут быть по­строены автоматически (с использованием соответствующих инструмен­тальных средств) из определения языка, хотя при этом требуется писать код для формирования абстрактного синтаксического дерева. Об исполь­зовании таких инструментов рассказывается в главах 4 и 5.

Фаза синтаксического анализа является ключевой на этапе анализа. Она непосредственно взаимодействует с лексической фазой, а результаты ее работы в дальнейшем будут использоваться семантической фазой. Кроме того, фаза синтаксического анализа создает основу для работы компилятора в целом, коды этапа синтеза образуются именно благодаря взаимодействию со структурой, которую образует фаза синтаксического анализа. К тому же, синтаксический анализ создает основу для работы большого количества инструментальных средств анализа исходного кода, например, различных инструментов измерений, перекрестных ссылок, компоновки и т.д. Все упомянутые типы анализа являются частными случаями статического анализа, т.е. анализа, который осуществляется над исходным кодом без его выполнения. Анализ кода, связанный с вы­полнением команд исходного кода, называется динамическим.

Методы синтаксического анализа требуют интенсивного изучения. Некоторые из них обладают большей общностью, чем другие (в смысле применимости к более широкому классу языков), некоторые легче авто-

матизировать, а некоторые более эффективны. Далее в главах 4 и 5 будут подробно рассмотрены два ведущих метода — метод рекурсивного спуска,^ являющийся наглядным и простым при кодировании, и синтаксический анализ SLR(1), который легко автоматизируется и пригоден для большого диапазона языков.

Некоторые свойства языков программирования не могут быть прове­рены простым сканированием слева направо без создания таблиц произ­вольного размера для обеспечения доступа к информации на некотором расстоянии (с точки зрения символов исходного кода). В эту категорию, к примеру, попадает информация о типах переменных и области их ви­димости. Проверка этих типов свойств языков программирования (называющихся статической семантикой) выполняется не в синтаксиче­ской, а в семантической фазе анализа. Это означает, что синтаксический анализатор не заметит несовместимости используемых типов. Проблема такого рода будет исследоваться в семантической фазе анализа.

Семантический анализ обычно инициируется синтаксическим анали­затором для создания и получения доступа к соответствующим таблицам. То, что семантический анализ может не производиться автоматически синтаксическим анализатором, имеет свои положительные стороны; ошибки статической семантики легко обнаруживаются, и после них лег­ко производится восстановление,

Как уже говорилось, этап синтеза процесса компиляции состоит из следующих основных фаз.

  • Генерация машинно-независимого кода.
  • Оптимизация машинно-независимого кода.
  • Распределение памяти.
  • Генерация машинного кода.
  • Оптимизация машинного кода.

В частных случаях некоторые из этих фаз могут отсутствовать. Например, если компилятор непосредственно компилирует в машинный код, пер­вые две фазы могут пропускаться. Оптимизация кода может происходить на уровне машинно-независимого кода, на уровне машинного кода, на

обоих уровнях или ни на одном. Распределение памяти является ключе­вой фазой, которая управляется одной из фаз генерации кода.

Существуют причины, по которым вначале необходимо создавать ма­шинно-независимый код; это способствует переносимости компилятора

и служит для обособления зависимости от языка и зависимости от ма­шины. Многие компиляторы также производят некоторые промежуточ­ные коды, которые могут быть независимы от исходного языка, машин­ного языка или от обоих.

В свое время были приложены значительные усилия для создания так на­зываемого Универсального промежуточного языка (Universal Intermediate Language — UIL), удобного для использования в качестве промежуточного языка для компиляции всех, или почти всех, языков на любую машину. К \

18

Глава 1. Процесс компиляции

1.4. Этапы, фазы и проходы

19

сожалению, эта великолепная идея оказалась неосуществимой. Однако, на данный момент существуют хорошо разработанные промежуточные языки для компиляции исходных языков, например, Р-код для Pascal, Diana для Ada, байт-код для Java. Также существуют промежуточные языки для компи­ляции на определенные машины, например, CTL для машины Manchester MU5. Если бы существовал удачный язык UIL, то проблема использования т языков на п машинах решалась бы созданием т препроцессоров (front end) (каждый из них состоял бы из соответствующего анализатора одного из язы­ков и генератора UIL) и л постпроцессоров (back end) (каждый из них состоял бы из соответствующего транслятора с UIL в один из машинных кодов). Сказанное выше иллюстрируется на рис. 1.8. С другой стороны, независимая реализация каждого компилятора потребует создания т* п программных блоков, отображающих каждый язык на каждую машину.

Одной из проблем при создании LJIL является проблема выбора уровня языка: UIL может оказаться либо слишком высокоуровневым для некоторых языков, либо слишком низкоуровневым для некоторых машин. Несмотря на это, существует множество примеров компиляторов с одним исходным язы­ком, который преобразуется в коды нескольких машин, и компиляторов, ко­торые преобразуют различные исходные языки в один и тот же машинный.

Рассмотрим вопрос оптимизации кода. Потребность в ней может быть различной. Если требуется очень эффективный код, то компилятор обязан обеспечить значительную оптимизацию. В то же время во многих средах скорость работы программного обеспечения не является критическим пара­метром, следовательно, необходима всего лишь незначительная оптимизация. Некоторые типы оптимизации реализовать просто, и поэтому их часто вклю­чают в компиляторы, тогда как другие формы оптимизации, в особенности глобальные (в отличие от локальных), трудоемки и требуют значительных за­трат времени при компиляции, а посему употребляются редко. Многие ком­пиляторы позволяют пользователю самому определить, требуется ли исчер- ■ пывающая (а следовательно, дорогая) оптимизация.

В фазе распределения памяти каждая константа и переменная, фигу­рирующие в программе, получают зарезервированное место в памяти для хранения своего значения. Данная область памяти может иметь один из следующих типов.

  • Статическая память, если время жизни переменной равно време­
    ни жизни программы. Не может быть освобождена до завершения
    выполнения программы.
  • Динамическая память, если время жизни переменной равно времени
    жизни определенного блока, функции или процедуры. Может быть
    освобождена после выполнения данного фрагмента программы.
  • Глобальная память, если на момент компиляции время жизни неиз­
    вестно, а память должна выделяться и освобождаться в процессе вы­
    полнения. Эффективный контроль подобной памяти обычно подразу­
    мевает определенные служебные издержки времени выполнения.

Результатом работы фазы распределения памяти является создание

адреса, в котором содержится полная информация о локализации памяти. В дальнейшем адрес передается генератору кода.

Этап синтеза процесса компиляции (в отличие от этапа анализа) не очень поддается автоматизации, поэтому нельзя сказать, что средства его инструментальной поддержки весьма широко распространены. Ранняя идея создания компилятора компиляторов (compiler-compiler), програм­мы, вход которой являлся бы спецификацией языка и машины, а вы­ход — реализацией языка на машине, была в значительной степени осу­ществлена для этапа анализа и в меньшей степени — для этапа синтеза.

Если в логических терминах компилятор рассматривается как состоя­щий из этапов и фаз, физически он составлен из проходов (pass). Компи­лятор осуществляет проход каждый раз при считывании исходного кода или его представления. Многие компиляторы являются однопроходными, т.е. полный процесс компиляции полностью выполняется при однократ­ном чтении кода. В этом случае различные описанные фазы будут вы­полняться параллельно (что, как правило, является наиболее удобным), что устраняет необходимость сложной связи между различными прохо­дами. Ранние компиляторы были многопроходными (обычно 7-8 прохо­дов) по причине недостаточного объема памяти машин того времени. Для современных компиляторов проблем с объемом памяти уже (как правило) не существует, поэтому большинство из них являются однопро­ходными. В то же время некоторые языки, такие как ALGOL 68, невоз­можно откомпилировать за один проход. Это связано с тем, что инфор­мация, необходимая какой-то конкретной фазе, недоступна в той части исходного кода, в которой она используется. Требуемые многопроходные компиляторы можно легко описать как компиляторы с несколькими предварительными проходами, в течение которых информация собирает­ся и записывается в таблицы с последующим использованием на этапах анализа и синтеза.

Глава I. Процесс компиляции

1.5. Интегрированные среды разработки

Современные компиляторы часто являются не отдельными, автономны­ми инструментальными средствами, а представляют собой часть интегри­рованных сред разработки (Integrated Development Environment — IDE), которые иногда называют средами программирования. Помимо предос­тавления средства компиляции, современная среда IDE предлагает сред­ства языково-ориентированного редактирования, отладки, определения рабочих профилей программы, управления конфигурацией и т.д. Хоро­ший пример такой среды — Borland IDE для C/C++, которая в среде Windows предлагает средства для выполнения множества различных опе­раций, часть из которых выделена в перечисленные ниже группы.

  • Редактированиесо средствамивырезания, вставки, отмены опера­
    ции
    и т.п.
  • Поиск со средствами поиска текста, замены текста и локализации

функций в процессе отладки.

  • Обзорразличных окон, содержащих средства диагностики и другую
    информацию, связанную с текущим проектом, включая информа­
    цию по иерархии вызовов, расположению точек прерывания про­
    граммы, содержимого регистров, расположению переменных, ис­
    пользованию классов и т.д.
  • Управление проектом, включая запуск новых проектов, компиля­
    цию и связывание различных компонентов проекта при раздель­
    ном контроле средств компиляции и сборочных файлов.
  • Отладку для возможности запуска программы в обычном режиме
    или режиме отладки со средствами пошагового выполнения, уста­
    новки точек прерывания, отслеживания значений выражений,
    просмотра таблиц символов и т.д.
  • Средства выполнения, связанные с IDE.

Borland Pascal IDE для Windows предлагает подобный интерфейс, что по­зволяет легко переходить^ одного языка на другой. Хотя подробный об­зор сред IDE выходит за круг рассматриваемых в книге вопросов, в даль­нейшем, время от времени, мы будем обращаться к инструментальным

Общая структура компилятора во многом зависит от его фазоюй структуры и структуры синтаксического анализатора, создающего основу большинства фаз, а структура синтаксического анализатора отражает свойства исходного языка. Обычно при проектировании компилятора необходимо руководство­ваться следующими нефункциональными требованиями.

  • Эффективная компиляция.
  • Минимальный размер компилятора.
  • Минимальная длина целевого кода.
  • Создание эффективного целевого кода.
  • Легкость переносимости.
  • Простота использования.
  • Практичность, что включает хорошие средства диагностики оши­
    бок и восстановления после ошибок.

Безусловно, одновременно удовлетворить всем вышеперечисленным

требованиям практически невозможно, поэтому некоторым из них при­ходится отдавать предпочтение. К примеру, легкость переносимости и простота использования может не согласовываться с требованием мини­мального размера компилятора, а создание эффективного целевого ко­да—с требованием эффективной компиляции.

В обучающих средах, например, эффективность компиляции и хоро­шие средства диагностики могут быть важнее создания эффективного це­левого кода,, тогда как для встроенных систем первоочередное значение имеет размер и эффективность целевого кода. Многие компиляторы раз­решают пользователю самому определять режим работы компилятора — степень оптимизации, выполнение проверок времени выполнения и т.д.

1.7. Использование инструментальных средств

При создании компиляторов используются два основных типа инстру­ментальных средств.

  • Генераторы лексическиханализаторов(lexical analyser generator).
  • Генераторы синтаксических анализаторов (syntax analyser generator,
    или parser generator).

На вход инструментального средства, которое создает лексический анализатор, поступает информация о лексической структуре языка (как из знаков составляются токены языка), а результатом его работы являет­ся лексический анализатор (например, программа на С) этого языка.

Графически данный процесс представлен на рис. 1.9.

На вход инструментального средства, создающего синтаксический анализатор, поступает синтаксическое определение языка, а результатом его работы является синтаксический анализатор (например, программа на С) этого языка. Графически этот процесс представлен на рис. 1.10.

В настоящее время разработаны генераторы синтаксических анализа­торов, поддерживающие наиболее распространенные методы грамматиче­ского разбора. Самым известным из генераторов синтаксических анали­заторов разбора является YACC на основе Unix, который обычно исполь­зуется совместно с генератором лексических анализаторов Unix,

Илон Маск рекомендует:  Вывод результатов запроса xml xslt
Понравилась статья? Поделиться с друзьями:
Кодинг, CSS и SQL