Теория синтаксического анализа, перевода и компиляции - Том 2 (943929), страница 11
Текст из файла (страница 11)
Поэтому элементы ошибка у функций деиствия этих таблиц не меняются. В ряде дру!их мест ошибка заменена на гр. ГД гл. т.мзтоды оптимнзлиии синтдксячксКих лндлиздтоеов те пэеоведзовлния нд множеств«к гиа1.тдьлиц Теорема 7.6. Д(ножеотао таблиц о"', построенное алгоритмом 7.6, ц-недогглижиио и эквивалентно каноническол»у множеапоу Я . Доказательство, Эквивалентность множеств о' и,у' очевидна, так квк единственное измевение, которое вносится в множество Д, состоит в там, что элементы ошибка заменяются на ц», Дшоэуае 7?еувгау Деба»»йее 7?Е»ктн? о 4 е х е б а 4 «у о б т, т, т, Тл Тз Тт тг в б Ряс.
7.24. Множество ЬД(1)-т«б«эе да е после оряиеееея«««гор«гы» 7.б« д — кнюняческее не«жест«о 1.Й(б-т«б«ищ б — Е-еедостзжяыое иэожыт«о т«б««а. з Е)((й)-алгоритм разбора не отличает ошибку ог Ел). Покажем теперь, чта если алгоритм 7,5, использующий множество габлнц ,У", обращается к элементу ф, то множество ыт' не была правильна построено по а . Пусть эг не ц»-недостижима. Тогда должно найтись такое наименьшее число», что С)-'С, где С,— начальная конфиглрация н в конфигурапии С алгоритм 7.8 запрашивает элемент ц множества Я".
Поскольку Т, не взменяегся на шаге (2а), да.»жиа быль» . О. Пусть С=(Т,Х,Т,...Х Т, ш, и), где Т„=л?] у> и ГП?8Т«(ш) =и. Элемент е может встретиться в трех случаях. Случай ?г Предположим, что ) (и) =гр. Тогда, согласно шагам (2б»1) и (2611!) алгоритма 7 6, предыдущим так»ил» аналнаагора должна была быть свертка, а не перенос. Значит, С„',— ' 'С'! — С, где С' =- (Т,Х,Т,... Х„,т.,т,(7,... Г,(7„», ч ) ') ~р.эд«меэты з«еде«м то«ько ддя тоге, «тебы огиеппь з«еые«ты, которые ыожзо меоять.
и свертка выполнялась по правилу Х вЂ” ° )'»...1; (п представляет собой пеночку ч', к которой приписан номер этого правила). Рассмотрим множество ситуаций, по которому построена таблица У,, (Если г = О, вместо У, читай Т ,.) Это множество должно включать ситуацию [Х Ул...г',, и]. Н определении допустимой ситуации требовалось, чтобы существовала такая цепочка у Е 2*, что Х,... Х иу †.правовывадимая цепочка.
Предполоягвм, чта нетерывпал Х появляется в результате применения правила Л аХ„(). Иными славами, в пополненной грамиатяке есть вывод Я' 1«,'?Лхо,уаХ„О»=:л",уаХ иу где уа=-Х,... Х„,. Так кзк и 6Р!НЭТ(Р»), ситуация [Л вЂ” аХ„Р, о] должна быть допустима для Х;...Х, если о= =- РП?8Т(х). й(омно заключить, что в каноническом множестве таблиц дейггвве таблицы Тж па цепочне и не „ошибка", и, значит, вопреки предположению в алгоритме 7.6 она не могло оказаться замененным на ц» Случай 17 Предоплат!»лг, что [(и) — перенос, а — первый сим.
вол цепочки и, д(а) =е. Поскольку [(и) .перенос, в ыножестве ситуаций, связанном с таблицей 78ы найдется такая ситуация вида[А а аб,о],что и Е ЕГР(або) и[А а аб, о] — допустиман ситуации для активного префикса Х,,Х (слг. упр. 7.3.8). Ио тогда ситуация [Л аа 6, о] допустиме для Х,...Х а н Х,... Х«а — также активный префикс. Следовательно, множество допустимых ситуаций для Х,...Х«а непусто, н у(а) пе мажет быть элементом ц» вопреки предположению. Случай уг Предположим, что [(и)=свертка р, где правило с номером р есть А Х,...
Х, Т, т=-<[', у'> и й'(А) =ц. Тогда ситуация [А Х,... Х °, и] допустньш для Х,... Х„, а ситуация [А Х,...Х, и] допустима для Х,...Х,, Кзк н в случае 1, приходим к выводу, что найдется ситуапия [В аА.Р, о], допустимая для Хт..,Х,,А, и, значит, у'(Л) не может быть элементом гр.
Г) Можно также показать, что алгоритм ?.6 заменяет на ц» мак. сил»ельни возможное число элементов ошибка в каноническом множестве таблиц, Поэтому, если произвольный элемент ошибка из,р' заменить на ц», полученное множество таблиц ие б) дст более ц»-недастижимылг. 7.3.4. Спнянне табпнц е помощью еовмеетммык разбиений Н этом разделе л»ы опишем важный метод, пряменяемый для уменьпгения множества Е(((й)-таблиц Этот метод состовг в том, чта две таблицы сливаются в одну, когда это не отражается па ГЛ 7. МЕТОДЫ ОПТИМИЗАЦИИ СИНТАКСИЧЕСКИХ АНАЛИЗАТОРОВ поведении Б(((й)-алгоритлга разбора, использующего рассматриваемое множество таблиц.
Пусть дано гр-недостижггмое множество таблиц и Т„Т,— две таблицы из этага множества. Предположим, что всякий раз, когда элементы действия или перехода таблиц не совпадают, один из них есть гр. Б этом случае будеч говорить, что таблицы Т, и Тл совместимы, и их можно слить, рассматривая Т, и Т, как одну таблицу. Далее, предположим, что Т, и Т, не совпадают талька в одном элементе перехода, который в одной таблице представляет собой Т„а в другой Т,. Если Т, и Т, совместимы, можно одгговремеино слить Т, с Т, и Тт с Т,.
Слияние таблиц можно е|це выполнить В том случае, корда Т, и Т, несовместимы только из-за того, что несавпадающеми элементами перехода служат Т, н Т,. Опишеы такой алгоритм слияния, определив понятие совместимого разбиения множества таблиц. Затем покажем, что вса члены каждого блока совместимого разбиения можно одновременна объединить в одну таблицу. Определеггие. пусть (47, т,) — кг-недостижизгое множества ! Д(й)-таблиц и П = (Тг, ..., Рр) — разбиение на м"'.
Другими славами, д',БТ„И... ИМр — — м и Т,П Тг —— й) для всех 17 Д Будем называть 1! савмесгииммм раэби|иием ширины р, если для всех блоков Т„! - г (Р, из пРинадлежпости элементов <)„йгз и <1| йгу блокУ д', вытекает, что (!) при Д(и)~Д(и) ха|я бы одно из значений Д(и) и Д(и) естыр, (2) прн уг(Х) ~уг(Х) либо (а) хотя бы одно из значений у,(Х) и йг(Х] естыр, либо (б) у,(Х) и у,(Х) принадлежат одному н таму же блоку разбиения П.
Совместимые разбиения множества С(((й)-таблиц можно найти методами, сходными с методаыи нахождения иеразличиммх состояний не полностью определеннОго конечного автомата. !)Вша цель состоит в нахождении совместимых разбиений яаименыпей ширины.
Изложим алгоритм, показывающий, как с помощью совместимых разбиений ширины Р на множестве Е)((й)-табл||к найти эквивалентное множество, содержащее р таблиц. Алгоритм 77. Слияние с помощью совместимых разбиений. Втод. гр-недостижимое лгножество (т, Т,] Ы(й)-таблиц и совместимое разбиение П=(Т„..., Т ) на Т. Выход. Эквивалентное |р-недостшкимое множество (Р', Тг) БД(й)-таблиц, дхя которого 4] у = р. Ва 7 3 пРеОВРлзОВлиия ИА множестВлх ьк|л|.т*Влип гИетод.
(!) д„я то ! ! (17 Р, по блоку разбиения П построить таблппу У,—.= <Д уу следую|цим Образом: (а) Если <Д, УУ чу', и 1'(и) чм|у ДлЯ аваниепочки и, положить ((и) =Д (и). Если такой таблицы а Тг нет, положить 7(и) =гр. (б) Если <)', у'лид', и у'(Х)б ТТ, положить у(Х)=-.УТ. Если в Тг пет теной таблины, что у'(Х]Е 5;, положить у(Х) =|р. (2) Т; — таблипа, построенная по блоку, солержащему Т,. 1| Корректность постраения, выполняемого алгоритлюм 7.7,сле- дует из опрехеления совместимого разбиения.
Пример 7.1й. Рассмотрим нашу обычную траиыатику арафме- тических выражений В,: (!] В Е -|-Т (2) Š— Т (3) Т Т«Р (4) Т Р (5) Р (Е) (б) Р и гр-ггедостижилгое множества БД(!).Таблиц для 67 показано па рпс, 7.26. Легка видеть, что как таблицы Т, и Тпи так н таблицы Ти и Т„совместимы. Поэтому можно настропать совместимое раз- биение, где блакамн будут (Т„Т|,), (Ты, Тм] и все остальные таблицы.
После за«гены (Т„, Т„) йа У, || (Т„, Ты) па У, мно- жество таблиц станет таким, как оно представлено па рис. 7.'26. Заметим, что элементы перехода Т„Т|„ТИ и Ты соответственна изменены на У| или У,. Совместимое разбиение, приведенное выше, наилучшее из всех, которые можно найти. Например, Ти и Т„почти совместимы, и можно было бы сгруппировать их в Один блок разбиения, если бы удалось сгруппировать в один блок этого же разбиения таб- лицы Тм и Тм. Но Тм н Тм не согласу|отса в действиях для +, «и')'. Докажем, что алгоритм 7.7 порождает на выходе эквивалент. иае |р-недостижимое множество ЕЕ(й)-таблиц, Теорема 7.б. Пусть м' — мкожетяао ~-Ы(й)-тибшй, пттроеи- иое по Ю огзаритмом 7.7.
Тогдо м и В эквивомилгиы и ооа гр-недостижимы. Доказательство. Пусть таблица Т' ИВ,Р' построена па блоку совместимого разбиения, содержащему таблицу Т из м". 41 ,Деасмгае а + ( ) е Пееззвд Е Т Г а + з ( ) г х х г х к т, т о т 7 Ф г т, и г Ф Ф х д т, Ф 2 г Ф 2 2 Тз Ф 4 4 и 4 Те Ф Ф Ф Ф Ф Ф Г, Ф Ф Ф Ф Ф Ф Ф Ф Х б 6 Х Х 6 г х х г х х г х х г к х т Ф Ф Ф и Ф Ф Ф и Т Тз оз 777 Ф Ф ззз Ф тз О Гз Ф и т Тз )б 7, г х к г х х тжт, т, Ф Ф т, в т„ Тв Ф 2 г Ф 2 2 Ф Ф Ф т,7 Ф Ф Ф Ф Ф Ф Ф Ф Ф Ф Ф Ф Ф Ф Ф Ф Ф Ф Тз 'зе 77 4 4 Ф 4 4 тм Х 6 6 Х 6 6 Тж т„ т т 5 Ф 5 5 Т,з Х 5 5 Х 5 5 т, Ф Ф и Ф Ф Ф Ф Ф Ф Ф Ф Ф Ф Ф и Тз 7 в та г х х г х х т те тз те и Ф Тз Т, Х 6 6 Х 6 Б Ф Ф Ф Ф Ф Ф Ф Ф т, г х х г к х 7, т, т а тм » Ф 7 з Т, г Х Х г Х Х Ф Ф )м 74 Ф Ф тз Тв Ф г Ф Ф г Х Ф Ф Ф Ф тм Ф Ф т7з т г Х Х г Х Х Т7з Тз Т,а Тз и Зо Тм Ф т г Х К г Х К т, т, тм Ф Ф т, т 7 г Х Х г Х Х Ф Ф Тзо 777 и Ф Т77 и та и г Ф Ф г Х и Ф Ф Ф т„Ф и Г„ т„Ф з г Ф з 7 Ф Ф Ф Ф Ф т„ т„е 5 5 Ф 5 5 т, х 5 5 х 5 5 Ф Ф Ф Ф и Ф Рис.
7.25, Ф.иедасзижззмаа меожвсзво забзии ддв Сз. д(жйлйе Пе~емз) а е з ( ) е Е Т Т а + е ( ) Ф г Ф Ф Ф д Ф Ф Ф Ф 7е Ф 2 г а Ф 2 Ф Ф Ф Ф Ф 77 Ф Ф Х Х г К Х и Ф ОЗ те Ф Ф Тв Ф г Ф и г Ф Ф Ф Ф Ф т7з Ф и 77з 2 г Ф 2 Ф Ф Ф и и и 7,7 Ф и Х 6 б Х 6 Х Ф и и Ф Ф Ф Ф Ф К Х г Х К Тж Тв Оз Тзз Ф Ф те 7 Ф Х 5 5 Х Х 5 Ф Ф Ф Ф Ф Ф Ф Х Х г Х Х Ф т„и, та Ф и т„ г К К г Х Х Ф Ф Оз Г Ф Ф тз Ф г Ф Ф г Ф Ф Ф Ф Ф тм Ф Ф тм Ф з Ф Ф Ф Ф Ф Ф Тз7 Х 5 5 К 5 К и Ф Ф Ф Ф Ф Ф 4 4 Ф 4 4 Ф Ф Ф Ф Ф Ф Ф Ф 5 5 Ф 5 5 Р7зс 7.26. Савмещеинае миа'кесзва таблиц.
ГЛ 7. МЕТОДЫ ОПТИМИЗЛПИН СИНТАКСИЧЕСКИХ АНАЛИЗАТОРОВ Пусть С, = (Т„ш, е) и С,'= (Т„ш, е) — начальные конфигурации Щй)-анализатора, использующего р и ВТ' соответственно. Пока. жем, что (7.3.1) С,7 †'(Т,Х,Т, , Х Т , х, и) для анализаторе, использующего Ф, тогда и ~олько тогда, когда Сл 7 — '(Т,Х,Т,...Х Т„, А, и) для анализатора, использ> ющего Г'. Это означает, что единственное различие между случаими, когда СВ(й).а77ализатор использует Г и т', состоит в том, что, используя й', анализатор заменяет таблицу Т из ЬР представителем содержащего ее блока разбиения!1. Докажем утверждение (7.3.!) индукцией по 7> начнем с необходичости условия. Базис, ! — б, тривиален.
![](https://s.studizba.com/z.php?f=/templates/si/i/noavatar.png&w=100&h=100&t=1"){kind=avatar}
