Рассмотрение основ теории формальных языков. Ознакомление с методами и алгоритмами построения основных частей трансляторов и интерпретаторов. Характеристика внутренних форм представления программы. Исследование и анализ способов решения задачи коллизии.
Аннотация к работе
19.10 Управление поиском 19.11 Примеры программТранслятор - это программа, которая переводит текст исходной программы в эквивалентную объектную программу. Если объектный язык представляет собой автокод или некоторый машинный язык, то транслятор называется компилятором. Ассемблер - это программа, которая переводит исходную программу, написанную на автокоде или на языке ассемблера (что, суть, одно и то же), в объектный (исполняемый) код. Обычно интерпретатор сначала анализирует исходную программу (как компилятор) и транслирует ее в некоторое внутреннее представление. Компилятор компиляторов (КК) - система, позволяющая генерировать компиляторы; на входе системы - множество грамматик, а на выходе, в идеальном случае, - программа.Исходная программа - текст программы на языке высокого уровня, который должен быть переведен в машинный код. Информационные таблицы - самостоятельные структуры, заполняющиеся в ходе лексического анализа и дополняющиеся во время работы. Лексический анализатор (или сканер), имеющий на выходе поток лексем, нужен для того, чтобы убрать все лишнее (комментарии, разделители), выделить лексемы, т.е. лексические единицы, из которых строится машинный язык, и преобразовать их к внутренним или промежуточным формам представления.На этом этапе осуществляется контроль типа и вида всех идентификаторов и других операндов. Условно все эти этапы можно изобразить следующим образом: Очевидна зависимость структуры компилятора от структуры ЭВМ, точнее, от имеющейся производительности системы. Например, при малой памяти увеличивается количество проходов компиляции (т.н. многопроходные компиляторы), а при наличии памяти большого объема можно все этапы компиляции произвести за один проход (и тогда мы имеем дело с однопроходным компилятором). Таким образом, лексический анализатор (ЛА) группирует определенные терминальные символы (т.е. входные символы) в единые синтаксические объекты - лексемы. Прямой ЛА определяет лексему, расположенную непосредственно справа от текущего указателя, и сдвигает указатель вправо от части текста, образующей лексему (ПЛА определяет тип лексемы, которая образована символами справа от указателя).Таблица имен представляет собой структуру, подобную следующей: Номер элемента Идентификатор Дополнительная информация (тип, размер и т.п.) Механизм работы с таблицами должен обеспечивать: быстрое добавление новых идентификаторов и сведений о них;Синтаксический анализ - это процесс, в котором исследуется цепочка лексем и устанавливается, удовлетворяет ли она структурным условиям, явно сформулированным в определении синтаксиса языка. Синтаксический анализатор расчленяет исходную программу на составные части, формирует ее внутреннее представление, заносит информацию в таблицу символов и другие таблицы. При этом обычно стремятся отделить синтаксис от семантики насколько это возможно - когда синтаксический анализатор распознает конструкцию исходного языка, он вызывает семантическую процедуру, которая контролирует эту конструкцию, заносит информацию куда надо, проверяет на дублирование описания переменных, проверяет соответствие типов и т.п. Существуют три вида записи выражений: инфиксная форма, в которой оператор расположен между операндами (например, "а b"); постфиксная форма, в которой оператор расположен после операндов (то же выражение выглядит как "а b ");Общение на каком-либо языке - искусственном или естественном-заключается в обмене предложениями или, точнее, фразами. Возникает вопрос - каким образом можно задать язык? Строго говоря, грамматика - это математическая система, определяющая язык. Если a - множество (алфавит или словарь), то a* - замыкание множества a, или, иначе, свободный моноид, порожденный a, т.е. множество всех конечных последовательностей, составленных из элементов множества a, включая и пустую последовательность. Символом a мы будем обозначать положительное замыкание множества a (или, иначе, свободную полугруппу, порожденную множеством a).Вернемся к определению грамматики как четверки вида G = (N, a, P, S), где нас интересует вид правил P, под которыми понимается конечное подмножество множества В зависимости от конкретики реализаций правил P существует следующая классификация грамматик (в порядке убывания общности вида правил): Грамматика типа 0: Правила этой грамматики определяются в самом общем виде. Для распознавания языков, порожденных этими грамматиками, используются т.н. Распознаются стековыми автоматами (автоматами с магазинной памятью) Грамматика типа 1 - контекстно-зависимая; в ней возможность замены цепочки символов может определяться ее (т.е. цепочки) контекстом.Начнем изучение грамматик с самого простого и самого ограниченного их типа - регулярных грамматик. Арифметическое выражение (без скобок) Порождаемый этой грамматикой язык состоит из последовательностей, образуемых парами 01 или 10, т.е.
План
Оглавление
Введение
1. Терминология
2. Процесс компиляции
2.1 Логическая структура компилятора
2.2 Основные части компилятора
2.2.1 Лексический анализ (сканер)
2.2.2 Работа с таблицами
2.2.3 Синтаксический и семантический анализ
3. Теория формальных языков. Грамматики
3.1 Формальное определение
3.2 Иерархия Хомского
4. Регулярные грамматики
5. Конечные автоматы
5.1 Формальное определение
5.2 Детерминированные и недетерминированные КА
5.3 Построение ДКА по НКА
5.4 Об условиях завершения работы автомата
6. Программирование сканера
7. Организация таблиц символов. Хеш-функции
7.1 Хеш-адресация
7.2 Способы решения задачи коллизии. Рехеширование
7.3 Хеш-функции
8. Контекстно-свободные грамматики
9. Ок-грамматики
10. Синтаксически управляемый перевод
11. Автоматы с магазинной памятью
12. Операторные грамматики
13. Алгоритм Дейкстры
14. Матрицы переходов
15. Внутренние формы представления программы
15.1 Польская форма
15.2 Тетрады
15.3 Об операторах и выражениях
16. Оптимизация программ
17. Интерпретаторы
18. Компиляторы компиляторов
19. Приложение. Введение в пролог
19.1 Описание взаимоотношений между объектами
19.2 Составные вопросы
19.3 Правила
19.4 Пролог с математической точки зрения
19.5 Формализм языка пролог
19.6 Переменные
19.7 Механизм поиска решения
19.8 Рекурсивные правила
Список литературы
Введение
В настоящем пособии излагаются основы классической теории компиляторов - одной из важнейших составных частей системного программного обеспечения.
Несмотря на более чем полувековую историю вычислительной техники, формально годом рождения теории компиляторов можно считать 1957, когда появился первый компилятор языка Фортран, созданный Бэкусом и дающий достаточно эффективный объектный код. До этого времени создание компиляторов было весьма "творческим" процессом. Лишь появление теории формальных языков и строгих математических моделей позволило перейти от "творчества" к "науке". Именно благодаря этому стало возможным появление сотен новых языков программирования. Более того, формальная теория компиляторов дала новый стимул развитию математической лингвистики и методам искусственного интеллекта, связанных с естественными и искусственными языками.
Основу теории компиляторов составляет теория формальных языков - весьма сложный, насыщенный терминами, определениями, математическими моделями и прочими формализмами раздел математики. Именно "языковой" стороне теории компиляторов прежде всего уделяется внимание в этом пособии. Разумеется, и формирование объектного кода, и машинно-зависимая оптимизация, и компоновка, безусловно, важны. Однако все это - частности, зависящие прежде всего от конкретной архитектуры вычислительной машины, от конкретной операционной системы. Наша же задача - научиться основам построения компиляторов. Архитектура меняется год от года, основы же остаются неизменными (на то они и основы) уже не один десяток лет.
Конечно, построить компилятор или интерпретатор можно и без всякой теории. Возможно, он даже будет работать. Но все дело в том, что, во-первых, этот титанический труд будет малоэффективен, а во-вторых, в лучшем случае мы получим "одноразовый" продукт, не пригодный для дальнейшего развития.
В пособии помимо теоретических сведений приводится ряд конкретных приемов, методов и алгоритмов. Фактически здесь содержится все то, что необходимо знать для построения одной из составляющей части компилятора - интерпретатора. Кроме того, в пособии приведен ряд примеров программ на языке Пролог. Знание Пролога является весьма желательным - уж больно просто и элегантно реализуются на нем важнейшие части компилятора. Несмотря на свой почтенный возраст, Пролог является достаточно экзотическим языком программирования, считаясь прежде всего языком искусственного интеллекта. Для создателя же компилятора Пролог - это очень удобный инструмент. В Приложении приведены некоторые сведения об этом языке, достаточные, по крайней мере, для того, чтобы понять суть приводимых примеров.
Но главное при изучении этого курса - постараться понять "анатомию" составных частей компилятора, представить себе, как можно самому реализовать тот или иной механизм. В этом смысле курс является весьма "практическим". Впрочем, и сама теория компиляторов не есть нечто искусственное, надуманное. Сначала была практика. Теория создавалась как раз для того, чтобы помочь разработчику в его практической деятельности, поэтому в любом, самом "заумном" определении, понятии и т.п. следует искать рациональное зерно.