Теория синтаксического анализа, перевода и компиляции - Том 2 (943929), страница 2
Текст из файла (страница 2)
7.1.3. П Сначала мы ладим алгоритм, который по данной матрице цредшествования М находит ф)нкцви предшес7воеания для М, 1О 7.7. ФУНКЦИИ ПРЕДШЕСТЕОВЛНИЯ если они существуют. В следуюшем разделе опишем модификацию этого алгоритма, где по данной ыатрице предшсствования с элементами --1, +1 и „пустоа строятся ф)нкции предшествоваиия для этой матрицы, которые по возмОжности чаШе представляют пустые элелгеиты нулями. Прежде всего заметим, что если две строки матрицы пред- шествования М совпадают, то их можно слить в одну строку, и зто не повлияет на факт существования функций предшествования для М. По той же причине можно слить совпадающие столбны. Матрицу предшествованвя, в которой все совпада7о~цнс строки и столбцы слиты, назовем приаедгнной матрицей пред- шествования.
Ясно, что, если сначала привести матрицу пред. гпествованвя, легче будет строить функции предшествования. Л л г о р п т м 7.1. В ы ч и с л е в и е ф у н к ц и й и р е д ш е с т а о. ванна. Вход. Матрица М размера тхл с элементами — 1, О, )-1 и „пусто". Выход. Два целочисленных вектора / = (/„ ..., /„) и й [д„..., да), У КтоРЫХ /,<д при Мг,— — — 1 /г=й. пра Мг =0 /7 ляг при Мг =- 11 или „пет", если такие векторы не существуют.
Мешод (!) Построим ориевтированный граф, содержаший не более и-7-п вершин и называемый графом линеаризациц для й(. Сна. чала пометим и вершин буквамп Е„РЛ, ..., Р, а оставшиеся и вершин букааьп1 6„6„..., 6„. В дальнейшем граф будет преобразовываться, причем в каждый момент будут существовать некоторая вершина Ро пргдсшакляюи(ая Рг, и некоторая вершина 6, предсшпэляюи(оя 6. Вначале РТ=Р, и 67=.67 для 7' всех л и /. Затем для всех 7 и ! выполним шаг (2) или ( ). (2) Если М,.=О, построим новую вершвиу йг, сливая РТ7 с 6 . Теперь 37 представляет все те вершины, которые ранее представлялись вершинами гг и 67. (3) Если Мг —. 1.1, проведем дугу из г", в 6 . Если Мг,= — 1, проведем дугу из 67 в Рг. (4) Если полученный граф содержит циклы, выдаем сообщение „нет".
(5) Если граф линеаризацин ациклп юский, положим значение /, Равным длине самого Длинного пУти, начинаюЩегосЯ в Рп а йу — длине самого длинного пути, начииаюшегося в 67. Д 1! ГЛ. х. МвтОДЫ ОП|ИМИЗхцнн сннхлкСиЧВскнк ХНХЛИЭХтОРОВ 1 |. Функции пеедшастаоахния На шаге (4) аягоритма 7,1 для выяснения, циклический или нт ориенп|рованный граф О, можно прньмнить следуюший общий метод: (1) Пусть 0 — исходный граф.
(2) Найти в данном графе першину У, не имеюшую прямых потомков. Если таких вершин нет, граф 0 — циклический. В противном случае удалить У '). (3) Если полученный граф пуст, то граф 0 — ациклический. В противном случае повторитыпаг (2). Установив в некоторый момент, что граф ациклический, вос. пользуемся для нахождения на шаге (5) алгоритма 7.1 длины самого длинного пухи, начинаюшегося в произво1ьпой вершине, следующим методом разметки вершин.
Пусть 0 — ориензироваиный ацнклический граф. (1) Сначала пометить есе вершины графа 0 нулями. (2) Повторять шаг (3) до тех пор, пока метки графа 0 не перестанут изменяться. Метка прн каждой вершине будет равна длине самого длинного пути, начинающегося в этой вершине. (3) Выбрать в 0 некоторую вершину У. Пусть У имеет прямых потомков У„У„..., Уь с меткамн !м 1м .,., !м Заме.
нить метку вершины У на шах(1„!м ., 1„).1-!. (Если 5=О, то меткой вершины У оставить 0,] Проделать этот шаг для всех вера|ни графа О. Ясно, что шаг (3) для каждой вершины повторяеуся не бо. псе ! раз, где ! — длина самого длинного пути в 6. Пример 7.3. Рассмотрим макриду предшествования М, изображенную на рнс. 7.4. 1 2 3 4 Ь Рве. 7,4 Матрица предшестааваои». Граф линеаризацни, построенный по М, показан па рис. 7.5. Заметим, что на шаге (2) алгоритыа 7.1 слива|отея трн пары вершин: (гш Вхх), (Лм О,) и [Ро О,).
'! Строго говор», аадо удалить |акме и дуга, входящие в У.— прим. герм. ы Граф лннеариэации — а|ьиклический. В результате выполнения шага (5) алгоритма 7,1 получаюхся функции предшествования )==(О, 1, 2, 1, 3) н Л=(3, 2, О, 2, 1). Например, Гь=-3, по. скольку длина самого длинного пути, начинающегося в верши. ие Р„равна 3. ! Рис 7.5.
Граф лвнеаризхачп. Теорема 7.1. Матрица пргдшго|ягогания имеет функции пргд|игшпоогания тогда и только тогда, когда гг граф лингаризакии ацикличгский. Доказательство. Доппаточность. Сначала отметим, что алгоритм 7.1 выдает на выходе функции Г и д только тогда, когда граф лнпсарнзапии ациклический.
Достаточно показать, что если Г' и а вычисляются прн помощи алгоритма 7.1, то (1) Мн.— -О означает, что (|=дл (2) М„=- 1-1 означает, что 71> Вю (3) М, — — — 1 означает, что Г, ~а Утверждение (1) сразу следует иэ шага (2) алгоритьм 7.1. Для того чтобы доказать утверждение (2), заметим, что при М, ==-|-1 к графу линеарнзацни добавляется дуга (Ё„Г|,). Следовательно, Г! > Л„так как, если граф линеаризации ациклнче- |э 1.1. Функции предшвстВОВАиия Пример 7,4. Рассмотрим нашу любимую грамматику 6» с правиламн Е ЕСРТ) Т т- Т.Г) Р г (Е) (а Матрица отношений операторного предшествования для 6, изображена на рис.
7.б. ф ( + * а ) Е 3 4 5 а,» Рис Т.з. Граф янис»ризе»ми Аия Атк Если заменить са на — 1, на 0 и 5Р на -1-1, то получится приведенная матрица предшествования М' (рис. 7.7). В цей 15 14 Гя. т методы Оптимиз»ции синтАксичгских АИАлизАтОРов ской, длина самого длинного пути, начинающегося в вершине г, 1 должна быть по крайней мере на единицу больше длины самого длинного пути, начинающегося в 6. Утверждение (3) доказывается аналогично. Необходимоспш Допустим, что матрица прсдыествоаання М имеет функции прелшсствованнн ) и у, по граф яянеаризации содержит пикл, состоящий из последовательности вершин дт,... » ..„Н,, Н»„, тле Н,,=-Н, и й)1. Тогда на шаге (3) для всех 1, ! (1(й, можно найти такие першины Н, и 1;, „что (1) Н, и !1„,— вертпнны, вначале помеченные букнамн Е и 6, (2) Н, и 7;„представляются вершинами Нт и Нг т соответственно, (3) либо Н, есть ун !1, есть 6, и М„-.
Ур!, лцбо Н, есть Из правила (2) алгоритма 7.1 видно, что если верппгны Е и 6, предсгавля1отся одной и той же вершиной но то 7, должно равняться у„если Г н у — функшш предшествованин для М. Предположим, что 7 н у — функции предшествования дяя М. 71ус1ь йг=(„, если Нт есть Ею и й — у„если Н, есть 6,. Положим )1; равным („если !1 есть У„и равным у„, если 71 есть 6,. Тогда д, > К, = Ие > й;, = ... =. й» ~ Ц'„ Ио так как Н»ет совпаДает с й м то й'„,4 й Одн показано, что й, > Ь»Ч,.
Таким образом, матрица предшсствовання с циклическим графом линеаризаш1И не может иметь функций предшествовавия. Д Следствие. »(лгорптм 7.! вычисляет функции предшестеонсния дхя М, если они существуюю, и еыдаееи огпвгю „нет" а противном сяу гас. Сз 7.!.й. Применения н разбору, основанному нв операторном предшнстнованмн Для любой матрицы, элементы которой приннмаитг не более трех значений, можно попытаться найти функции прсдшествовання.
Описанный метод применим нечависямо от того, что именно представляют злементы. Чтобы проиллюстрировать это, покажем сейчас, как применяются функции операторного предшествовапия для представления отношений операторного предшество. ванин. Рис. 7 а. Метрике етиои ий еперетернага иредшеетвовввии А»игр»ни»гиии д,. + е ) а Рис т т Привеаеинии нм. рине предшеетзеввииа МК ГЛ. 7.
МНТОДЫ ОНТИЧИЗАНИИ СИНТАХСИЧЕСКНХ АНАЛИЗАТОРОВ ешпсции предшьстэовлния слиты строки, помеченные символами О и ), и столбцы, помеченные символами ( и а. Граф линеаризанни для М' изображен на рис. 7.8. С помощью этого графа находим функции нредшествонания )'=(О, О, 2, 4, 4) и у' = (О, 5, 1, 3, 0) для чатрицы М'. Следоаательно, фуакциямн предшествоаанпя для исходной матрицы будут )=:(0,0,2,4,4,4) и у=(0,5,1,3,5,0). Д 7.1.3. Фуинцин слабого предшвсгеоеания Как уже отмечалогь, с элеменгамн — 1, 0 и .' ! матрицы из алгоритма 7.! можно снязатьотноншаия предшестаояанпя Вирта— Вебера сю — ' и з соответственно.
Если функция предшестаояання найдены, то отношение предшествоианпя между символами Х и !' можно определить, применив перную функшно к Х, а вторую к У. В этом случае для нссх пар Х и У между символами Х и У выполняется какое-нибудь огношеинс предшествования, вследствие чего обнаружение ошибки задерживается до тех пор, пока нс будет достигнут конен входной иепочкн или пока не потребуегся проделать невозможную свертку. Однако метод функцнй предшествования можно применить для представления шагов работы алгоритма разбора типа „перенос— сасртка", сохранив некоторую возможность обнаруживать Ошибки, которая отражается пустыми элементами исходной матрицы отношений предшествования. Определим матрицу слабого предшгсшвовалил М как (шхл)-матрицу с элементами — 1, +! и „пусто".
Элементы со значением — 1, вообще говоря, обозначают переносы, элементы со значением + 1 обозначают свертки, а пустые элементы — ошибки. С помопшю такой матрицы можно описать функцию „перенос — свертка" алгоритма разбора типа „перенос †сверт" дяя грамматики слабого предшестаояания, грамматики (1,1)-предшестноааиия и простой грамматики со смешанной стратегией предшествояания. Назовем векторы ) и у функциями слабого лредшгсшнования для матрицы слабого предшествования М, если )/-.
у всякий раз, когда М, .=- — 1, а )/ > уж когда М, = л-!, / / Условие 7/=у/ можно использовать как указание на ошибочную гитуяцию, представляемую пустым элементом М, Вообще '/' говоря, не нсегда, когда М,/ — пустой элемент, удается удовлетворить условию ); =у/, но желательно сохранить, наснолько это возможно, способность обнаружения Ошибок, заложенную в исходной матрице. Таким образом, можно рассматривать проблему нахождения функций слабого предшествования для матрицы слабого пред. шествования М как задачу отыскания функция, которые в наиболыпем числе случаев порождают нули для пустых элементов матрицы М. Мы предпочитаем не заменять сразу ясе пустые !6 элементы матрицы слабого предшестноаания нулями, поскольку это ограничило бы число матрац слабого предшествовання, имеющих функции слабого предшествовапия. Некоторые пустые элементы, аозможно, придется заменить на — ! или ' 1 для тога, чтобы существоаали функции слабого предшествования (см.
![](https://s.studizba.com/z.php?f=/templates/si/i/noavatar.png&w=100&h=100&t=1"){kind=avatar}
