Теория синтаксического анализа, перевода и компиляции - Том 2 (943929), страница 32
Текст из файла (страница 32)
Пусть 6=(В, 2, р, 5) -клноническая грамматика. Рассмотрим тря возмои<пых конфликта отношений предшествоввпия и покажем, что нн оЛин из них не реализуется. Случай !' Предположим, что Х (1' и Х вЂ” )'. Поскольку Х ' У, долгкно быть правило А ХУ типа 2 или 4. Поэтому Х=-[бд') и либо У ЕЕ и д' — состояние чтения, либо У =[рр') и р' †состоян стирания. Пасколысу Х( 1', должно быть правило  — ХС типа 4, где С~+ Уа для некоторой кепочки а. Пусть, как и раньше, Х=-[дд']. Тогда д' должно быть состоянием записи, потому что В ХС вЂ” правило типа 4.
Более того, У должен иметь яид [рр'], где р' — состояние стирания, и, значит, А ХУ вЂ” правило типа 4. Из вида пранил типа 4 можно заключить, что р--второе состояние в пишущей последовательности для 92 Так как В ХС вЂ” правило типа 4, то С -[рр ) для некоторого р". Рассмотрим теперь вывод С~", Уа, который можно записать в виде [зз,]---ог[з,з!]а,=от., ~, [з„з„)а„ где [з,зД=[рр") и [в„зД=.[рр'). Ич вида правил заключаем, что для каждого ) либо з„,=з, (если [зЛД заменяется по правилу типа 2 или 4), лнбо з;„— состояние, которое в пишущей последовательности для д' следует за состоянием з, (если [з,зД заменяется ао правилу типа 3).
Только в последнем случае з,'„будет состояпнем стирания, и, значит (посколыгу з„'(= рг) есть состояние стирания), з„( — р) в пишущей последовательности для д' следует зэ з„ ,. Твк каи з„ , либо есть р, либо следует за р В этой последовательности, то р появляется в пи|пущей последовательности для д' дважды. Это означает существование никла, и мы заключаем, что в канонической грамматике конфликтов между отношениями ( и ' нет. ') Для аьга чтобы лакввьть, что кьнанвчаекая гваммвтввв является врастай ССП.грэннэтчвай,,шетатачва лачьвать.
что авэ — граннвтньа слабого предшествовав в (а ве О,))-ввавшествавачвя). Однако эта Лавалввтгльвае условие аредетавляет аяреяелегвый нвгерес, э Ланвэвтельсгвэ ве услажевег. )10 Случай 2. Х()' и Х) )'. Поскольку Х()', мы, как и в случае 1, выводим, что Х=-.[йц'], где д' — состояние записи. С друтой стороны, если Х ' 1', то есть правило Л В7., где В~" аХ и 2~' У(). Вид правил таков, что если В=>ь а[дую'], то ц' — состояние стирания. Но мы уже нашли, что д'- — состояние записи. Отсюда заключаем, что конфликтов между ( н Уь нет. Случай 3: Х='У и ХйьУ.
Поскольку Х -У, мы, кэк и в случае 1, выводим, что Х=[дд'], где ц' — состояние чтении или записи. Но из Хйгу, как в случае 2, заключаем, что д' — состояние стирания. Таким образом, наноническая грамматика является грамматикой предшествования. Г) Теорема 8.11. Калоничегкич граммояита явеягтгя простой граллютокой со слмшлнлой гтратегией лредшеотвовонил. Доказательства. В соответствии с теоремой 8.!О и леммами 8.8 и 8.9 достаточно поквзатьч что для каждой канонической грамматики 6=(М, 2, Р, 3) (1) если А аХУ)) и В Уй принадлежат Р, то Хк1(В), (2) если А а и В а принадлежат Р, А~В, то )(А)6 В!(В) = 8. Справедливость утверждения (1) сразу следует из того, что если Х (В или Х вЂ” 'В, то Х(У. Но если существует правило Л аХ1'11, то Х ' 1', и потому есть конфликт отношений предшествовапия, что противоречит лемме 8.9.
Рассмотрим теперь утверждение (2). А а и В а ке могут быть различными пряяиламн типа 2, так кэк если А — [дд'], В = [рр'), а = [гг ) а и грамматика 6 построена па ДМП.автомату М =-(Я, 2, Г, й, ом Я,, (йг)), то 8 (г', а, 2) = (я', 2) = 0 ', Е) Следовательно, д' — р'.
Но из вида правил типа 2 вытекает, что д=-. р=г, так что А =. В вопреки условию. Аналогичное рассуж. денис, которое предлагаем читателю в качестве упражнения, показывает, что Л и и В а не могут быть различными правилами типа 4. Разберем теперь случай а — а, т. е. случвй, когда А а н  †.а -- правили типа 1. Вообще, если Х ' У или Х ' У, то, как мы видеян (доказлтельство теоремы 8.9, случай 1), Х должен быть нетсрминалом.
Итак, допустим, что С принадлежит и 1(А), и 1(В). Тогда существуют правила Р, СР, и Ег СЕм где Рг--о'Ай и Е,"— о*ВТ. Случай Л =-Р, или В =-Е, не исключается. Положим С-=-[йй'], А =[рр ] и В=[гг'). Тогда р и г— состояния чтения, так как [рр') а и [гт') а — правила типа 1. Согласно предыдущему рассужденикт, каждое из состояний р и г должно появиться в пни|у~ней последовательности для д' н, гл. з. теогия детсиминигованного глзвогл следовательно, должно заканчивать эту последовательность, Значит, Р=г. Так как 8 (р, о, 2) =(Р', 7) = (г', 7) то Р'==г', А=В вопреки условию. Таким образом, Л и и  — - в не могут быть правилами типа 1. Наконец, предположим, что А а и В а--правила типа 3.
Как и раисе, пусть С принаалежит 1(А)б((В), С=(дй'), А.= = (рр') и В=(гг'). Тогда каждое из состояний р и г должно появиться в пишущей последовательности для й'. Если Р=-г, положим 8(р, е, 2) =(з, У). Е этом случае а -)зт') для неиоторого з' и 8(з, е, 1')=-(р, а) =(г', е). С.тедовательно, г'=-Р' и опять А = В попреки условию, ПУсть тогда Рэмг. Если о=(зз'1, то з стоит в пиш)щей последовательности для й' и после р, и после г, а, заачит, появляется там дважды. Отсюда выводим, что А а и В и не являются правилами типа 3, Таким образом, утверждение (2) верно, н 6 в простая ССП-грамматика.
Из теоремы 8.11 следует, что язык Яй порождается простой ССП-грамматикой, если Ь вЂ” детерминированный язык, а 4 †коцпевой маркер. На самом деле верно более сильное утверждение: если 4 убрать с конца каждой цепочки, порождаемой канонической грамматикой, то измененная таким образом грамматика останется простой ССП-грамматикой. Учитывая, что построение, убирающее концевые маркеры, будет проводшься неоднократно, мы представим сто здесь в виде алгоритма.
Алгоритм 8.4. Удаление правого концевого маркера из слов, порождаемых приведеннов грамматикойй. Вход. Приведенная грамматика 6= (К, Е б (г), Р, 5), где 422 и Я(6) =-!щ для некоторого Я си 2 . Выход. Грамматика 6, = (Р)„Е, Р„5), для которой Я (бг) — !.. Метод. (1) Убрать из Р все пранила вида Л (2) Заменить в Р все правила вида Л ае, где атве, аа А и. (3) Если правило А аВ принадлежит Р, псле, и В~ой, добавить к Р правило Л а, (4) Исключить из )й и нз полученного множества правил бесполезные нетермяналы и правила.
Обозначить поные множсстоа нетсрминалов н правил Н, и Р, соответственна. Д Теорема 8.12. Если б,— гразсиаглпки, пссглроеинил алгариш. лом 8.4, ао Я(6,) (,. з з. гглммхтики. позождлющив детееминияавхиныв языки До к аз а тельство. Поско ~ьку каждое слово щ языка Я(6) имеет вид х!г для хЕЕ, то для любого АЕК нз А=оси следует, что либо и Е Е, либо и =об где об Е".
Назовем нетермипалы первого типа лрамеждточиыли, а нетермипалы второго типа — зовсршающили. Простви индукция по длине выводов пока. зывает, что если А — промежуточный нетерминал, то Л ~2 и тогда и только тогда, когда А~„, и, пЕ2*. Аналогично, если А — завершающий нетерминал, то .4 =ого( тогда и только тогда, когда А ~2 о.
Доказательство оставляел~ в качестве упражнения. Итак, 5Ею( тогда и только тогда, когда 5~о,ю. Следовательно, Я (6,) =- Я. Теорема 8. 13. Яс т Я вЂ” детермииирозоииый лзыь и е Т Я, шо Я порождоешсл лросшой ССП-грамлапшкси, Доказательство. Пусть ЯснЕ и и'ТЕ. Тогда, согласно следствию 2 теоремы 8.10, ЯС порождается канонической грамматикой б = (1М, Е, Р, 5), которая по теореме 8.11 является простой ССП.грамматикой. Пусть 6,.=-(5„ Е, Р„, 5)- .грамма. тика, построенная алгоритмом 8.4 нэ грахгматйки б.
Тогда 1 (6 ) = С. Мы докажем, что 6,— также простая ССП грамма|ика. Легко показать, что 6, не имеет е-правил и бесполезных сим. волов. Если бы грамматика б, содержала цикл, в ней было бы правило Л В, входящее в Р„ оо не в Р. Допустим, что правило А ВХ принадлежит Р для некоторого Х, для ко1орого Х ~с, щ Предволажим далее, что Л =зо, В~г А.
Тогда А =ьойшу дтя некоторой цепочки ш нз (2 6 (4))*; следовательно, 6 порождает цепочки, содержащие более одного символа й Поскольку это, как мы знаем, неверно, закяючаем, что 6,— ориведенная грамматика. Теперь надо показать, что 6, — грамматвка предшсствования.
Так как 4 встречается только йа правом конце цепочек, порождаемых в 6 символом 5, легко показатэи что в б не выполгппотся только те сост!гошен!гя, выполняющиеся в б„ которые содержат справа символ 8 (концевой маркер, встречавшийся при описании метода предшсствования). Но Х в 8 †единственн соотношение, имеющее справа К которое может выполняться, поэтому 6, должна быть грамматикой предшествования. Далее, покажем, что в б, пет новых конфликтов А аХУб и  — У(1, где ХЕ((В). Как и в теореме 8.11, свойства простого прсдшссгвовавия искзю!ают эту возможность. Наконец, мы должны доказать, что в Р, нет пары правил А — и и В и, где Л~В, Рассиотрим отдельно три случая.
Случай 1: Допустим, что а=С и правила А СХ и В С)', где Х =во р и у=вой, принадлежат Р. Пусть С=(йд'1, Если 4 — состояние чтения, то Х=.у — р. Как мы видели при доказательстве теоремы 8,11, левая часть правила типа 2 однозначно 173 гл. в, теоеия дктееминиэовлнного газзаев в > ггвммвтики.
погождвющие детсгминнговлпныа языки определяется его правой частью, поэтому вопреки условию А = В. Если д' †состоян записи, обозначим через р единственное состояние чтения в пишущей последовательности для 4' и положим 6(р,э, 2) = (р', 2), где 6 †функц переходов ДМП-автомата, по которому была построена грамматика 6. После того как ДМП-автомат попадает в состояние р', ои пе может выполнять никаких операций, кроме стирания содержимого магазина, потому что если он будет читать входную цепочку влн писать в магазин, то либо он допустит цепочку, содержащую в серсдине символ С, либо Х и Г окажутся бесполезными снмволамв. Существует единственное состояние р", в котором ДМ11-автомат находится после стирания сю>полов, записанпьж в магазин при прохонгденив пишущей последовательности для 4'.
![](https://s.studizba.com/z.php?f=/templates/si/i/noavatar.png&w=100&h=100&t=1"){kind=avatar}
