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