Размещено на http://www.allbest.ru/

10

Классическая теория компиляторов

В.Э. Карпов

Москва 2011

УДК 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

Оглавление

• Введение
• 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 Рекурсивные правила
• 19.9 Списки
• 19.10 Управление поиском
• 19.11 Примеры программ
• 19.11.1 Программа поиска всех циклов в графе
• 19.11.2 Анализатор арифметических выражений
• 19.11.3 Некоторые полезные предикаты
• Библиографический список

Введение

В настоящем пособии излагаются основы классической теории компиляторов - одной из важнейших составных частей системного программного обеспечения.

Несмотря на более чем полувековую историю вычислительной техники, формально годом рождения теории компиляторов можно считать 1957, когда появился первый компилятор языка Фортран, созданный Бэкусом и дающий достаточно эффективный объектный код. До этого времени создание компиляторов было весьма "творческим" процессом. Лишь появление теории формальных языков и строгих математических моделей позволило перейти от "творчества" к "науке". Именно благодаря этому стало возможным появление сотен новых языков программирования. Более того, формальная теория компиляторов дала новый стимул развитию математической лингвистики и методам искусственного интеллекта, связанных с естественными и искусственными языками.

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

Конечно, построить компилятор или интерпретатор можно и без всякой теории. Возможно, он даже будет работать. Но все дело в том, что, во-первых, этот титанический труд будет малоэффективен, а во-вторых, в лучшем случае мы получим "одноразовый" продукт, не пригодный для дальнейшего развития.

В пособии помимо теоретических сведений приводится ряд конкретных приемов, методов и алгоритмов. Фактически здесь содержится все то, что необходимо знать для построения одной из составляющей части компилятора - интерпретатора. Кроме того, в пособии приведен ряд примеров программ на языке Пролог. Знание Пролога является весьма желательным - уж больно просто и элегантно реализуются на нем важнейшие части компилятора. Несмотря на свой почтенный возраст, Пролог является достаточно экзотическим языком программирования, считаясь прежде всего языком искусственного интеллекта. Для создателя же компилятора Пролог - это очень удобный инструмент. В Приложении приведены некоторые сведения об этом языке, достаточные, по крайней мере, для того, чтобы понять суть приводимых примеров.

Но главное при изучении этого курса - постараться понять "анатомию" составных частей компилятора, представить себе, как можно самому реализовать тот или иной механизм. В этом смысле курс является весьма "практическим". Впрочем, и сама теория компиляторов не есть нечто искусственное, надуманное. Сначала была практика. Теория создавалась как раз для того, чтобы помочь разработчику в его практической деятельности, поэтому в любом, самом "заумном" определении, понятии и т.п. следует искать рациональное зерно.

1. Терминология

Начнем с того, что дадим классические определения терминам, которые будут использоваться нами далее.

Транслятор - это программа, которая переводит текст исходной программы в эквивалентную объектную программу. Если объектный язык представляет собой автокод или некоторый машинный язык, то транслятор называется компилятором.

Автокод очень близок к машинному языку; большинство команд автокода - точное символическое представление команд машины.

Ассемблер - это программа, которая переводит исходную программу, написанную на автокоде или на языке ассемблера (что, суть, одно и то же), в объектный (исполняемый) код.

Интерпретатор принимает исходную программу как входную информацию и выполняет ее. Интерпретатор не порождает объектный код. Обычно интерпретатор сначала анализирует исходную программу (как компилятор) и транслирует ее в некоторое внутреннее представление. Далее интерпретируется (выполняется) это внутреннее представление.

Условно это можно изобразить следующим образом:

Компиляторы пишутся как на автокоде, так и на языках высокого уровня. Кроме того, существуют и специальные языки конструирования компиляторов - компиляторы компиляторов.

Компилятор компиляторов (КК) - система, позволяющая генерировать компиляторы; на входе системы - множество грамматик, а на выходе, в идеальном случае, - программа. Иногда под КК понимают язык программирования, в котором исходная программа - это описание компилятора некоторого языка, а объектная программа - сам компилятор для этого языка. Исходная программа КК - это просто формализм, служащий для описания компиляторов, содержащий, явно или неявно, описание лексического и синтаксического анализаторов, генератора кодов и других частей создаваемого компилятора. Обычно в КК используется реализация схемы т.н. синтаксически управляемого перевода. Кроме того, некоторые из них представляют собой специальные языки высокого уровня, на которых удобно описывать алгоритмы, используемые при создании компиляторов.

2. Процесс компиляции

2.1 Логическая структура компилятора

Ниже приведена классическая структура компилятора. Это - достаточно общая схем. Реальный компилятор чаще всего представляет собой целый программный комплекс.

Рассмотрим далее некоторые ее составляющие.

Исходная программа - текст программы на языке высокого уровня, который должен быть переведен в машинный код.

Информационные таблицы - самостоятельные структуры, заполняющиеся в ходе лексического анализа и дополняющиеся во время работы.

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

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

2.2 Основные части компилятора

Итак, можно выделить следующие этапы компиляции:

Лексический анализ. Замена лексем их внутренним представлением (например, замена операторов, разделителей и идентификаторов числами).

Синтаксический анализ. Иногда на этом этапе также вводятся дополнительные разделители и заменяются существующие для облегчения обработки.

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

Оптимизация кода.

Распределение памяти для переменных в готовой программе.

Генерация объектного кода и компоновка программных сегментов.

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

Очевидна зависимость структуры компилятора от структуры ЭВМ, точнее, от имеющейся производительности системы. Например, при малой памяти увеличивается количество проходов компиляции (т.н. многопроходные компиляторы), а при наличии памяти большого объема можно все этапы компиляции произвести за один проход (и тогда мы имеем дело с однопроходным компилятором). Тем не менее, независимо от вычислительных ресурсов, всю вышеперечисленную работу приходится так или иначе делать.

Далее мы рассмотрим вкратце некоторые из этих составных частей процесса компиляции.

2.2.1 Лексический анализ (сканер)

На входе сканера - цепочка символов некоторого алфавита (именно так выглядит для сканера наша исходная программа). При этом некоторые комбинации символов рассматриваются сканером как единые объекты. Например:

один или более пробелов заменяются одним пробелом;

ключевые слова (вроде BEGIN, END, INTEGER и др.);

цепочка символов, представляющая константу;

цепочка символов, представляющая идентификатор (имя);

Таким образом, лексический анализатор (ЛА) группирует определенные терминальные символы (т.е. входные символы) в единые синтаксические объекты - лексемы. В простейшем случае лексема - это пара вида <тип_лексемы, значение>.

Задача выделения лексем из входного потока зачастую оказывается весьма нетривиальной и зависящей от структуры конкретного языка. Как будет интерпретироваться такая входная последовательность "567АВ"? Это может быть одна лексема (идентификатор), а может - и пара лексем - константа "567" и имя "АВ". Во втором случае либо между лексемами необходимо указание разделителя (например, пробела), либо надо заранее знать, что будет следовать дальше.

Существует два основных типа лексических анализаторов - прямые (ПЛА) и непрямые (НЛА).

Прямой ЛА определяет лексему, расположенную непосредственно справа от текущего указателя, и сдвигает указатель вправо от части текста, образующей лексему (ПЛА определяет тип лексемы, которая образована символами справа от указателя).

Непрямой ЛА определяет, образуют ли знаки, расположенные непосредственно справа от указателя, лексему этого типа. Если да, то указатель передвигается вправо от части текста, образующей лексему. Иными словами, для него заранее задается тип лексемы, и он распознает символы справа от указателя и проверяет, удовлетворяют ли они заданному типу. транслятор программа интерпретатор

У ПЛА более сложная структура - он должен выполнять больше операций, нежели НЛА. Тем не менее в большинстве современных языков программирования используется синтаксис прямых лексических анализаторов (это может быть видно по внешнему виду фраз языка).

Фортран - это классический пример языка, использующего непрямой лексический анализатор. Все дело в том, что в этом языке игнорируются пробелы. Рассмотрим, например, конструкцию

DO5I=1,10 …

Для разбора этого предложения необходим непрямой лексический анализатор, который и определит, что означает цепочка "DO5I" - идентификатор "DO5I", или же ключевое слово "DO", за которым следует метка 5, а далее - имя переменной "I". Впрочем, аналогичные неприятности ожидают и разработчиков компиляторов языков типа C или C++, в которых существуют строковые комментарии "/*…*/" и "//…". При проведении лексического анализа, встретив символ "/", изначально неясно, является ли он оператором или началом строкового комментария. И вообще, многосимвольные лексемы - штука малоприятная для анализа.

Итак, на выходе сканера - внутреннее представление имен, разделителей и т.п. Например:

Вход сканера: AVR := B + CDE; // Комментарии

Выход сканера:38, -8, 65, -2, 184

(Если мы условимся обозначать оператор присваивания ":=" числом с кодом -8, операцию сложения - числом -2, а имена переменных числами 38, 65 и 184).

Кроме того, сканер занимается формированием различного рода таблиц. И прежде всего - таблицы имен, в которую он будет заносить распознанные имена - идентификаторы, константы, метки и т.п.

2.2.2 Работа с таблицами

Таблица имен представляет собой структуру, подобную следующей:

Номер элемента	Идентификатор	Дополнительная информация (тип, размер и т.п.)
1	A	идент., тип = "строка"
…	…	…
N	3.1415	константа, число

Механизм работы с таблицами должен обеспечивать:

быстрое добавление новых идентификаторов и сведений о них;

быстрый поиск информации.

К работе с таблицами мы еще вернемся, когда будем рассматривать хеш-функции.

2.2.3 Синтаксический и семантический анализ

Синтаксический анализ - это процесс, в котором исследуется цепочка лексем и устанавливается, удовлетворяет ли она структурным условиям, явно сформулированным в определении синтаксиса языка. Это - самая сложная часть компилятора.

Синтаксический анализатор расчленяет исходную программу на составные части, формирует ее внутреннее представление, заносит информацию в таблицу символов и другие таблицы. При этом производится полный синтаксический и, по возможности, семантический контроль программы. Фактически, это - синтаксически управляемая программа. При этом обычно стремятся отделить синтаксис от семантики насколько это возможно - когда синтаксический анализатор распознает конструкцию исходного языка, он вызывает семантическую процедуру, которая контролирует эту конструкцию, заносит информацию куда надо, проверяет на дублирование описания переменных, проверяет соответствие типов и т.п.

Предложения исходной программы обычно записываются в инфиксной форме. Однако эта привычная форма, в которой оператор записывается между операндами, является совершенно не пригодной для автоматического вычисления. Дело в том, что необходимо постоянно помнить о приоритетах операторов, "забегая" при анализе выражения "вперед". К тому же очень усложняют жизнь применяемые скобки, определяющие очередность вычислений. Альтернативой инфиксной форме является польская форма записи (в честь польского математика Лукасевича): постфиксная и префиксная. Обычно под польской формой понимают именно постфиксную форму записи. Кроме того, используются и такие внутренние формы представления исходной программы, как дерево (синтаксическое) и тетрады.

Дерево. Пусть имеется входная цепочка i=(a+b)*c. Тогда дерево будет выглядеть так:

У каждого элемента дерева может быть только один “предок”. Дерево “читается” снизу вверх и слева направо. Дерево - это прежде всего удобная математическая абстракция. На практике дерево можно реализовать в виде списковой структуры.

Польская форма записи. Существуют три вида записи выражений:

инфиксная форма, в которой оператор расположен между операндами (например, "а+b");

постфиксная форма, в которой оператор расположен после операндов (то же выражение выглядит как "а b + ");

префиксная форма, в которой оператор расположен перед операндами ("+ а b").

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

В этой форме записи выражение i=(a+b)*c выглядит так: " iab+c*=". Это выражение удобно расписывается по дереву: с нижней строки записываются “a” и “b”, далее “+” и “с”, выше - “i” и “*” и в вершине дерева “=”.

Тетрада- это четверка, состоящая из кода операции, приемника и двух операндов. Если требуется не два, а менее операторов, то в этом случае тетрада называется вырожденной. Например:

Исходное выражение	Код	Приемник	Операнд1	Операнд2
a+bT1	+	Т1	а	b
T1+cT2	*	T2	T1	c
i=T2	=	I	T2	(вырожденная тетрада)

Польская форма записи и тетрады удобны своей однозначностью. Фактически в обеих этих формах мы раскладываем исходное выражение на элементарные составляющие.

Пусть на вход синтаксического анализатора подаются выражения

"<ид1>=(<ид2>+<ид3>)*<ид4>" и "A = B+C*D"

На выходе будем иметь:

Дерево для выраженияДерево для выражения

"<ид1>=(<ид2>+<ид3>)*<ид4>""A = B+C*D"

Тетрады для "<ид1> = (<ид2>+<ид3>)*<ид4>"

+, <ид2>, <ид3>, T1

*, T1, <ид4>, T2

=, T2, <ид1>

Тетрады для "A = B+C*D"

*, C, D, T1

+, B, T1, T2

=, T2, A

(T1, T2 - временные переменные, созданные компилятором)

Польская форма для "<ид1> = (<ид2>+<ид3>)*<ид4>":

<ид1> <ид2> <ид3> + <ид4> * =

Польская форма для "A=B+C*D" будет выглядеть как "ABCD*+=". Обратите внимание на то, что порядок следования операндов в польской форме записи такой же, как и в исходном инфиксном выражении (записи "abc*=" и "bc*a=" - это вовсе не одно и то же).

Алгоритм вычисления польской формы записи очень прост:

Просматриваем последовательно символы входной цепочки. Если очередной символ является операндом (идентификатором или константой), то читаем дальше. Если символ является бинарным оператором, то извлекаем из цепочки два предыдущих операнда вместе с оператором, производим операцию и помещаем результат обратно в цепочку символов.

Более подробно этот алгоритм будет рассмотрен ниже. Оставшиеся стадии компиляции, связанные с подготовкой к генерации команд, распределением памяти, оптимизацией программы и собственно с генерацией команд и генерацией объектного кода, безусловно важны, однако сейчас на них останавливаться мы не будем.

3. Теория формальных языков. Грамматики

3.1 Формальное определение

Общение на каком-либо языке - искусственном или естественном- заключается в обмене предложениями или, точнее, фразами. Фраза - это конечная последовательность слов языка. Фразы необходимо уметь строить и распознавать.

Если существует механизм построения фраз и механизм признания их корректности и понимания (механизм распознавания), то мы говорим о существовании некоторой теории рассматриваемого языка.

Определение: Язык L - это множество цепочек конечной длины в алфавите .

Возникает вопрос - каким образом можно задать язык? Во-первых, язык можно задать полным его перечислением. С точки зрения математики это вовсе не является полной бессмысленностью. А во-вторых, можно иметь некоторое конечное описание языка.

Одним из наиболее эффективных способов описания языка является грамматика. Строго говоря, грамматика - это математическая система, определяющая язык. Как мы убедимся далее, грамматика пригодна не только для задания (или генерации) языка, но и для его распознавания.

Далее нам потребуются некоторые термины и обозначения. Начнем с определения замыкания множества.

Если - множество (алфавит или словарь), то ^* - замыкание множества , или, иначе, свободный моноид, порожденный , т.е. множество всех конечных последовательностей, составленных из элементов множества , включая и пустую последовательность.

Например, пусть A = {a, b, c}. Тогда A*={e, a, b, c, aa, ab, ac, bb, bc, cc, …}. Здесь e - это пустая последовательность.

Символом ⁺ мы будем обозначать положительное замыкание множества (или, иначе, свободную полугруппу, порожденную множеством ). В отличие от свободного моноида в положительное замыкание не входит пустая последовательность.

Теперь все готово к тому, чтобы дать основное определение.

Определение. Грамматика - это четверка G = (N, ,P,S), где

N - конечное множество нетерминальных символов (синтаксические переменные или синтаксические категории);

- конечное множество терминальных символов (слов) (N=);

P - конечное подмножество множества

(N)^*N(N)^* (N)^*

Элемент (,) множества P называется правилом или продукцией и записывается в виде ;

S - выделенный символ из N (SN), называемый начальным символом (эта особая переменная называется также "начальной переменной" или "исходным символом").

Пример:

G = ({A,S},{0,1},P,S),

P = (S0A1, 0A00A1, Ae)

Определение. Язык, порождаемый грамматикой G (обозначим его через L(G)) - это множество терминальных цепочек, порожденных грамматикой G.

Или, иначе, язык L, порождаемый (распознаваемый) грамматикой, есть множество последовательностей (слов), которые

состоят лишь из терминальных символов;

можно породить, начиная с символа S.

И опять нам требуются определения и обозначения:

Определение: Пусть G = (N, , P, S). Отношение _G на множестве (N)^* называется непосредственной выводимостью _G ( непосредственно выводима из ), если - цепочка из (N)^* и - правило из P, то _G.

Транзитивное замыкание отношения _G обозначим через ⁺_G.

Запись ⁺_G означает: выводима из нетривиальным образом.

Рефлексивное и транзитивное замыкание отношения _G обозначим через ^*_G. Запись ^*_G означает: выводима из . (Если ^* - это рефлексивное и транзитивное замыкание отношения , то последовательность ₁₂, ₂₃,.., _m-1m, где _i(N)^*, записывается так: ₁^*_m.)

При этом предполагалось наличие следующих определений:

Определение A. k-я степень отношения R на множестве A (Rk):

(1) aR1b тогда и только тогда, когда aRb (или R1єR);

(2) aRib для i>1 тогда и только тогда, когда $ cОA: aRc и cRi-1b.

Определение B. Транзитивное замыкание отношения R на множестве A (R+):

aR+b тогда и только тогда, когда aRib для некоторого i>0.

Определение C. Рефлексивное и транзитивное замыкание отношения R на множестве A (R*):

(1) aR*a для " aОA;

(2) aR*b, если aR+b

Таким образом, получаем формальное определение языка L:

L(G)={| ^*, S^*}

Нормальная форма Бэкуса-Наура. Нормальная форма Бэкуса-Наура (НФБ или БНФ) служит для описания правил грамматики. Она была впервые применена Науром при описании синтаксиса языка Фортран. По сути БНФ является альтернативной, более упрощенной, менее строгой и потому более распространенной формой записи грамматики. Далее мы будем пользоваться ею наравне с формальными определениями в силу ее большей наглядности.

Пример:

<число> ::= <чс>

<чс> ::= <чс><цифра>|<цифра>

<цифра> ::= 0|1|...|9

3.2 Иерархия Хомского

Вернемся к определению грамматики как четверки вида G = (N, , P, S), где нас интересует вид правил P, под которыми понимается конечное подмножество множества

(N)^*N(N)^* (N)^*

В зависимости от конкретики реализаций правил P существует следующая классификация грамматик (в порядке убывания общности вида правил):

Грамматика типа 0: Правила этой грамматики определяются в самом общем виде.

P: xUyz

Для распознавания языков, порожденных этими грамматиками, используются т.н. машины Тьюринга - очень мощные (на практике практически неприменимые) математические модели.

Грамматика типа 1: Контекстно-зависимые (чувствительные к контексту)

P: xUyxuy

Грамматика типа 2: Контекстно-свободные. Распознаются стековыми автоматами (автоматами с магазинной памятью)

P: Uu

Грамматика типа 3: Регулярные грамматики. Распознаются конечными автоматами

P: Ua или UaA

При этом приняты следующие обозначения:

u (N)⁺

x, y, z (N)^*

A,U N

a

Условно иерархию Хомского можно изобразить так:

Итак, иерархия Хомского необходима для классификации грамматик по степени их общности. При этом, как видно,

Грамматика типа 0 - самая сложная, никаких ограничений на вид правил в ней не накладывается.

Грамматика типа 1 - контекстно-зависимая; в ней возможность замены цепочки символов может определяться ее (т.е. цепочки) контекстом.

Грамматика типа 2 - контекстно-свободная; в левой части нетерминалы меняются на что угодно.

Грамматика типа 3 - регулярная грамматика, самая ограниченная, самая простая.

4. Регулярные грамматики

Начнем изучение грамматик с самого простого и самого ограниченного их типа - регулярных грамматик. Вот некоторые примеры:

Идентификатор (в форме БНФ)

<идент> ::= <бкв>

<идент> ::= <идент><бкв>

<идент> ::= <идент><цфр>

<бкв> ::= a|b|...|z

<цфр> ::= 0|1|...|9

Арифметическое выражение (без скобок)

G = (N, ,P,S)

N={S,E,op,i}

={<число>, <идент>,+,-,*,/}

P={Si

SiE

Eop S

op+

op-

op*

op/

i<число>

i<идент>}

Ту же грамматику бесскобочных выражений можно изобразить в виде БНФ (это не совсем строго, зато весьма наглядно):

<expr> ::= <число>|<идент>

<expr> ::= <expr><op><expr>

<op> ::= +|-|*|/

<число> ::= <цфр>

<число> ::= <число><цфр>

Еще один пример:

Z ::= U0 | V1

U ::= Z1 | 1

V ::= Z0 | 0

Порождаемый этой грамматикой язык состоит из последовательностей, образуемых парами 01 или 10, т.е. L(G) = { Bⁿ | n > 0}, где B = { 01, 10}.

Стоит, однако, рассмотреть чуть более сложный объект (например, арифметические выражения со скобками), как регулярные грамматики оказываются слишком ограниченными:

Арифметическое выражение (со скобками)

G₀=({E,T,F},{a,+,*,(,),#},P,E)

P = {E E+T|T

T T*F|F

F (E)|a}

Это, разумеется, уже не регулярная, а контекстно-свободная грамматика.

Тем не менее, регулярные грамматики играют очень важную роль в теории компиляторов. По крайней мере, их достаточно для того, чтобы реализовать первую часть компилятора - сканер. Ведь сканер имеет дело именно с такими простыми объектами, как идентификаторы и константы.

Итак, будем считать, что мы как минимум умеем порождать фразы регулярных языков. Однако все-таки нашей основной задачей является не порождение, а распознавание фраз. Поэтому далее рассмотрим один из наиболее эффективных распознающих механизмов - конечный автомат.

5. Конечные автоматы

5.1 Формальное определение

Как уже говорилось выше, грамматика - это порождающая система. Автомат - это формальная воспринимающая система (или акцептор). Правила автомата определяют принадлежность входной формы данному языку, т.е. автомат - это система, которая распознает принадлежность фразы к тому или иному языку.

Говорят, что автомат эквивалентен данной грамматике, если он воспринимает весь порождаемый ею язык и только этот язык. Как и грамматики, автоматы определяются конечными алфавитами и правилами переписывания.

Определение. Конечный автомат (КА) - это пятерка КА = (,Q,q₀,T,P), где

- входной алфавит (конечное множество, называемое также входным словарем);

Q - конечное множество состояний;

q₀ - начальное состояние (q₀Q);

T - множество терминальных (заключительных) состояний, TQ;

P - подмножество отображения вида QQ, называемое функцией переходов. Элементы этого отображения называются правилами и обозначаются как

q_ia_kq_j, где q_i и q_j - состояния, a_k - входной символ: q_i, q_j Q, a_k.

КА можно рассматривать как машину, которая в каждый момент времени находится в некотором состоянии qQ и читает поэлементно последовательность символов из , записанную на конечной слева ленте. При этом читающая головка машины двигается в одном направлении (слева направо), либо лента перемещается (справа налево). Если автомат в состоянии q_i читает символ a_k и правило q_ia_kq_j принадлежит P, то автомат воспринимает этот символ и переходит в состояние q_j для обработки следующего символа:

Таким образом, суть работы автомата сводится к тому, чтобы прочитать очередной входной символ и, используя соответствующее правило перехода, перейти в другое состояние.

Связь между конечными автоматами и регулярными грамматиками самая непосредственная, что следует из утверждения:

Каждой грамматике можно поставить в соответствие эквивалентный ей автомат, и каждому автомату соответствует эквивалентная ему грамматика.

Итак, мы установили взаимосвязи между грамматиками, языками и автоматами:

5.2 Детерминированные и недетерминированные КА

Конфигурация конечного автомата - это элемент множества Q^*, т.е. последовательность вида q, где q - состояние из Q, - элемент из ^*.

Если к любой конфигурации q_i применимо не более одного правила, то такой автомат называется детерминированным конечным автоматом (ДКА). В противном случае мы имеем дело с недетерминированным конечным автоматом (НКА).

Итак, недетерминированные конечные автоматы отличаются от ДКА

неоднозначностью переходов;

наличием, в общем случае, более чем одного начальных состояний.

КА удобно представлять в виде диаграммы состояний (переходов), представляющей собой ориентированный граф.

Пример 1. Пусть задан следующий НКА

КА = (,Q,q₀,T,P)

= {0,1},

Q = {S, A, B, Z},

q₀ = S,

T = {Z},

P = {S0Z, S0A, A1B, B0Z, B0A}

Диаграмма его переходов будет выглядеть так:

Пример 2. Рассмотрим понятие идентификатора, представленное в НФБ и в виде ДКА:

<идент> ::= <бкв>

<идент> ::= <идент><бкв>

<идент> ::= <идент><цфр>

<бкв> ::= a|b|...|z

<цфр> ::= 0|1|...|9

Изобразим множество P в виде матрицы (т.н. матрицы переходов)

P:

	1	2	3
<бкв>	2	2	-
<цфр>	4	2	-
<конец>	4	3	-
<иначе>	4	-	-

Строки матрицы - входные символы, столбцы - состояния автомата. Некоторые элементы этой матрицы - явно лишние. В частности, 3-й столбец вовсе не нужен. Эти "лишние" состояния могут служить для диагностики ошибок.

Обобщенный алгоритм работы этого автомата может быть реализован на языке С следующим образом:

char c;//текущий исходный символ

int q;//номер состояния

int a;//входной текущий символ для автомата

q=0;//начальное состояние автомата

while(1)//бесконечный цикл

{c = readchar();//считывание входного символа

a = gettype(c);//распознавание входного символа -

//отнесение его к одной из известных автомату

//категорий - <бкв>, <цфр>, <конец> или <иначе>

//Выполнение перехода

q = P[a, q];

//Обработка

if (q==3) return 1;//нормальный выход из программы

if (q==4) return 0;//выход по ошибке

}

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

Пример 3. Арифметическое выражение (без скобок)

<expr> ::= <число>|<идент>

<expr> ::= <expr><op><expr>

<op> ::= +|-|*|/

<число> ::= <цфр>

<число> ::= <число><цфр>

(На самом деле грамматкика, соответствующаяэтому автомату несколько иная, однако сути дела это не меняет.)

Рассмотрим анализатор языка, распознаваемый КА, структура которого приведена ниже:

Автомат этот недетерминированный и его реализация с помощью процедурных языков программирования может вызвать определенные сложности. Обратимся поэтому к языку Пролог:

/*

АНАЛИЗАТОР РЕГУЛЯРНОЙ ГРАММАТИКИ - 1

S->1S

S->1B

S->0A

A->0A

A->0B

B->1S

Начальное состояние S

Конечное состояние B

*/

goal

Recognize([1,1,1,1,1,0,0,0,0,0,0,1,1,0,0,0,0]).

clauses

Recognize(L) :- s(L), write("ФРАЗА РАСПОЗНАНА").

Recognize(_) :- write("*** ОШИБКА ! ФРАЗА НЕ РАСПОЗНАНА").

append([],L,L).

append([H|T],B,[H|C]) :- append(T,B,C).

S(L) :- append(L1,L2,L), L1=[1], S(L2).

S(L) :- append(L1,L2,L), L1=[1], B(L2).

S(L) :- append(L1,L2,L), L1=[0], A(L2).

A(L) :- append(L1,L2,L), L1=[0], A(L2).

A(L) :- append(L1,L2,L), L1=[0], B(L2).

B(L) :- append(L1,L2,L), L1=[1], S(L2).

B([]).

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

/* АНАЛИЗАТОР РЕГУЛЯРНОЙ ГРАММАТИКИ - 2 . Вариант без предиката append */

goal

Recognize([1,1,1,1,1,0,0,0,0,0,0,1,1,0,0,0,0]).

clauses

Recognize(L) :- s(L), write("ФРАЗА РАСПОЗНАНА").

Recognize(_) :- write("*** ОШИБКА ! ФРАЗА НЕ РАСПОЗНАНА").

S([1|L]) :- S(L).

S([1|L]) :- B(L).

S([0|L]) :- A(L).

A([0|L]) :- A(L).

A([0|L]) :- B(L).

B([1|L]) :- S(L).

B([]).

Вернемся к вопросу о конечных состояниях. Смысл конечного состояния заключается в определении условия завершения работы автомата. Работа автомата может быть завершена при попадании его в одно из заключительных состояний (такие состояния назовем поглощающими), и тогда мы имеем дело с ПЛА. Однако условие завершения может быть более сложным: работа автомата заканчивается тогда, когда входная последовательность исчерпана и при этом автомат находится в одном из терминальных состояний. Эта ситуация характерна для НЛА.

Реализовать недетерминированный автомат на Прологе достаточно просто. А сделать то же самое на процедурном языке - задача весьма нетривиальная. На практике поэтому предпочтительнее работать с "нормальным", детерминированным автоматом, не допускающим неоднозначностей.

5.3 Построение ДКА по НКА

Обычно при описании тех или иных объектов наличие дополнительных ограничений снижает общность. Однако большая общность НКА по сравнению с ДКА является кажущейся. Дело в том, что справедливо следующее утверждение:

Для любого НКА можно построить эквивалентный ему конечный детерминированный автомат.

Для построения детерминированного автомата можно воспользоваться следующей теоремой:

Теорема. Пусть НКА F= (,Q,q₀,T,P) допускает множество цепочек L. Определим ДКА F'= (',Q',q₀',T',P') следующим образом:

Множество состояний Q' состоит из всех подмножеств множества Q. Обозначим элемент множества Q' через [S₁,S₂,..,S_l], где S₁,S₂,..,S_lQ.

' = .

Отображение P' определяется как

P'([S₁,S₂,..,S_m],x) = [R₁,R₂,..,R_m],

где P({S₁,S₂,..,S_m },x) = { R₁,R₂,..,R_m }, S_i,R_iQ, x.

Пусть q₀={S₁,S₂,..,S_k}.

Тогда q₀'=[S₁,S₂,..,S_k].

Пусть множество заключительных состояний T={S_j, S_k,.., S_n}.

Тогда T'=[S_j, S_k,.., S_n].

Или, иначе,

T'={t=[S_a,S_b,..,S_c] | S_b: S_bT}.

Построенный таким образом детерминированный конечный автомат будет эквивалентен в смысле "вход-выход" исходному НКА.

Приведем пример построения ДКА по НКА. Пусть дан недетерминированный автомат

Правила переходов: {S1S, S1Z, S0P, P1Z, P0Z, Z1P, Z1S}.

Начальные состояния: {S, P}.

Заключительные состояния: {Z}.

Множество состояний ДКА будет таким: {S, P, Z, PS, SZ, PSZ, PZ}. Их будет ровно 2ⁿ-1, где n - количество состояний исходного автомата.

Его правила переходов:

{S1SZ, S0P, P1Z, P0Z, Z1PS, PS1SZ, PS0PZ, SZ1PSZ, PSZ1PSZ, PZ1PSZ}.

Начальное состояние: SP.

Заключительные состояния: {Z, PZ, SZ, PSZ}.

Тогда детерминированный автомат будет выглядеть так:

После упрощения автомата, т.е. удаления вершин, не достижимых из начальной, получим такой автомат:

Завершая рассуждения о недетерминированных автоматах, следует отметить еще один момент, связанный с множеством начальных состояний (н.с.) в НКА. Когда имеется несколько н.с., работа автомата заключается в том, что переход по входному символу осуществляется одновременно из всех начальных состояний. Именно в этом заключается суть процедуры объединения всех н.с. в одно. Это особенно важно при моделировании НКА, скажем, средствами Пролога.

5.4 Об условиях завершения работы автомата

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

Автомат нормально завершает работу тогда, когда он попадает в одно из заключительных состояний и при этом входная последовательность исчерпана.

Эта ситуация характерна для непрямых лексических анализаторов.

Таким образом, можно рассматривать два вида распознающих автоматов: автоматы для прямых лексических анализаторов (А_ПЛА) и автоматы для непрямых анализаторов (А_НЛА).

Рассмотрим в качестве примера некоторый конечный автомат:

Начальное состояние q₀=A, множество терминальных состояний T={D}.

Распишем грамматику, соответствующую этому автомату (или, строже, рассмотрим грамматику, порождающую язык, распознаваемый данным автоматом).

Для начала выпишем правила подстановок, которые получаются явным образом из правил переходов автомата. Ниже слева представлены правила переходов автомата, справа - соответствующие правила грамматики:

№	Правила перехода	Правила грамматики
1	A0A	A0A
2	A1B	A1B
3	B0C	B0C
4	B1A	B1A
5	C0A	C0A
6	C1D	C1D
7	D0D	D0D
8	D1A	D1A

Очевидно, что подобные правила грамматики не смогут породить язык. Дело в том, что в них отсутствуют терминальные подстановки, т.е. те правила, в правой части которых были бы одни терминальные символы.

В зависимости от условия завершения работы автомата будут разниться и правила соответствующих грамматик.

Для А_ПЛА, завершающего свою работу при попадании в терминальное состояние, меняется правило №6:

C1D преобразуется в терминальную подстановку C1, т.к. D - терминальное состояние.

Формально терминальные правила получаются из правил грамматики путем отбрасывания имен терминальных состояний в правой части. Таких правил у нас два - правила №6 и 7, однако правило № 7, равно как и №8, являются для нашей грамматики лишними (недостижимыми). Это видно из автомата: переходы D0D и D1A в А_ПЛА не работают.

Для грамматики, соответствующей А_НЛА, напротив, происходит добавление правил подстановки. Добавляются все терминальные правила, т.е. правила, в правой части которых отбрасываются терминальные состояния.

Таким образом, к имеющимся восьми правилам грамматики добавляются правила C1 (из правила №6) и D0 (из правила №7).

6. Программирование сканера

Итак, теперь все готово к тому, чтобы приступить к построению сканера. Напомним, что нам необходимо построить лексический анализатор для выделения из входного потока исходных составляющих языка - лексем или символов. Символами являются:

разделители или операторы (+,-,*,/,(,) и т.п.);

служебные слова (что-то вроде begin, end,... и т.п.);

идентификаторы;

числа.

Кроме того, необходимо исключать комментарии (как строчные, типа '//', так и многострочные, вида '/*...*/').

Строить сканер мы будем, используя конечный автомат. К автомату предъявляются следующие минимальные требования:

Автомат должен формировать поток лексем;

Автомат должен заносить полученные лексемы в таблицу символов или имен.

Наш распознающий автомат упрощенно может выглядеть следующим образом:

Здесь под символом D понимается цифра, L означает букву, а delim - разделитель (пробел, табуляцию и т.п.). Состояние int отвечает за распознавание числа, id - за распознавание имени, а sla, com, end и R - за распознавание комментариев. Чтобы не загромождать схему дугами, переходы в основное состояние S обозначены дублированием этой вершины.

При этом следует отметить, что

При переходе в начальное состояние S иногда требуется возвращать обратно считываемый символ входной последовательности, т.е. необходимо сместить указатель на одну позицию назад. Иначе мы просто будем терять часть лексем, т.к. автомат - это устройство, последовательно считывающее очередной входной символ на каждом такте работы.

Автомат в таком виде бесполезен, он не выполняет никаких полезных процедур.

Следовательно, автомат необходимо дополнить процедурной частью. Именно процедурная часть отвечает за формирование имен, которые далее будут заноситься в таблицу символов, за возврат считанного символа обратно во входной поток, за инициализацию и т.д. Дополнение автомата этой процедурной частью автомата заключается в том, что когда автомат совершает очередной переход, должна выполняться связанная с этим переходом одна или несколько процедур (или подпрограмм). Это, разумеется, несколько усложняет структуру автомата, однако эту работу выполнять необходимо, т.к. мы занимаемся не только проверкой входной последовательности, но и ее преобразованием в поток лексем.

7. Организация таблиц символов. Хеш-функции

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

Простейший способ организации - использовать неупорядоченную таблицу. Новый элемент добавляется в таблицу в порядке поступления. Среднее время поиска пропорционально n/2 (в среднем приходится делать n/2 сравнений).

Элементы таблицы можно отсортировать. Тогда можно использовать процедуру бинарного поиска, при котором максимальное число сравнений будет равно 1+log₂n. Однако сортировка - это слишком трудоемкая процедура для того, чтобы ее использовать при организации таблиц.

7.1 Хеш-адресация

Идеальный вариант - уметь по имени сразу определить адрес элемента. В этом смысле "хорошей" процедурой поиска является та, которая сможет определить хотя бы приблизительный адрес элемента. Одним из наиболее эффективных и распространенных методов реализации такой процедуры является хеш-адресация.

Хеш-адресация - это метод преобразования имени в индекс элемента в таблице. Если таблица состоит из N элементов, то им присваиваются номера 0,1,..,N-1. Тогда назовем хеш-функцией некоторое преобразование имени в адрес. Простейший вариант хеш-функции - это использование внутреннего представления первой литеры имени.

Пока для двух различных символов результаты хеширования различны, время поиска совпадает с временем, затраченным на хеширование. Однако, все проблемы начинаются тогда, когда результаты хеширования совпадают для двух и более различных имен. Эта ситуация называется коллизией.

Хорошая хеш-функция распределяет адреса равномерно, так что коллизии возникают не слишком часто. Но прежде, чем говорить о реализации хеш-функций, обратимся к вопросу о том, каким образом разрешаются коллизии.

7.2 Способы решения задачи коллизии. Рехеширование

Пусть хешируется имя S и при этом обнаруживается коллизия. Обозначим через h значение хеш-функции. Тогда сравниваем S с элементом по адресу (h+p₁)mod N, где N - длина таблицы (максимальное число элементов в таблице). Если опять возникает коллизия, то выбираем для сравнения элемент с адресом (h+p₂)mod N и т.д. Это будет продолжаться до тех пор, пока не встретится элемент (h+p_i)mod N, который либо пуст, либо содержит S, либо снова является элементом h (p_i=0, и тогда считается, что таблица полна).

Способы рехеширования заключаются в выборе чисел p₁,p₂,..,p_n. Рассмотрим наиболее распространенные из них.

Для начала введем параметр, называемый коэффициентом загрузки таблицы lf:

lf = n/N, где

n - текущее количество элементов в таблице, N - максимально возможное число элементов.

Линейное рехеширование

p_i = i (т.е. p₁=1, p₂=2,..,p_n=n).

Среднее число сравнений E при коэффициенте загрузки lf определяется как

E(lf) = (1-lf/2)/(1-lf).

Это - очень неплохой показатель. В частности, при 10-ти процентной загрузке имеем E, равное 1.06, при 50-ти процентном заполнении E равно всего 1.5, а при 90 процентах загрузки требуется сделать в среднем всего 5.5 сравнений.

Ниже приведен график этой функции:

Случайное рехеширование

Пусть максимальное число элементов в таблице кратно степени двойки, т.е. N=2^k. Вычисление p_i осуществляется по следующему алгоритму:

R := 1

Вычисляем p_i:

R := R*5

выделяем младшие k+2 разрядов R и помещаем их в R

p_i := R>>1 (сдвигаем R вправо на 1 разряд)

Перейти к П.2

Среднее число сравнений E при коэффициенте загрузки lf

E = -(1/lf)log₂(1-lf)

Рехеширование сложением

p_i = i(h+1), где h - исходный хеш-индекс.

Этот метод хорош для N, являющихся простыми числами.

7.3 Хеш-функции

Как уже говорилось, хеш-адресация - это преобразование имени в индекс. Имя представляет множество литер (символов), и для вычисления индекса поступают обычно следующим способом:

Берется S', являющееся результатом суммирования литер из исходного символа S (либо простое суммирование, либо поразрядное исключающее ИЛИ):

Вычисляется окончательный индекс. При этом возможны самые различные варианты. В частности:

Умножить S' на себя и использовать n средних битов в качестве значения h (для N=2ⁿ);

Использовать какую-либо логическую операцию (например, исключающее ИЛИ) над некоторыми частями S';

Если N=2ⁿ, то разбить S' на n частей и просуммировать их. Использовать n крайних правых битов результата;

Разделить S' на длину таблицы, и остаток использовать в качестве хеш-индекса.

Итак, хорошая хеш-функция - это та, которая дает как можно более равномерное и случайное распределение индексов по именам, т.е. для "похожих" или "близких" имен хеш-функция должна выдавать сильно разнящиеся индексы, т.е. не допускает группировки имен в таблице символов.

Приведем пример фрагмента программы, реализующей хеш-адресацию:

struct name//элемент таблицы символов

{char *string;//имя

name *next; //ссылка на следующий элемент

double value; //значение

};

const TBLSIZE = 23; // Количество "ящиков", по которым раскладываем символы

name *table[TBLSIZE];

name *findname(char *str, int ins)

// Функция поиска в таблице имени name

// Если ins!=0, то происходит добавление элемента в таблицу

{int hi = 0;//Это, фактически, наш хеш-индекс

char *pp = str;

// Суммируем по исключающему ИЛИ каждый символ строки.

// Далее сдвигаем для того, чтобы индекс был лучше

// (исключаем использование только одного байта)

while (*pp)

{hi<<=1; // На самом деле здесь лучше применить циклический сдвиг

hi^= *pp++;

}

if (hi<0) hi = -hi;

//Берем остаток

hi %= TBLSIZE;

//Поиск. Мы нашли список, теперь используем

// метод линейного рехеширования

for(name *n=table[hi];n;n=n->next)

if(strcmp(str,n->string)==0) return n;//Нашли. Возвращаем адрес

//Ничего не нашли

if(ins==0) return NULL; // error("Имя не найдено")

//Добавляем имя

name *nn = new name;

nn->string = new char[strlen(str)+1];

strcpy(nn->string, str);

nn->value = 0;

nn->next = table[hi];

table[hi] = nn;

return nn;

}

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

Условно механизм работы с подобной организацией таблицы символов можно изобразить так:

8. Контекстно-свободные грамматики

Следующей по сложности за регулярной грамматикой следует контекстно-свободная (context-free) грамматика (КСГ).

Естественно, определение КСГ внешне выглядит как и обычное определение грамматики: G_ксг = (N, , P, S), однако при этом характерным для КСГ является форма ее правил (продукций)

P: A,

где AN, (N)⁺.

В качестве примера рассмотрим, как мог бы выглядеть некий командный, внешне приближенный к естественному язык:

N = {группа_существ, глагол, прилагательное, существительное, предлог, фраза}

= {печатать, стереть, зеленый, первый, последний, символ, строка, страница, в}

S = фраза

P = {Фр Г, Гс

Гс Прил, С

Гс Прил, С, Предлог, Гс

Гпечатать

Гстереть

Прилзеленый

Прилпервый

Прилпоследний

Ссимвол

Сстрока

Сстраница

Предлогв}

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

...