Теория синтаксического анализа, перевода и компиляции - Том 1 (943928), страница 91
Текст из файла (страница 91)
Чтобы помочь анализатору принять правильное решение, в нужных ячейках магазина будут находиться „Ы(й)-таблицы", содержащие необходимую для разбора информацию, извлеченную из соответствующего множества ситуаций. В частности, если а — префикс магазинной цепочки (верхняя часть ее расположена спРава), то таблица, приписываемая самому правому символу цепочки а, получается из множества снтуаций кгв(а).
Следователы1О, построение правого анализатора состоит по существу ГЛ. Б. ОДНОПРОХОДНЫЙ СИНТАКСИЧЕСКИЙ АНАЛИЗ БЕЗ ВОЗВРАТОВ в нахождении (.К(я)-таблиц, соответствующих множествам сигуа. ций. Определение. Пусть 6 — КС-грамматика и У* — системз мнт жеств 1.К(й)-ситуаций для 6. 1 К(я) таблицей Т(А), соответствую щей множеству ситуаций А из д', назовем пару функций (г, у) Функцию 7 назовем функцией дгйствия, д — функцией пгргходо и определим их следующим образом: (1) 7 отображает в*А в множесгво (ошибка, перенос, допуск) ( (свертка 1) ~' — номер правила из Р, 1) 1), причем (а) 7(и) =перенос, если [А — (1, (3„о] содержится в А ()е--Р'=г и и Е Е!'ГА(Р,О), (б) 7" (и)=свертка 1, если [А- !1, и] содержится в А г А — )) — правило из Р с номером 1, 1~1, (в) !'(г) =допуск, если [5' — 5 . Е] содержится в А, (г) 7(и) =ошибка в остальных случаях.
(2) д Определяет очередную применяемую таблицу, она ис- пользуется сразу после переноса и свертки. Формально, д отоб- ражает (ч'(! д в множество таблиц и сигнал ошибка, Значением у (Х) является таблица, соответствующая множеству бОТО(А, Х). Если СОТО(А, Х) пусто, то д(Х) =ошибка. Следует подчеркнуть, что сслн 6 — !.К(к)-грамматика и:У— каноническая система множеств ЕК(й)-ситуаций для 6, то по теореме 5.9 между действиями, определяемыми по правилам (1а) — (!в), не возникает конфликтов.
Будем говорить, что таблица Т(А) соответствует активному префиксу у грамматики 6, если А=)'„(7). Определение. Канонической системой (.К(к)-таблиц для 1.К(я)- грамматики 6 назовем пару (в~, Т,), где У вЂ” множество ЕК(й)- таблиц, соответствующее канонической системе множеств ЕК(Ь)- ситуаций для 6, а Т,— ЕК(й)-таблица, соответствующая множеству ) 7 (г). Обычно каноническнй 1.К(Ь)-анализатор представляется в виде таблицы, каждая строка которой является (.К(я)-таблицей. Если ).К(Ь)-алгоритм разбора, описанный ранее как алго- ритм 5.7, использует каноническую систему 1 К(й)-таблиц, будем называть его каноническим 1.К(в)-алгоритмом разбора или, ко- роче, каноническим 1-К(я)-анализаторам. Итак, опишем процесс построения по (.К(е)-грамматике кано- нической системы 1.К(Ь)-таблиц.
А л г о р и т м 5.1! . П о с т р о е н и е п о 1.К(й)-г р а м м а т н к е канонической системы 1К(к)-табл и ц. Вход. 1.К(я)-грамматика 6=. (Х, 2, Р, 5). Выход. Каноническая система 1К(й)-таблиц для 6. Б В ДЕТЕРМИНИРОВАННЫЙ ВОСХОДЯЩИЙ СИНТАКСИЧЕСКИЙ АНАЛИЗ Метод. (1) Построить пополненную грамматику 6'=(~(!(5'), ~, Р!1(5' 5), 5') где 5' 5 — нулевое правило. (2) По 6' построить каноническую систему У' множеств допустимых !.К(й)-ситуаций для 6. (3) Взять У =-(Т ~ Т =-Т (А) для некоторого А Ед') в качестве множества 1.К(й)-таблиц. Положить Т, = Т (А,), где ~, =-.
У~ (г). Пример 5.32. Построим каноническую систему ЕК(1)-таблиц для грамматики 6, которой соответствует пополненная грамматика (О) 5' 5 (!) 5 5а5Ь (2) 5 — г Каноническая система У множеств 1К(!)-Ситуаций для 6 приведена в примере 5.30. По З' построим систему 1.К(Ь)-таблиц. Вычислим таблицу Т, = — ()„д,), соответствующую А,. Так как Ь =. 1, го аванцепочками могут быть только а, Ь и г.
Поскольку,7, содержит ситуации [5, г!а], то 7", (г) =-7",(а) =-свертка 2. Из остальных ситуаций, принадлежащих А„находим, что ),(Ь) = ошибка (так как ЕЕЕ (5а) пусто). Чтобы вычислять функцию переходов д„заметим, что бОТО(.7„5) .=- А, и СОТО(А„Х) =- Я в осгальных случаях. Если Т, обозначает Т (А„), то д„(5) = Т, и у, (Х) — -ошибка для остальных Х. Вычисление таблицы Т, закончена.
Оиа имеет вид 5 Ф ) аЬЕ)5аЬ Т, !2Х2)Т,ХХ Здесь 2 обозначает свертку, в которой применено правило 2, а Х вЂ” символ ошибки. Найдем теперь элементы таблицы Т, =-(гп у,). Так как [5'- 5, г]ЕАО то [,(г)=допуск, и так как [5 — 5 а5Ь, г!а]ЕА„ то ),(а) =перенос. Заметим, что аванцепочки последних ситуаций здесь не играют роли.
Далее, 7",(Ь)=ошибка, и, так как СОТО(А„а) =- А„полагаем у, (а) =- Т„где Т, —.— Т (А.,). Продолжая в том же духе, получаем систему 1.К(1)-таблиц, приведенную на рис. 5.9. г) В гл. 7 мы изложим другие методы построения 1К(й)-анализаторов по грамматикам, Зги методы часто дают анализаторы меньшего объема, чем канонический 1К(й)-анализатор. Однако Гл. б. ОднОпРОХОдный синтАксическип АнАлиз Без ВОВВРАтОВ последний обладает рядом замечательных свойств, которые будут служить эталоном для сравнения с другими 1.Й()г)-анализаторами. Отметим несколько таких свойств.
(1) Простой индукцией по числу сделанных шагов можно показать, что каждая таблица, находящаяся в магазине, соот. ветствует цепочке символов грамматики, расположенной слева от нее. Поэтому, как только первые й символов необработанной части входной цепочки оказываются такими, что нет суффикса, который вместе с обработанной частью давал бы цепочку, прп. надлежащую ЦО), анализатор сразу сообщает об ошибке. В каж. дый момент его работы цепочка символов грамматики, хранящаяся в магазине, должна быть активным префиксом грамматики, Г1оэтому ).й(к)-анализатор объявляет об ошибке при первой же возможности в ходе считывания входной цепочки слева направо, (2) Пусть Т;=-(1у, бт). Если 12 (и) =-перенос и анализатор находится в конфигурации (5.2.4) (Т,Х,Т,Х,Т,...
Х Тго х, и) то найдется ситуация (В 5, (),, В1, допустимая для Х,Х,,...Х, причем и Е ЕГЕ ф,с). Поэтому если 5'=О',ХгХ,...Х,иу для пе. которой цепочки уЕ 5', то по теореме 5.9 правый конец основы цепочки Х,Х,...Хгид должен быть где-то справа от символа Х,. (3) Если в конфигурации (5.2.4) ~т (и) = свертка 1 и А — 1',1', ... 1', †прави с номером г, то цепочка Х, „„, Х, „,,...Х, в магазине должна совпадать с У'г...
1'„, так как множество ситуаций, по которому построена таблица Т, содержит ситуацию (А — )'г)'г ... 1',, и(. Таким образом, на шаге свертки не обязательно рассматривать символы верхней части магазина, надо только выбросить из магазина 2г символов. (4) Если 1г (и) — допуск, то и = е. Содержимое магазина в этот моьюнт имеет вид Т,5Т, где Т вЂ” 1.)х()г)-таблица, соответствующая множеству ситуаций, в которое входит (5' 5, г(. (5) Можно построить ДМП-преобразователь с концевым маркером, реализующий канонический 1.11(й)-алгоритм разбора. Действительно, так как аванцепочку можно хранить в конечной памяти управляющего устройства ДМП-преобразователя, то ясгго, как построить расширенный ДМП-преобразователь, реализующий алгоритм 5.? (1К(й)-алгоритм разбора).
Доказательство этих фактов оставляем в качестве упражнений. По существу это переформулироаки Определений допустимой ситуации и (.К(й)-таблицы. Таким образом, справедлива следующая теорема. Теорема 5.12. Канонический 1К(й)-алгоритлг разбора правильна находит ггривый разбор входной цепочки, если он существует, и объявляет об ошибке в ггротивнолг случае, 444 бл. детегминиговлниып Восходящип синтхксическия Анхлиз д о к а з а т е л ь с т в о.
На основании сформулированных выше свойств ипдукцией по числу шагов, сделанных алгоритмом разбора, можно показать, что если а — цепочка символов грамма. тики, находящихся в магазине, и х — необработанная часть ВХОДНОЙ ЦЕПОЧКИ, ВКЛЮЧаюшая аваицЕпоЧКу, то ах=>„ Пг, ГДЕ Ш-- первоначальная входная цепочка и пи †текущ выходная цепочка. В качестве частного случая получаем, что если алгоритм допускает цепочку пг н выдает иа выходе пя, то 5 =,бв цг.
() Из 1,Я(1)-условггя непосредственно следует однозначность 1 р,-грамматики. Пусть даны два различных правых вывода 5 =о, а, ~, ... =>,а„=:,>,иг и 5=.>,рг =>,... =->,() ==;>„пг. РассбготРим наименьшее из чисел г, ДлЯ котоРых гб„г~()„г Сразу получаем, что ьц()г)-условие нарушается для любого й. Детали оставляем в качестве упражнения.
Итак, канонический Ьгг(н)-алгоритм разбора для (-Я(гг)-грамматики б выдает правый разбор входной цепочки гв тогда и только тогда, когда юЕЕ(6). Вначале не совсем очевидно, что канонический ьгх()г)-анализатор выполняет свою работу за линейное время, даже если элементарными операциями считать его собственные шаги. Докажем, что это действительно так, Теорема 5.13. Канонический ).Р(п)-алгорггтлг ггри разборе входной цепочка длины п делает О(п) шагов. Д о к а з а т е л ь с т в о. Определим С-конфигурации рассматриваемого анализатора: (1) начальная конфигурация является С-конфигурацией, (2) конфигурация, непосредственно следующая за шагом переноса, является С-конфигурацией, (3) конфигурация, непосредственно следующая за сверткой, которая делает магазин короче, чем в предыдущей С-конфигурации, является С-конфигурацией.
При разборе входной цепочки длины п анализатор может оказаться не более чем в 2п С-конфигурациях. Назовем характеристикой С-конфигурации число, равное сумме числа символов грамматики в магазине и удвоенного числа необработанных входных символов. Если С, и С, †последовательн С-конфигурации, то характеристика конфигурации С, ио крайней мере на единицу больше характеристики конфигурации С,.
![](https://s.studizba.com/z.php?f=/templates/si/i/noavatar.png&w=100&h=100&t=1"){kind=avatar}
