Иванова Г.С., Ничушкина Т.Н. - Основы конструирования компиляторов (1075568)
Текст из файла
ОглавлениеАннотация.......................................................................................................................................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), в противном случае сначала будет выполняться операция сложения.
Характеристики
Тип файла PDF
PDF-формат наиболее широко используется для просмотра любого типа файлов на любом устройстве. В него можно сохранить документ, таблицы, презентацию, текст, чертежи, вычисления, графики и всё остальное, что можно показать на экране любого устройства. Именно его лучше всего использовать для печати.
Например, если Вам нужно распечатать чертёж из автокада, Вы сохраните чертёж на флешку, но будет ли автокад в пункте печати? А если будет, то нужная версия с нужными библиотеками? Именно для этого и нужен формат PDF - в нём точно будет показано верно вне зависимости от того, в какой программе создали PDF-файл и есть ли нужная программа для его просмотра.
![](https://s.studizba.com/z.php?f=/templates/si/i/noavatar.png&w=100&h=100&t=1"){kind=avatar}
