Классическая теория компиляторов
 Скачать 1.25 Mb.
|
|
В.Э. Карпов КЛАССИЧЕСКАЯ ТЕОРИЯ КОМПИЛЯТОРОВ Москва 2011 2 УДК 681.3.06 ББК 32.973 К26 Рецензенты: докт. техн. наук И.П.Беляев (НИИ информационных технологий); канд. техн. наук А.Н.Таран (НИИ информационных систем) Карпов В.Э. К26 Теория компиляторов. Учебное пособие. 2-е изд. М., 2010. – 91 с ISBN 5–230–16344–5 Рассматриваются основы теории формальных языков, приводятся методы и алгоритмы построения основных частей трансляторов и интерпретаторов. Для студентов, изучающих курсы «Системное программное обеспечение», «Теория компиляторов» и аналогичные. УДК 681.3.06 ББК 32.973 ISBN 5–230–16344–5 Карпов В.Э., 2003, 2011 3 ОГЛАВЛЕНИЕ ВВЕДЕНИЕ ................................................................................................................. 5 ТЕРМИНОЛОГИЯ ................................................................................................... 6 ПРОЦЕСС КОМПИЛЯЦИИ .................................................................................. 7 ЛОГИЧЕСКАЯ СТРУКТУРА КОМПИЛЯТОРА............................................... 7 ОСНОВНЫЕ ЧАСТИ КОМПИЛЯТОРА ............................................................. 9 Лексический анализ (сканер)............................................................................ 10 Работа с таблицами ............................................................................................ 12 Синтаксический и семантический анализ ...................................................... 12 ТЕОРИЯ ФОРМАЛЬНЫХ ЯЗЫКОВ. ГРАММАТИКИ............................... 15 ФОРМАЛЬНОЕ ОПРЕДЕЛЕНИЕ....................................................................... 15 ИЕРАРХИЯ ХОМСКОГО .................................................................................... 17 РЕГУЛЯРНЫЕ ГРАММАТИКИ ........................................................................ 19 КОНЕЧНЫЕ АВТОМАТЫ .................................................................................. 20 ФОРМАЛЬНОЕ ОПРЕДЕЛЕНИЕ....................................................................... 20 ДЕТЕРМИНИРОВАННЫЕ И НЕДЕТЕРМИНИРОВАННЫЕ КА................ 22 ПОСТРОЕНИЕ ДКА ПО НКА............................................................................. 27 ОБ УСЛОВИЯХ ЗАВЕРШЕНИЯ РАБОТЫ АВТОМАТА ............................. 29 ПРОГРАММИРОВАНИЕ СКАНЕРА................................................................ 31 ОРГАНИЗАЦИЯ ТАБЛИЦ СИМВОЛОВ. ХЕШ-ФУНКЦИИ.................... 33 ХЕШ-АДРЕСАЦИЯ .............................................................................................. 33 СПОСОБЫ РЕШЕНИЯ ЗАДАЧИ КОЛЛИЗИИ. РЕХЕШИРОВАНИЕ ........ 34 ХЕШ-ФУНКЦИИ................................................................................................... 35 КОНТЕКСТНО-СВОБОДНЫЕ ГРАММАТИКИ .......................................... 37 ОК-ГРАММАТИКИ ............................................................................................... 40 СИНТАКСИЧЕСКИ УПРАВЛЯЕМЫЙ ПЕРЕВОД...................................... 41 АВТОМАТЫ С МАГАЗИННОЙ ПАМЯТЬЮ ................................................ 45 ОПЕРАТОРНЫЕ ГРАММАТИКИ..................................................................... 49 АЛГОРИТМ ДЕЙКСТРЫ..................................................................................... 52 МАТРИЦЫ ПЕРЕХОДОВ .................................................................................... 53 ВНУТРЕННИЕ ФОРМЫ ПРЕДСТАВЛЕНИЯ ПРОГРАММЫ................. 58 ПОЛЬСКАЯ ФОРМА ............................................................................................ 58 ТЕТРАДЫ ............................................................................................................... 63 ОБ ОПЕРАТОРАХ И ВЫРАЖЕНИЯХ.............................................................. 64 ОПТИМИЗАЦИЯ ПРОГРАММ .......................................................................... 65 ИНТЕРПРЕТАТОРЫ ............................................................................................. 69 КОМПИЛЯТОРЫ КОМПИЛЯТОРОВ............................................................. 72 ПРИЛОЖЕНИЕ. ВВЕДЕНИЕ В ПРОЛОГ....................................................... 75 ОПИСАНИЕ ВЗАИМООТНОШЕНИЙ МЕЖДУ ОБЪЕКТАМИ.................. 75 4 СОСТАВНЫЕ ВОПРОСЫ ................................................................................... 78 ПРАВИЛА ............................................................................................................... 79 ПРОЛОГ С МАТЕМАТИЧЕСКОЙ ТОЧКИ ЗРЕНИЯ..................................... 80 ФОРМАЛИЗМ ЯЗЫКА ПРОЛОГ ....................................................................... 80 ПЕРЕМЕННЫЕ ...................................................................................................... 80 МЕХАНИЗМ ПОИСКА РЕШЕНИЯ................................................................... 81 РЕКУРСИВНЫЕ ПРАВИЛА ............................................................................... 81 СПИСКИ.................................................................................................................. 82 УПРАВЛЕНИЕ ПОИСКОМ................................................................................. 84 ПРИМЕРЫ ПРОГРАММ ...................................................................................... 85 Программа поиска всех циклов в графе ......................................................... 86 Анализатор арифметических выражений....................................................... 87 Некоторые полезные предикаты ...................................................................... 89 БИБЛИОГРАФИЧЕСКИЙ СПИСОК ............................................................... 91 5 ВВЕДЕНИЕ В настоящем пособии излагаются основы классической теории компиляторов – одной из важнейших составных частей системного программного обеспечения. Несмотря на более чем полувековую историю вычислительной техники, формально годом рождения теории компиляторов можно считать 1957, когда появился первый компилятор языка Фортран, созданный Бэкусом и дающий достаточно эффективный объектный код. До этого времени создание компиляторов было весьма "творческим" процессом. Лишь появление теории формальных языков и строгих математических моделей позволило перейти от "творчества" к "науке". Именно благодаря этому стало возможным появление сотен новых языков программирования. Более того, формальная теория компиляторов дала новый стимул развитию математической лингвистики и методам искусственного интеллекта, связанных с естественными и искусственными языками. Основу теории компиляторов составляет теория формальных языков – весьма сложный, насыщенный терминами, определениями, математическими моделями и прочими формализмами раздел математики. Именно "языковой" стороне теории компиляторов прежде всего уделяется внимание в этом пособии. Разумеется, и формирование объектного кода, и машинно-зависимая оптимизация, и компоновка, безусловно, важны. Однако все это – частности, зависящие прежде всего от конкретной архитектуры вычислительной машины, от конкретной операционной системы. Наша же задача – научиться основам построения компиляторов. Архитектура меняется год от года, основы же остаются неизменными (на то они и основы) уже не один десяток лет. Конечно, построить компилятор или интерпретатор можно и без всякой теории. Возможно, он даже будет работать. Но все дело в том, что, во-первых, этот титанический труд будет малоэффективен, а во-вторых, в лучшем случае мы получим "одноразовый" продукт, не пригодный для дальнейшего развития. В пособии помимо теоретических сведений приводится ряд конкретных приемов, методов и алгоритмов. Фактически здесь содержится все то, что необходимо знать для построения одной из составляющей части компилятора – интерпретатора. Кроме того, в пособии приведен ряд примеров программ на языке Пролог. Знание Пролога является весьма желательным – уж больно просто и элегантно реализуются на нем важнейшие части компилятора. Несмотря на свой почтенный возраст, Пролог является достаточно 6 экзотическим языком программирования, считаясь прежде всего языком искусственного интеллекта. Для создателя же компилятора Пролог – это очень удобный инструмент. В Приложении приведены некоторые сведения об этом языке, достаточные, по крайней мере, для того, чтобы понять суть приводимых примеров. Но главное при изучении этого курса – постараться понять "анатомию" составных частей компилятора, представить себе, как можно самому реализовать тот или иной механизм. В этом смысле курс является весьма "практическим". Впрочем, и сама теория компиляторов не есть нечто искусственное, надуманное. Сначала была практика. Теория создавалась как раз для того, чтобы помочь разработчику в его практической деятельности, поэтому в любом, самом "заумном" определении, понятии и т.п. следует искать рациональное зерно. ТЕРМИНОЛОГИЯ Начнем с того, что дадим классические определения терминам, которые будут использоваться нами далее. Транслятор – это программа, которая переводит текст исходной программы в эквивалентную объектную программу. Если объектный язык представляет собой автокод или некоторый машинный язык, то транслятор называется компилятором. Автокод очень близок к машинному языку; большинство команд автокода – точное символическое представление команд машины. Ассемблер – это программа, которая переводит исходную программу, написанную на автокоде или на языке ассемблера (что, суть, одно и то же), в объектный (исполняемый) код. Интерпретатор принимает исходную программу как входную информацию и выполняет ее. Интерпретатор не порождает объектный код. Обычно интерпретатор сначала анализирует исходную программу (как компилятор) и транслирует ее в некоторое внутреннее представление. Далее интерпретируется (выполняется) это внутреннее представление. Условно это можно изобразить следующим образом: 7 Программа на Языке 2 Исходная программа (ЯВУ -1) Транслято р Автокод или Машинный яз ык Исходная программа (ЯВУ -1) Компилято р Компиляторы пишутся как на автокоде, так и на языках высокого уровня. Кроме того, существуют и специальные языки конструирования компиляторов – компиляторы компиляторов. Компилятор компиляторов (КК) – система, позволяющая генерировать компиляторы; на входе системы – множество грамматик, а на выходе, в идеальном случае, – программа. Иногда под КК понимают язык программирования, в котором исходная программа – это описание компилятора некоторого языка, а объектная программа – сам компилятор для этого языка. Исходная программа КК – это просто формализм, служащий для описания компиляторов, содержащий, явно или неявно, описание лексического и синтаксического анализаторов, генератора кодов и других частей создаваемого компилятора. Обычно в КК используется реализация схемы т.н. синтаксически управляемого перевода. Кроме того, некоторые из них представляют собой специальные языки высокого уровня, на которых удобно описывать алгоритмы, используемые при создании компиляторов. ПРОЦЕСС КОМПИЛЯЦИИ ЛОГИЧЕСКАЯ СТРУКТУРА КОМПИЛЯТОРА Ниже приведена классическая структура компилятора. Это – достаточно общая схем. Реальный компилятор чаще всего представляет собой целый программный комплекс. 8 Литеры Компилятор Анализ Сканер Синтаксический и семантический анализ Генерация внутр. формы представления программы Синтез Подготовка к генерации команд, оптимизация Генерация команд Информационные таблицы Таблица символов (таблица имен) Таблица констант Таблица циклов Таблица переходов (таблица адресов) Исходная программа Объектная программа Символы (лексемы) Внутреннее представление исходной программы Рассмотрим далее некоторые ее составляющие. Исходная программа – текст программы на языке высокого уровня, который должен быть переведен в машинный код. 9 Информационные таблицы – самостоятельные структуры, заполняющиеся в ходе лексического анализа и дополняющиеся во время работы. Лексический анализатор (или сканер), имеющий на выходе поток лексем, нужен для того, чтобы убрать все лишнее (комментарии, разделители), выделить лексемы, т.е. лексические единицы, из которых строится машинный язык, и преобразовать их к внутренним или промежуточным формам представления. На этом этапе идет активная работа с таблицами, в которые заносится информация о распознанных лексемах, их типах, значениях и т.д. Результатом является поток лексем, эквивалентный исходному тексту. Синтаксический анализатор необходим для того, чтобы выяснить, удовлетворяют ли предложения, из которых состоит исходная программа, правилам грамматики этого языка. Наряду с проверкой синтаксиса параллельно происходит генерация внутренней формы представления программы. ОСНОВНЫЕ ЧАСТИ КОМПИЛЯТОРА Итак, можно выделить следующие этапы компиляции: 1) Лексический анализ. Замена лексем их внутренним представлением (например, замена операторов, разделителей и идентификаторов числами). 2) Синтаксический анализ. Иногда на этом этапе также вводятся дополнительные разделители и заменяются существующие для облегчения обработки. 3) Генерация промежуточного кода (трансляция). На этом этапе осуществляется контроль типа и вида всех идентификаторов и других операндов. При этом обычно преобразование исходной программы в промежуточную (например, польскую) форму записи осуществляется одновременно с синтаксическим анализом. 4) Оптимизация кода. 5) Распределение памяти для переменных в готовой программе. 6) Генерация объектного кода и компоновка программных сегментов. На всех этих этапах происходит работа с различного рода таблицами. В частности, для каждого блока (если таковые существуют в языке) идентификаторы, описанные внутри, запоминаются вместе со своими атрибутами. Условно все эти этапы можно изобразить следующим образом: 10 Исходная программа Синтакси- ческий анализ Сканер Генерация промежу- точного кода Оптимизация кода Генерация объектного кода Работа с таблицами Очевидна зависимость структуры компилятора от структуры ЭВМ, точнее, от имеющейся производительности системы. Например, при малой памяти увеличивается количество проходов компиляции (т.н. многопроходные компиляторы), а при наличии памяти большого объема можно все этапы компиляции произвести за один проход(и тогда мы имеем дело с однопроходным компилятором). Тем не менее, независимо от вычислительных ресурсов, всю вышеперечисленную работу приходится так или иначе делать. Далее мы рассмотрим вкратце некоторые из этих составных частей процесса компиляции. Лексический анализ (сканер) На входе сканера – цепочка символов некоторого алфавита (именно так выглядит для сканера наша исходная программа). При этом некоторые комбинации символов рассматриваются сканером как единые объекты. Например: - один или более пробелов заменяются одним пробелом; - ключевые слова (вроде BEGIN, END, INTEGER и др.); - цепочка символов, представляющая константу; - цепочка символов, представляющая идентификатор (имя); Таким образом, лексический анализатор (ЛА) группирует определенные терминальные символы (т.е. входные символы) в единые синтаксические объекты – лексемы. В простейшем случае лексема – это пара вида <тип_лексемы, значение>. Задача выделения лексем из входного потока зачастую оказывается весьма нетривиальной и зависящей от структуры конкретного языка. Как будет интерпретироваться такая входная последовательность "567АВ"? Это может быть одна лексема (идентификатор), а может – и пара лексем – 11 константа "567" и имя "АВ". Во втором случае либо между лексемами необходимо указание разделителя (например, пробела), либо надо заранее знать, что будет следовать дальше. Существует два основных типа лексических анализаторов – прямые (ПЛА) и непрямые (НЛА). Прямой ЛА определяет лексему, расположенную непосредственно справа от текущего указателя, и сдвигает указатель вправо от части текста, образующей лексему (ПЛА определяет тип лексемы, которая образована символами справа от указателя). Непрямой ЛА определяет, образуют ли знаки, расположенные непосредственно справа от указателя, лексему этого типа. Если да, то указатель передвигается вправо от части текста, образующей лексему. Иными словами, для него заранее задается тип лексемы, и он распознает символы справа от указателя и проверяет, удовлетворяют ли они заданному типу. У ПЛА более сложная структура – он должен выполнять больше операций, нежели НЛА. Тем не менее в большинстве современных языков программирования используется синтаксис прямых лексических анализаторов (это может быть видно по внешнему виду фраз языка). Фортран – это классический пример языка, использующего непрямой лексический анализатор. Все дело в том, что в этом языке игнорируются пробелы. Рассмотрим, например, конструкцию DO5I=1,10 … Для разбора этого предложения необходим непрямой лексический анализатор, который и определит, что означает цепочка "DO5I" – идентификатор "DO5I", или же ключевое слово "DO", за которым следует метка 5, а далее – имя переменной "I". Впрочем, аналогичные неприятности ожидают и разработчиков компиляторов языков типа C или C++, в которых существуют строковые комментарии "/*…*/" и "//…". При проведении лексического анализа, встретив символ "/", изначально неясно, является ли он оператором или началом строкового комментария. И вообще, многосимвольные лексемы – штука малоприятная для анализа. Итак, на выходе сканера – внутреннее представление имен, разделителей и т.п. Например: Вход сканера: AVR := B + CDE; // Комментарии Выход сканера: 38, -8, 65, -2, 184 (Если мы условимся обозначать оператор присваивания ":=" числом с кодом – 8, операцию сложения – числом –2, а имена переменных числами 38, 65 и 184). Кроме того, сканер занимается формированием различного рода таблиц. И прежде всего – таблицы имен, в которую он будет заносить распознанные имена – идентификаторы, константы, метки и т.п. 12 |