Теория синтаксического анализа, перевода и компиляции - Том 2 (943929), страница 7
Текст из файла (страница 7)
под- множества дуг, которое образует дерево и вкльочаст в себя асе вершины графа> наименьшего веса. Здесь весом остапа назы- вается сумма меток его дуг, Рас 7.!7, Граф герьгагоа, сзязаияыа с М,. путь из !З в Е, проходнщий через У, можно сначала сгенерн. ровать операторы оореноса для У. Для того чтобы построить операторы переноса, соответствующие /, можно юять операторы переноса для У и написать перед ними те из операторов переноса для Е, которые еще не написаны Тогда для строк у и к будет порождена такая последовательность операторов переноса: 52: Операторы переноса для алиментов строки л, не содержащихся в строке У, и'У: Операторы переноса для элементов строки У'. Ргс.
7.!8 Осгегяге дерево. 5У;. )а, а, (а, а, а„ а, а, а, аг аг а, а, иг а, а, гл 2 методы оптимиззции синтгксичаских Аиглнзгтогов Число операторов переноса для У и Е будет, таким образом, равно 1(8, 'г)+1()', 3).=1(Ы, Я), а не 1(8, у) +1(23, 3). Мы попутно получили Операторы переноса для У. Можно обобщить этот прием и построить алгоритм, который, получая на вход произвольный ориентированный остов графа переносов, выдает множество Операторов переноса, „соответствующих" этому остову. Число операторов переноса равно сумме меток всех дуг остова.
Метод можно представить в виде следующего алгоритма. Алгоритм 7.3. Построение множества операторов переноса по остову. Вход. Матрица переносов М, и остов ее графа переносов. Выход. Последовательность операторов языка Флойда — Эванса. Мгиюд. Для каждой вершины У остова, за исключением корня, строим последовательность операторов (а, а,!»5а, (а, а) е5а, )а„ а„! е 5а„ ! ! 1.' Здесь ь — метка строки у в матрице М , (т .
е . множество метан 5Х2, ..., 5Х„, где Х,, ..., Х вЂ” символы, строки которых в матраце предшествовайия образуют строку )' в М,), а' †мет прямого предка вершины У в остове; а„ ..., а„ вЂ столб, покрываемые страной у матрицы М„ но не ее прямым предком. Для вершины 2З добавляем новый вычисляемый оператор перехода: 23: эр! ! )777 Операторы, соответствующие вершинам, можно располагать в любам порядке, ио сслн оператор 1.' непосредственно предшествует оператору с меткой Г, то его можно выбросить. С) Пример 7.!2. Дерево, изображенное на рис, 7.!8, является остовои графа переносов, изображенного на рис.
7.!7. С помощью алгоритма 7.3 по дереву рис. 7.)8 порождается приведенная ниже последовательность операторов. Конечно, последовательность операторов, порождаемая алгоритмом 7.3, не т 2. Оптиь2изАпия АнглизАРОРОВ ФлОйдА — ввАисА единственно возможная; допустимы п другие последовательности. Под 5); подразумевается множество меток, соответствующее строке )', матрицы переносов. е5а, е Эаг Я е 5иг е5аг е5а е5и Эа, 8 е 5а» )7:Ф к ю послед Теорема 7,3.
Алгоритм 7.3 строит та у оэаглгльиость операторов яэьгка Флойда--Эгаиси, что залгии гю посгсдогатгльнасти алгртиорог переноса, пастрагииьы илгоритлол 7.2, ле отражается иа логгдглии аиагиэатари Флойда — Эмгиса. Д о к а з а т е л ь с т в о. Заметии, что если сначала вычисляется последовательность операторов, полученная для вершины )' по алгоритм» 7.3, то затем будут выполняться в точности те операторы, которые былп сгенернровапы для предков вершины )'. 7)сгко показать, что эти операторы служат для ароверки того, ГЛ.
т. МЕТОДЫ ОптимизАУ)ии синтАксичвских АЯАЛизАтОРОВ что в следующей позиции входной цепочки стоит один из символов, столбцы которых покрываются строкой У матрицы ПЕРЕНОСОВ. Оператор с меткой 8 гарантирует, что если не выполняется перенос, то происходит переход на соответствующую Е-групп)с Если дан граф переносов, то найти его остов, для которого алгоритм 7.3 порождает наименьшее число операторов переноса, удивительно просто. Легко видеть, что, не считая операторов безусловного перехода, число операторов, вырабатываемых алгоритл)ои 7.3 (каждый нз них имеет вид (а а! э5а для некоторого а), в точности равно сумме меток дуг дерева. Алгоритм 7.4.
Построение ос) ова наименьшего асса по графу переносов. Вход. Граф переносов (А, )7) для матрицы Оредшествования М. Выход. Остов (А, Е'), для которого сумма ~ ((Х, 1') )х. Т) еж принимает наиыеиынее значение, Метод. Для каждой вершины У нз А, отличной от корня, выбрать такую вершину Х, что величина ((Х, У) принимает наименьшее значение для всех дуг, входящих в )г. Включить (Х, 1') в Е'. С) Пример 7.13.
Остов на рис. 7.!8 получен Оо графу переносов рис. 7.!7 с помощью алгоритма 7 4. (З Теорема 7.4. Число операторов переноса, ко)норме страши лгоритм 7.3 по остову, минимолано длл донного графа переносоо, если е качестве остога еа)брина дергео, порождаемое алгоритмом 7.4. Доказательство. Поскольку каждая вершина, кроме корня графа (А, )(), имеет единственного прямого предка, граф (А,)х') должен быть деревом. В каждан остове графа (А,)7) в каждую отличную от корня вершину входит одна дуга— отснща сразу гледует минимальность дерева (А, Е').
(З Заметим, что, как н в случае матрицы переносов, по матрице предшествования М можно построить ма)прицй сверток М„выбросив из М все элементы, кроме ТР, и слив совпадающие строки. После этого полностью аналогично графу переносов определяется граф свертои и миннмизируется число операторов проверки с помощью алгоритма, аналогичного алгоритму 7.4. Детали построения мы оставлием читателю. Приведем пример минимизации полного анализатора Флойда †Эван для грамматики 6,, тл оптимизлция лнллизлтооов олоядл — эвлисл Пример 7.14. Матрицы Ме и М, для 6е показаны в табл, 7.2.
Здесь ) = ((,.(-, ", 3! и с= (Е а )!. Т блана Т.У ( а 1 е * ) г>> > г >'» (> ы м, Применяя алгоритм 7,4 для слиянии операторон переноса и операторов проверки, получаем следующий анализатор )рлойда— Эванса для 6,. Началы)ый оператор помечен меткой 53. е5( «5а 8 е 5) «5№ ! ( ( ! а а ! ! ) ) (+ — +! допуск 5Т; ЕП ЕТ 5а: Еа Вц Е)) ЙЕ: Е() Е+) Е ': Еб: СЕ: Са: С): СТ: (+ (3 ! №! ') Здесь этот аееретао выаалзеетея тальха э таи случае, если э еерху:аее ыегеэнее аахахетех Е.
Есле бы эта была эе тах, оРншлась бы зеыееэть уи сеиеалаи Е (елэ, е абшеи случае, начальным симвален). ау №! Š—; у(г )(е Те№ № № (Е№ ! Е Е Т Т ! ! — Е! )Э е5» Е.№ выдача 1 СТ выдача 2 СТ выдача 3 СЕ выдача 4 СЕ выдача б Са выдача б С) ошибка 6 6 6 6 ошибка 5 у№ гл. г методы огживгизвции синтвксичесхих АнАлнзхтовов УПРАЖНЕНИЯ х, хв )а Р) выдача 6 Са х, УПРАЖНЕНИЯ Е вЂ” + ТЕ' Е' +тб') е Т РТ' т',гт')е Р (Е)(а (а) 5 5 -р 7 ) 1 ) (5))и(5))а (б) 5 051)01 (в) Е Е+Т)Т Т ТвР)Р Р Р)Р)Р Р (Е) (а) 42 Предпоследний оператор яграет роль 1Э для операторов проверки.
Р) Меж!го улучшать анализаторы на языке Флойда — Эванса, исходя и из других соображений. Одним пз таких улучшений может служить преобразование, при котором два оператора обьеднняются в один. Например, второй оператор анализато д О, можно обьединить с оператором, помеченным меткий 5а, ,ля а ат ра и написать Если надо слегка изменить поведение анализатора, можно внести а него дальнейшие изменения. Однилв нз них ыожет быть задержка в обнаружении опвибок.
Например, анализатор для Со из равд. 3.4.3 использует то.высо 11 операторов, зо в некого ых случаях обнаружение ошибок в нем задерживается. Р Необходимо подчеркнуть, что на языке Флойда — Эванса можно записать любой из рассмотренных в гл, б анализаторов. Для того чтобы сделать это эффективно, можно применить приемы, аналогичные тем, которыми мы пользовались в настоящем разделе Наконец, встает вопрос реа.тизацин анализатора, заднсанного на языке Флойда †-Эванса.
Оператор языка может вызвать одну из следующих элементарных операций: чтение входного символа, сравнение символов, запись символов в магазин, выталкиван и,!волов из магазина, порождение выходной цепс ~хи. Реализовать эти операции весьма просю. Следовательно, можно написать программу, которая будет отображать анаяизатор на языке да — вапса в последовательность таких элементарных операций.
Для выполнения этой последовательности элементаримк операций лостаточно неболыпого интернрстатора. 7,2.1. С языке ... С помощью алгоритма 7.2 постройте анализата Флойда — Эванса лля следующих грамматик слабого п едры на шествования: ого пред- 7.2.2. Воспользуйтесь методами этого раздела для улучшения анализаторов, построенных в упр, 7.2.1. 7.2.3. Найдите матрицы переносов и саертои для матрицы слабого предшествования, приведенной на рнс. 7.19. х, хв х х, хв Ряс 7. Ш Мвтрвщ слвбого првлшвствовв вв. 7.2.4. Постройте графы переносов и сверток для матриц пе.
реносов и сверток, найденных в упр. 7.2.3. 7.2.5. Примените алгоритм 7.3 для нахожденввя кратчайшей последовательности операторов переноса и проверки для графов, построенных в упр. 7.2.4. *7.2,6. Разработайте ялгорятм построения детерминированного левого анализатора па языке Флойда †Эван для !.1(1)-грамматики. 7.2.7. С помощью алгоритма, разрагютаниого в упр, 7.2., .2.3, напишите на языке Флойда — Эванса левый анализатор для 1 Е(1).грамматики *7.2З.
Пользуясь методами этого раздела, улучшите анализатор, построенный в упр. 7.2.7. 43 ГЛ. Т МЕТОДЫ ОПТИМИЭАГ!ИИ СИНТАКСИЧЕСКИХ АНАЛИЗАТОРОВ "7.2,9. Разработайте алгоритм построения детерлэиинрованнаго правого анализатора на языке Флойда -Эванса для 1.Я(1)-гран. матнкн. 7.2.10. С памшцью алгоритма, разработанного в упр. 7.2.9, посгройте правые анализаторы для бэ н граммагнкн нз уп р.
![](https://s.studizba.com/z.php?f=/templates/si/i/noavatar.png&w=100&h=100&t=1"){kind=avatar}
