Теория синтаксического анализа, перевода и компиляции - Том 1 (943928), страница 81
Текст из файла (страница 81)
(11)-грамматике 6, линеино зависит от и, где и — длина входной цепочки. Доказательство. 11.(й)-грамматика 6 не может быть леворекурсивной. По лемме 4.1 максимальное число шагов в выводе вида А =>се В!х меньше некоторой константы с. Таким образом, максимальное число шагов, которое может потратить й-предсказывающий алгоритм .4 на обработку одного входного символа вплоть до операции выброса, сдвигающей с этого сим- аа аь а ьа ьь ь е Рис. 5.6. Управляющая таблица хля граииатики ба.
ГЛ. 3. ОДНОПРОХОДНЫЙ СИНТАКСИЧЕСКИЙ АНАЛИЗ БЕЗ ВОЗВРАТОВ ЗП. ЕЬ (»РГРАММАТИКИ вола входную головку, не превосходит с. Следовательно, при обработке входной цепочки длины и алгоритм 4 может проде. лать не более 0 (и) шагов, РА.б. Проверив !3. (й)*условия По отношению к произвольной данной грамматике 6 возникает ряд естественных вопросов. Во-первых, является ли 6 *с1 (й)-грамматикой для данного й? Во-вторых, является ли 6 ЬЬ-грамматикой, т. е.
существует ли такое й, что 6 — 1.1.(й) грамматика? И наконец, так как для с1(1)-грамматики левые разборы строятся особенно просто, естественно спросить: если 6 не ЕЕ(1)-грамматика, то существует ли эквивалентная ей 11. (1)-грамматика 6', для которой Е(6') =Е(6)? К сожалению, только для первого вопроса есть отвечающий на него алгоритм. Можно показать, что вторая и третья проблемы алгоритмическн неразрешимы. В этом разделе мы опишем алгоритм, проверяющий, является ли б 1.ь (й)-грамматикой для заданного значения й, Если А=1„ можно воспользоваться теоремой 5.3. Для произвольного й можно применить теоре»ту 5.2. Здесь мы рассмотрим общий случай. По существу надо просто показать, что алгоритм 5.3 успешно строит управляющую таблицу только тогда, когда 6 — 1.1.
(К)-грамматика. Напомним, что 6 — (Р1, Х, Р, 5) пе является (Л (й)-грамматикой тогда и только тогда, когда для некоторой цепочки аЕ (1»( ц Х)» (1) 5=э,"шАа, (2) Ь=- Г(КЗТ»(а), (3) (Г1КЬТ»(()) ~~» !) П (Г1КЗТ»(у) Ш»Т) Ф Я для некоторых Р Фу, для которых А — р и А —.у — правила из Р. Алгоритм 54. Проверка 1.1.(й)-условия. Вход.
КС-грамматика 6 == (14, Х, Р, 5) н целое число й. Выход. „Да", если б — 1.1.(й)-грамматика, и „нет" в противном случае. Метод. (1) Для каждого нетерминала А Е 5(, имеющего две или более альтернативы, вычислить о(А)=(5(Т. Х*" и существует такая цепочка я, что 5=>,"шАа и Л=Г1КЗТ»(а)». (В дальнейшем будет дан алгоритм вычисления о(А).) (2) Если А — р и А у — различные А-правила; то для каждого Е Е п(Л) вычислить !(Е) =-(Г1КВТ»((1) Я»Т) П (Г1КВТ»(у) (+» ! ) Если !(Е)~ 8, остановиться и выдать „нет".
Если Щ= о для 394 Вначале 5 ВЛ А — +ВА (е  — ОС С я0С)е О (5) (а Г,(5) = Г, (В) = З Г,(А) =-(+, е» Г,(С) = (. » Г„(В) =((, а» гЕо(Л), повторить шаг (2) для всех различных пар А- правил. (3) Повторить шаги (1) и (2) для всех нетермнналов нз Х. (4) Выдать,да", если нарушений Щя)-условия не обнаружено. П Цтобы реализовать алгоритм 5.4, нужно уметь вычислять Г1КЗТ»о(р) для любой КС-грамматики 6=(я, Х, Р, 5) и всех ЗЕ(ыцХ)". Во-вторых, нужно уметь находить множества о(А). Сейчас мы дадим соответствУющие алгоРитмы, Алгоритм 55.
Вычисление функции Г(КЗТ»(р). Вход. КС-грамматика 6=(!ч, Х, Р, 5) н цепочка р=Х,Х,... ... Х„Е (51 ц Х)". " 'Выход. ЛЮта(1). Метод. Так как по лемме 5.1 Г(КЗТ»ф) =-- Г1КЗТ»(Х,) Я» Г1КЗТ„(Х») Я„... Я~ Г1КЗТ (Х„) то достаточно показать, как найти ЛКЗТ»(Х) для Х Е 5(. Если ХЕХ ц(е», то очевидно, что Г(КЗТ,(Х) =-(Х». Опрсделим множества Г,(Х) для каждого ХЕ)»(ПХ и возрастающих значений !) 0: (1) Гт(а) ==--(а» для всех аЕХ и 1)О. (2) Г,(Л)=(х~хЕХ*» и существует правило А — хя из Р, для которого либо (х(=й, либо )х) < й и а=е».
(3) Допустим, что ÄÄ..., Г,, уже определены для всех Айй(. Тогда Г»(А) = Гт,(А) ц (х ~ Л вЂ” 1; ... Г» принадлежит Р и х Е'Г,,(Г,) 9» Г;,(1;) 9» ... 9» Г»,(Г„)» (4) Так как Г;,(А) ~ Гт(А) ~ Х*" для всех А и 1, то в конце концов мы дойдем до такого 1, что Г;,(Л)=Г;(Л) для всех А Е!»(. Тогда положим Г! КЗТ„(А) = Р»(Л) для этого значения !. Г) Пример 5,18. Построим множества Г»(Х) для й=-1 и грамматики б с правилами гл.
ь. однопроходный синтлксичвскнй лнллиз ьнз возврлтов з. ь ьь сл)-Грлммлтнкн Затем Р,(В) = ((, а) и Р,(Х) =Р,(Х) для всех остальных Х Далее Р,(5) =((, а) и Р,(Х) =-Р,(Х) для всех остальных Х, Так как Р,(Х) ==Р,(Х) для вссх Х, то Г[КЗТ(5) =- Г[КЗТ(В) = Г[КЗТ(Е[) — ((, а) Р1КЗТ(А)=(-Р, е) Г1ЮТ(С) =- (е, е) (З Теорема 5.7. Алгоритм 5.5 правильно вычисляет Г[КЗТ (А), Доказательство. Заметим, что если Р;,(Х)=Р;(Х) для всех Х 6 5[В Х, то Р;(Х) — Р~(Х) для всех 1' > [ и всех Х.
Таким образом, мы должны доказать, что хЕГ[КЗТ,(А) тогда и только тогда, когда хЕРг(А) для некоторого !. Достаточность. Индукцией по 1 покажем, что Р,(А) = ~Г[КЗТл(А). Базис, ! =О, тривиален. Рассмотрим фиксированное значение ! и допустим, что наше утверждение верно для всех меньших значений !'. Если хЕР,(А), то либо хЕР,,(А) (и в этом случае сразу получается нужный результат), либо в Р можно найти такое правило А — У, ...
!'„, что х,ЕР,,(1;,) для 1(р(п и х= =- Г[КЗТ„(х,...х„), По предположению ийдукции х„„~ Г[КЗТл(Ур). Таким образом, для каждого р существует такой вйвод Г ~л у, что хр — -- Г[ЮТ„(ур). Следовательно, А =>* у,... у„. Теперь надо показать, что х=- Г[КЯ"„(у, ... у„), и заключить отсюда, что х Е Г[ЮТл(А). Случай [: ~х, х„(<й. Тогда ур — — — хр для каждого р, и х=у, ... у„. Так как в этом случае у, ... у„ЕГ[ЮТл(Л), то х Е Р1КЗТ,(А). Случай 2: 1х, ... х, ( < й для некоторого в) О, но 1х, ...
... х„.,1-ь[ь, Тогда ур — хр для 1(р=.з и х состоит из первых й символов цепочки х, ... х„,. Так как х„„— префикс цепочки у„„то х — префикс цепочки у, ... у,,„а значит, и цепочки у,... у„. Итак, х ЕГ1КЯ'„(А). Необходимость. Пусть хЕГ!КЗТ (А). Тогда А~" у для некоторого г н х= Г1КЗТ„(у). Докажем индукцией по г, что х ЕР,(Л). Базис, г= 1, тривиален, так как х Е Р, (А), (На самом деле предположение индукции можно было бы несколько усилить, по здесь это не к чему.) Зафиксируем г и предположим, что наше утверждение верно для меньших значений г.
Тогда А > Г [Р,р с-1 у где у=у, ... у„и Гр~'рур для 1(р(п. Очевидно, г < г. По предположению индукции хрЕР, 1(Рр), где хр — --Г!КЗТ (У,). Таким образом, Г[ЮТл(х, ... х„) = х Е Р„(А). П 398 Следующий алгоритм представляет собой метод вычисления ля заданной грамматики 6 -- (Ь[, Ез Р, 5) тех множеств Е из г,*л, для которых существуют такие в, А и я, что 5=>1вАя и Г[КЗТл(я) =Е. а,(5, А) = ((е, а, Ьи о,(А, Л) = ((еЦ 399 л ягор итм 5,6.
Вычислен не а(Л). Вход. КС-грамматика 6 — (Ь[, Х, Р, 5). Выход. а(А)=(Е1Е~л*л и 5=о",вАя, Г!КЯ'л(я)=Е для некоторых в и я). Метод. Будем вычислять для всех А и В из Ь[ множества о(А, В)= (Е ~Е с: — Х*л и А =-ь[хВя, Š— Г[ЮТл(я) для некоторых х и я).
С этой целью будем строить множества а;(А, В) для 1=0, 1, (1) Положим о„(Л, В) = (Е1Е ~ Хчл„А 5Вя принадлежит Р и ! =Г[КЗТ„(я)). (2) Допустим, что а;,(Л, В) уже построены для всех А и В. Определим а;(А, В) следующим образом: (а) Если Е 6 о; .,(А, В), то поместим Е в о,(Л, В).
(б) Если в Р есть правило А Х, ... Х„, то в а,(А, В) поместим такой язык Е, для которого найдутся такие 1([(п и Е' Е о;,(Хр,В),что Е =Е'®ьГ1ЮТ„(Х +,)Ял... ... © ГГКЗТ (Х„). (3) В тот момент, когда ас(А, В)=-о;,(А, В) для некоторого [ и для всех А, В, положим а(А, В)=а;(А, В). Так как а,,(А, В) = о;(А, В) ы У(л "л) для всех [, то такое [ должно найтись. (4) Нужное нам множество а(А) есть а(5, А). Г~ Теорема 5.8. Е принадлежат множеству о(5, А) построенному алгорит.яом 5.6, тогда и только тогда, когда 5=!>,*вЛя и Е= — Г[КЗТл(я) для некоторых вЕу~* и я Е(5[[[1)ь.
Д о к а з а т е л ь с т в о. Доказательство аналогично доказательству предыдущей теоремы; оставляем его в качестве упражнения. гз Пример 5.!9. Проверим, выполняется ли [ Е(1)-условие для грамматики 6 с правилами 5 — Л51е А — аА(Ь Начнем с вычисления Г1КЗТ,(5) =.. (в, а, Ь) и Г[ЮТ,(А) — (а, Ь). Затем нужно вычислить а(5)- о(5, 5) и о(А)=а(5, А).
На шаге (1) алгоритма 5.4 получаем а,(5, 5) — ((в)) а,(А, 5) = 8 Гл. ь. ОднОпРОхОдный синтАксическии Аиллиз еез возвРлтов На шаге (2) к этим множествам добавить нечего. Например, так как есть правило 5 — А5 и О,(А, А) содержит (е), то на шаге (2б) надо добавить к о(5, А) множество В = (е)Д+1Р1К5Т1(5) = (е, а, Ь). Но а,(5, А) уже содержит множество (е, а, Ь), так как его со. держит О,(5, А).
Таким образом, О(А)=-((е, а, Ь)) и О(5)=-((е)). Чтобы проверить, что 6 — Щ1)-грамматика, нужно убедиться в том, что (Р!ЮТ1(А5) Д+! (е)) П (Р1ЮТ1(е) Я, (е)) =. 8. (Это делается для двух 5-правил и единственного элемента (е) множества п(5, 5).) Так как Н К5Т,(А5) = Р)К5Т,(А) ®1 ГП(5Т,(5) =. (а, Ь) и РП(5Т!(е) — — (е), то действительно (а, Ь) П (е) =-Й/. Для двух А-правил нужно показать, что (НК5Т!(аА)®,(е, а, Ь)) П(Г1К5Т,(Ь)Д+! (е, а, Ь))=»а' Это сводится к проверке равенства (а) П(Ь):=-!Э', которое, очевидно, верно. Итак, 6 — это ЕЕ(1)-грамматика. (! УПРАЖНЕНИЯ 5.1.1.
![](https://s.studizba.com/z.php?f=/templates/si/i/noavatar.png&w=100&h=100&t=1"){kind=avatar}
