Главная Промышленная автоматика.

гл. I. ВВЕДЕНИЕ В КОМПИЛЯЦИЮ

1.2. ОВЗОР ПРОЦЕССА КОМПИЛЯЦИИ

компилятора. Соответствующие понятия теории контекстно-свободных языков будут изложены в гл. 2.

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

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

Замечания по литературе

Языки программирования высокого уровня появились в начале 1950-х годов. В это время вычислительные машины нуждались в арифметических операциях с плаваюи;ен точкой, так что первые языки программирования служили для представления этих операций. Первым из главных языков программирования был Фортран, который появился а середине 1950-х годов. Тогда же было создано несколько других алгебраических языков, ио Фортран иашел наиболее широкое применение. С тех пор появились сотнн языков программирования высокого уровня, в книге Саммета [1939J дается обзор многих изыков, существовавших в середине 1930-годов.

Теория языков программирования и компиляторов значительно отставала от практики. Сильным стимулом для развития теории формальных языков стало использование прп определении синтаксиса Алгола 60 [Наур, 1963] того, что теперь называют формой Бэкуса -Наура (БНФ) ). Сообщение об Алголе 60 вместе с ранними работами Хомского [)959а, J963] вызвало бурное развитие теории формальных языков в 1960-е годы. Большая часть нашей книги посвящена результатам теории языков, связанным с построением и пониманием трансляторов для языков програм.чирования.

Большинство ранних работ по теории языков касалось синтаксического аспекта определения языков. Определение семантики языков - проблема гораздо более трудная -привлекло меньше внимания идаже к моменту написания данной книги не было вполне решенным делом ). Хорошие антологии по вопросам формального задания семантики -[Стил, 1966] и [Эигелер, 1971]. . Определение изыка ПЛ/1, разработанное в Венской лаборатории фирмы ИБМ [Лукаш и Вальк, 1959], служит примером полностью формального подхода к определению большого языка программирования.

Очень интересным результатом в области языков программирования было создание расширяемых языков, синтаксис и семантику которых можно менять внутри программы. Одна из самьгх ранних и наиболее известных схем расширения языка -макроопределение (см,, например, [Мак-Илрой. 1960], [Лнвенворт, 19jG] и [Читэм, 1966]). Галлер и Перлис [1937] предложили

1) То же самое чаще неправильно, как отметил Кнут [1934], называют нормальной формой Бэкуса. - Прим. иерее.

) С тех пор появилась обширная литература, посвященная вопросам формальной семантики. Однако их рассмотрение выходит за рамки данной книги, -Я;Р1Ш. перев.

схему расширения, посредством которой в Алгол можно ввести новые типы дзггных и новые операторы. Более поздние результаты, касающиеся расширяемых языков, содержатся в работах Кристенсена и Шоу [19J9] и Вегбрейта [1970]. В качестве примера больпюго языка программирования, в котором есть средства расширения языка, можно привести Алгол 68 [паи Вейнгаарден, 1969].

1.2. ОБЗОР ПРОЦЕССА КОМПИЛЯЦИИ

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

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

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

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

(1) Лексический анализ.

(2) Работа с таблицалш.

(3) Синтаксический анализ, или разбор.

(4) Генерация кода, или трансляция в промежуточный код (например, язык ассемблера).

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

(6) Генерация объектного кода (например, ассемблирование).

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



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

Мы кратко опишем первые пять фаз компиляции. В реальном компиляторе они не обязательно разделены. Однако методически часто оказывается удобным расчленить компилятор иа эти фазы, чтобы изолировать проблемы, присущие именно этим частям процесса компиляции.

1.2.2. Лексический анализ

Первая фаза -лексический анализ. Входом компилятора, а следовательно, н лексического анализатора, служит цепочка символов некоторого алфавита. В версии языка ПЛ/Г, предназначенной для публикаций, алфавит терминальных символов содержит 60 знаков:

А В С ... Z $ @ О I 2 ... 9 „ пробел

В программе некоторые комбинации символов часто рассматриваются как единые объекты. Среди типичных примеров можно указать следующие:

1) В таких языках, как ПЛ/1, цепочка, состоящая из одного или более пробелов, обычно рассматривается как один пробел.

2) В некоторых языках есть ключевые слова, такие, как BEGIN, END, GOTO, DO, INTEGER и т. д., каждое из которых считается одним символом.

3) Каждая цепочка, представляющая числовую константу, рассматривается как один элемент текста.

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

Работа лексического анализатора состоит в том, чтобы сгруппировать определенные терминальные символы в единые синтаксические объекты, называемые е/огелг«лггг. Какие объекты считать лексемами, зависит от определения языка программирования. Лексема - это цепочка терминальных символов, с которой мы связываем лексическую структуру, состоящую из пары вида (тип* лексемы, некоторые данные). Первой компонентой пары является синтаксическая категория, такая, как „константа" или „идентификатор", а вторая-указатель: в ней указывается адрес ячейки, хранящей информацию об этой конкретной лексеме. Для данного языка число типов лексем предполагается конечным. Пару (тип лексемы, указатель) тоже будем называть лексемой, когда это не будет вызывать недоразумений.

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

Пример 1.1. Рассмотрим следующий оператор присваивания из языка, подобного Фортрану:

COST = (PRICE + TAX) * 0.98

На этапе лексического анализа будет обнаружено, что COST, PRICE и TAX - лексемы типа идентификатора, а 0.98-лексема тина константы. Знаки =: ( + ) * сами являются лексемами. Допустим, что все константы и идентификаторы нужно отобразить в лексемы типа <ид>. Мы предполагаем, что вторая компонента лексемы представляет собой указатель элемента таблицы, содержащего фактическое имя идентификатора вместе с другими собранными нами данными об этом конкретном идентификаторе. Первая компонента используется синтаксическим анализатором для разбора. Вторая компонента используется на этапе генерации кода для изготовления подходящего машинного кода.

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

<ид>;=«ид>2 + <ид>з) * <ид>4

Здесь вторая компонента лексемы (указатель данных) показана в виде нижнего индекса. Символы - ( + ) » трактуются как лексемы, тип которых представлен ими самими. Они не имеют связанных с ними данных и, значит, не имеют указателей. □

Лексический анализ провести легко, если лексемы, состоящие более чем из одного знака, изолированы с помощью знаков, которые сами являются лексемами. В примере 1.1 знаки - ( -j- ) не могут быть частью идентификатора, так что COST, PRICE и TAX легко выделяются как лексемы.

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

(1) DO 10 1 = 1.15

(2) DO 10 1 = 1, 15

В операторе (1) цепочка DO 10 I- переменная i), а цепочка 1.15 - константа. В операторе (2) DO - ключевое слово, Ю-Константа, I - переменная, 1 и 15-константы.

Если бы лексический анализатор был реализован как сопрограмма [Джентльмен, 1971; Мак-Илрой, 1968] и должен был на-

1) Напомним, что в Фортране пробелы игнорируются.



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

Таким образом, лексический анализатор иногда должен заглядывать вперед за интересующую его в данный момент лексему. Еще худший пример встречается в ПЛ/1, где ключевые слова могут быть переменными. Глядя на входную цепочку вида

DECLARE(X1, Х2, ..Хп)

упомянутый выше лексический анализатор не знал бы, что ему сказать: то ли DECLARE~идeнтификaтop функции и XI, Х2, ...

Хп -аргументы этой функции, то ли DECLARE - ключевое слово, требующее, чтобы у идентификаторов XI, Х2, Хп был атрибут (или атрибуты), расположенный непосредственно справа от правой скобки. Здесь различение лексем должно осуществляться с помощью части текста, которая идет после правой скобки. Но так как число п может быть сколь угодно большим ), то, работая с языком ПЛ/1, этот лексический анализатор должен заглядывать вперед сколь угодно далеко. Одиако существует другой подход к лексическому анализу, менее удобный, но позволяющий избежать проблемы произвольно далекого заглядывания вперед.

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

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

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

Пример 1.2. Рассмотрим текст из Фортрана DO 10 1-1, 15

с указателем, расположенным на левом конце. Непрямой лексический анализатор ответит ,да", если его спросят о лексеме

) В определении языка верхняя граница для п не указывается, однако в каждом конкретном компиляторе с языка ПЛ/1 она, конечно, существует.

типа DO или о лексеме типа <идентификатор>. Но в первом случае указатель передвинется на два символа вправо, а в последнем- на пять символов.

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

Вообще мы будем описывать алгоритмы синтаксического анализа в предположении, что лексический анализ прямой. В случае непрямого лексического анализа можно использовать „недетерминированные" алгоритмы или алгоритмы с возвратами. Синтаксический анализ этого типа мы обсудим в гл. 4 и 6.

1.2.3. Работа с таблицами

После того как в результате лексического анализа лексемы распознаны, информация о некоторых из них собирается и запасается в одной нли нескольких таблицах. Какова эта информация, зависит от языка. В случае Фортрана, например, мы хотели бы знать, что COST, PRICE и TAX - переменные с плавающей точкой, а 0.98 - константа с плавающей точкой.

Допустим, что COST, PRICE и TAX не описаны оператором описания типа. Тогда необходимую информацию об этих переменных можно извлечь из того, что COST, PRICE и TAX начинаются с букв, отличных от I, J, К, Е, М, N.

В качестве другого примера на сбор информации о переменных рассмотрим оператор Фортрана DIMENSION вида

DIMENSION А (10.20)

Встретив этот оператор, мы должны запасти информацию о том, что А - идентификатор, являющийся именем двумерного массива с размерами 10 и 20.

В сложных языках, таких, как ПЛ/1, объем сведений, которые надо запомнить о данной переменной, может быть очень велик.

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

Допустим, что в тексте встречается оператор

COST = (PRICE + TAX) * 0.98

После просмотра этого оператора таблица может иметь вид табл. 1.1.

Если позднее во входной цепочке попадется идентификатор, надо справиться в этой таблице, не появлялся ли он раньше.





0 1 2 3 4 5 6 7 8 9 10 [11] 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 62 63 64 65 66 67 68 69 70 71 72 73 74 75 76 77 78 79 80 81 82 83 84 85 86 87 88 89 90 91 92 93 94 95 96 97 98 99 100 101

0.0036