Теория синтаксического анализа, перевода и компиляции - Том 1 (943928), страница 35
Текст из файла (страница 35)
Допустим, что (2.4.2) истинно для и, н пусть А=р"'ллпл. Тогда можно написать А =рХл... Ха:>аш, где цепочка пл=шл... ша такова, что Х;:-"уюу длЯ каждого 1 н и, л,'). Согласно (2,4,2), если Х Е1л1, то Х,Е)ч(т для некоторого 1. 'у 7' Если ХуЕ2, то 4,=0, Пусть 4= — 1+шах(1„..., 44). Тогда по определению А Е 1ч)а Индукция завершена. Положив А = 5 в (2.4.!) и (2.4.2), получим утверждение теоремы. П Следствие.
Для КС-градлматики 6 проблема пустоты языка 7. (6) разрешима. Г) Определение. Символ ХЕ)л(ОЕ назовем недостижимым в КС- грамматике 6=()ч), Е, Р, 5), если Х не появляется нн в одной выводимой цепочке. Недостижимые символы. можно устранить из КС-грамматики с помогцью следующего алгоритма, который легко получить из алгоритма 0.3. л) Это „очевидное" аамечание требует телл ие лленее некоторого осчыспе. Ння: Нредетаавто Ссбе дсрЕаО ВЫВОда А =~аьЛЛа, Н НЕМ М! — Крапа ПОдд р Ва а поддерева с корнем Х . д 170 Алгоритм 28. Устранение недостижимых симво- л о в. Вход. КС-грамматика 6=-(1чт, Е, Р, 5), Выход, КС-грамматика 6'=-(1ч', Г, Р', 5), у которой (1) 1. (6') =7.(6), (й) для всех Х Е1л('() Х' существуют такие цепочки и и р из (Х'ОГ)* что 5=>а аХ(1 Метод.
(1) Положить т'л== (5) н 4'=-1. (2) Положить 1';= — (Х) в Р есть А аХР и А ЕУ,,) ирт (3) Если у, вну,. „положить 4'=4+1 и перейти к шагу (2). В противном случае пусть Р(' = Ут П Р(, х'=у,'пх, Р' состоит из правил множества Р, содержащих только символы из уи 6' = (лч ', г.', Р', 5). Алгоритмы 2.7 и 2.8 очень похожи, Заметим, что шаг (2) алгоритма 2.8 можно повторить только конечное число раз, так как ут — Х() Х.
Кроме того, прямое доказательство индукцней по 4 показывает, что 5=за,аХ)) тогда и только тогда, когда ХЕ!'; для некоторого 4. Теперь мы готовы устранить из КС-грамматики все бесполезные символы, А л г о р н т м 2.9. У с т р а н е н и е б е с и о л е з н ы х с и м в о- ЛОВ. Вход. КС-грамматика 6=-. (1ч, 2, Р, 5), у которой 1-(6) ФЯ. Выход. КС-грамматика 6' =- ((ч', Х', Р', 5), у которой 1. (6') = 7 (6) н в 1л)'() Е' нет бесполезных символов.
Метод. (1) Применив к 6 алгоритм 2.7, получить 1ч',. Положить 64=-()л)ПМ„Е, Р„5), где Р, состоит из правил множества Р, содержащих только символы из 1л),Цг.. (2) Применив к 6, алгоритм 2.8, получить 6'=(7ч', Е', Р',5). С) На шаге (1) алгоритма 2.9 из 6 устраняются все нетермнналы, которые ие могут порождать терминальных цепочек.
Затем на шаге (2) устраняются все недостижимые символы. Каждый символ Х результирующей грамматики должен появиться хотя бы в одном выводе вида 5=э" шХулаплху. Заметим„что если сначала применить алгоритм 2.8, а потом алгоритм 2.7, то не всегда результатом будет грамматика, не содержащая бесполезных символов, Гл.
2. элемаиты теОРии языкОВ 2л. контекстно-своводные языки Теорема 2.13. Грамматика 6', которую строит алгоритм 2.9, не содержит бесполезных сил!волов и Е (6) =-Е (6'), Д о к а з а т е л ь с т в о. Доказательство того, что Е (6') — -Е (6), оставляем в качестве упражнения. Предположим, что А ЕХ'— бесполезный символ. Тогда по определению бесполезности символа могут представиться два случая: Случай 1: Вывод 5=>о, аА)) ни для каких а и )1 невозможен. В этом случае символ А устраняется на шаге (2) алгоритма 2.9.
Случай 2: 5 =>о, аА)) для некоторых а и р, но вывода А=,*>о,т для и!ЕТ." не существует. Тогда А не устраняется на шаге (2) и, кроме того, если А =>ауВ8, то и В не устраняется на шаге (2). Таким образом, если А=эот, то А=>о,и!. Тогда можно заключить, что вывода А =,">" ш для шЕ г," не существует и А устраняется на шаге (1).
Доказательство того, что ни один терминал в 6' не может быть бесполезным, проводится аналогично; мы оставляем его в качестве упражнения. ез Пример 2.22. Рассмотрим грамматику 6=((5, А, В), (а, Ь), Р, 5), где Р состоит из правил 5 — а~А А — А  — Ь Применим к 6 алгоритм 2.9. На !ваге (1) получим Х,=(5, В) и 6,=((Я„В), (а, Ь!, (5 а,  — Ь), 5). Применив алгоритм 2.8, получим 'Р'2=)г! =(5, а). Итак, 6' — ((Я), (а), (5 — а), 5), Если применить к 6 сначала алгоритм 2.8, то окажется, что все символы достижимы, так что грамматика не изменится. Затем применение алгоритма 2.7 дает Х,=-(5, В), и результирующей будет грамматика 6„отличная от 6'. С) Часто бывает удобно устранить нз КС-грамматики 6 е-правила, т.
е. правила вида А — е. Но если е ЕЕ (6), то очевидно, что без правил вида А — е не обойтись. Определение. Назовем КС-грамматику 6= — (Х, Х, Р, 5) гра,яма!пикой без е-правил (нли неукорачиваюи(ей), если либо (1) Р не содержит е-правил, либо (2) есть точно одно е-правило 5 — е и 5 не встречается в правых частях остальных правил из Р. Алгоритм 2. 1О. П р е о б р а з о в а н и е в грамматику б е з е-правил. Вход.
КС-грамматика 6=(Х, Х, Р, 5). Выход. Эквивалентная КС-грамматика 6' = (Х', Х, Р', 5') без е-правил. Л(етод. (1) Построить Х, — (А ! А Е Х и А =>се). Это аналогично тому, что было в алгоритмах 2.7 и 2.8, и остается в качестве упражнения. (2) Построить Р' так: (а) Если А а,В,а2В,а2...В„аь принадлежит Р, й)0 н В!6 Х, для 1(г(й, но йи один символ в цепочках а (О /.=Й) не принадлежит Х„то включить в Р' все правила вида А — ~ авХ!а!Хг... сс„!Хьаь где Х,— либо В!, либо е, но не включать правило А — е (это могло бы произойти в случае, если все и,. равны е). (б) Если 5 Е Х„включить в Р' правила 5' — е)5 где 5' — новый символ, и положить Х' = Х() (5').
В противяом случае положить Х'=Х и 5'= 5. (3) Положить 6'=-(Х', Х, Р', 5') С Пример 2.23. Рассмотрим грамматику из примера 2.19 с правилами 5 а5Ь5)Ь5аЯ)е Применяя к этой грамматике алгоритм 2.10, получаем грамматику 5' 5/е 5 в аЯЬЯ)ЬЯаЯ/аЯЬ/аЬЯ/аЬ!ЬЯа/ЬаЯ)Ьа С) Теорема 2.14. Алгоритм 2.10 даетп грал!матику без е-правил, вквиваленп!ную входной гримлютике. До к а з а т ел ь с т в о, Непосредственно видно, что алгоритм 2.10 дает грамматику 6' без е-правил.
Чтобы показать, что Е (6) = Е (6'), достаточно доказать индукцией по длине цепочки ш, что (2.4.3) 'А =>а,ю тогда и только тогда, когда щ~е н А >оп. Доказательство этого утверждения оставляем в качестве упражнения. Подставив Я вместо А в (2.4.3), видим, что !ЭЕЕ(6) для т~=е тогда н только тогда, когда и ЕЕ(6'). Очевидно, что еЕЕ(6) тогда и только тогда, когда еЕЕ(6'). Таким образом, Е(6) =-Е(6'). е ! Другое полезное преобразование грамматик — устранение правил вида А — В, которые мы будем называть цепньы!и. 273 гл, г. элементы теОРии языкОВ ".а контекстпо-свОВОдные языки А л г о р и т м 2.! 1.
У с'т р а н е н и е ц е п и ы х и р а в и л. Вход. КС-грамматика 6 без е-правил. Выход. Эквивалентная КС-грамматика 6' без е-правил и без цепных правил. Метод, (1) Для каждого А ЕХ построить Ял — — (В ) А ~'В) следую- щим образом: (а) Положить г)о=(А) и )=1, (б) Положить 1йг = (С ~  — С принадлежит Р и В Е )т); г) 1) (в) Если г(; ФР); „положить г'=г'+1 и повторитыпаг (б). В противном случае положить Хл-— -1)О (2) Построить Р' так: если  — и принадлежит Р и не яв- ляется цепным правилом, включить в Р' правило А — гх для всех таких А, что ВЕ'Р!л. (3) Положить 6'=-(Х, Х, Р', 5).
() Пример 2.24. Применим алгоритм 2.11 к грамматике 6, с пра- вилами Š— Е+Т(Т Т вЂ” Тпр)Р Р- (Е))а На шаге (1) )Чн=(Е, Т, Р), ъ(т=(Т Р) )т)п=(Р), После шага (2) множество Р' станет такнм: .Е . Е + Т ~! Т и Р ~1 (Е) ~1 а Т вЂ” ~Тмр)(Е) )а Р— (Е))а П Теорема 2.15. Грамматика 6', которую строит алгоритм 2.11, не имеет цепных правил и Е(6) =Е(б'). Д о к а з а т е л ь с т в о.
Непосредственно видно, что алгоритм 2.!1 дает грамматику 6' без цепных правил. Покажем сначала, что Е(6') ыЕ(б). Пусть шЕЕ(6'). Тогда в грамматике 6' существует вывод 5=оае=оа,=;>...=~гк„=ш. Если прп переходе от аг к аь„применяется правило А — р, то существует такой символ В ЕМ (возможно, В=А), что А=ЯВ и В=>о(). Таким образом, А — о(1 и яг=>йаг„.
Отсюда следует, что 5~йги н ао Е Е, (6), так что Е (6') ы Е, (6). Теперь покажем, что Е(6):-Е(6'). Пусть шЕЕ(6) и 5= сс,:=,>г иг=.>,...~, ап =ш — левый вывод цепочки игв грамматике б. Можно найтн последовательность индексов г„г„..., га, состоящую в точности из тех 1', для которых на шаге ау,=>га, применяется не цепное правило. В частности, га=-п, так как вывод терминальной цепочки не может оканчиваться цепным правилом. )74 Так как мы рассматриваем левый вывод, то последовательные применения цепных правил заменяют символ, занимающий одну и ту же позицию в левовыводимых цепочках, из которых состоит соответствующая часть вывода.
Отсюда видно, что 5=оп сси — -оп аг,=>в . °,=>и а, =-ш. Таким образом, шЕЕ(6') н, значит, Е(6') =Е(6). П Определение. КС-грамматика 6= (Х, 2, Р, 5) называется Х г амматикой без циклов, если в ней иет выводов А=~+А для Е !1. Грамматика 6 называется приведенной, если она без циклов, без е-правил и без бесполезных символов').
Грамматики с е-правилами или циклами иногда труднее анализировать, чем грамматики без е-правнл и циклов. Кроме того, в любой практической ситуации бесполезные символы без необходимости увеличивают объем анализатора. Поэтому для некоторых алгоритмов синтаксического анализа, обсуждаемых в этой книге, мы будем требовать, чтобы грамматики, фигурирующие в них, были приведенными. Докажем, что это требование все же позволяет рассматривать все КС-языки.
![](https://s.studizba.com/z.php?f=/templates/si/i/noavatar.png&w=100&h=100&t=1"){kind=avatar}
