Теория синтаксического анализа, перевода и компиляции - Том 2 (943929), страница 12
Текст из файла (страница 12)
Для проведения шага индукции прсдположиы, что утверждение [7,3.1) верно для 7. Докажем, что оно верно для т+!. Так как множество дт 7р.не. достижимо, действия таблиц Т и Т' на Е!((5ТА(х) совпадают. Пусть это общее действие — пе!мнос, а — дервый символ цепочки х и элемент перехода таблицы Т на и есть Т. В соответстнни с алгоритмом 7.7 и определением совместимого разбиения переходам таблицы Т' иа п будет Т' тогда и только тогда, когда Т' — представитель содержащего Т блока разбиения П.
Если действие — свертка по некоторому правилу с г символамн в правой части, то, сравнивая таблицы Т ,и Т„', „ убеждаемся, что утверждение верно для 7 + 1. Для доказательства достаточности п>жно только заметить, что, если в Т' у функции действия для цепочки Р1257(х) стоит элемент, ОгЛичный От 7Р, таблица Т' должна соаиадатЬ С Т, поскольку множество Р 37-недостижимо. Итак, алгоритм 7.7 сохраняет эквивалентность в самом сильном смысле. Анализатор, использующий два таких множества таблиц, всегда вычисляет очередные конфигурации за одно и то же часло шагов независима от того, имеет ли входная цепочка р.7збор. УЗ.5. Отсрочка В обнаружении ошибок Наш основной метод улгеньшепия множества СД(й)-таблиц должен сливать таблицы всегда, когда это возыажно.
Однако дзе таблипы люжно слить в одну только тогда, когда они совместимы. В данном разделе мы обсудилг метод, применяемый для замены в некоторых таблицах существенных элементов ошибка элементами свертка с тем, чтобы >вели гить число совместимых пар таблиц в множестве С(((й)-таблиц. В качестве примера расслютрим таблицы Т, и Ти, приведенные на рис. 7,25, Для удобства представим их функции дейст- Т.л пРеОВРлзовлния нА мнОжестВлх сии! тлэлиц вия отдельно в виде рис. 7.25(а).
Если изменить действие таблицы Т, ва аванцепочке ) с ошибки на свертку 6 и действие таблицы Т„иа аваипепочке Р с ошибки па свертку 6, то Т, и 7',т станут совместимыми и можно будет слить их в одну таблицу. Однако, прежде чем вьшолнять такие замены, хотелось бы удостовериться, что ошибки, Обнаруживаемые таблицей Т, на ) и таблицей Т„на Р, будут обнаружены па одном из послед>ющнх шагов перед операпией переноса. В этом разделе ыы пал>чиы ДЕРРИРРЕ Т777 Рас 7 ТВ(л> условия, при которых мокно отсрочить обнаружение о7пибки, не изменив позицш7 по входной цепочке, в которой С)((й)-анал77затар сообщает об ошибке.
В частности, леюсо показать, что а каноническом множестве таблиц л7обан такая замена допустима. Предположилг, что Ер(й)-анализатор находится В конфигурации (Т„Х,Т,... ХАТ„, ш, и) и действием таблицы Т„на аванцепочке и=РП(5Т„(ш) служит ошибка. Предположим далее, что этот элемент ошибка замепиется в Т иа свертку р, где р — помер правила А У, У,. Эту ошибку впоследствии можно обпарумнть двуми способачи.
При свсртке из магазина удалшотся 27 сичволов и управление передается таблице Т„ ,. Если у функции переколов таблицы Т, символу А Отвечает элемснт й7, то можно сообщ>пь об ошибке, заменив 27 элелгентом ошибка. С другой стороны, символу А у функции переходои таблицы Т, может соответствовать некоторая таблица Т. Если действием таблицы Т на аванцевочке и служит ошибка или элемент 7р (ксггорый можно заменить на ошибку, чтобы сохранить свойство й7-77едостижилгостгг), 7о 7лоапш обнаружить огпибку и иа этой стадии. Удастся обнар>- жить ошибку и в том случас, когда действисч таблицы Т иа аванпепочке и будет свертка р' и описанный выше пропесс повторится. Короче говоря, мы хотим, чтобы таблицы, которые становятся управляющими после свертки по правилу р, не вылы.
вали на аванцепочке и переноса (нли допуска). Заметим, 7то для того, чтобы заменить ошибку на свертку, нам приходится во всей широте использовать определение эквивалентносю7 множеств 12(й)-таб.77777. При разборе с новым множествоч таблпп последую>дне конфигурации ыогут Вычисляться Ьз В А.ААР.ДВ.Р7 л.сэ ~л, г. матоды оптимизлпии синтаксических лнллизхтогов 3 пгсаагхзавхния ил ьгножкстзэх ья(ептлвлиц на несколько шагов позже, чем при разборе с помощью старого множества, но входные символы цри этом считыватьсн ие буд>т.
Чтобы описать условия, при которых допустима такая замена, нужно для любой таблицы, появляющейся при разборе в верхушке магазина, знать, какие таблицы могут встретиться в магазине в качестве (г-1- 1) й таблицы сверху. Определим сначала три функции на таблицах и цепочках символов грамматики. Определение. Пусть (4Г, Т,) — множество Е)(()г)-таблиц для грамматнки 6=.(Н, 2, Р, В). Расширим область определения функции (зОТО из равд. 5.2.3. Функция СОТО отображает м' Х()4 В 2)* в й следующим образоьс (1) СОТО(Т, е) =Т для всех Т нз,Т. (2) Если Т= <Ей>, то бОТО(7', Х) =й(Х) для всех Х из Х () Е иТизй.
(3) ГзО'ГО(Т, иХ) = СОТО(БОТО(Т, а), Х) для всех а из (7( В 2)* и Т нз Т. Вешл таблицы Т нз ('", Т„) будем называть такое наиболь. шее число г, что если СОТО(Т,, и)= — Т, то )а)) г. Нам придется также пользоваться функциеи СОТО ', „обрат. ной" к СОТО. Она отображает множество Я х (Х () Е)* в множество всех подмножеств множества й. Положим СгОТО *(Т, и).—..(7") бОТО(Т', а) =- Т).
Наконец, определим функцию КЕХТ(Т, Р), где ТЕ ", а ив номер правила А Х, ... ХР (1) Если вес таблицы Т меньше г, то )чЕХТ(Т, Р) не определено. (2) Если вес таблицы Т пе меньше г, то р)ЕХТ(Т, Р) =-(7") существуют такие Т" Е эт и и Е(Х() 2)', что Т" Е СОТО-'(Т, и) и Т' — СОТО(Т", А)).
Таким образом, БРЕХТ(7', Р) дает все таблицы, которые могут стать управляющими после Т, если Т находится в верхушке магазина и вызывае~ свертку но правилу р. Заметим, что не требуется', чтобы верхними г символами л~агазина были Х,...Х,. Единственное требование: чтобы в магазине было пе меньше г символов. Если таблипы канонические, можно показать, что среди всех цело мк длины г множество СОТО '(Т, а) будет неп>етым только для и=-Х,... Х,.
В качестве упражнений (см. конец равд. 7.3) предлагаем >становнп некоторые алгебранческнесвойства ф)нкцийбОТО в)(ГХТ. Функция СОТО для множества !.)1(й)-таблиц хороню описывается с помощью помеченного графа. Вершины графа СОТО помечены ююнанн табтиц, н еслн СОТО(7'о Х) =-Т,, то из вершины, почеченнои Т„в верши»у, помечснн>ю Т, проведена дуга, помеченная Х. Следовательно, если БОТО(Т, Х,Х,, Х,) — -Т', та сущесгвтет такой путь из вершины Т в вершину ТС что метки дуг, составляющих этот путь, образуют цепочку Х,Х, ...
Х,, Вес таблицы Т можно интерпретировать как длину кратчайшего пути пз Т, в Т в ~ рафе СОТО. По графу БОТО легко вычисляется функция 5)ЕХТ. Для того чтобы найти НЕХ'ЦТ, г), где правило с номерам 1 есть А Х,Х,... Х„найдем в графе БОТО все такие вершины Т", что нз Т" в Т проходит путь длины г. Затем для каждой такой вершины Т" включим БОТО(Т", Л) в 5)ЕХТ(Т, г). Пример 7.20. Граф СОТО для множества таблиц рис. 7.25 приведен на рнс. 7.27.
Из это~о графа получаем, что СОТО(Т„(Г)) =.Тм, так как СгОТО(То ( ) = Т„СОТО(То Е).=Т, и (ТОТО(Т„,)) =Ты. Таблнпа Т, имеет вес 2, поэтому ЫЕХТ(Т„, 5), где правило 5 есть Р- (Е), нс определено. Вычислим теперь >(ЕХ((Т„,5). Путь длины 3 в Т,.„выло. дит только из трех таблиц, а именно из Т„7', и Т,. Поэтому И>ТО(Т„Р) = Т„БОТО(Т„Р) =- Т„и СОТО(Т„Р) = Тм, так что В)ЕХТ(Тм, 5)=(Т„7'„). ьз Дадим теперь алгоритм, преобразующий вьггедастижимае множество таблиц так, чтобы некоторые ошибки обваруживалвсь позже во времени, но на том же месте входнои цепочки. Наш алгоритм не будет самылг общим, но из пего будет ясно, как асуществля~отся и более общие преобразования.
)бы будем заменять некоторые элементы ошибка и элементы В у функний действия па элементы свертка. Для каждого изменяемого элемента мы точно определяем правило, ко~орое н>жно применить при новой свертке. Допустимые замены образуют так называемое множество отсрочки. Каждый элемент множества отсрочки представляет собой тройку (Т, и, г), где Т вЂ” имя таблицы, и — аванцепочка и г — помер правила.
Элемент (Т, и, 1) указывает, что нужно изменить действие таблицы Т па авапцепочке и на свертку Е Определение. Пусть (м, Т,) — множество Е)1(й)-табтгиц для грамматики С == (Х, 2, Р, 3). Назовем подмножество ГР множества Р хх*ьхр лиожествозг отсрочки длл (я, т,), если удовлетао. Ряются следующие >славия Если (Т, и, г) Е У и Т=. (Д й>, то (1) )(и) --ошибка или йг; (2) если правило( есть А-ьи и Т =СОТО(Т„()), то а — суффикс цепочки )); (3) нет такого правила Р, что (Т, и,)') также пришщлежит У; (4) если Т' Е ЫЕХТ(Т, 1) и 7" = <)',й)>, тоД (и)=.ошибка или гг.
э' ,ау Рнс. 7.27. Грзф СОТО. ГЛ Т. МЕТОДЫ ОПТНМИЗАГГИИ ГИНТАЧСИЧЕГКИХ АНАЛИЗАТОРОВ Условие (1) утверждает, что на свертку залгеняются только элементы ошибка и ср. Условие (2) гарантирует, что свертка по правилу 1 возможна только тогда, когда в Верх)шке магазина находится пеночка ос Условие (3) обсспечирает однозначность, а (4) означает, чта свертки, вызванные паявлеяием дополнительных сверток, в ковегном итоге будут проделаны без переносов. Т Э ПРЕОВРАЗОВАНИЯ НА МНОЖЕСТВАХ СИФРТАВЛИЦ Па поводу условия (4) заметим, что (Т', и, 1) также может входить в РД Б этом случае значение /'(и) также будет изменено с ошибки или гр на свертку ). Поэтому, прежде чем будет выдано сообщение об ошибке, Возможно, придется выполнить последовательно несколько сверток.
Нахождение ьшажества отсрочки, повволяюгцего максимизировагь общее чиста совместимых таблиц в множестве Е)7(й)-таблиц, составляет большую комбинатарную задачу. В одном из приведенных ниже примеров мы коснемся некоторых эвристических методов нахождения соответствующих множеств отсрочки. Но сначала покажем, как используется множество отсрочки при преобразовании данного множества ЕК(й)-таблиц. Алгоритм 78. Отсрочка в обнаружении опгибок. Влад. Е(((й)-грамматика С = (Р), Е, Р, В), дг-недостижггнгое множество (В, Т,) ЕЕ(й)-таблиц для С и множество отсрочки дд Выход.
![](https://s.studizba.com/z.php?f=/templates/si/i/noavatar.png&w=100&h=100&t=1"){kind=avatar}
