Теория синтаксического анализа, перевода и компиляции - Том 2 (943929), страница 10
Текст из файла (страница 10)
Инымв словами, пусть (Т„ в,е) н (Т„ в,е) †начальн конфи. гурации для двух множеств таблиц Ф и Я С Тогда для всех т,м О при использовании таблиц нз м' (Та в, е) 1 — ' (Г,Х,Т, ... Х„Т„, х, и) тогда н толька тогда, когда при использовании таблиц из в' (Т;,в, е)1- (Т;Х;Т; ...
Х;Т„, л', и') причем щ =л, х =л', и = и' и Х, = Х; для 1 =.> (щ. >л пгвовглзовлния нл мвожяствлх ьяв>.тлзлнц Каждое из этих аг> ределеннй позволяет разработать такие а:ю ие и еаб азований множеств таблиц, что саответстаующ з я. 3 есь мы будем рассматривать екото ю промежуточную эквивалентность. Конечно, тре устоя. ннходн днл для входной цепочки в разбор тогда когда он находит этот жс разбор для в, и по 'у др с льз я, угае мно- жество та лиц. ол б . Б ее того, как и в определении самой сильной н ти, потребуем, чтобы алгоритм 7.5 выполня д, эквивалентности, потре о а ля каждой входной и ту же последовательность шагов разбора для ка д пеночки незав исимо от того, какое множество та лиц определяет этн шаги.
Однано разрешим при ра оте с о еще производить свертки, свертки, в та время как при работе с другим оп авды- разоар уже мож ет закончнтьсн. Такое определеаие опр дается следующими соображениями. е ательяо, чтобы Если во входной цепочке есть ошибка, желательяо, что ы и любого из множеств это обнаруживалась при использовании л> б н этом местонахождение ошибки была опре- таблиц и чта ы прн > в товемя делена как можно точнее. Нежелательна, чтабь р во таблиц позволяет обнаружить ошибку, дру- как одна множество та л а е е многих входных гое множества требовало бы просмотра еще м> я создания разумных и символов. Зта связана с тем, что дл ых методов диапюстики нужно, что ы б ошибка о на:жн- панятнь ст , г, е ана находится. валась как можно ближе к таму месту, д В и актических ситуациях, когда встречается ошибка, управ- ление передаетсп программе нейтрвли ц практ за ни ошибок которая изменяет оставшуюся часть входной ц й епочки н(или содержимое магазина так, чтобы анализатор мог продолнтить разбор остатка одни просмотр входа найти возмо>кно за- плыве ошибок.
Было бы очень жаль, если бы рабата аналн тара, обработавшега значительные час обнаружения ошн ки, б и, оказалась бессмысленной. Исходя из этого, введем понят> . >. но и ' >е эквивалентности мнолгеств таблиц. но пр ставляет собой частный случай тога неформал эквивалентности, которое обсуждалось р д. Оп еделение. Пусть (А, Т,) и (е' ', '",) — д ' Т' — ва множества Ы(Ь)- 'б иц для КС грамматики 0=.(Х, Е, Р, . У входная цепочка нз х*, С, =-(Т>, в, е),, = (, тельнасти конфигураций, построенные алгоритмом 7.5. Назовем Т, Т ) н,'й", Т') эквиэилелтныни, если для всех >.м О во яются следующие и для произвольной цепочки в удовлетворяют четыре условия: 11) Если Сг и С; обе существуют, то их можно записать ээ гл х методы оптимизации синтаксических хнхлизхтоеоа т.е.
пока сущсству1от обе последовательности конфигураций, они совпадают во всем, за исключением имен таблиц. (2) Со†допускающая конфигурация тогда и талька тогда, когда С,— допускающая конфигурация (3) Если конфигурация Сг определена, з С,' нет, то вторые компоненты у С,, и С, совпадают, (4) Если канфигурацг~я С; определена, а С, пет, то вторые компоненты у С;, н С совпадают.
Условия (3) и (4) утверждают, что если при работе с одним множеством таблиц обнаруживается ошибка, то при работе с л гим з гиожеспюм после этого не должно быть чтения символов на те с дру- входе, т. е, не выполняются действия перенос. Но усла я (3) н 4 ви ( ) допускают, пабы в то время„как одна нз мновгеств вы- зывало остановку на несущественном действии илп на действии ошибка, другое требовало выполнить одно нли более действий свертка. Отметим, что ни одно из мновгеств таблиц пе обязано быть корректным для 6.
Теи не менее, если два множества таблиц эквивалентны и одно из них корректно для 6, то другое также будет корректным для 6. Пример 7.17. Рассьютрим ! К(1)-грамматику с правилами (!) 3 аЯЬ (2) Я оЬ Множество (аТ, Т,) — каноническое множества 1.К(!)-таблиц дли 6 наказано на рис. 7.22. Е1а рис. 7.23 приведено другое множество ЕК(!)-табли1г для 6 — множество (ой, У„). Исследуем поведение ЕК(!).алгоритма разбора, испальзу1ощего,Т и оп', на входной цепочке аЬЬ. Используя б, алгоритм разбора делает последовательность тактов (Т„аЬЬ, е) !- (Т,иТ„, ЬЬ, е) ! — (Т„аТ,ЬТ„Ь, е) Последняя конфигурация — сигнал ошибки. Используя множество ~облиц и', алгоршм разбора действует так: (См аЬЬ, е) — (С,аУм ЬЬ, е) ,, - (6,пУ,Ь6а Ь, е) (6„36„Ь, 2) Последняя конфигурация- ошвбочиая.
Заметим, что канонический анализатор сообщает об ошибке, как только он впервые обнаружит во входной пепочке второй символ Ь. Анализатор, использ)ющий мнозкество таблиц ои, прежде чем сообщить об ошибке, 54 т.з, пеаозехзовьния нх множествах зим!.тавлнц свертывает аЬ в 3. Правда, второй символ Ь ие записывается в магазин, поэтому условия эквиваяентности не нарушаются. Нетрудно показать, что множества йг и 41 действительно эквивалентны. Существует алгоритм, позволяющий определить, эквивалентно ли произвольное мна- 5 о Ь жество 1.К(й)-таблиц чля 1.К(й]- грамматики каноническому миот, игестау ЕК(Ь)-таблиц для этой грамматики.
Построение такого Тз алгоритма оставляем в начестве упражвения. (й т, перегар Ю о Ь хуейспдае о Ь е ио го и, то ит из гт гв Рве. 7.22. Мзожос~зо таблиц (4; Т,). Рвс. 7.23 Множество ззбляз гы, 6,1. 7.3.3. ф-недостижимые множества таблиц Многие из элементов ошибка канонического множества ЕК(Ь)- таблиц никогда не используются ЕК(й)-алгоритмолг разбора. Такие элементы ошибка можно заменить элементами гр, действительно несуществеинмми в там смысле, что нп а какай достижимой конфигурации ани не влияют на вычисление очередной ианфигурапни. Мы покажем, чта все символы ошибка у функпии переходов канонического множества таблиц можно заменить элементами е и, сели даииаи таблица может стать управля~ащей талька сразу после свертки, аналогичную замену можно проделать н для фуикппи действия. Определение.
Пусть ( К', Т,) — множество ЕК(й).таблиц, й ) 1 н С =(Т,Х;Т,Х,Т,...Х Т, ш, и) — любая достижимая кавфигурация П)сть Т„=-б), ду и и =- — Е1КБТ„(ш). Будем говорить, что в Р иет достижимых эле- гл г методы оптимизации синтаксических хнхлизхтогов ментов Чь или, короче, Ю р-иедостиясимо, если для любой конфигурации С справедливы следующие утверждения: (1) 7(и) ~(р. (2) если 1(и) .=.перенос, то д(а) Ф о, где а — первый символ цепочки и. (3) Если)(п) = сяертиа 1, правило с номером ! сеть А 1', .Е„ г ~)0 и Т„, =-<)', д'>, то д'(А) ~р. Неформально можно сказать, что множество Ей(й)-таблиц гр-недостижимо, если все элементы о, появдя|ощиеся в таблицах, никогда не используются алгоритмом 7.6 при разборе цепочек.
Приведем теперь алгоритль ааменяющнй в каноническом множестве Ей(й)-таблиц по возмон<ностн большее число элементов ошибка на р так, чтобы полученное множество таблиц осталось ~Р-недостижимым. Применяя этот алгоритм к каноническому множеству 1.й(й)- таблиц, можно отыскать н заменить ив гр псе элементы ошибна, которые никогда не используются Ей(й)-алгоритмом разбора. Алга рнты 7 6. Построение й недостижимого множества Ей(й) таблиц с мансимально возможным числом элементов гр.
Вход, Ей(й).грамматика 6=(Р), 2, Р, Я), где й)1, и каноническое множество (ер, Т,) Ей(й)-таблиц для 6, Выход. Эквивалентное множество (еу", Т',) Ей(й)-таблиц, где все неиспользуемые элементы ошибка заменены символами гр. Метод. (1) Для каждой таблицы Т=<1, д> из Ф' построить новую таблицу <7', д'>, где д(Х), если д(Х):Фошибна д'(Х) = р в противном случае =( П>сть (м „Т,') — мноисество построенных таким образом таблиц. (2) Множество таблиц (Р', Т',) строится затем следу1ощим образом: (а) Т; принадлехгит,д'; (б) для каждой таблицы Т= <7, д> из еТт — (Т,') включить в Т' таблицу Т'=-<1', д>, где )> определяется так: (1) 1' (и) =1(и) всякий раз, когда)(и) чхошибка; (Ш если !'(ой) =ошибка для некоторых о 6 Еэ ' и 662 и дла пекотоРого и Е 2 сУществУет такаЯ таблица <!г, д,> нз ,д „что рг (ае) = псйеиос и д, (а) =-Т, то)'(ей)=ошибка; тз.
пгговгхзовхния их множествах ькыьтхьяиц (111) если 1(н) =-ошибка для некоторой цепочки и 62 и дла некотоРого о 62 сУществУет такаа таблице <)г, дг> из яо что )г(ои)=перенос и д,(а)=Т, то )'(а)= ошибка; ((ч) в противном случае )'(и) =р. С) На шаге (1) алгоритма 7.6 все элементы ошибка в функциях переходов заменяются на элементы Чь так как прн й) 1 кено. ннческий Ей(й)-анализатор всегда обнаруживает ошибку сразу после операции переноса. Следовательно, значение ошибка у фуни. ции переходов никогда ие используется Шаг (2) алгоритма 7.6 заменяет на м чначевие ошибка у функции действии таблицы Т, если нет такой таблицы <!о д,> и такой аванцепочки аи, что !г, (аи) —.— перенос и д, (а) =-Т. При таких условиях таблица Т может появиться в верхушке магазина только сразу после свертки, Однако, если ошибка есть, канонический Ей(1)-апалггзатор сообщит о ней перед сперткой.
Таким образом, в тиблицах, аналогичных Т, никакие элементы ошибка не запрашиваются и, значит, могу~ рассматриваться как несущественные. Отметим еще раз, что алгоритм 7.6 в том виде, как он был определен, работает только для множеств Ей(й)-таблиц с й>1. В случае Ей(0)-грамматики аванцепочка всегда пуста. Поэтому все щцибкн должны распознаваться при обращении к функции переходов. Следовательно, в множестве ! й(0)-таблиц пе все элементы ошибка у функций переходов несущественны. В качестве упражнения предлагаем выяснить, какие нз этих элементов несущественны. Пример 7.16. Пусть 6 — Ей(1)-грамматика с правилами (И В-Водо (2) 5 е Каноническое множество Ей(1)-таблип для 6 показано на рис.
7.24, а, а множество таблиц, полученное в результате применения алгоритма 7.6,— на рис. 7.24,6. Заь~етим, ~то на рис. 7.24,6 все элементы ошибка в правых половинах таблиц (у функций переходов) заменены элементами гр. У' фуниций действия таблица Т„согласно правилу (2а) алгоритма 7.6, оставлена без изменений. Действия перенос встречаются только в таблицах Т, и Тм они приводят к тому, что управляющей становится одна из таблвц То Т„или Т,.
![](https://s.studizba.com/z.php?f=/templates/si/i/noavatar.png&w=100&h=100&t=1"){kind=avatar}
