Теория синтаксического анализа, перевода и компиляции - Том 2 (943929), страница 20
Текст из файла (страница 20)
Таблица Тг соответствует ус Зто множество таблиц совпало с множеством на рис. 7.37. Далее мы увидим, что это пронзопгло не случайно. Сл Покажем теперь, что такой подход позволяет получить мно- жество ЕЕ(1)-таблиц, эквивалентное каноническому множеству !от гл г.методы оптимизации сицтлксических »и»лиз»гонов С()(1)-таблиц. Начнем с тога, что охарактеризуем объединенную систему мкожеств ситуаций, построенную на шлге (4) алгорит- ма 7.!3.
Дейан дог Пврвшд в Е Т Т и» * ( 1 е е н ( ) те Т, Тг Т» Т» 7»о Тм Рнс. 744. Множестно гнолгш хла б», оостроеннсе ннгорнгнон 7.!3. Огтренелеиие. Пусть КООТΠ— функция, определенная на шаге (4) алгоритма 7.!3. Расширим ее область определеиип, очевидныы образо»1 включив в нее цепочки символов, т. е. (1) КООТО(7, в) =3, (2) КООТО(3, ах) =КСОТО(КООТО(3, а), Х). Пусть О=(М, В, Р, 5) — КС-грамматика и 1Ч' — расщепляю- щее множество. Будем называть ситуацию [А а 6, а] квови- долуотимой для цепочки 7, если она допустима (в смысле равд. 5.2.3) или в пополненной грамматике есть такой вывод 5'~,'Ь,Вх~~ Ь,Ь,Ах=», 616»ай, что (!) Ь,б,а = 7, (2) В б ЬР (3) а Б РО(.1.0%(В).
Отметим, что если ситуация [А а й, а] ивазидопустима для у, то существует такая авапцепочка Ь, что ситуация [А а 6, Ь] допустима для у (Ь может совпасть с а). Х Х Х Х Х Х Л Х Х Х 4 Х 2 Х И 2 2 Х 4 4 Х 4 4 Х 6 6 Х 6 6 х х х д х х Х Х Х Г Х Х 5 Х Х Х Х х х х х х л х Х ! 8 Х т Х 3 5 Х 5 5 Х 5 5 Х 5 5 тг Т» Т, Х Х Г, Х х х х х т, х х х Х Х Х Х Х Тг Х Х Х Х Х Х Х Х Х Х Х Х Х Х Х Х Х Х Т Т Т Т Л' Л' Т Х х т т т х х 7 х Х Х Тгр Т» Х Х 7» Х Х Х Х Х Тн Х Х Тп Х Х Х Х л 77 Х Х Х Х Х Х Х Х Х Х Х Х Х Х Х Х Х Х 1.». ИетОды псстРОения ья(м.анализаторов лемма 7,3. Пусть 0 =-(К, 2, Р, 5) — КС-гРамматика, Уломинавигаяся выше, и КООТО(й„у) =7 для некоторой цепочки у из (К О Б)'. Тогда 2 — множество квазидопуотимых соогуаций для у.
доказательство. Докажем лемму индуицией по [7[. Базис, у=в, опустим, так как при проведении шага индукпии он станет очевидным. Пусть 7 = у'Х и уй †множест квазндопустимых ситуаций даа 7', Равное КООТО(7„7'). ПУсть уй= 3(,'О... О 3~»Слрчай, когда [5' .5, в] или [5' 5 е] принадлежит уд, проаналиаи. ровать легко, поэтому подробности мы опустим. Предположим, ч»о [А а Ь, а] принадлежит 3=-КООТО(р„у Х). Ситуапия [А —.а Ь, а] могяа попасть в 3 тремя путями. Случай 1: Допустим, что [А а 6, а]БООТО(д,», Л) для ! некоторых р, а=-а'Х и [А а' ° ХЬ, а]чд,». Тогда ситуация '» [А а'.ХЬ, а] ивазидопустима для у', а ото»ода следует, что ситуация [А а Ь, а] квазидопустимз для у.
l Случай 2: Допустим, что [А а.д, а]600ТО (7,», Х) и а--.е. Тогда найдется ситуация [В Ь,Х СЬМ Ь], принадлежащая ООТО(3,», Х), и вывод С=в, Аш, где об Г1ДБТ (иб»Ь). Следовагельно, ситуация [В 6, ХСЬМ Ь] квазидопустима для у', а ситуация [В 6,Х.С6„Ь] квазидопустима для 7. Бели первым символом пеночки ш служит а или ш=в и а появляется в Ь„ то снтуапия [А а д, а] допустима для 7. Аналогично, если ситуация [В 6,Х СЬ„Ь] допустима для 7, то допустимой дли у будет и ситуация [А а.б, а]. Поэтому предположим, что ш=в, 6»~'е, а=Ь и ситуация [В Ь,Х СЬО Ь] квазидопустима для у.
Тогда существует вывод 5' т»,' 6,0х ~', 6»6,Вх ~, 6„6,6,ХСЬ,х ~1 6,6,Ь,ХАк где 6,6,6,.х=у, Рб)6' и ЬБРОП.0%(Р). Такилг образом, поскольку а=Ь, ситуация [А а 11, а] квазидопустииа для 7. Случай 3; Допустим, что [А — а Ь, а] попадает о У на шаге (41 при выполнении операции пополнения. Тогда а=в и в СОТО(У,», Х) должна быть такая сит>ация [ — Ь,Х Сбм Ь] что С=Р',Рш, ю, Ашш,, 065' и обрП(БТ(юге) для некоторого гч РОССО%(Р). Другими словами, 0=5„а [А и (1, а] попадает в уд при присоединении множества й,'. Далее все аналогично случаю 2. Теперь докажем угнерждение, обратное к сформулированному выше, а именно: если ситуация [А — а 6, а] квазидопустима (69 гл.
т. мюоды опгимизгини син~лк~ичьских анализа~огсз т.е методы пОстРОения ьлаьхнх.чизхтороя для у, то она принадлежит д. Мы не рассматриваем более простои случай, когда ситуация доп)стима для 7. Предположим поэтому, что ситуация [А а Р, а] квазидопустнма, но недопустима. Тогда существует вывод 5'~) Ь,Вх=~'„Ь,Ь,Ах~,б,б.,абх где 7=616га, ВЕЬР и ай РОССО)У(В). Если атьг, то ьюжно записать а в виде а'Х. Тогда ситуация [А — а' ° Хб, а] квази- допустима для 7' и, значит, принадлежит 36.
Отсюда сразу следует, что [А а б, а]ЕР. Поэтому будем счьщзть, что а=.е. Рассмотрим деа случаи, соотвегству!ощие Ьь~=г и Ь,=е. Случай 1: Ь,~е. Тогда существуют выводы В=ь'.ЬгС~, бгЬ,ХЬ, н 6„~",А. Значит, ситуация [С вЂ” 6, ° Хб„а] каазидоп)стима для у' и потому принадлежит уд. Отсюда вытекаег, что [С 6,Х.Ь„а]й,э. Так как Ь,~,А, нетрудно показать, что либо при выполнении операции замыкания, либо при выполнении операции пополнения ситуация [А- а Ь, а] попадае1 в У. Случай 2; Ь,—...е. В этол1 случае существует вывод 5'=ь, 6 Су~гбьд,ХЬьу, где Ь,у~', Вх. Тогда ситуания [С 6, ° Хб„с], где с=р1((57(у), допустима для у'. Следовательно, [С Ь,Х Ь„ с]йу.
Так как Ь„у=ь',Вх, то прн выполнении операции пополнения в д включаются ситуации вида [В-' е, Ь], где В е— правило, а Ь принадлежит РОССО%(В). Поскольку В =.ь', А, ситуации [А а.б, а] добавляется к й либо при замыкании (в смысле определения, данного при описании алгоритма 7.12) множества, содержащего [В - е, Ь], либо при последующем выполнении операции пополнения. Теорема 7.10. Пусть (М, Х, Р, 5) — КС-грамматики и (ат, Т,)— мнсжестоо Е(((1)-таблиц дт 6, построенное алгоритмом 7.13. Пусть (ьт„т,) — каноническое множество. Эти дга множества лшблиц экгиеахеитны. До к а з а т е л ь с т в о.
Из леммы 7 3 вытекает, что таблица из множества Я, связанная с цепочкой у, совпадает в действиях с таблицей из Ф;, связанной с 7, везде, гпе в Ю, стоит дей. степе, отличное от ошибка, Поэтому, если два множества не эквивалентны, можно найти такую входную цепочку ю, что при работе с а, анализатор делает последовательность тактов (Т„м)) — *(ТХ Т,...Х Т„, х)'), после чего сообщает об ошибке, а при работе с у он делает последовательность тактов (Т„м)) — "(Т,Х,Т;...Х Т', х) ) — (Т„Р,Пы ..)г„(7„, х) )- "(т„р,и, . Р,П„и(), х') ') Дле ярсстоты им опусгнла ь этих ншфигурачиех вмхохнме леночке. 1!о Предположим, что таблица ()„строится по множеству ситу.
аций у. Тогда р содержит такую ситуацию [А а (1, Ь], что биме и айЕРР(6). Так как ситуация [А а 6, е] квазидопу. стима для У, ..У„, то по лемме 7.3 супгествует вывод 5'=р) 7Ау=>, (аду для некоторого у, где уа: —. Ры .. Г„. Так нак есть вывод 'г',... У„~',Х,...Х„, то У содержит ситуацию [В 6 е, с], допустимую для Х,...Х, где ай ЕРР(ес). (Случай е=е и а=с не исилючается. В самом леле, это будет в том слуЧае, если последовательность тактов (7',Х,Т;... Х„Т', х) — *(Т,Р,Ц...Т„П„, х) имеет ненулевую данну.
Если длина равна нулю, то роль ситу. алии [В Ь а, с] и~рвет [А а д, Ь].) Так как а=р!ВВТ(х), предположение о том, что при работе с множеством Ю' анализатор сообшает об ошибие в конфигурации (Т„Х,Т;... Х Т„'х), неверно. Теорема доказана. Сравним алгоритм расщепления грамматики с 5Ей-алгоритмом.
Алгоритм расщепления представляет собой обобщение 5СВ метода в следующем смысле. Теорема 7.11. Пусть С=(М, В, Р, 5) — КС-грамматика. 0 является 5Щ!)-грамматикой тогда и только тогда, когда алгоритм 7.13 работает успешно с Расщедляюи(и и множестеом Ьй В мпсм случае множестеа таблиц, порождаемые этими двумя методами, согпадают. Доказательство. Если Ы'=-(ц, то ситуеиия [А а.Ь, а] квазидопустима для 1 тогда и только тогда, когда ситуация (А — а Ь, Ь] допустима для некоторых Ь и а из РОССОЙ(А). Это следует из того, что если В ~', ЬС, то РОССО%(В) од ш РО!Л.ОХу(С).
Из леммы 7.3 вытекает, что Я.й-множества ситуаций совпадают с множествами, пОстроенными алгоритмом 7.13. ьз Теорема 7.9 представляет собой, таким образом, следствие теорем 7.10 и 7.11. В алгоритме 7.13 законченная процедура построения канани ческого Сй(1)-анализатора применяется к каждой грамматике-компоненте. Поэтому интуитивно, если грамматика не является 5(.В-грамматикой, желвтатьно собрать в олной нз компонент все те особенности данной грамматики, из-зв которых она нс является 5СВ-грамматикой. Проиллюстрируем это рассужденис примером. гл. Р.матоды оптнмнззцнн сннтлкснчаскн» лнглнзлтогов упглжненяя Прнмер 7.31.
Рассмотрим (1) (2) (3) (4) (б) (б) (7) ,длнлдм а Ь с а е !.П(1)-грамматику 5 Аа 5 8АЬ 5 сЬ 5 ВВ А с В Вс В Ь йреклу 8 4 8 с 5 с 8 впвлжненмя 6„...) ).)((0)-гралгматнк, тг Тг Тг Х Тс Тг Тг Т Х Х Х Х Х Х ХХ Тг !<!<л 1<1~!<п !<!<а 1~1, 1<л Тг !к Тг 1гг 7\г Рас. 7.45. Мнсжсстсс !.3(!Ьггблзп. Ыз.эа правпл (1) — (3) н (б) она не является 51.р-грамлгатикой Взяв в качестве расщепляющего мвожества (5, В), объединим этн четыре правила в одну' грамматику-компоненту, а затем применим к ней (.)7(1)-лгетцд.
Алгоритм 7.13 применительно к такому расщепляющсму множеству выдаст множество (.Пл(1). таблнгг, показанное на рнс. 7АЬ. С) гщ мз Х 8 8 8 Х Х Х Х Х Л 8 Х Х Х Х Х 8 8 Х Х Х Т 7 Х 7 5 8 Х Х Х Х Х 8 Х Х хххх Х Х 8 Х 4 Х 6 6 Х 6 Х Х Х Х 3 Х 8 Х Х Х Х 5 Х Х Х х х х х а Х Т Х Х Х Х Х Та Х Т, Тг Х Х Х Х Х Х Х Х Х Х Х Х Тгс Х Х ХгмХХХТ„Х Х Х Х Х Х Х Х Х Х Х Х Х Тз Х Х Х Х Х Х Х Х Х Х Х Х Х Х Х Х Х Х Х тм Х Х Х Х Х Х Х Х Х Х Х Х Х Х Х Х Наконец, отметим, что ии алгоритм 7.10, ни алгоритм 7.13 не используют в полной мере технику отсрочки в обнаружении ошибок и слияния таблиц.
![](https://s.studizba.com/z.php?f=/templates/si/i/noavatar.png&w=100&h=100&t=1"){kind=avatar}
