Теория синтаксического анализа, перевода и компиляции - Том 2 (943929), страница 9
Текст из файла (страница 9)
иА Т '). Теперь ,дсйопдсе Пера сд а д А 3 Х ть х Рпс уха Г й(1) табапца а Ь т, к управление передано таблице Т,. В верхушку магазина помещается нетерминал В и вызывается функция перехода таблицы Т„которая определяет, чта в верхушку магазина нужно поместить таблицу Т, =д(Я). Мы будем счь1тать, что узловыми при Ей-разборе пвляютсп моменты, когда в верхушку магазина помещается новая таблица.
Такую таблицу назовем упраеаяюи(сй. Изучим характеристики Ей-анализатора а терминах последовательности управляющих таблиц. Если управляющая таблица Т вызывает перенос, то следующая управляющая таблица определяется непосредственно с помощью функшаи переходов таблицы Т. Если, с другой стороны, управляьощая таблица Т вызывает свертку, то следующая управлающая таблица определяется с помощью функпии переходов (с к1)-й сверху таблицы, содержапгейся в магазине, где 1 †дли праной части правила, применяемого для выполнения свертки.
Мажет показаться, что трудно определить, какая таблина находится в указаНном мссте, однако можно построить алгоритм, определяюгций множества возмоисных таблиц. Попытаемся установить, в каком случае два множества Ей(й). таблиц определяют эквивалентные анализаторы. Мы сформулируем критерии поведения анализаторов, из которых должна быть ясно, что понимать пад эквивалентностью. Сначала дадим определение мяожествв Ей(йнтаблиц, обобщающее определепве, приведенное в равд.
б.2.5. Теперь как элемент возможного действия, так и элемент вОзможного перехода может быть специальным символам ць, который можно интерпретировать как „несущественный" элемент. Ыга увидим, что многие из элементов типа „ошибка" в Ей(й)-таблицах никогда не используются, т. е. независимо от входной цепочки к некоторым э.чементам типа 1 1 Заметим, ато котка кацоаачаскоцу 1й(Е)-ааааааатору праасюат аипшаить саертцу по араааау Г, правая часть прааааа Г всагаа бтааг «уфонцсон цепочки сацаолоа граццатака, иахоаащайса а кагаапаа.
ракии обпаюи, а процесса разбора аа аоаапкааг асобаоапиоста сраааааать правую часть пэааааа с находящейся а цагазпца цепочкой сацаоаоа граицатаки. аа „ошибка" 1 й(й)-анализатор никогда не обращается. Таким образам, можно произвольно менять эти элеченты; при этом анализатор будет работать по-прежнему. Определение. Пусть 6 — КС-грамматика. Мнопеесшаои Ей(й)- таблиц для 6 назовем пару (й, Т,), где У' — ьаиожество таблиц для 6 и таблица Т„называемая иочильиой, принадлежит Ф'. Таблица для 6 — зто пара функций <П й>м где (1) 1 — отображение из Х'» в множество, состоящее из эле.
ментов су, ошибка, перенос, допуск и свертка 1 для всех правил с номерами 1 (2) й отображает р) 62 в й'0(щ, ошибка). Если ясна, а какой таблице Т, идет речь, будем писать вместо (ю, Т,) просто ю . Каноническое множество Ей(й)-таблиц, построенное в равд. 5.2.5, удовлетворяет данному здесь ппределению множества Ей(й]-табаьиц.
Ваьгетим, чта в каноническом множестве 1 й(й]-таблиц элемент ць нииогда не встречается. Пример 7.15. Пусть 6 определяется правиламн (1) В ВА (2) Я А (3) А пА (4) А — Ь Множество Ей(1)-таблиц для 6 приведено иа рис. 7.21. Мы увидим, что анализатор, испальзуаащпй множество таблиц на рис. 7.21, проводит разбор, не привлекая для этого Дадсюд а Перел д ' а Ь а .С А ц Ь т, та Р„с 1 2! Маомащао 1 й(Ц таблиц непосредственно грамматику 6. Просто таблицы „подходят" грамматике, т.е в нпх фигурируют толька спмво,ьы из 6, и вызываемые свертки выполняьотся по правилам, действительно суще.
ствующим в 6. П Персопределим Ей(й)-алгоритм разбора, опираясь на попятив множества Ей(й)-таблиц, введенное выше. Этот алгоритм по существу тот же, что и алгоритм 5.7, если элемент ф рассматривать как элемент ошибки. для удобства определим алгоритм заново. гл методы оптнлзнзлцми сннтлксичгскпх лнллизлтогов т.г. Птеавелзовлния нл мно>кгствлх ьн(ьгтльлиц Определенне. Пусть (Т, Т„) — мкожество БЯ(й)-таблоц для КС-грамматнкн 6 =- (Н, 2, Р, 3). Конфигурацией Б)((й)-анализатора для (ыв, Т„) назовеы тройку (Т„Х,Т,...
Х Т„„в, и), где (1) Т, прквадлежнт йТ, 0((юйгл, и Т,— начальная таблица; (2) Х, принадлежит >)112, ! =(к.гл! (3) в принадлежит 2"; (4) и - выходная цепочка, состоящая из номеров правил. Первая компонента копфигурацвн представляет содержимое магазина, вторая — непросмотренную часть входной цепочки, третья - построенный к этому моменту разбор. Ничигькпя колфигурш(ия аналнзатора - это конфнгурацня вила (Т„,в, е) для некоторой пеночки в нз Ец Как н раныпе, такг алгорптма разбора будем представлять с помацью отношения !-, заданного нв лзножестве конфигурацяй. Прелположнм, что анализа~ар яахолнтся в конфигурации (Т„Х,7',... Х,„Т„, в, я), где Т =с(,й> — таблица из В Пусть вб 2* к и =- РП!ЗТь(в).
Зто озйачает, что в представляет непросмотренную часть входной цепочки, а и — авандепочку. (!) Если )(и! = перенос н в = ав', где а Е 2, то (Т,Х,Т, ... Х„Т, ов', и) ) — (Т,Х,Т,... Х„Т иТ, в', и) где Т вЂ”.А(и). В этом случае выполняется перенос; прн этом следующий входной символ и записываетсп в магазин, а за ням в всрхуп!ку магазина помещается таблица д(п). (2) Пусть ((и) =саертка 1 н А 7 — правило с номером С )7(-.=г.
БУдсм считаттч что г (т н Т„,= <7', й>. Таблица 7'„ , †э таблицы которой передается управление, нагда нз магазина удаляется цепочка Х , , Т„ ,„, ... Х Т . Тогда (Т,Х,Т, ... Х Т, в, н) ) — (Т,Х,Т,... Х,Т,АТ, в, и!) пте Т=.й'(Л). В этом случае выполняется свертка па правилу А — у Номер этого правила приписывается к выходной цепочке, иепочка длины 2(7) удаляется нз верхугпнн магазина и замевяется цепочкой А Т, где Т = й'(Л) и й' †функц перехолов верхней оставшейся в магазине таблицы. Заметим, что при свертке спмвалы, удаляемые кз магазина, не просматриваются.
Поэтому возможна такая свертка, когда удаляемые символы грамматики и составляют правой части правила, управляющего сверткой'). (3) Если 7(и) — ~р, ошибка или допуск, то нет такой очередчой конфигурация С, что (Т„Х,Т,... Х Т, ю, я) ) — С. ') Зю ие елучите», есле чсчельзуетса «авеиизескее мкежесззе вгика. П:.чаще гееепя, такая «итугиия чежелгтельиг, и ее емче аепусти~ь телгже в гом случае, когда есть уверевкееть, что ешзака будет вскоре эее раэее еаварумеяа. Очередной конфкгурацнн нет также и в следующих случаях: в правиле (1) в=с (т.
е. входная цепочка исчерпана) клн й(о) не является именем таблицы, в правиле (2) г ) т (т.е. в магазине недостаточно символОв) кли й'(А] не является имевем таб. лицы. Назовем конфигурацию (Т,Х,Т, .:. Х Т, в, и) сигналил оигибки, если очередной конфигурации нет. Исключение составляет конфигурация (ТьВТ„г, и), которую в случае Те=<7, й> н )(г) =допуск бугем называть допускающей. Отношепкя ) -', ! -* и 1 — + определяются как обычно. Конфигурацию С нававем достижимой, если С,' 'С для некоторой начальной нонфигурацки С,.
Приведем теперь алгоритм разбора. А з~ притч 7 5 Б)((й) а з~ арнты разбора Вход КС грамматика 6 =(К, 2, Р,З), множество( У, Т ) 1 К(й). таблиц для 6 н входная цепочка в Е 2*. Вьгхед. Последовательность правил к нли сигнал ошнбкн. Метод. (1) Построить начальную конфигурацию (Т„в, е).
(2) Пусть С вЂ” -последняя построенная нонфигурацня. Построить таку!о очередную конфигурацию С', что С( — С', и затем повторить шаг (2). Если очередной конфигурации нет, перейтк к шагу (3). (3) Пусть С = (и, х, к) — последняя построенная конфягурацня. Если С вЂ” допускающая конфигурация, выдать и и остановиться.
В противном случае сообщнть об ошибке Ясно, что этот алгоритм можно реализовать с помощью детей. минированного МП-преобразователя с правым конпевым маркером Если алгоритм 7.5 достигает допускающей конфигурации, то выходная цепочка и называется разбором для входной цепочки в. Разбор и называкп корргквльгм, если п — правый разбое для в в соответстикн с граьгмгзнкоз! 6 11одобно этому, множество БЯ(й)-таблиц называют коургктими для грамматики 6, если алгорнзм 7.5 порождает корректный разбор для любав цепочки из 5(6) и не порождает разбора нн для какой цепочкн в, нс принадлежащей ь(6).
Па теореме 5.!2 каноническое множество Е(7(й)-таблиц длэ )-!з(й)-граыывтнки 6 корректно для 6. Однако проязвольнгм маожества Бя(й)-таблиц для грамматики 6, раз>моется, не обд ° зательно корректно для 6. Пример 7.15. Проследим последователыюсть шагов алгорнтмз 7 5 на входной цепочке иб ирк условнн, что алгоритм исполь. гл >, методы оптнмизлцин сннтлкснчкскнх лнллизлтогаз зует множество Е(((1)-таблиц, приведенное на рнс.
7,21, а начальной таблицей служит Т,. Начальная конфигурация есть (Т„ иЬ, е). Действием таблнцм Т, на аванцепочке а будет перенос, а переходом.- Т„ так что (Т„иЬ, е)1 (Т,иТ„Ь, е) Действием таблицы Т, на символе Ь также будет перенос, но переходам — Т и поэтому (Т,иТ„Ь, е) 1 — (Т,иГ,ЬТ,, е, е) Действием таблицы Т, на символе г будет свертка 4; правило 4— это А Ь. Таким образом, верхняя таблица и символ грамматики удаляются из Т,пТ,ЬТм в результате чего остается цепочка Т,иТ,. Переход таблицы Т, на символе А есть Тм так что (Т,иТ,ЬТм е, е) ь- (Т,иТ,АТ„е, 4) Действие таблицы Тз на аванцепочке е есть >у.
Другими славамн, настроить очередную конфигурацию не удается, Так как (Т,иТ,АТм е, 4) не является допускающей конфигурацией, окав сигнал ошибки. Поскольку аЬ Е ЦС), зто множество таблиц, очевидно, не корректно для грамматики из примера 7.!5. П 7.3.2. Эквмввпентнееть множеств твбпнц Опишем теперь, что значит, что два множества Е)((й)-таблиц эквива.чентны. Самая слабая эквивалентностзь которая может нас заинтересовать, означает, чта алгоритм 7.5, работающий с двумя множествами таблиц, порождает один и тот же разбор для цепочек, принадлежащих языку (.(6), н что цепочки, не анализируемые при использовании одного множества таблиц, не анализиру>отса и прн использовании другога множества таб. лнц. Ошибочные ситуации могут обнаруживаться в разное время. Самая сильная эквивалентность, которую можно рассматривать, требует, чтобы прн работе с двумя множествами таблиц порождались одн>ыковые последовательности шагав разбора.
![](https://s.studizba.com/z.php?f=/templates/si/i/noavatar.png&w=100&h=100&t=1"){kind=avatar}
