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

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

сивно перечислнмое множество? Обязательно ли скомпилирует эту программу заданный компилятор?

1.2,3. Приведите пример программы Фортрана, которая синтаксически построена правильно, но не задает (всюду определенный) алгоритм.

**1.2.4. На какое максимальное число символов требуется заглядывать вперед при прямом лексическом анализе Фортрана? (Имеется в виду число символов, которые просматриваются анализатором, но не составляют часть лексемы, для обнаружения которой осуществляется этот просмотр.)

**1.2.5. На какое максимальное число символов требуется заглядывать вперед при лексическом анализе Алгола 60? (Можно считать, что лишние пробелы и концевые маркеры перфокарт уже удалены.)

1.2.6. Разберите оператор используя дерево с внутренними вершинами, как на рис. \ Л. Указание: Вспомните, что по известному соглашению при отсутствии скобок умножения выполняются перед сложениями.

1.2.7. Разберите так же, как в упр. 1.2.6, оператор X -Л» (S + C)»D. Указание: При перемножении нескольких операндов можно считать, что порядок умножений не играет роли). Выберите любой, какой Вам нравится.

1.2.8. Примените правила генерации кодов, изложенные Б разд. 1.2.5, для синтаксически управляемого перевода деревьев разбора из упр. 1.2.6 и 1.2,7.

*1.2.9. Сохраняет ли преобразование последовательности LOAD а; STORE Р; LaAD у; STORE в последовательность LOAD у; STORE б; LOAD ее; STORE р отношение между входом и выходом, определяемое программой? Если нет, то какие ограничения надо наложить на идентификаторы ос, р, Yi (Предполагается, что к операторам преобразуемой последовательности не происходит переходов извне.)

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

*1.2.11. Сделайте синтаксически управляемый перевод, отображающий разбор, приведенный на рис. L3, прямо в код ассемблера (1.2.5).

оказатьсУважныГ "Р""" округления порядок может

ЗАМЕЧАНИЯ по ЛИТЕРАТУРЕ

*1.2.12. Постройте схему синтаксически управляемой трансляции арифметических выражений, содержащих как целые, так и вещественные переменные. (Считайте, что тип каждого идентификатора известен и операция над вещественным значениел] и целым дает вещественное.)

*1.2.13, Докажите, что алгоритм Ы работает правильно. Сначала нужно определить, когда входной оператор присваивания эквивалентен выходному коду ассемблера.

Проблема для исследования

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

1.2.14, Разработайте технику доказательства корректности (правильности) компиляторов. В этой и более широкой области доказательства корректности программ и алгоритмов уже проделана некоторая работа (см. ниже замечания по литературе). Однако ясно, что необходимы дальнейшие исследования..

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

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

Развитие компиляторов и техники компиляции шло параллельно с развитием языков программирования. Первым компилятором, который давал эффективный объектный код, был компилятор с Фортрана Бэкус и др., 1957J. С тех пор били иаписаиы многочисленные компиляторы и появилось несколько новых методик компиляции. Большие успехи были достигнуты в лексическом и синтаксическом анализах и в понимании техники генерации кодов.

Статьи, относящиеся к построению компиляторов, многочисленны. Мы не будем пытаться перечислить здесь все источники. Исчерпывающие обзоры истории компиляторов и их развития написаны Розеьюм 11967], Фельдманом и Грисои [1968], Коком и Шварцем [1970]. В ряде книг описывается техника



построения компиляторов: [Реиделл и Рассел, 1964], [Мак-Киман и др., 1970], [Кок и Шварц, 1970], [Грис, 1971]. Хопгуд [1969] дает краткий, но хорошо написанный обзор техники компиляции. Элементарное изложение вопросов компиляции см. в (Ли, 1967].

Написано несколько ком]]иляторов (таких, как DITRAN [Моултон и Мюллер, 1967], IITRAN [Дьюар и др. 1969]), в которых особое внимание уделяется всесторонней диагностике ошибок. Написаны также компиляторы, которые пытаются исправить каждую ошибку и выполнить объектную программу независимо от того, сколько оказалось ошибок. Идея здесь состоит в том, чтобы несмотря на ошибки продолжать компиляцию и выполнение программы и выявить возможно больше ошибок. Такими компиляторами являются CORC [Коивэй и Максвелл, 1963; Фримэн, 1964], CUPL [Коивэй и Максвелл, 19GSJ и PL/C (Коивэй и др., 1970].

В программе часто встречаются орфографические ошибки. Фримэи [1964 и Морган [1970] описывают технику, которую они нашли эффективной для обнаружения и исправления таких ошибок.

Общий обзор методов обнаружения ошибок при компиляции можно иайти в (Элспас и др., 1971].

Попытки создания теоретических основ доказательства корректности компиляторов излагаются в [Мак-Карти, 1963], [Мак-Карти и Нейнтср. 1967], [Пейнтер, 1970] и ]Флойд, 1967а].

Построение компилятора -задача, требующая больших затрат труда. Попытки сделать эту работу менее трудоемкой привели к появлению большого числа систем программирования, называемых компиляторами компиляторов. [Брукер и Моррис, J963(, [Читэм и Стэндиш, 1970), [Ингермаи, ]966], [Айронс, 19636], [Фельдман, 1966], [Мак-Клюр, 1965], [Мак-Кимаи и др., 1970], (Рейнольде, 165], [Шорре, 1964] и (Уоршолл и Шапиро, 1564] -только часть литературы по этому предмету. На компилятор компиляторов люжио смотреть просто как на язык программирования, в котором исходная программа -это описание компилятора для некоторого языка, а объектная программа -сам компилятор для этого языка.

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

Б нескольких компиляторах компиляторов для задания компиляторов используется какой-нибудь вариант схемы синтаксически управляемого перевода, некоторые из них обеспечивают автоматический механизм синтаксического анализа. Система TMG [Мак-Клюр, 1965] -первая из систем этого типа. Другие компиляторы компиляторов, такие, как TGS [Читэм, 1965], вместо этого обеспечивают искусный язык высокого уровня, на котором удобно описывать алгоритмы, используемые при создании компиляторов. Фельдман и Грис [196SJ написали хороший обзор По компиляторам компиляторов.

1.3. ДРУГИЕ ПРИЛОЖЕНИЯ АЛГОРИТМОВ РАЗБОРА И ПЕРЕВОДА

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

1.3.1. Естественные языки

Казалось бы, текст, написанный на естественном языке, можно переводить на другой естественный язык или на машинный язык (если этот текст описывает алгоритм) точно так же, как транслируются языки программирования. Однако проблемы возникают уже на стадии синтаксического анализа. Языки, предназначенные для вычислительных машин, имеют точное определение (не без исключений, разумеется) и легко распознаваемую структуру утверждений („предложений"), из которых они состоят. Обычная модель этой структуры - дерево, описанное в разд. 1.2.4.

Естественные языки прежде всего страдают двусмысленностью-как синтаксической, так и семантической. Возьмем в качестве очевидного примера естественного языка английский; предложение I have drawn butter имеет по крайней мере два смысла в зависимости от того, является drawn в этом предложении прилагательным или глаголом). Таким образом, однозначный разбор можно провести не для всякого английского предложения, особенно если предложение рассматривается вне контекста.

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

Распространенный пример - английское существительное реп, имеющее по крайней мере два различных значения-ручка (в выражении fountain реп -автоматическая ручка) и загон (в выражении pig pen-загон для свиней) Допустим, мы хотим переводить с английского на язык (например, русский), в котором fountain pen и pig pen обозначаются разными словами. Если нам дано для перевода предложение This pen leaks, то как будто бы ясно, что правильным значением реп здесь будет „ручка". Однако если это предложение взято из доклада „Преду-

) Приведем пример двусмысленности в русском языке, извлеченный из одной статьи о синтаксическом анализе языков программирования: „Подъем по ПОЛЮ слоев захваченных понятий". Разные смыслы получаются в зависимости от того, к чему относится „слоев" -к „полю" или к „понятий".- Прим. перев.

Есть более живые примеры, скажем название одного из органов в Академии иаук: „Комиссия по изучению четвертичного периода АН СССР".- Прим. ред.

) Пример Омонимии в русском языке: слово „ключ" имеет разные значения в выражениях „ключ в замке" и „прозрачный ключ".-Яриж. перев.

4 А. Ахо. Дж. Ульман, t. 1



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

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

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

1.3.2. Структурное описание образов

Некоторые важные классы образов допускают естественные описания, которые в каком-то смысле поддаются синтаксическому анализу. Шоу [1970], например, проанализировал фотографии, полученные с помощью камеры Вильсона, придав изображенным на них кривым подходящую древовидную структуру. Мы опишем особенно привлекательный способ определения множеств графов с помощью так называемых грамматик, порождающих графы [Пфальц и Розенфельд, 1969]. Полное их описание требует знакомства с разд. 2.1, так что здесь мы лишь приведем простой Пример, иллюстрирующий основные идеи.

Пример 1.6. Наш пример относится к графам, называемым б.Схемами), которые можно представлять себе как блок-схемы программ некоторого языка программирования, определяемых следующими правилами:

(1) Простой оператор присваивания является программой.

(2) Если 5i и Sg -программы, то ; - тоже программа.

(3) Если и Sa -программы и Л -предикат, то

if Л then else end является программой.

) В честь Э. Дейкстры.


а 5 в

Рис. 1.8. Структуры, представляющие подпрограммы блок-схемы,

на рис. 1.8. Эти правила замены, нли подстановки, соответствуют приведенным выше правилам (2) - (4).

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

(1) Дуги, входившие в теперь входят соответственно в п, ГЦ нли п.

(2) Дуга, ведущая из в п, заменяется либо (в случае а) дугой из «3 в л, либо (в случае б) дугами, ведущими из обеих вершин пц. пв вершину п, либо (в случае в) дугой из в п.

В вершинах /г и /7 проверяются предикаты, поэтому нх нельзя заменять структурами. Другие вершины представляют программы и их можно заменять далее.

Построим d-схему, соответствующую программе вида

if Si then

while do

if then Si else S. end end;

(4) Если S-программа и Л - предикат, то while Л do S end

является программой.

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





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.0037