Теория синтаксического анализа, перевода и компиляции - Том 2 (943929), страница 4
Текст из файла (страница 4)
Но Хгт мог бы появиться а магазине вслед за Х„ только если бы была возможна свертка некоторой цепочки Уа 21 гл т мктоды ОптимизАции сигжхкснческих АнАлизАтОРОВ я Х,-, Другими словами, должна суцьестяояать конфигурация (Х,... Х,)'а, Ь,... Ь„, л'), принодяшая к (? и такая, что (Х,... Х,)'а, Ь,... Ь„, и')1- 7 (Х,... Х,Х,„,, Ь,...Ьп, и"с). Но тогда быяо бы Х, еп У вопреки усяоаию (4). Неабходимосшь. Нетрудно показать, что если ие удоклеткоряется условие (1), алгоритмы разбора не язляются строго экаиналентнымн. Поэтому опустим эту часть доказательства и займемся более слоткнысси случаямн.
Слч ша )г Пусть ие удонлетаоряется условие (2). Это значит, что для неноторой пары Ь, а верно Ь?са и незерпо Ь?а Так как 6- граммасика прас~ого предшестзоаання (и, следовательно, принедгнная), и (,(6) найдется слово вида шух. Посмотрим, как происходит разбор пеночки пба согласно алгоритмам л(, н .4.
Поскольк) юЬх Е Е(6), ни тот, ни другой алгоритм не сможет обнаружить ошибку, прежде чем симзол а нз юЬа не станет следующим входным снмаолом. Таким образом, оба анализатора должны достичь некоторой конфиг)ра~гпн [Ва, Ьах, и), когда Ь помещается з зерхушку эсагазсгна н образуется нонфигурация (баЬ, аш п). Так как Ь?,а верно, а Ь?а нет, алгоритмы 2, н Л пе являюсся строго экниналентпыми. Слу~ас) 2г Пусть нарушено (3).
Это значит, что верно А?,а, неверно А?а и я Р есть такое правило А — аХ, что Х Зэ, а. Так как б --принедепиая грамматика, найдутся прааояыаодимая и 6 цепочка )!Аш и цепочка х Е 2', для которых А =р, аХ=Ь, ))с ~, ... =?,р„ =р,х. Кроме того, найдется такая цепочка у Е 2', что ))=р' у. Согласно лемме 5.3, если У вЂ последн снмаол какой-либо нз цепочек У„ ...,()„ или х, то У з, а. Заметим, что при разборе цепочки узы первый симнол пеночки ш не будет перенесен я магазин, пока не яыполиится саертка ух и УА.
Поэтому разбор цепочки уха будет происходить сочно так жс, как и разбор цепочки ужа, пока не будет достигнута конфиг)рация (3))А, ад, и'). Но А?,а верно, а А?а нет, гак что эти дна алгоритма ие яияяются строго эизияаленгными. Схуча) уг Пусть нарушено условие (4). Другими словами, псрно Х?,А, незерно Х?А и з Р есть такое праанло А — -Ха, что Хе,.У. Пусть(!Аш — праяояыаодимая цепочка н А о,Уа=>, у, =о,...
ш?, уп ~рх. Далее, пусть ЬХи — такая праноиызоднмая цепочка, что б=р" у н Х=р'з. Тогда, согяасио лемме б 3, дла Х и пеРвых символов цепочек 7„..., Уп н х ныполнаезса отношение се,. Кроме того, для последнего сникала каждой праноиыаоднмой цепочки и выводе Х=р,'з и псркого символа цепочки х зыполняется отношение Э,. При разборе цепочки угхш будет достигнута конфигурация (ЬЬХ, хюб, и), а затеы конфигурация (ВЬХА, пб, и').
Анализа. торы попытаются здесь произвести свертку по правилу, и резуль. 22 т г шрнкции прядшгстаоаяния тате применения которого и цепочке йдш поянкяся символ А. Если Х?,А верно, а Х?А нет, снова приходим к противоречию тому, что анализаторы строго экзнналентиы. Пример 7.7. Рассмотрим грамматику простого предшестнонания 6 с правилами Е Е ЬА)А А 7' Т Тпг)Р Р (В)а В Е) Ясно, что С(б) = Е(6,). Матрица канонических отношений пред- шествования Вирта в Вебера для б принедеиа на рис. 7.13. в л г г в а ( ) + и й Рпс 7 !3.
Мптрппп кп пппчссппп пспсшсппа прсашсс ш папах Вирта — Всасра яхп бп. Выясним, какие элементы на рис. 7.!3 можно изменить и соотзетстнни с теоремой 7.2. Условие (1) гласит, что непустые элементы ис изменяются. Услозне (2) угнерждает, что ясе п)етые элементы, расположенные на пересечении последних шести стотбцок н последних шесюс строк, сушсстэенны По условию (3) (Е, 3)--сущестзенный пустой элемент, так 23 ГЛ Т МЕТОДЫ ОПТИЛТИЗАЦИИ СИН1АКСИЧДГКИХ АНАЛИЗАТОРОВ УПРАЖНЕНИЯ как есть правило Е А и А) 3 верно. Оставшиеся в последних шести столбцах пустые элементы несущественны, и, значит, они могут меняться пропзвольныч образом.
По условию (4) пус1ой элемент (3, В) существен, так как есть правило В Е) и ВсйЕ верно. Оставшиеся в первых пяти столбцах пустые элементы можно произволыю изменять. П Если алгоритм разбора типа „поренос †сверт" для обратимой грамматики слабого предшествования строить с помощью алгоритма 5.!4, то можно показать, что анализаторы, аналогичные анализаторам 7 и А, из теоремы 7.2, строга эквивалентны тогда и 1олько тогда, когда удовлетворяются первые три условия теоремы 7.2'). Пример 7.3.
Применим условия (1) — (3) теоремы 7.2 к матрице Отношений слабого предшествоваиия для бш приведенной на рис. 7.9. Легко видеть, что есе пустые элементы, стоящие в последних пгести строках, сущаственны. Кроме них есть только один существенный пустой элемент, а именно (Е, 3), Так как правило Е Т принадлежит Р и Труб верно. Изучим граф линеаризацни, изображенный на рис. 7.11.
Мы видим, что для него нет таких функций предшествования, по каждому существенному пустому элементу соответств>ет О. В противном случае вершины РО бш 6, и ВО например, были бы объединены в одну кисть. На этом можно закончить описание использования функций предшествования для построения анализаторов. Олнако мы могли бы воспользоваться несколько более слабым определением эквивалентности анализаторов. Строгая экаивалеитность — очень сильное условие.
На практике желательно, чтобы два алгоритма разбора типа „перенос— свертка" считались эквивалентными, если они допускают Одну и ту же входную цепочку или оба выдают сообщение об о1пибке в одном и том же месте ошибочной входной цепочки. Таким образом, может оказаться, что один анализатор сразу сообщил об ошибке, в то время как другому понадобилось сделать неско1ько свергок (но иа перенпсоа из входной цепочки), прежде чем выдать аналогичное сообщение. При таком условии, которое будет называться просто эквивалентностью, можно шгачптелокее видоизменять отношения предшсствования,сохраняя эквивалентность анализаторов (см.
упр, 7.13). При таком расширенном определении эквивалентности алгоритм разбора типа „перенос †сверт", использующий функшш првдшествования, приведенпые в табл. 7.1, эквивалентен анали- '> Ваоояяок, ото оаоргкк э аоалкзоторо слабого предшоо~ооо зоя ио зависят от яотрнцм ородшеотвоооккя.
24 затору, построенному при помощи алгоритма 5.14 по матрице отношений слабого предшествования, приведенной на рис. 7.9. С3 Подробна эта более слабая форма эквивалентности булет изучаться в равд. 7.2 — 7.4. Тобдод 7 ! Д 7 Р о ( > — 3 УПРАЖНЕНИЯ 7.1.!.
)(ля следующих грамматик найдите функпии слабого предшгштвовакия или докажите, что таких функций нет: (а) 3 ВА)А А — (В)(( ) (б) Е Е -(- Т (т Т ( Т Т вЂ” Т»Р(Р Р (Е)(а 7.!.2. Покажите, что если М' — матрипа, полученная из М перестановкой некоторых строк и>или столбцов, то векторы 7 и й, построенные для М' алгоритмом 7.1, будут получаться перестановкои компонент векторов, построениых лля М.
7.1.3. р!Зйдите фуикпии предшествования для матрицы, изображеаной на рис. 7.14. Рас. 7,>4. Матриц» ородшоствоэаоия. 25 гл т.методы оптимизхции синтлксических Аихлизхтагов 7.1.4. Постройте алгоритм, определяющий, имеет ли матрица такие фунцин предшествования / и й, что /=д. *7.1.5. (а) Покажите, что описанный после алгоритма 7.1 метод, определяющий, является ли ориентированный граф ациклическим, действительно работает. (б) Покажите, что можно сделать так, гжобы этот метод работал за время 0(л) (-0(е), где л — число вершин, а е — чис.ю дуг данного графа.,указание: Выберите неко~орую вершину. Рас. красьте все зергпины, лежапгие на пути, ведущем из этой веригины либо к листу, лнба к уже раскрашенной вершине, Если астреющся лист, удалите е~о, подНимитесь к его прямому предку, а затем продолжите процесс раскраски.
7.1.8. (а) Покажите, что метод разметки, приведенный после алгоритма 7.1, позволяет найти длину самого длннгюга пути, начгщающе~ оси в произвольной вершине. (б) Покажите, что этот метод можно определить так, чтобы он требовал времени 0(л)+0(е), где п — число верщпн, а е — число дуг данного графа. 7.!.7.
![](https://s.studizba.com/z.php?f=/templates/si/i/noavatar.png&w=100&h=100&t=1"){kind=avatar}
