Теория синтаксического анализа, перевода и компиляции - Том 2 (943929), страница 27
Текст из файла (страница 27)
Аа|а В Во|а является лево- н правоанализируемой, по не Е)(. (4) Грамматика 64 с правилами 5 АЬ(Вс А Аг|а В Вс|а С а является правоаналнзируемой, но пе 1В и не левоанализируемой. (5) Грамматика б, с правилами 5 ВАЬ!САс А ВА|а В а С- а является левоанэлнзируемой, но не правоаналнзнруемой.(См. пример 3.25, том 1.) 146 ВЛ.2.
Аь-грамматики в нормальной форме Грейбае В настоящем разделе ьгы рассмотрим преобразования Е(.-грамматик, сохраняющие 1Л.-свойство. Ывшн первые резулыаты касаются г-правил. Мы дадим два алгоритма, применяя которые последовательно, можно преобразовать ЕЦЬ)-грамматику в эквивалентную Е1(й+ 1)-грамматику, не содержащую г-правнл. Первый ал1орнтм изменяет грамматику так, чтобы каждая правая часть либо стала равна е, либо начиналась с символа (возможно, терминального), из которого не выводится пустая цепочка.
Второй алгоритм преобразует грамматину, удовлетворяющую этому сяовию, в грамматику без е-правил. Оба алгоритма сохраняют ).-свойство грамматики. Оаределение. Пусть 6 =(М, 2, Р, 5) — КС.грамматика. Вудам называть нетермннал А исчезающим, если вз А выводится пустая кепочка. В противном случае символ из 562 назовем нгисчезтащим. Таким Образом, каждый терминал — неисчезающий символ. Вудем говорить, что грамматика б удаглгтгорлгт усгоги4о ( ), если каждое правило из Р имеет вид А г или А Х,... Х, где Х,— неисчезающий символ'). А л г о р и т м 8.1.
П р е о б р азова н и е г р а м м а т и к и в г р а м- Агат И К У, УДОВЛЕтза Р Я ЮЩУЮ УСЛОВИЮ (6). Вход. КС.грамматика 6=(Ы, В, Р, 5). Выход. КС-грамматнка 6,=-(М„В, Р„Ь',), удовлетворяющая условию (ь), для которой Цб,) =7(б) — (г) '). А(гтад. (1) Пусть Ьр = )ч 6 (А | А — исчезающий нетерминал из М). Из не- терминала А будут выводиться те же цепочки, что и из А, за исключением е. Следовательно, А будет неисчеаающим.
(2) Если ебб(б), положим 5,=5. В противном случае 5,— 5. (3) Каждое правило нз Р, не являющееся е-правилом, можно единственным образом представить в виде А В, ... В Х, .Хь (где т)0, и ~0 и т+л ) О), прнчем наждый символ В; исчезающий и, если и >О, Х,— неисчезающий снмвол.
Остальные ХА(1<)(л) могут быть как Исчезающими, так и неисчезающйми. Таким образом, Х,— самый левый неисчезающий символ в правой части правила, Для каждого правила А В,... В„Х,...ХБ, не являющегося г-правилом, построим Р'. '1 В арнгнньле тькья граннкткка еььнзьатая ааппаньые,— прим. Берег. ') Паяучьеньк аа ьлгарнтнт 8 ! грэинатикь 04 ка ьквнзьлактка ксяадкай 0 тедть примеру ьэтараь, рекомендуем чнтьтьяю аккаиу в кьчаапи уа1ммнення еьйтк н нспрзвнть ашкбкн алгарнтиа 8.!.
†Пр. Ргд. 147 ~ л °, ТЕОРИЯ ДЕТРРМИИИРОВАИИОГО РАЗБОРА 4 Ь ТЕОРИЯ ЛС.ЯЗЫКОЗ (а] если т)~1, включилг в Р' т правил А В,В,...ВХ,...Х„ А —.В,В, ... В„Х, ... Х„ А В„Х, ...Х„ (б) если пми! н т ) О, включим в Р' правило А Х,...Х„ (в) кроме того, если А — исчезающий символ, включим в Р' все правила из (а) и (б), где слева вместо А стоит А. (4) Если правило А е пренадлежит Р, включим в Р' правило А е. (б) Положим 0,=(ВО 5, РО 5,), где 6,— это грамматика С' =(Р(', Х, Р', 5,), из которой выброшеяы все бесполезные символы и правила. Е] Пример 8.1.
Пусть 0 — Щ1)-грал«матика с правилами 5 АВ А аА(е В ЬА)е Здесь все нетермнналы исчезающие, так что введем яовые не- терминалы 5, А и В; первый из ннх будет новым начальным символом. Правила А аА н В ЬА оба иачинакггся с неисчезающего символа, позгому их поавые части имеют вид Х,Х, (для шага (3) алгоритма 8.1). Таким образом, эти правила будут сохранены, а к множеству правил добавятся еще правила А аЛ В ЬА В правиле 6 АВ все символы правой части исчезаюрцие, так что ее можно записать в виде В,В,, Зто правило заменяется на четыре правила 5 АВ(В 5 ЛВ(В Так как 5 — новый начальный символ, находим, что симаол 5 теперь недостижим. Окончаюлыюе мио«кество правил, построен- 14а ное по алгоритму 8.1, таково: 5 АВ)В А аА А аА(е В ЬЛ В ЬА]е П Докажем, что алгоритм 8.1 сохраняет свойство грамматики быть ].(.(й]-грамматикоин Теорема 8.3.
Пусть 6,— грамматика, полученная из 6 ло а ~гор«го!му 8,1. Тогда (1) !.(0,) -- 6(0) — (е], (2) ггли 6 — (.(.()г)-ьраллапгика, гпо 6,— тоже (.(.(й).гроз«- малика. Доказательство. (1) Инду кцией по длине цепочки можно показать, что дчя псех Л из Ы (а) Л=.>ьт ю тогда '] н только тогда, котла Л лйю, (б) А«ро ю тогда' ) и только ~огда, когда а Фе и Л ~'ю Подробное доказательство оставляем читателю в качестве упражнения.
Утверждение (2) докажем от противного. Допустим, что оно неверно. Тогда в 6, можно найти выводы 54 тло,г БРА О ~о,«ю(!а =зол шх 5, =Лг, МА а ~он ЮУа «Ььо ЮУ тле Г!йЗТА(х) 6-Р1КЗТА(У), (]ФУ и Л вЂ” либо А, либо А, По этим двум выводам можно построить соответствующие выводы цепочек юх и юу в грамматике О. Начнем с того, что определим й(А) =-й(Л) =-А для А 8 В и й(а) — — а лля ай В. Для кажлого правила В 6 иэ Р, найдем в Р правило  —.6'й(6), из которо~о оно было построено иа шаге (3) алгоритма 8.!.
Другими словами,  — -й(В), а 6' — некоторая (Боз. можно, п]стая) цепочка исчезающих символов. Всякий раз, когда правило В 6 применяется в каком-нибудь из выводов в грамматике 0М в соответствующем выводе в грамматике 6 заменим его правилом В 6'й(6), а затем произведем левый вывод цепочка е из 6', если 6'~=е. Таким образам, получаем 5 тлйг юАЬ(а) лг~ыр Я)й(а) =ло«ш(г(8)й(а) ьог юх 5 юо«юАЬ (а) ~о юу'й(у]й(а) ~о«юй(у!)«(а! ~о«шу ') ЭТО ЯЕЬСРЕО.
СН, ЛР«АЬАУШУЮ СКЕЕКУ вЂ” !1Р . Р«О. ГЛ 8. ТЕОРИЯ ДЕТЕРМИНИРОВАННОГО РАЗЕОРА 8.8: ТЕОРИЯ ЛЛ ЯЗЫКОВ Шаги вывода от вй'йф)18(а) до вйф)й(а) можно запнгать в виде н(уй(Ь]й(а].— — нь, юс вб, юс... ~с вб„= вй(Ь]й(а) а шаги от ву'й(у)Ыа) до вй(у)й(а) — в виде ву'й(у)й(а) = вес ~ч ве, Ю,...
~, ве„= вй(у)й(сс) Пусть г=-Г1ЕВТ(х) =ГПТВТ(у). Мы утверждаем, что г принэдлежит Г!КВТ(Ь,) и Р1ВВТ(ед для всех с, поскольку (]' и у' состояг только из исчезающих символов (если Ь' и у' непусты). Тас как 6 — 1.1.(й)-гралсматика, то Ь, = ел для всех 81 В частности, Ь'йф! =-у'Ь(у). Следовательно, Ь и у получаются по алгоритму 8,1 из одного и того же правила. Если Ь'~у', то в одном из приведенных выше выводов из нетермииала Выводится е, а в другом не выводится.
Так кэк это противоречит Ш.(й]-условию, заключаем, что ф=у'. Так как цепочки (! и у предполагаются различными, они не могут одновременно быть пустыми, и значит, обе начинаются с одного и того же неисчезающего символа. Итак, т =-л, а это противоречит предположению о том, что Ьчьт. С) Следующее наше преобразование полностью исключает из 1Л,.грамматики Е.правияа. Будем с 8нтатль 8то г8)ь(6).
Идея заключается в том, чтобы сначала применить к Щй]-грамматнке алгоритм 8.1, а затем, скомбинировав в выводах неисчезающие символы со всеми последующими исчезающими символами, заменить полученную пеночку одним символом Если гралсматика является ЕЕ(й).грамлсатикой, то число 8юследовательных исчезающих символов, которые могут стоять за неисчезающими символами, ограничено, Определение. Пусть 6 = (Х, Е, Р, 5] — КС.гралсматика.
Обозначим через РО множество символов вида [ХВТ...ВА], где (!) Х вЂ” неисчезающий силсвол грамматини 6 (возможно, терминальный), (2) Ви, .., „— исчезаюадие символы (следовательно, нетерыинэлы), (3) если ! Ф В то В, чь Вг (т, е, список Вм ..,, В„не содержит повторений). Зададим гомоморфнзм й из множества ра в множество (Х О 2)*, положив й([а]) =-а, Лемма 8.2. Пуапь 6= (Х, Е, Р, В)- П Е(й)-граммаглика, удоглгтатряюсцал уссоаию (л) и такал, что из каждого нгтгрмииаяа емгодитгя хотя ба одяа кгпугтая тгрминальнал цглгска, а Уа и й определены выше. Тогда для каждой яггссгьсгодимо81 г 6 игпугтай цепочки а существует единственная цгпочка Ь иэ Ра, для которой й(Ь) ..: а. До каза тея ь ство.
Цепочку а можно единственным образом записать а виде сса,...а„, гл~)1, где а, лля всех с — это неисчезающий символ, за которым следует цепочка исчезающих символов (поскольку в 0 каждая непустая выводимая цепочка начинается с неисчюающего символи). Достаточно показать, что [а,] для всех ! принадлежит т'а. Если зто не так, то а, можно представип, в виде Хрвувб, где  — некоторый исчезающий символ, а Ь, у и Ь состоят только из исчезающих символов, т.
е. а, не удовлетворяет условию (3) определения 1'О. Пусть в — такая непустая цепочка, что В ЮЬ в. Тогда найдутся два различных левых вывода ьвувь ю,' вувь ~, !вь ю", []Вувд ~! ВЬ Ю; вб М в Отсюда сразу получаем, сто грамматика 0 неоднозначна и, следовательно, не является ЕЕ-грамматикой. С) Чтобы доказать, что всякий Щй)-язык, не содержащий г, имеет Щй, 1)-грамматику без г-правил, применим следующий алгоритм. Алгоритм 82.
![](https://s.studizba.com/z.php?f=/templates/si/i/noavatar.png&w=100&h=100&t=1"){kind=avatar}
