Теория синтаксического анализа, перевода и компиляции - Том 1 (943928), страница 89
Текст из файла (страница 89)
е. в этом примере и=па и в=с. Обратите внимание иа сходство данного здесь определения ситуации с тем, что встречалось раньше при описании алгоритма Зрли. Между этими двумя понятиями возникает интересная связь, если алгоритм Эрли применяется к 1.К(Й)-грамматике (см. упр. 5.2.16). Представление о (.К(Й)-ситуациях, соответствующих активным префиксам грамматики, дает ключ к пониманию того, как работает детерминированный правый анализатор для ).К(Й)-грамматики. В некотором смысле основной интерес для нас представляют ьК(Й)-ситуации вида [А — 5, и], в которых точка находится на правом конце правила. Эти'ситуации указывают, какие правила можно применить для свертки правовыводимых цепочек.
В основе 1.К(Й)-разбора лежат следующие определение и теорема: Определение. Определим функцию ЕЕЕА (а) так (далее мы опускаем Й иуили 6, если ясно, о чем речь): (1) если а начинается терминалом, то ЕЕЕА(а) =-Е1КВТА(а), (2) если и начинается иетерминалом, то ЕЕЕ (я) = (еа! ест ЕГКВТ„(а) и существует Вывод а=э',р=О,шх, где () ~ Агах длЯ ЛЕ5(). Гч. з. ОднОпРОхОдныЙ синтАксический А!!Аа!Нз Без ВОЗВРАТОВ В З ДетЕРМИИИРОВАНИЫЙ ВОСХОДИ!ЦИЙ синтАКСНЧескин ~Нализ Таким образом, ЕРРА(я) включает все элементы множества Р!КЗТА(я), при выводе которых нетерминал, стоящий на левох! конде цепочки, не заменяется пустой цепочкой е (иначе говоря, в правом выводе из цепочки я, начинающейся нетерминалом, па последнем шаге не должно применяться е-правило).
Пример 5.28. Рассмотрим грамматику 6 с правилами 5 — АВ А Ва(е  — ~СЬ) С С р)е Здесь Г1КЗТ,(5)=(е, а, Ь, с, аб„ас, Ьа, са, сб'), ЕГР,(5) —... (са, сЬ). Г) Напомним, что в гл. 4 излагался восходящий алгоритм разбора, который не работал для грамматик, содержащих е-правила. В случае 1К(й)-разбора е-правила в грамматике разрешаются, но надо быть осторожным при „свертке" пустой цепочки к нетермипалу.
Мы увидим, что функция ЕГГ помогает правильно устанавливать, когда пустая цепочка является основой, к которой надо применить свертку. Сначала, однако, введем слегка видоизмененное определение ЕК(й)-грамматики. Два вывода, входящие в это определение, фактически играют взаимозаменяемые роли, и, следовательно, пе теряя общности, можно считать, что основа цепочки во втором выводе простирается по крайней мере так же далеко вправо, как в первом.
Лемма 5.2. Если 6 = (!з, Х, Р, 5') — пополненная грамматика, которая не является ЕК(й)-грамматикой, то суи(ествуют выводы 5' =З,'яАи!=!>„я()и! и 5' =Ф," уВх =;>, убх = яру, где Г!КЗТА(!о) =- Р!КЗТА(у) и (уб(:=: )яф), но ТВХФяАу. Д о к а з а т е л ь с т в о. Согласно (.й(я)-определению, можно найти выводы, удовлетворяющие всем нужным условиям, за исключением, быть может, условия (уб ~ '-)я()!. Допустим поэтому, что !Тб) < ~ яр!. Пока!кем, что 1.К(й)-условие нарушается для другого примера, в котором уб играет роль я() в первоначальном условии.
Так как дано, что убх = я!)у и )уб! < )я()), то для некоторой цепочки гЕХ' можно записать яб=убг. Таким образом, есть выводы 5'~,'уВх "„убх и 5' =>, 'яА!о =Ф, яр!в = убгто далее, цепочка г была определена так, что х=-гу. Так как Р!КЗТ,(!о) =Р!КЗТ,(У), то Г1КЯТА(х)=Р!КВТА(по). ЕК(й)-Условие, если оно выполняется, говорит, что яАИ!=-уВги!. Поэтому отцепляя" от обеих сторон равенства !о, получаем яА=тВг, „прицепляя" в новом равенстве у, получаем ТВгу =- яАу.
Но гу=х, и, значит, мы показали, что яАу = уВх, а это с самого начала предполагалось ложным. Если сопоставить два приведенных выше вывода с ЕК(Ь)-условием, окажется, что они удовлетворяют условиям леммы (разумеется, надо подходящим образом переименовать цепочки). Метод ЕК(й)-разбора основан на следующей теореме. Теорема 5.9.
Грамматика 6=(х(, Х, Р, 5) является Ей(й)- громмтпикой тогда и только тогда, когда для каждой цепочки иЕХ'А выполняется такое условие. Пусть я)) — активный префикс яравовыводимой цепочки сф!в пополненной грамматисси 6'. Если 1К(я)-ситуация [А — !) °, и) допустима для яр, то нет другой 1 К(я)-ситуации !А! — (), (1„о), допустимой для яр, причем ИЕЕРР (!з,о), (Заметим, чтоб., может быть пустой цепочкой е.) Доказательство.
Необходимость. Пусть !А — р °, и] и 1А,— р, бг, о1 — две различные ситуации, допустимые для я(1, т. е. в пополненной грамматике существуют выводы 5 ~,яА!о=О„яр!в 5' =>, "я, А,х ~, я,Ц3.,х причем Г1КЗТА(п!)=и, Р)КЗТ (х) =о и я()=я!р,. Кроме того, (),х=-З",иу для некоторой цепочки у и в этом (возможно, пустом) выводе нетерминал на левом конце никогда не заменяется пустой цепочкой. Мы утверждаем, что 6 не может быть 1К(я)-грамматикой.
Чтобы доказать это, исследуем три случая: (1) р, = е, (2) р.,~Х и (3) Ц, содержит нетерминал. Случай 1: Если р,=е, то и=о и выводы имеют вид 5' =о', яАгв =о, я~!в 5' =;>, 'я, А,х =->„яДх тле Р)КЗТА(!в) = Р1КЗТА(х) = и = — о. Так как рассматриваемые "й(Я)-ситуации различны„то либо А~ А„либо ~~~,.
В любом случае нарушается 1.К(й)-условие. Случай 2: Если ~,= — г для некоторой цепочки ЗЕБР+, то 5' =з', яА!в =з, арго 5' =>,'я!А!х=>„я!р,гх где яи=я!(), и Р!КЗТА(гх)=и. Но тогда 6 — не ЕК(й)-грамма. тика, так как яАгх не может совпадать с я,А,х, если гЕа '. 435 Гл. Б. ОднопРОходныи синтАксическиЙ АнАлиз Без ВОВВРАтОВ В,е детеРминиРОВАнпый Восходящий сиптлксическиЙ АнАлиз Случай 3: Допустим„что р„содержит хотя бы один петер. мииальный символ. Тогда р, =О, 'и,Вит-— О, и,и.,и„где и,и, Фе, так как в этом выводе нетерминал на левом конце не заменяется на е. Итак, имеем два вывода 5' =Ф', яАсо=Ф, ябсо 5' Р" ,а,А,х =ос арф,х в которых яфс=сф и и,и,и,х=иу. В определении 1.К(й)-трам.
матикн требуется, чтобы яЛи,и,и,х=-яф,и,Ви,х, т. е. аАи,и, = я1[[,и,В. Подставляя ар вместо а1р„получаем Ли,и,=()и,В, Но это невозможно, так как и,ис Фь е. Заметим, что именно здесь используется условие, что и Е ЕГГА(р„о). Если бы в формулировке теоремы мы заменили ЕГГ на Г[КЗТ, то цепочка и,и, могла бы быть пустой, и тогда аАи,и,и,х=-=а,[),и,Ви,х (если и,й,=е и р =в), Достаточность.
Допустим, что 6 — не [.К(й)-грамматика. Тогда в пополненной грамматике есть два вывода (5.2.!) 5' =О, *аА со =!>„арсе (5.2.2) 5'=О,"уВх=ь,убх = яру для которых Г[КВТ (со) =Г[КЗТА(у) =-и, ио аАу~уВх. Зти Выводы можно выбрать такими, что цепочка ар будет настолько короткой, насколько это возможно. В силу леммы 5.2 можно считать, что 1!5[~!а[1!. Пусть я,А,у, †последн цепочка в выводе 5' ~„уВх такая, что длина ее открытой части не больше [я[[!+1, т. е. я,А,! < !яр!+1. Тогда вывод (5.2.2) можно записать в видо (5.2.3) 5' =о, 'а, А,у, =->, а,!3,р,у, =;>*, аср,у где а,д, =ад. В силу нашего выбора цепочки я,А,у, получаем !а,!(~я~(~!уб! и, кроме того, на последнем шаге вывода р,у,=ь',у не участвует правило  — е.
Если бы это правило применялось последним, то а,А,у, не была бы последней цепочкой вывода 5~',урх, у которой длина открытой части не превосходит ~ яр(+! . Таким образом, и = Г[КВТл(у) содержится в ЕРРА9,у,), и можно заключить, что ситуация [А,— ~, ~„о] допустима для ар, где о= Г[КЗТ (у,). Из существования вывода (5.2.1) вытекает, что ситуация р! р., и] тоже допустима для а[1, так что осталось доказать, что А„--.~,.~, отличается от Л р .
Итак, пусть А,— ![, ~, совпадает с А р . Тогда вывод (5.2.3) имеет вид 5'~*,а,Ау=Ф„а !3у где я18=ар. Поэтому а, =я и аАу=-аВх, что противоречит предположению о том, что 6 ие [.К()с)-грамматика. Е) Чтобы построить детерминированный правый анализатор для [К(л)-грамматики, надо знать, как дли вссх активных префиксов найти все допустимые [.К(й)-ситуации. Определение. Пусть 6 — КС-грамматика и у — ее активный префикс. Определим 1Я(у) как множество 1.К(й)-ситуаций (относительно й и 6), допустимых для у.
Как и раньше, будем опускать индексы й и 6, если понятно, о чем Идет речь. Назовем множество У=(.1! [=-[сьо(у) для некоторого активного префикса у грамматики 6) системой' множеств допустимых 1К()с)-еишуиций, соответствующей грамматике 6. Теперь приведем алгоритм построения множества [.К(й)-ситуаций, допустимых для произволышй заданной цепочки, а затем алгоритм построения системы всех таких множеств для л1обой грамматики 6. Алгоритм 58. Построение множества Щу). Вход, КСграмматика 6 =(Р[, 2, Р, 5) и у Е(МОЕ)*. Выход.
)с~(у). Метод. Если у=Х,Х ...Х„, то для того, чтобы построить)'„(у), построим !'„(е), 1'А(Х,), ['А(Х,Х,), ..., ~'А(Х,ХА... Х„). (1) Построим [сА(е) так: (а) Если 5 — аЕР, включить [5 — а, е] в )сА(е). (б) Если ситуация [А — Вя, и] уже включена в )сА(е) и  — р ЕР, то для каждой цепочки х Е Г!КВТА(аи) включить ситуацию [В [), х] в !'А(е) при условии, что там ее еще нет. (в) Повторять шаг (б) до тех пор, пока в 1' (е) нельзя будет включить новую ситуацию. (2) Допустим, что мы уже построили [сА(Х,Х,...
![](https://s.studizba.com/z.php?f=/templates/si/i/noavatar.png&w=100&h=100&t=1"){kind=avatar}
