Теория синтаксического анализа, перевода и компиляции - Том 1 (943928), страница 14
Текст из файла (страница 14)
*0.5.4. (а) Придумайте алгоритм, отображающий левое скобочное представление дерева в правое. (б) Придумайте алгоритм, отображающий правое скобочное представление дерева в левое. 0,5.5. Во сколько разных линейных порядков можно вложить частичный порядок, заданный ациклическим графом на рис. 0.8? 0.5.6. Докажите теорему 0,4, 0.5,7. Укажите верхние границы времени и емкости, необходимых для реализации алгоритма 0.1, считая, что' требуется одна ячейка памяти для хранения имени вершины или целого числа и один элементарный шаг для каждой операции из некоторого разумного множества примитивных операций, включающего арифметические операции и операции проверки или изменения ячейки массива, индексом которой является известное целое число.
0,5.8. Пусть А = (а, Ь, с, д) и )7 = ((а, Ь), (Ь, е), (а, с), (Ь, г()). Найдите линейный порядок )с', для которого )7 с:-')7'. Сколько существует таких линейных порядков? Определение, Неориенчированный граф 6 — это тройка (А,Е,7), где А — множество вершин, Š— множество имен ребер и 7 — отображение множества Е в множество неупорядоченных пар вершин. Запись 7(е):=(а, Ь) означает, что ребро е соединяет вершины а и Ь. Путем в неориентированпом графе называется такая последовательность вершин а,, а,, а.„..., а„, что для каждого !, ! е ((н, найдется ребро, соединяющее а,, с а;. Неориентированный граф называется связным, если для каждых двух его вершин существует соединяющий их путь.
Определение. Неориентированное дерево можно определить рекурсивно следующим образом. Неориентированное дерево — это 66 я ее из одной или более вершин, в котором множество, сос она нз од елена одна вершина г, называемая корнем. выде ль или более множеств шины разбиваются иа нуль и. ое из которых образует дерево. Деревья г и корень каждого такого поддеваются поддеревьями корня г и о рева соединен неориентироваиным ребром с г. Остовом связного неориентированного гра а ерево с ребрами из грач,а ф б содержащее все его вершины.
д апи я остова связного иео- 0.5.9. Напишите алгоритм построения осто риентированного графа. — не по ядочениый) граф, в котором 0.5.10. Пусть (4, )7) — (неу ор отношения и в ычислите М+ и покажите, что смежностей графа (А, Н+). 0.5.11. Покажите, что алгоритм О. р у т еб ет по ядка и" элеи . 0.5.7. ментарных шагов, подо бных тем, которые упоминались в упр. 0.5.12. Докажите, что алгоритм 0.3 от мечает ве шину Ь тог- Р да и только тогда, когда а!7' а ~Ь 0.5.13. Покажите, что алгоритму 0.3 р у т еб ется время, прс порцпональное большему из чисел 'А и 0.5,14.
Какие из следующих трех неупорядоченных ориентированных графов равный б, = ((а, Ь, е), ((и, Ь), (Ь, с),(с, а))) 6, =-: ((а, Ь, е), ((Ь, а), (а, с), (Ь, с))) б, = ((а, Ь, е), ((с, Ь), (с, а), (Ь„а))) 0.5.15. Даны три упо . Д ~ т и порядоченных ориентированных гра а, у акис из иих равны? которых помечены только вершины. Какие из ии б, = ((а, Ь, с), (((а, Ь), (а, с)), ((Ь, а), (Ь, с)),((с, Ь)))) с разметкой 1,(а) =Х, 1,(Ь) =2 и 1,(с) = ! . 6,=((а, Ь, с), (((и, с)), ((Ь,с), (Ь, а)), ((с,Ь), (с, а)))) с разметкой 1,(а)= 1', 1, (Ь) — Х и 1, (с)=-2.
б, = ((а, Ь, с), Яа, с), (а, Ь)), ((Ь, с)), ((е,а), (с, Ь)Е с разметкой 1, (а)= Г, !з (Ь) =Х и 1, (с) =Е. 0.5.16. Закончите доказательство теор тео емы 0.5. ляю ий связеи ли ие- 0.5.17. Дайте алгоритм, определяющ ", ориентированный граф. *0.5.18. Дайте алгоритм, определяющий, равны ли два графа. 67 зФ 69 ГЛ. О. ПРЕДВАРИТЕЛЬНЫЕ МАТЕМАТИЧЕСКИЕ СВЕДЕНИЯ "0.5.19. Пост ой р те эффективный алгоритм, выясняю нй, ле "*0.5,20. Пост ойте е р зфф ктнвный алгоритм нахождения б жайшего общего предка двух а д нных вершин дерева. ия ли- Упражнения на програмлгарование 0.5.21 Н . Напишите программу, которая будет ст оить ма смежностей по представлению графз, за ного списка.
ю графз, заданному в виде связан- 0.5.22. Напишите программ, кот р р мму, которая по матрице смежностей тронть представление графа в виде связанного списка. 0.5.23. Напишите п о рограммы, реализующие алгоритмы 0.1 — 0.3. Замечания по литературе Графы представляют собой старую и почетяую часть ь графов излагается в книгах Аарари [!9691 О е )С 1 р [)г621 ~~ржи [)9661з).техрошо освещена Кнутом "[!9681 "Р"'"'и 'ВУ'Ри 'ычи"н"л"юй " """" Алгоритм 0.2 — зто алгоритм Уоршолла в том ви е, как да [!962а[ Один интересный резул ного замыкания отноше, ун 97 н й результат, каса!о~ ения, приведен в работе Мун о )97 что транзитивное замыкание можно слепня произведения двух матриц над б 'ле можно вычислить за в емя, р е Ш р осе [)9691 уя ного замыкания нс превосходит пз'вт а одит и, а не пз как для алгоритма 0,2, ч Р ) иомекдуется также кинга лыкова ',!969,".— П вЂ” рил.
перев. | ВВЕДЕНИЕ В КОМПИЛЯЦИ10 В этой книге рассматриваются проблемы, связанные с отображением одного представления алгоритма в другое. Один из самых распространенных примеров такого отображении — компиляция исходной программы, написанной на языке программирования высокого уровня, в объектный код конкретной вычислительной машияы. )ч[ы обсудим технику трансляции алгоритмов, применяемую при конструировании компиляторов и других устройств, предназначенных для работы с языками.
Чтобы показать зту технику в надлежащей перспективе, мы резюмируем здесь узловые аспекты процесса компиляции и упомянем о других областях, где синтаксический анализ или трансляция играют главную роль. Как и в предыдущей главе, те, кто уже знаком с материалом (в данном случае с компиляторами), обнаружат, что изложение довольно элементарно. Такие читатели могут пропустить эту главу или только просмотреть ее для ознакомления с терминологией.
1 1. ЯЗЫКИ ПРОГРАММИРОВАНИЯ В этом разделе мы кратко обсудим понятие языка программирования, а затем коснемся проблем, связанных с заданием языка программирования и построением транслятора для такого ! языка. 11.1. Задание языков программирования Операции машинного языка цифровой вычислительной машины неизменно оказываются гораздо более примитивными по сравнению со сложными функциями, встречающимися в математике, технике и других областях. Хотя любую функцию, которую можно задать алгоритмом, можно реализовать в виде последовательности чрезвычайно простых команд машинного языка, ГЛ.1.
Взнданнк В КОМПИЛЯЦИЮ в большинстве приложений гораздо предпочтительнее использовать язык высокого уровня, элементарные команды которого приближаются к типу операций, встречающихся в приложениях. Например, если выполняются матричные операции, то для выражения того обстоятельства, что матрица А получается перемножением матриц В и С, удобнее написать команду вида А=ВэС чем длинную последовательность операций машинного языка, предназначенную для выполнения того же умножения.
Языки программирования могут значительно облегчить тяжелую и нудную работу, связанную с программированием на машинном языке, но вместе с ними появляется ряд новых присущих им проблем. Само собой разумеется, что так как вычислительные мап1ииы пока могут „понимать" только машинный язык, то программу, написанную на языке высокого уровня, надо в конце концов перевести (транслировать) на машинный язык. Устройство, выполняющее этот перевод, называют компилятором. Другая проблема, связанная с языком программирования,— это проблема задания самого языка. Задавая язык программирования, мы, как минимум, должны определить (1) множество символов, которые можно использовать для записи правильных программ, (2) множество правильных программ, (3) „смысл" каждой правильной программы.
Допустимое множество символов определить легко. Однако надо иметь в виду, что в некоторых языках, таких, как Снобол или Фортран, должны приниматься во внимание начало и/или конец перфокарты и, следовательно, они должны рассматриваться как символы. Пробел тоже в некоторых случаях считается символом. Определить множество программ, которые следует считать „правильными", гораздо более трудно. Во многих случаях как раз трудно решить, считать ли правильной данную программу.
При задании языков программирования стало уже обычным определять класс допустимых программ с помощью грамматических правил, позволяющих строить и такие программы, правильность которых сомнительна. Например, многие определения Фортрана допускают оператор вида Е ООТО Е в качестве части „правильной" программы Фортрана. Однако задать множество, содержащее все действительно правильные программы, но не только их, часто бывает гораздо проще, чем задать все те и только те программы, которые считаются правильнымя в самом строгом смысле слова. 70 1.1. ЯЗЫКИ ПРОГРАММИРОВАНИЯ Третий и самый трудный аспект задания языка — определение смысла каждой правильной программы. К решению этой проблемы было предпринято несколько подходов.
Один из методов заключается в определении отображения, связывающего с каждой правильной программой предложение в языке, смысл которого мы понимаем. Например, в качестве „вполне понятного" языка можно взять функциональное исчисление или лямбдаисчисление. Тогда можно определить смысл программы, записанной на любом языке программирования, в термняах эквивалентной „программы" в функциональном исчислении нли лямбдаисчислении.
Под эквивалентной программой подразумевается программа, определяющая ту же функцию. Другой способ придать смысл программам заключается в определении идеализированной машины. Тогда смысл программы выражается в тех действиях, к которым она побуждает эту, машину после того, как та начинает работу в некоторой предопределенной начальной конфигурации. В этой схеме интерпретатором данного языка становится абстрактная машина. Третий подход — вообще игнорировать глубокие вопросы о „смысле", и именно этот подход мы выберем здесь. Для нас ,,смысл" исходной программы состоит просто в выходе компилятора, когда он применяется к этой программе. Мы будем исходить из предположения, что компилятор задан как множество пар (х, у), где х — программа в исходном языке, а у — программа в том языке, на который нужно перевести х, Предполагается, что мы заранее знаем это множество и наша главная забота — построить эффективное устройство, которое по данному входу х выдает выход у.
Мы будем называть это множество пар (х, у) переводом. Если х — цепочка в алфавите Х, а у — цепочка в алфавите Ь, то перевод — это просто отображение множества Х* в Лв. 1.1.2. Синтаксис и семантика При определении и реализации переводов часто бывает удобнее рассматривать перевод как композицию двух более простых отображений. Первое из них, называемое синтаксическим отображением, связывает с каждым входом (программой в исходном языке) некоторую структуру, которая служит аргументом второго отображения, называемого семантическим.
![](https://s.studizba.com/z.php?f=/templates/si/i/noavatar.png&w=100&h=100&t=1"){kind=avatar}
