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

*0.5.19. Постройте эффективный алгоритм, выясняющий, лежат ли две данные вершины дерева на одном пути. Указание: Рассмотрите прямой порядок вершин.

**0.5.20. Постройте эффективный алгоритм нахождения ближайшего общего предка двух данных вершин дерева.

Упражнения на программировакие

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

0.5.22. Напишите программу, которая по матрице смежностей будет строить представление графа в виде связанного списка. 0.5.23. Напишите программы, реализующие алгоритмы 0.1-0.3.

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

Графы представляет собой старую к почетную часть математики. Теория графов излагается в книгах Харари [IS69J, Оре [1062] и Бержа [ 1958] Техника обращения с графами и деревьями внутри вычислительной машины хорошо освещена Кнутом [1968].

Алгоритм 0.2 -это алгоритм Уоршолла атом виде, как он описан у Флойда [1962а]. Один интересный результат, касающийся вычисления транзитивного замыкания отношения, приведен в работе Мунро [1971], где показано, что транзитивное замыкание можно вычргслнть за время, требуемое для вычисления произведения двух матркц над булевым кольцом. Отсюда, нспользуя результат Штрассена [1969J, получаем, что временная сложность транзитивного замыкания не превосходит п-, а не как для алгоритма 0.2.

) Рекомендуется также книга Зыкова [1969]. -Ярож. перев.

ВВЕДЕНИЕ

В КОМПИЛЯЦИЮ

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

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

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

1.1. ЯЗЫКИ ПРОГРАММИРОВАНИЯ

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

1.1.1. Задание языков программирования

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



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

1.1. ЯЗЫК.И ПРОГРАММИРОВАНИЯ

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

А-В*С

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

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

Другая проблема, связанная с языком программирования,- это проблема задания самого языка. Задавая язык программирования, мы, как минимум, должны определить

(1) множество символов, которые можно использовать для записи правильных программ,

(2) множество правильных программ,

(3) „смысл" каждой правильной программы.

Допустимое множество символов определить легко. Однако надо иметь в виду, что в некоторых языках, таких, как Снобол или Фортран, должны приниматься во внимание начало и/или конец перфокарты и, следовательно, они должны рассматриваться как символы. Пробел тоже в некоторых случаях считается символом. Определить множество программ, которые следует считать „правильными", гораздо более трудно. Во многих случаях как раз трудно решить, считать ли правильной данную программу.

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

L GOTO L

в качестве части „правильной" программы Фортрана. Однако задать множество, содержащее все действительно правильные программы, но не только их, часто бывает гораздо проще, чем задать все те и только те программы, которые считаются правильными в самом строгом смысле слова.

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

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

Третий подход - вообще игнорировать глубокие вопросы о „смысле", и именно этот подход мы выберем здесь. Для нас „смысл" исходной программы состоит просто в выходе компилятора, когда он применяется к этой программе.

Мы будем исходить из предположения, что компилятор задай как множество пар (х, у), где х-программа в исходном языке, а у - программа в том языке, на который нужно перевести X. Предполагается, что мы заранее знаем это множество и наша главная забота - построить эффективное устройство, которое по данному входу х выдает выход у. Мы будем называть это множество пар {х, у) переводом. Если х-цепочка в алфавите S, а у-цепочка в алфавите Д, то перевод-это просто отображение множества 2* в Д*.

1.1.2. Синтаксис и семантика

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



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

The pig is in the pen

имеет грамматическую структуру, представленную в виде дерева на рис. 1.1. Неконцевые вершины этого дерева помечены синтаксическими категориями, а концевые вершины, т. е. листья.

<щта оа1вуемого>

<ёруппа.>

is <предлог>

m <рпределени> <треля9ш

the реп

Рнс. 1.1. Древовидная структура английского предложения.

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

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

а\-Ь * с

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

) Использов/ие трех синтаксических категории <выражение>, <терм> и <множитель> вмес" одной категории <в1.гражеиие> вызвано желанием обеспечить однозиачн1,.,ть синтаксической структуры арифметического выражения. Читатель должен иметь эго в виду, иначе efy покажутся чересчур сложными насни последующие примеры синтаксического анализа арифметических выражений.

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

<J77epM>

<.выраж.ени.е>

+


а. Ь

Рис. 1,2. Дерево арифметического выражения.

которой соответствует категории <предложсние>. В следующей главе мы рассмотрим несколько методов строгого определения синтаксиса языка.

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

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

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





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