Главная » Просмотр файлов » Теория синтаксического анализа, перевода и компиляции - Том 2

Теория синтаксического анализа, перевода и компиляции - Том 2 (943929), страница 17

Файл №943929 Теория синтаксического анализа, перевода и компиляции - Том 2 (Теория синтаксического анализа, перевода и компиляции) 17 страницаТеория синтаксического анализа, перевода и компиляции - Том 2 (943929) страница 172013-09-12СтудИзба
Просмтор этого файла доступен только зарегистрированным пользователям. Но у нас супер быстрая регистрация: достаточно только электронной почты!

Текст из файла (страница 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)-ситуаций.

Характеристики

Тип файла
DJVU-файл
Размер
3,44 Mb
Тип материала
Высшее учебное заведение

Список файлов книги

Свежие статьи
Популярно сейчас
Зачем заказывать выполнение своего задания, если оно уже было выполнено много много раз? Его можно просто купить или даже скачать бесплатно на СтудИзбе. Найдите нужный учебный материал у нас!
Ответы на популярные вопросы
Да! Наши авторы собирают и выкладывают те работы, которые сдаются в Вашем учебном заведении ежегодно и уже проверены преподавателями.
Да! У нас любой человек может выложить любую учебную работу и зарабатывать на её продажах! Но каждый учебный материал публикуется только после тщательной проверки администрацией.
Вернём деньги! А если быть более точными, то автору даётся немного времени на исправление, а если не исправит или выйдет время, то вернём деньги в полном объёме!
Да! На равне с готовыми студенческими работами у нас продаются услуги. Цены на услуги видны сразу, то есть Вам нужно только указать параметры и сразу можно оплачивать.
Отзывы студентов
Ставлю 10/10
Все нравится, очень удобный сайт, помогает в учебе. Кроме этого, можно заработать самому, выставляя готовые учебные материалы на продажу здесь. Рейтинги и отзывы на преподавателей очень помогают сориентироваться в начале нового семестра. Спасибо за такую функцию. Ставлю максимальную оценку.
Лучшая платформа для успешной сдачи сессии
Познакомился со СтудИзбой благодаря своему другу, очень нравится интерфейс, количество доступных файлов, цена, в общем, все прекрасно. Даже сам продаю какие-то свои работы.
Студизба ван лав ❤
Очень офигенный сайт для студентов. Много полезных учебных материалов. Пользуюсь студизбой с октября 2021 года. Серьёзных нареканий нет. Хотелось бы, что бы ввели подписочную модель и сделали материалы дешевле 300 рублей в рамках подписки бесплатными.
Отличный сайт
Лично меня всё устраивает - и покупка, и продажа; и цены, и возможность предпросмотра куска файла, и обилие бесплатных файлов (в подборках по авторам, читай, ВУЗам и факультетам). Есть определённые баги, но всё решаемо, да и администраторы реагируют в течение суток.
Маленький отзыв о большом помощнике!
Студизба спасает в те моменты, когда сроки горят, а работ накопилось достаточно. Довольно удобный сайт с простой навигацией и огромным количеством материалов.
Студ. Изба как крупнейший сборник работ для студентов
Тут дофига бывает всего полезного. Печально, что бывают предметы по которым даже одного бесплатного решения нет, но это скорее вопрос к студентам. В остальном всё здорово.
Спасательный островок
Если уже не успеваешь разобраться или застрял на каком-то задание поможет тебе быстро и недорого решить твою проблему.
Всё и так отлично
Всё очень удобно. Особенно круто, что есть система бонусов и можно выводить остатки денег. Очень много качественных бесплатных файлов.
Отзыв о системе "Студизба"
Отличная платформа для распространения работ, востребованных студентами. Хорошо налаженная и качественная работа сайта, огромная база заданий и аудитория.
Отличный помощник
Отличный сайт с кучей полезных файлов, позволяющий найти много методичек / учебников / отзывов о вузах и преподователях.
Отлично помогает студентам в любой момент для решения трудных и незамедлительных задач
Хотелось бы больше конкретной информации о преподавателях. А так в принципе хороший сайт, всегда им пользуюсь и ни разу не было желания прекратить. Хороший сайт для помощи студентам, удобный и приятный интерфейс. Из недостатков можно выделить только отсутствия небольшого количества файлов.
Спасибо за шикарный сайт
Великолепный сайт на котором студент за не большие деньги может найти помощь с дз, проектами курсовыми, лабораторными, а также узнать отзывы на преподавателей и бесплатно скачать пособия.
Популярные преподаватели
Добавляйте материалы
и зарабатывайте!
Продажи идут автоматически
6553
Авторов
на СтудИзбе
299
Средний доход
с одного платного файла
Обучение Подробнее