Теория синтаксического анализа, перевода и компиляции - Том 2 (943929), страница 15
Текст из файла (страница 15)
Пометим этот новый столбец символом Е. Новое множество таблиц приведено иа рис. 7.33,б. В алгоритм разбора осталось внести лиань одна изиенепие, а именно при вычислении элементов перехода вместно символов Т и Г использовать Е. В результате множество таблиц рис.
7.33,6 приводит к разбору согласно остовной грамматике (Н Е ЕЯЕ (3) Е Е»Е (5) Е (Е) (6) Е и определенной в равд. 5.4.3. Разберем, например, входную пепочку (о-!-а)аа с помощью множества таблиц рис. 7.33, б. ЕЯ(!)-анализатор выполняет такую последовательность тактов: [Т„(о+а) на, е]) — (Та (Т„а-'а) на, е] ) — [То (Т,аТ„-ь а) на, е] ! — )Т, (Т,ЕТ„-(- и)» а, 6] ! — (Та(Т,ЕТ„+Т„а) на, 6] ! — (Т, (ТаЕТ,-а- Т,о7'о ) на, 6] (Т, (Т,Е Т„; Т,ЕТ,„) а а, 66] ,'-(Т,(Т,ЕТ„) а, 66)( ',-'(Та (ТаЕТа) Т„, на, 66)] ! — (Т,ЕТ„ни, 66!5! ! — ]Т,ЕТ, Та, и, 6")5] (-(Т,ЕТ,а ТгаТо е, 66)5) ) — ]Т„ЕТ, Т,Е!'ы, е, 66)56] )- (ТаЕТо е, 66!563] Последняя нонфнгурация — допускающая Канонический 1Я())- анализатор длн ба пря разборе этой же входной цепочки сделал ао Та Та Таа Таа Таа рас.
7 ач. множество Ьд(!)-тащил оооае нснлмчанян наяаиа г~раанхт а — ло слияния столбцов; б — после слнанна стоабноа, гл г методы оптимизации синтлксических лньлнзлторов Т 3 ПРЕОЗРЗЗОВЛНИЯ ПА МНОЖЕСТВАХ Ьа(Ы ТАБЛИЦ бы пять дополнительных тактов, соответствующих сверткам по цепным правилам, Т) Укетод исключения цепных правил формально описан и алга- ритме 7.9. Хотя мы и не будем подробно доказывать его корректность, этот алгоритм позволит нам исключить все свертки по цепным правилам, если для каждого нетерминала грамматика содержат не более одного цепного правила. Даже если какой.то нетерминал имеет более одного пенного правила, этот алгоритм все-таки будет работать достаючно хорошо.
Алгоритм 7 9. Исключение сверток по цепным правилам. Вход. 1.К(Ь).грамматика 6=(1Ч, 2, Р, 5) н Х-иедостижнмое множество (т, Т„) таблиц для 6. Выход. Измененное множество таблиц для 6, „эквивалентное" лшожесгзу ! У, 7',) в гом смысле, чго оно позволяет так же рано обнаруживать ошибки, но может привести к неудаче при свертке по некоторым цепным правилам.
г)(егаад. (1) Упорпдочить цегерминалы так, чтобы В=(ЛО ..., А„) и если Л, — ° Л вЂ” цепное правило, то г щ 1. Воаможность такого упорядочения обеспечивается однозначностью грамматики. (2) Выполнять шаг (3) последонателыю длз 7 = 1, 2, ..., и. (3) Пусть Л,. 1, -цепное правило с номером р и Т,— таблица, вызывающая действие свертка р на одной или более аванцепочках. 1)редположим, что Т, принздлс>кггт множеству Р(ЕХТ(Т„ р)') и для всех аваицепочек либо действия таблиц 7', и Т, совпала!от, либо одно из пих есть 9, либо действием таблацы Т, служит свертка р. Наконеп, допустим, что элементы перехода таблиц 7', и 7', также либо совпадают, либо один из них есть гр.
Построим теперь новую таблицу Тз, элементы котоой всегда совпадают с отличаыми от 9 злвмегпами таблиц Т, и Ти сключеиие составляют элементы, соответствугощие тем аванцепочкам, которым в таблнпе Т, отвечает свертка р. В этом случае лействия таблицы Т, будут совпадать с соответствующими действиями таблицы Т,. Затем прсобрвзусы кажпую таблицу Т=<Д УИ дла котоРой У(Аг) =Тг и У(Аг) =ТО по южна У(АТ)— - у(Лг)=-т,. (4) По окончании преобразований шага (3) устраним все таблицы, не являющиеся более достижимыми из начальной таб.
липы. С) Установим ряд результатоа, необходимых для доказательства того, что для 1К(!)-грамматик!! алгоритм 7.9 полностью исклю') Следугт отиьтцть, чш всякий рвз, когда приигягвчг ызга !3) влечет зз собой щиенсвле множества тьблчц, соответственно изигизгтсз ч сзязачввя с ьгчи иножг твои функцлч ЫЕХТ. 82 чает свертки па цепным правилам, если нет двух правил вида А — В и А -- С, при условии что ни из какого нетсрмнвала грамматики не выводится только пустая цепочка (Такой кетермииал легко убрать, причеы после этого грамматика останется ЕК(1)- грамматикой.) Лемма 7.1, Лугов 6 — (Х, 2, Р, 5) -ЕК(1)-граллагпика, обладаюи!ая тем свойством, чтгг для каждого С Е (Ц существует такая цепочка шРае из 2*, что С,*ю. Допустил, что Л.- В с аомогцью последовательности цепных правил.
Пугть Л, и лножеыпва ! К(11.щапуицгт, допустимых для активных префиксоо уА и уВ гоотщтстеелно. Тогда удтглетеоряютсл следующие условия: (!) Ески [С а, Хй„а]ЕЛ, и [О а, УйОЬ]ЕЛО тоХФУ, (2) Если [С- а, [)О о] 6 г1, и Ь Е Еррй)а) '), тое Л, нет такой сгггпуацгги вида [О а„!)„с], что Ь Е ЕГГ(йчс), кролы, быть лгожет, ситуации [Е В °,))], где А -р'Е.='ЭВ с помои(ью логледовательлоспго цепных правил. Д о к а э а т е л ь с т в о.
Предоставляем читателю в качестве упражнения убедиться в том, что нарушение условия (1) или (2) приводит и противоречию с 1.К(1)-условиеы. Следствие. 1.К(1)-таблицы, построенные ло Л, и Лз, соепадаюгп аи всех Элементах перехода и деиствия, кроме глучпгв, ковда один из иих есть гр и ки когда таблица, построенная ло Л„ еызьгооет ни этом элементе свертку по ценному правилу.
До к аз ательст во. Согласно теореме 7.7, поскольку две таблицы построены по множествам допустимьгх ситуаций для цепочек, оканчивающихся нетериипалом, все элементы ошибка иес!щссгвенны. Выполнение условия (1) леммы 7.1 обеспечивает отсутстпие конф,гиктов в элементах перехода; условие (2) утверждает, что конфликтов нет и в элементах действия, за исключекием раарешимых конфликтов, Относящихся к цепным правилам.
ь) Лемма 7.2. В ходе рабогпьг юггоритма 7.9 каждая гиаолици явтетгся резульпкатом глилнил списки !еавлажно, длины 1) 1.К(1). таблиц ТО ., Т„, аоггаросняьщ гю множествам допугтимьт ситуаций для некогпорых ока|попых префиксов уАО уА„., ., уА„, где Аг Аг, принадлежит Р длл 1=.гм.гг. Доказательство. Оставляем в качестве упражнения.
(З '! Зьигтни, что здесь й, иожгт рззччться г; тогда ч(, пв азввцепочкг Ь зизызвгт сзертзу, В протнзвьи слуиь Л, вызывает перги с, 83 Гл т методы Опти«1изАпии синтлксичаских Аиллиз«тОРОЕ Теорема 7.8. Пусть алгоритм 7.9 арилеляется к ЕК(1)-грал. латике 6 и ее канокическоиу множеству ЕК(1)-таблиц вп Е!лл 6 имеет для каждого яетермикала ке более одншо цепкого правила и ни из какого нгтерминала ле выводится толско е, то полученное множегтоо таблиц не содержит сверток по цепным прививал!. Доказательство.
Интуитивно ясно, что лемлгы 7.! н 7.2 гарантируют, что все пары таблиц Т, и Т«, рассмотренные на шаге (3), действительно удовлетворя!от условиям э!ого шага. Формальное доказательство оставляем в качестве упражнепня. ез УПРАЖНЕНИЯ 7.3.1. Постройте канбническне множества ЕК(1)-таблиц для следующих грамматик: (а) 5 ЛВАС А а0 В. Ь)с С с)д Е> Г>0(0 (б) 5 а55) Ь (в) 5 55а)Ь (г) Е Е-;Т)Т Т- Т«Р(Р Р Р',Р(Р Р (Е)]а)а(1) Е Е,Е)Е 7.3.2. Испольауйте каноническое множество таблиц нз упр 7.3.1(а) и алгоритм 7.5 для разбора входной цепочки аОЬа00с.
7.3.3. Покажите, как можно реализовать алгоритм 7.5 (а) с помощью детерминированного МП-преобразователя, (б) в виде анализатора на языке Флойда — Эванса. 7.3НЕ Постройте анализатор па языке Флойда — Эванса для граыматики 6, по (а) множеству ЕК(1)-таблиц, приведенноыу иа рис. 7.33,а, (б) множеству ЕК(1)-таблиц, приведенном> на рис 7.33,б. Сравните полученные аналиааторы с анализатором из упр. 7.2. П . УПРЛЖИЕИИЯ 7.3.5.
Рассьютрнм грамматику 6, порождаюш>ю язык 1. —,(а«0а Ь", 1, а~)0) 0 (Оа«>ос«! 1, а- О): 5 — Л(ОВ Л аАЬ)0)ОС В вЂ”. аВс, '! ( !С С аС(а Сконстр>нруйте для 6 анализатор простого прсдшествования и 1.К(!)-анализатор. Покажите, что анализатор простого предшествования нри разборе цепочки а"1а'Ь, прежде чем сообщить об ошибке, прочтет все символы а, следующие за символом !. Покажите, что канонический 1К(! )анализатор сообщит об ошибке, как только прочтет сил!вол 1. 7.3.8. С помощью алгоритма 7.5 постройте !Р.недостижимые множества 1.К(1)-таблиц для каждой грамматики из упр. 7.3.1.
7.3ЛЕ Пользуясь методами настоящего раздела, постройте наименьшее эквивалентное множество ЕК(1)-таблиц для каждой грамыатики из упр. 7.3.1. 7.3.8. Пусть,у — каноническая система множеств ЕК(Ь)-ситуа. ций дяя ЕК(Ь)-грамматики 6 =- ()2, 2, Р, 5). Пусть у( — множество ситуаций, принадлежащее Т. Покажите, что (а! если [Л а.д, и]ЕИ, то иЕЕОЕЕ0%'А(Л), (б) сели 4 не является начальным множеством ситуаций, то 4 содержит по меньшей мере одну ситуацию вида [Л аХ.Р, и] для некоторого Х из (Ц 0 2, (в) если [ — р, с] Е г( и В па 5', то в ( есть ситуация вада [Л аВу,и], (г) если [А с! ВР, и]Е.4 и ЕРЕА(ВРи) содержит символ а, то «2 есть сигуапия вида [С ..ау, о( для некоторых у в о.
(Этот результат позволяет получить простой метод вычисления зле«1ептов перенос в ЕК(1)-анализаторе.) *7.3.9. Поиажите, что если в множестве Т' ЕК(Ь)-таблиц, построенном алгоритмом 7,5, заменить какой-нибудь элемент ошибка па 1Р, то новое множество таблип не б>дет более !Р-недостижимым. "7.3.10. Покажите, что канонический ЕК(й)-анализатор гообщает об о!лидке либо в начальной конФИТ>рации, либо сразу после операция переноса.
**7.3.11. Пусть 6 — ЕК(Ь)-грамматика, Найдите верхпю!о и нижнюю границы для !псла таблиц в каноннческом множестве ЕК(Ь)-таблнп для 6. Можете ли Вы найти разумные верхнюю ГЛ 7. МЕТОДЫ ОПТИМИЗАПИИ СИНТАКСИЧЕСКИХ АНАЛИЗАТОРОВ УПРАЖНЕНИЯ и ннжнюю граняпы числа таблиц в произвольном допустимом ьшожестве Ей(й)-таблиц для 67 *7.3.12.
![](https://s.studizba.com/z.php?f=/templates/si/i/noavatar.png&w=100&h=100&t=1"){kind=avatar}
