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

Естественно, для каждой новой системы команд требуется полный набор новых компиляторов с распространенных языков.Наконец, бурно развиваются различные параллельные архитектуры.Среди них отметим векторные, многопроцессорные, с широким командным словом (вариантом которых являются суперскалярные ЭВМ). Нарынке уже имеются десятки типов ЭВМ с параллельной архитектурой,начиная от супер-ЭВМ (Cray, CDC и другие), через рабочие станции (например, IBM RS/6000) и кончая персональными (например, на основемикропроцессора I-860).

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

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

В этом случае таблицы объектов строятся в последующих фазах (например, в процессе синтаксического анализа).На этапе лексического анализа обнаруживаются некоторые (простейшие) ошибки (недопустимые символы, неправильная запись чисел, идентификаторов и др.).Основная задача синтаксического анализа – разбор структуры программы. Как правило, под структурой понимается дерево, соответствующее разбору в контекстно-свободной грамматике языка. В настоящеевремя чаще всего используется либо LL(1)-анализ (и его вариант – рекурсивный спуск), либо LR(1)-анализ и его варианты (LR(0), SLR(1),LALR(1) и другие).

Рекурсивный спуск чаще используется при ручномпрограммировании синтаксического анализатора, LR(1) – при исполь-1.2. СТРУКТУРА КОМПИЛЯТОРАE_dkbq_kdbcZgZeba>bZ]ghklbdZDhg_qgu_Z\lhfZlu9Ihlhde_dk_flZ[ebpuh[t_dlh\KbglZdkbq_kdbcZgZeba>bZ]ghklbdZDhgl_dklgucZgZeba>bZ]ghklbdZDK]jZffZlbdb>_j_\hjZa[hjZlZ[ebpuh[t_dlh\:ljb[mlgu_]jZffZlbdb:ljb[mlbjh\Zggh_^_j_\hlZ[ebpuh[t_dlh\=_g_jZpbyijhf_`mlhqgh]hij_^klZ\e_gbyIjhf_`mlhqgZynhjfZij_nbdkgZyihklnbdkgZyljhcdbb ^jKMljZgkeypbyHilbfbaZpbyIjhf_`mlhqgZynhjfZhjb_glbjh\Zgguc]jZnIhlhdh\ucZgZeba=_g_jZpbydh^ZH[t_dlgucfh^mevLZ[ebpuj_r_gbc^bgZfbq_kdh_ijh]jZffbjh\Zgb_Рис. 1.1:10ГЛАВА 1. ВВЕДЕНИЕзовании систем автоматического построения синтаксических анализаторов.Результатом синтаксического анализа является синтаксическое дерево со ссылками на таблицы объектов. В процессе синтаксического анализа также обнаруживаются ошибки, связанные со структурой программы.На этапе контекстного анализа выявляются зависимости между частями программы, которые не могут быть описаны контекстно-свободнымсинтаксисом.

Это в основном связи “описание-использование”, в частности, анализ типов объектов, анализ областей видимости, соответствиепараметров, метки и другие. В процессе контекстного анализа таблицыобъектов пополняются информацией об описаниях (свойствах) объектов.Основным формализмом, использующимся при контекстном анализе, является аппарат атрибутных грамматик. Результатом контекстного анализа является атрибутированное дерево программы. Информацияоб объектах может быть как рассредоточена в самом дереве, так и сосредоточена в отдельных таблицах объектов. В процессе контекстного анализа также могут быть обнаружены ошибки, связанные с неправильным использованием объектов.Затем программа может быть переведена во внутреннее представление.

Это делается для целей оптимизации и/или удобства генерации кода. Еще одной целью преобразования программы во внутреннее представление является желание иметь переносимый компилятор. Тогда только последняя фаза (генерация кода) является машинно-зависимой. Вкачестве внутреннего представления может использоваться префикснаяили постфиксная запись, ориентированный граф, тройки, четверки идругие.Фаз оптимизации может быть несколько. Оптимизации обычно делят на машинно-зависимые и машинно-независимые, локальные и глобальные. Часть машинно-зависимой оптимизации выполняется на фазегенерации кода. Глобальная оптимизация пытается принять во внимание структуру всей программы, локальная – только небольших ее фрагментов.

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

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

СТРУКТУРА КОМПИЛЯТОРА11ные синтаксические методы.Конечно, те или иные фазы транслятора могут либо отсутствовать совсем, либо объединяться. В простейшем случае однопроходного транслятора нет явной фазы генерации промежуточного представления и оптимизации, остальные фазы объединены в одну, причем нет и явно построенного синтаксического дерева.12ГЛАВА 1. ВВЕДЕНИЕГлава 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 префиксом является любая цепочка из множества L1 = {e, a, ab, abb, abbb, abbba}, суффиксом является любая цепочка измножества L2 = {e, a, ba, bba, bbba, abbba}, подцепочкой является любая цепочка из множества L1 ∪ L2 .Длиной цепочки w (обозначается |w|) называется число символов вней. Например, |abababa| = 7, а |e| = 0.Язык в алфавите V – это некоторое множество цепочек в алфавитеV.Пример 2.2. Пусть дан алфавит V = {a, b}.

Вот некоторые языки в алфавите V :а) L1 = ∅ – пустой язык;13ГЛАВА 2. ЯЗЫКИ И ИХ ПРЕДСТАВЛЕНИЕ14б) L2 = {e} – язык, содержащий только пустую цепочку(заметим, что L1 и L2 – различные языки);в) L3 = {e, a, b, aa, ab, ba, bb} – язык, содержащий цепочки из a и b, длина которых не превосходит 2;г) L4 – язык, включающий всевозможные цепочки из a и b, содержащие четное число a и четное число b;2д) L5 = {an |n > 0} – язык цепочек из a, длины которых представляют собойквадраты натуральных чисел.Два последних языка содержат бесконечное число цепочек.Введем обозначение V ∗ для множества всех цепочек в алфавите V ,включая пустую цепочку. Каждый язык в алфавите V является подмножеством V ∗ .

Для обозначения множества всех цепочек в алфавитеV , кроме пустой цепочки, будем использовать V + .Пример 2.3. Пусть V = {0, 1}. Тогда V ∗ = {e, 0, 1, 00, 01, 10, 11, 000, ...}, V + ={0, 1, 00, 01, 10, 11, 000, ...}.Введем некоторые операции над языками.Пусть L1 и L2 – языки в алфавите V . Конкатенацией языков L1 и L2называется язык L1 L2 = {xy|x ∈ L1 , y ∈ L2 }.Пусть L – язык в алфавите V . Итерацией языка L называется языкL∗ , определяемый следующим образом:(1) L0 = {e};(2) Ln = LLn−1 , n > 1;(3) L∗ =∞SLn .n=0Пример 2.4.

Пусть L1 = {aa, bb} и L2 = {e, a, bb}. ТогдаL1 L2 = {aa, bb, aaa, bba, aabb, bbbb}, иL∗1 = {e, aa, bb, aaaa, aabb, bbaa, bbbb, aaaaaa, ...}.Большинство языков, представляющих интерес, содержат бесконечное число цепочек. При этом возникают три важных вопроса.Во-первых, как представить язык (т.е. специфицировать входящиев него цепочки)? Если язык содержит только конечное множество цепочек, ответ прост.