Иванова Г.С., Ничушкина Т.Н. - Основы конструирования компиляторов

ОглавлениеАннотация.......................................................................................................................................31 Структура компилятора............................................................................................................41.1 Основные понятия и определения....................................................................................41.2 Этапы процесса компиляции.............................................................................................51.3 Ранние методы разбора выражений.

Метод Рутисхаузера.............................................7Контрольные вопросы...............................................................................................................92 Основные положения теории формальных грамматик........................................................102.1 Формальная грамматика и формальный язык ...............................................................102.2 Понятие грамматического разбора.................................................................................122.2.1 Левосторонний восходящий грамматический разбор(«слева-направо») ........142.2.2 Левосторонний нисходящий грамматический разбор («сверху-вниз»)..............152.3 Расширенная классификация грамматик Хомского......................................................17Контрольные вопросы.............................................................................................................193 Распознавание регулярных грамматик .................................................................................203.1 Конечный автомат и его программная реализация.......................................................203.2 Построение лексических анализаторов .........................................................................223.3 Построение синтаксических анализаторов....................................................................24Контрольные вопросы.............................................................................................................264 Распознавание КС-грамматик.................................................................................................274.1 Автомат с магазинной памятью......................................................................................274.2 Синтаксические анализаторы LL(k)-грамматик.

Метод рекурсивного спуска..........304.3 Синтаксические анализаторы LR(k)-грамматик. Грамматики предшествования......374.4 Польская запись. Алгоритм Бауэра-Замельзона............................................................39Контрольные вопросы.............................................................................................................425 Распределение памяти под программы и данные.................................................................43Контрольные вопросы.............................................................................................................446 Генерация и оптимизация кодов............................................................................................45Контрольные вопросы.............................................................................................................46Литература....................................................................................................................................472МГТУ им.

Н.Э. БауманаФакультет «Информатика и Системы Управления»Кафедра ИУ-6 «Компьютерные системы и сети»ИВАНОВА ГАЛИНА СЕРГЕЕВНА,НИЧУШКИНА ТАТЬЯНА НИКОЛАЕВНАОсновы конструирования компиляторовУчебное пособиеМОСКВА2010 год МГТУ им. БауманаОглавление3АннотацияУчебное пособие содержит сведения из математической логики и теории формальных языков, составляющие основу для построения компилирующих программ. Оно включает:• математическое определение формального языка и формальной грамматики;• описание классификации формальных грамматик Хомского;• определение математических моделей конечного автомата и автомата с магазиннойпамятью;• описание и анализ применимости методов грамматического разбора;• примеры практического применения указанного математического аппарата для выполнения лексического и синтаксического анализа формальных языков регулярного и контекстно-свободного типов.Пособие предназначено для студентов 2 курса кафедры Компьютерные системы исети, изучающих дисциплину Системное программное обеспечение.Оглавление41Структура компилятора1.1Основные понятия и определенияТранслятор – программа, которая переводит программу, написанную на одном языке, в эквивалентную ей программу, написанную на другом языке.Компилятор – транслятор с языка высокого уровня на машинный язык или язык ассемблера.Ассемблер – транслятор с языка Ассемблера на машинный язык.Интерпретатор – программа, которая принимает исходную программу и выполняет ее, не создавая программы на другом языке.Макропроцессор (препроцессор – для компиляторов) – программа, которая принимает исходную программу, как текст и выполняет в нем замены определенных символовна подстроки.

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

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

Лексический анализ – процесс преобразования исходного текста в строку однородных символов. Каждый символ результирующей строки – токен соответствует словуязыка – лексеме и характеризуется набором атрибутов, таких как тип, адрес и т. п., поэтому строку токенов часто представляют таблицей, строка которой соответствует одномутокену.Лексема обозначает простое понятие языка. Всего существует 2 типа лексем:а) лексемы, соответствующие символам алфавита языка, такие как «Служебные слова» и «Служебные символы»;б) лексемы, соответствующие базовым понятиям языка, такие как «Идентификатор»и «Литерал».Пример.

При лексическом разборе предложения: if Sum>5 then pr:= true; будет получена таблица токенов (см. таблицу 1) и, возможно, расширены таблицы переменных(см. таблицу 2) и литералов (см. таблицу 3):Таблица 1 – Пример таблицы токеновЛексемаifSum>5thenpr:=true;Тип лексемыСлужебное словоИдентификаторСлужебный символЛитералСлужебное словоИдентификаторСлужебный символЛитералСлужебный символЗначениеКод «if»Код «>»Код «then»Код «:=»Код «;»СсылкаАдрес в таблице идентификаторовАдрес в таблице литераловАдрес в таблице идентификаторовАдрес в таблице литералов-Оглавление6Таблица 2 –Таблица идентификаторов переменныхИмяТипАдресSumInteger∅ (пока не распределена)prBoolean∅ (пока не распределена)Таблица 3 – Таблица константИмяТипЗначение«5»Byte00000101«true»Boolean000000012. Синтаксический анализ – процесс распознавания конструкций языка в строке токенов.

Главным результатом является информация об ошибках в выражениях, операторахи описаниях программы.Пример. На этом этапе для предыдущего примера должны быть распознаныконструкции: <Логическое выражение>, <Оператор присваивания>, <Оператор if>.3. Семантический анализ – процесс распознавания/проверки смысла конструкции.По результатам распознавания строится последовательность, приближенная к последовательности операторов будущей программы и выполняются предусмотренные проверкиправильности программы.Пример. На этом этапе может быть проверена инициализация переменной Sum.4. Распределение памяти – процесс назначения адресов для именованных константи переменных программы.5. Генерация и оптимизация объектного кода – процесс формирования программына выходном языке, которая семантически эквивалентна исходной программе.

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

В основе такого перевода лежитпредставление выражения в виде последовательности троек, где каждая тройка включаетдва адреса операндов и операцию:EL  ER, где EL, ER – левый и правый операнды,  – операция.Основной проблемой при этом является необходимость учета приоритетов операций. Например, для выражения:d = a+b*cдолжны быть построены тройки:T1 = b*c, d = a+T1Исторически первым для решения этой задачи был предложен метод Рутисхаузера.Метод Рутисхаузера требует, чтобы выражение было записано в полной скобочнойзаписи, когда порядок выполнения операций указывается скобками. Так, выражение d =a+b*c должно быть записано в виде d = a+(b*c), в противном случае сначала будет выполняться операция сложения.