Теория синтаксического анализа, перевода и компиляции - Том 2 (943929), страница 17
Текст из файла (страница 17)
Пусть, как обычно, 6,— грамматика с правилами Š— Е ч-Т) Т Т-- Тнг)Р Г- (Е) [а Каноническая система мпохкеств 1.й(0)-ситуаций для 6в приведена на рис 7.36; вторые колшоиеиты, равные везде е, оп)щепы. 6,— не Я.й(0)-грамматика, потолчу что Ан например, содержит такие две ситуапии [Е' Е ° ) и [Š— Е. л-т), что Г011 0%в(Е) = (г) = ЕГГ[ ' ТГОЫО%ь(Е)) *) ') Здмь можно васаовьвоввться ф>нхннсй ГО!Бок'в х(А), пасхальну нваачнв 6 должна порождать ххх~н бм адни снмнчм вмбх~й ~ганочка, нрннвдвв .
мвй БГГ„(Р РОСЬОВв(Л) х) Звмчтнн, что Г'!Цзтв(а)=нггв(а)=БОБ!.ОП'ч(а)=.(а) вт всех а. ээ Однако 6,— 5гй(1)-гран!митина. Пля того чтобы проверить выполнение Я.й(!)-усгговия, достаточно исследовать множества, (1) содержащие ве менее двух ситуапнй, !2) содержащие ситуапию, в которой точка стоит справа от исех символов. Ьй(О).снтувннй двн Б,. Итак, нас могут интересовать только множества АО, Гв и,(,.
Для А, имеем Г01ЛЕО мг, (Е') .=- (е) и ЕГГ[+Т ГОЕ( 0%, (Е!) =- х -, '). Так как (с) 0(-ь) — я, то А, удовлетворяет условию (3) определения 5Ей(1)-гралхматики. По той же причине условию (3) удовлетворяют множества А, и А,. Следовательно, можно заключить, что 6, есть 5!.й(!)-грамматика. Теперь попытаемся построить множество Ей(!) таблиц для 51й(1)-грамматики 6, начиная с каншшческой системы Т, множеств |й(0).ситуаний для 6.
Пусть некоторое множество А из Тч содержит только две ситуалгь~и: [А — а, е) н [В р.у, е). По мому множеству лгожно построить 1.й(1)-таблицу Элементы перехода строятся огсвкдным образом, как и для Ей(0)-таб.ььхьт. Но какое действие нужно совершит!и если аванцепочкой служит символ а; свертку по правилу Л вЂ” а или перенос) Ответить иа этот вопрос можно, выяснив, верно ли, что ай ГОЕБО!Ух(Л). Если аЕ ГО1.1.0% (Л), то а не может принадлежать ЕГГ,(у) по Ав. Е' Б Е- Е~Т Е ° Т Т Т ° Р т Р Р .(Б) Г .а Ан е'. е.
Е Г-Т Ах: Е Т ° Т Т ° Р А т Р. Г- а Г: Р- (Г). Е ° Е, Т Е Т Т ° Т Р т Р г — .(ΠР— ° .а Рнс Т.ЗБ Множество А: Е Е) Т т .т*Р' Т .Р Г ° (Е! Р- а а(,х Т вЂ” Ть ° Р Р- (Б) А,ч Г-(Б) Š—. Е ч-Т А„: Š— Б~т. Т Т.*Р т т г. РПч Р (Г) гл - методы оптнмнзлции сингл<он»неких лнллизлтоеав гл метОды пОстРОения ьжл! АнАлизлтаРОа определению 5!.П(!)-граьглгатнки. Поэтому действием здесь б)дег свертка. Если же ац~ЕОЕ!.0%,(Л), то свертка не подходит. Если аЕ ЕГГ(!), то действие — перенос, в противном случае— ошибка. В законченном виде этот алгоритм приведен ниже.
Алга ритм 7.10. Построение множества 16(й) таблиц д л я 55(((й)-г р а и м а т и к и. Вход 351((й).грамлгатика 6 = (Н, 2, Р, 3) н каноническан система У, ыиожеств Е!((О)-ситуацийс для 6. Вотод. Множество (Я', Т,) Ей(й)-таблиг! для 6, называемое 5ЩА)-мложеггггвом таблиц для 6. Метод. Пусть,( — множество ЕВ(0)-сггтуацнй из д',. ЕП(й)- таблица Т, связанная с А, представляет собой пару <Д ХН по.
строеннуго так: (1) Для всех и нз лмл (а) )(и)=-пеРенос, если [Л а Р, е) пРинадлежит А, ((чае н а Е ЕГЕ« (Р ЕОЕ!.ОР(л[Л)), (б) ) (и) =свертка 1, если [Л а, е]Е А, правило ! есть Л а п л6!»ОП,0%«(Л), (в) ) (е) =допуск, если )Я'-- Я., е) Е, ! '), (г) ('(и) =-огинбка в остальных случаях. (2) й(Х) для всех Х из В 0 2 представляет собой таблицу, постросннтдо по СОТО(..1, Х). Начальная таблица Т, — это таблица, связанная с множеством, содержащим ситуацию [3' Ь, е). Алгоритм 7.10 аналогичен нашему первоначальному методу построения множества таблиц ио системе множеств сит)аггий, приведенному в равд.
5.2.5. Пусть А' — множестоо таких ситуаций [Л а.р, и), что [Л а.й,е[ЕА н иЕЕОЕ10[У (Л), и пусть Т,=(А')АЕХ,). Тогда а результате применения к д'; алгоритма 7.10 получается то же мпожестаа таблиц, что н в результате применения к д"„метода, описанного в разд. 5.2.5.
Из определения сразу видно, что каждое множество с»гтуацгтй из Х; непротиворечиво то~да и только та~да, когда 6 — 5ЕК(й)- грамматика. Пример 7.25. Построим 51.П[!)-множество таблиц длн множества ситуаций, наказанного на рис. 7.35, Таблицу, построенную по А„ назовем Т,. Мы рассмотрим толька построение таблацы То Моо кество А,— эта ([Е Т 1,)Т Т ° «Е)). Путь Т,— <ЕХ>. Так квк ГОЕЕО%(Е) — -(+,), е), то)(4-) = [))) — — )(е) =-свертка 2.
'! Кввомвческвя с«стемв мнем«ств свтуацвй стронтея о повал«в«вой грвммвтнле. (Правила перенумерованы как обычно.) Так как ЕЕГ(вр ЕОЫ.О%[Т)) — (»), то )(«) = перенос. Для остальных аванпепочек Ди) = )[)1=- ошибка. у(Х) определено только для Х =в. Из рис. 7.35 легко видеть, что Х(в)-.-Т,. Все множество таблиц' показано на рнс. 7.37. Аее2лдве Переход а + ( ) е Е т е а + е ( ) Та т, Тг Тз т« 77 т, Тз 7»о т Рис 7 Зт.,в!пол«ство 5! ЦП!.тгелве лле 0» С точностью то имен таблиц и элементов»Р это множества совпадает с множеством, проведенным на рис.
7.32. Докажем, что алгоритм 7.10 для БЕ(((й).грамматигги 6 всегда строит допустимое множество Е)((й)-табл»»и. На самом деле получаемое множества »аблиц эквиоалситна каноническому множеству ЕП(й)-таблиц для 6. Теорема 7.9. Если 6 — 55(((й)-грамматика, то 5ЕЫ(й)-лнтжегтел глаблиц (,7, Т„), построенное аггоритл»ом 7 !О, еквивалемтло комоигтескому множеству (вт„Т,) 16(й)-таблиц для 6. Дока за тел ь ство. Пусть УА — каноническая система множеств Е)((й)-ситуаций для 6 и й,— -система множеств Е(((0)-си.
туаций для 6. Определим ядро множества ситуаций А как множество заключенных в скобки первых компонент ситуаций нз 3 Х Х Л Х Х х к х х х л х 3 ю х а х Х 4 4 Х 4 4 Х 6 6 Х 6 б Л Х Х Л Х Х Х Х д Х Х К Х Х Л Х Х Х 8 Х К Л Х х т у х х з з х з з К 5 5 Х 5 5 т т г т х х т х Х Х А' Х Т, А' Х Х Х Х Х Х Х Т, Х Х Х Х Х Х Х Х Х Х х х х х х х к х Тв тх Тв Т» Х Х Т«Х х т т т х х т к Х Х Т,в Т„ Х Х Тз Х Х Х Х Х Т, Х ХТи х х х х х тт к х Х Х Х Х Х Х Х Х Х Х Х Х Х Х Х Х гл. г.мгтады аптижизчцнн синтаксических днплиздтарав г.ч методы пашпояння ья!пьпнплнзптопов этога множества. Например, ядром множества [А и.(з, и] является [Л а.б] '). Обозначим ядро множества и( через СОКЕ( О.
Все множества ситуацнй в системе д', различны, однако не. которые множества нз 4'„могут иметь одинаковые ядра. Легко наказать, что Уп = (СОКЕ (и() ] и( Е Кп) . Определим на множестве таблиц функцию й, соответствующую фувкцни СОКЕ, определенное на множествах ситуаций.
Положим й (7') =Т', если Т вЂ” канопичгская ЕК(й)-таблица, связанная с,(, а Т' — В.К(й)-таблица, полученная с помощью алгоратма 7.10 нз множества СОКЕ(п(). Легко провернть, гта й коммутнрует с СОТО, т. с, СОТО(й(Т), Х) =й(СОТО(Т, Х)). Как н раньше, пусть Ш'=.(г[Л а б. ]([Л и 8, е[йи( н и ЕГО!.ЕОТчгп(Л)) Пусть Т'„=( ((А'Е:Т,). Мы уже знаем, что ф', Т„) совпадает с пгноагсс~ вам 1.К(й)-таблгщ, построенным по б'; методам, описанньгп| в равд. 3.2,5. Покажем, что (ж', Т,) всегда можно получить, последовательно преобразуя каноническое множество ('"„7',) ЕК(й)-таблиц для 6. 11ля этого нужно проделать следующее. (!) Пусгь М вЂ” ьшожсство отсрочки, состоящее нз таких троек (Т, и, г), что действие таблицы Т на аванцепачке и есть ошибка, а действне й(Т! па и есть свертка г Применяя к у и (ч'„ Т,) алгоритл~ 7.8, получим множество таблиц (У"„ Т;).
(2) Воспользуемся теперь алгоритмом 7.7 для слняняя всех таках пар таблиц Т, н Тп чта й(Т,) =ЦТч). Назым множеством таблиц и будет (Ч", Т„). Пусть (Т, и, П вЂ” элемент множества зд Чтобы доказать, что гр удовлетворяет требованням, прельявляемым к множеству отсрочки для й' „нужно показать, что если Т" =ч[", 8 ? принадлежит Р(ЕХТ(Т, г), та Т (и) =-ошибка. Для этого предположнм, что правило г есть Л вЂ” -и н Т" =СОТО (Т„бд! для некоторого актнвнога прн(шкса ОЛ Тогла Т вЂ” -(ТОТО(Т„йи! Предположим противное, а именно, что К(и)чп ошибка.
Тогда найдется ситуация [В у б, а], допустимая для 8Л, причем и Е ЕГЕ (би) ') Каждое множества ситуаций, аа нсключеннем нзчалыюго, содержит снгуацню, в которой слева от точки стоит хотя бы один символ (см. упр. 7.3.8). Начальное множество дапустнмо галька для е, Поэтому без потери общности можно считать, что у =-у'А для некоторой цепочки у'. Тогда ситуацяя [В - у' ° Аб, и] допустима для 8 То же справелливо н в отнапгеннн ситуации[Л а,и].Следовательно,ситуання[Л вЂ” а,и] '! дппчп ми пп Зудпи лпждиа рпз оговаривать рпзпп и ппжду (А а.б! п (А и 8, е!.
") Зпипгппь чтп эгп утвержденна спрпппддппп нчзпппсиип пг тпш, пппя. п сп З пустой пчппчюп ппн ппт. допустима для би, н )(и) вопреки предположению не есть ошнбна. Отсюда заключаем, что й действительно нвлнется множеством отсрочки для 5, Множество, полученное в результате применения к,б; алгоритма 7.8 с использованием множества отсрочки й, абозначнм через ж,. Пусть Т вЂ” таблица нз Т„ свнзанная с множеством ситуапий и(, и Т' — соответствующая видоизмененная таблица нз,у,. Тогда Т н Т' отличаются только тем, что в то время как Т сообшает об ошибке, Т' может взывать свертку.
Зто происходит, если и 6 ГОЕЕ0%(А) и а~и только для ситуации нз и( вида [Л а, и]. Утверждение вытекает из того, чта по праввлу (10) алгоритма 7.10 таЯчнца Т' вызывает свертку прн всех таких и, чта иЕР01ЛОУ(г(Л) и [Л ж ]ЕСОКЕ(Л). Определим теперь на,'Гг разбиение П=- (М„З„..., З„], группирующев таблицы Т, н Т, в один блок тогда н только тогда, когда й(Т,)=.й (Т,). Так как й каммугнрует с СОТО, разбиение П совьчешг~ма. Слияние таблиц в каждом блине, проведенное с помощью алгоритма 7.7, дает множества Ю.
Так как алгоритмы 7,7 и 7.8 сохраняют эквивалентность мно- ) жества таблиц, мы показали, что ьгножества Я ЕК(й)-таблиц лпя 6 эквивалентно каноническому множеству,'Т, ЬК(й)-таблнц двя 6, С) Прежде чем закончить изучение 5ЕК-разбора, ать!егин, что методы оптнмязапни, опнсанныв в равд. 7,3, прамепнмм также и к 5ЕК-таблицам. В упр.
7Л.18 выясняется, какие элементы ошибкн в 5!Я(!)-множестве таблиц несущественны 7.4.2. Рнспрпстрвнннив 5ьйчппдхада на грамматики, нв явля. ющився 5ьй-грамматиками Метод построения анализатора для грамматики по канонической системе множеств д', ЕК(О)-ситуаций обладает двумя значительными преимушествами. Во-первых, для ланной грамматики абьем выгнсленнй, неабходнмых для построеняя д'ч, вообще говоря, гораздо меньше объема рзбаты по построению системы -. -.Т, множеств ЕК(1)-ситуаггггй. Во-нгарых, число множеств 1.К(О)- ситуаций обычно гораздо меньнге числа множеств 1.К(1)-ситуаций.
![](https://s.studizba.com/z.php?f=/templates/si/i/noavatar.png&w=100&h=100&t=1"){kind=avatar}
