Теория синтаксического анализа, перевода и компиляции - Том 2 (943929), страница 33
Текст из файла (страница 33)
Поэтому опять Х = У, н мы заключаем, что А =В. Случай 2: Предположим, что а=С н правила А С н В СХ, где Х=в'г, принадлежат Р. Если С=[44'), то 4' ссстоинне стирания, так как А С- правило типа 3. Но поскольку В СХ правило типа 2 нли 4, 4' должно быть состоянием записи илн чтения. Мы пришли к противоречию. Слу>ай 3: Если и=С и правила А СХ и  — С принадлежат Р, то возникает ситуация, симметричная той, что рассматривалась в случае 2.
Следовательно, 6, — простая ССП-грамматика. г'т 8.2.3. ОПК-грамматики, 'ьй-грамматики н детерминированные языки Покажем, что каноническая грамматика является таки<с (1, О)- ОПК-грамматикой, а значит, согласно теореме б.!8, п Е(1 (О)- грамматикой. Интуитивно причина того, что для рэабора канонической грамматики при помощи атгоритв>а типа „перенос— свертка" не требуетсп заглядывать вперед, состоит в том, что каждый терминал и каждый нетерминал [44'), где 4' состояние стирания, определя>от правый конец осноны. Ладим формальное доказательство, основанное па юой идее. Теорема 8.14.
Ко>ядоя каноническая граммажика яч>ягтгя (1, 0).ОПК-грамматикой. Доказательство. Пусть 6=-()5, Е, Р, 5) — каноннческэя грамматика. Предположим, что 0 пе является (1, О)-ОПК-грамматикой. Тогда в пополненной грамматике 6'=(К В(5'), Е, РВ(5' 5), 5') можно найти выводы 35'=ь,'иХАш=э„аХбш и 85'~,"уух=>,убх, где убх можно записать в виде и'Х(1у, причем )х)()у), но а'ХАу.-~уВх. Заметим, что всякая правовыводимая в 6 цепочка имеет открытую часть, состоящую толька из !74 нетерминалов, т. е. Х Е М, а и, а' и у принадлежат Мв. В зависимости от типа правила Л 8 рассмотрим четыре случая. Случай 1> Допустим, что 8 =и, где а Е 2.
Так как )х) ..)у), то должно быть х — у и либо б=-а, либо 6 =Ха. Если 6 — а, то ХЕ((А) 61(В), а это может быть, тольки сели Л =-В, поскольку 6 — простая ССП.грамматика. Если 6=-Ха, то в Р есть прави.>а Л а и В Ха, где ХЕ((А); это опять противоречит тому, что 6 †прост ССП.трав>матика. Случаи' 2> Допустим, что 8=Си, >де СЕ зЕ Тогда, поскольку )х[ ( )у), должно быть х=у н либо 6 а, либо 6.= Са. Если 6 = — Са, то А = В, так как правила типа 2 обратимы (теорема 8.11). Отсюда вытекает, чтои'ХАу — уух вопреки предположению.
Если 6 =а, ю из А Са следует С А.а. Так как символ С должен быть последним символом цепочки у, то С а В вли С '. В и, следовательно, С ч а, а это противоречит тому, что 6 †грамматика прсдшествования. Случай 3> Допустим, что 6 =.- С, где С Е вС Здесь четыре возмо>кности: 6 = С, 6 = а, 6 =- Са длп некоторого а Е Е, 6 †- ХС.
Если 6 = С, то Х принадлежит !(А) 0 1 (В), а это протнворе >ит тому, что 6 -- простая ССП-грамматика. Пусть С = )44 ). Тогда 4' †.состояние стирания. Если 6 =-а, то С- последний символ цепочки у. Поскольку В в праэоныводнмой цепочке с~опт справа от С, 4' должно быть состоянием записи. Итак, пришли к про. тиаоречию. Если 6.—..Са, то 4' лолжно быть сос>оннием чтения, а это нетак. Если 6=ХС, то, поскольку ХЕ((А), наличие правил А С н В ХС противоречит тому, что 6 — простая ССП- граммаж>ка.
Случаи 4' Лопустим, что 8 = СР для С п 0 из 6). То>да 6 есть либо Р, либо а, либ>о Ра для некоторого аЕ2, либо СР. Так как правила типа 4 обратимы (доказательство теоремы 8. !1), то при 6 —.-СР имеем Л =- В и а'ХАу=уВх. Пусть 0=[44'). Из вида правила А СР следует, что 4' †состоян стирания.
Если 6---. Ра, то 4' должно быль состонпнем чтения, и >ютому этот случай исключаегся. Если б:- а, то, как и в случае 3, можно показать, что 4' — состояние записи. Если 6 = О, то последним символам цепочки у является С, а значит, С Е 1(В). Наличие правил А СР и  — Р п(ютиворечит тому, что 6 — простая ССП-грамматика. Е) Следствие 1. Всякий дгтерминироганный юых Е, обладающий арефиксным свойством, имеет (1, 0).ОП К-грамматику.
До к в з а тельство. Если гц Е, результат очевиден. Если г ЕЕ, то Е=-[е). Для этого языка легко найю! (1, О)-ОПК-грамматику. Е) Следствие 2. Если Е =. Е* -детермонироеаннмй язвы и 4 ле принадлежит Е, то Ей имеет (1, 0).ОПК.граммапшку. ьз >71 гл э тсогня дгтегминиговкнного гкэзогк э >. ггкммктики, погождкющиг детьгмиииговкннь>а Теперь мы можем доказать теорему о произвольных детерми нироваиных языках, представляющую собой по суиысгву пере фразировку следствия 2. Теорема 8.!Г>.
Всякий детермииираеииный яэькк порождается некоторой (1, 1)-ОНК-граиматикои. До к аз а тел ь от в о. Пусть 6 — каноническая грамматика. С помощью алгоритма 8.4 построим по 6 грамматику 6,. Надо показать, что б,— это (1,!)-ОПК-граыматика. Наг]итивно проблема состоит в том, чтобы распознать, когда для свертки нужно применить правило А В грачматини б„ не являющееся правилом грамматики 6. Заглядывание на один символ вперед позвогшет выполнить такую свертку только тогда,когда аваннепочка состоит только из концевого маркера 5. Форчалщ>ое доказательство оставляем в качестве упражнения.
Теорема 8.!8. (1) Всякий детерминироганиый язык, обладаю' щий пргфихсиькн свойством, имеет Щй)-грамма>иик]>. (2) Всякий детерминироепииьы хэнк имеет Ей(1]-грамматикуь Доказательство. Согласно теореме 5.18, ка кдая (т, й)- ОПК-грамматика является 1.(((й).грамматикой. Результат вытекает из теоремы 5.18 и следствия 1 теоремы 8.!4.
8.2.4, Грамматики расширенного предшеетвавання и детерминированные язынн К касгояикему моменту мы установили, что если !.— детерминированный КС-изык, то (1) существует такой ДМП-автомат Р в нормальной форме, что Е(Р)=Ей, (2) существует такая простая грамматика со счешанной стратегией предшсствовапия б, что Е (6) =Š— (ег, (3) существует такая (1, 1).ОПК-грамматика 6, что Е (6) —.— Е.
Покажем теперь, что существует также обратимая грамматика (2, 1)-предшествования 6, для которон Е(6)=-Š— (е). Нам уже известно, что каноническая грамматика является грамматикой (1, 1)-предшествования, хотя она не обязательно обратима. Для того чтобы получить нужный результат, выполним некоторые преобразования канани~вской грамматики, превращающие ее в обратимую грамматику (2, 1)-предшествовании. Зги преобразования выглядят следующим образом: (1) Каждый нетерминал пополняется так, чтобы ои „помнил" символ, стоящий слева от него в правом выводе.
(2) Цепаые правила исключаются в результате замены правил вида А. В и В и,)...(а правилами А а,]...]и . ла (3) Нетерминалы „расщепляются" так, чтобы каждый нетермннал либо имел только одно правило вида А а, либо не имел правил такого вида. (4) Наконец, нетеринналы „растягиваются" так, чтобы устранить необратимость, возникшую в результате появления правил вида А а. Другими словами, множество правил А, а, Л, а заменяется множеством Л, А„ ..., А„, — Л, и А, а. Каждая иэ первых трех операций сохраняет свойство грамматики быть грамматикой (1,!)-предшествовапия. Четвертая может в худшем случае сделать ее гракгматикой (2, 1)-предшествования, но ова необходима для того, чтобы обеспечить обратимость.
Дадим законченный алгоритм. Алгоритм 85. Превращение канонической граммати ки в обратимую г р ам мати ку (2, 1) п редшествования. Вход. Каноническая грамматика 6>=.(В, 2, Р, 5), Выход. Эквивалентная обратимая грамматика (2, 1).предше- стзозаияя 6,=(В„2, Р„5,). Метод. (1) Построить по 6 граиматику бе=(Н„2, Р„5,]: (а) пусть В; — множество символов Лх, где А 5 Н и Х 5 К 6 (5)1 (б) положим 5> = 55, (в) если А В, А ВС, А Ва и А а — правила нз Р, то в Р; включаются соответственно правила А» — В», Ах ВхСа Ах Вха н Ах а дла всех Хйдб(8]; (г) В> и Р,— зто соответственно Н; и Р; после удалепвя бесполезных символов в правил.
(2) Построить по 6, грамиатику 6,=-(5„2, Р„5,); (а) убрать из Р, все цепные правила, выполняя следующую операцию до тех пор, пока грамматика не перестанет изменяться: если А  — рассматриваемое правило иэ Ро добавить правила А и длн всех прзвил В и, принадлежащих Р„ и выбросить правило А В; (б) обозначим через Н„и Р, полученные в резулыэте множества полезных нетерминзлов и правил. (3) Построить по б, грамматику 6„= — (Вм 2, Р„5г): (а) пусть К; — множество В> вместе со всеми символами Л", такими, что правило Л а принадлежит Рб (б] для каждого А' из Н.,' включить о Р, 'правило А" а; (в) если А5Нм А айР> и а не явлнется одиночным терминальным символом, добавить к Р; правило Л а гл гл с туоуия дктеюснииуов»нного улзвоул эх.
гу»мм»тики, поуождлющиэ дктуумнниуов»нных языки для каждого а' из Ь '(а), где й — гомоморфизм, определенный равенствами Ь(а) =-а для всех об 2 Ь(В')=В для всех В'бв); Ь(В) =-В для всех В С(4, (г) обозначим через Вх и Р, полезные подмножества множеств В; и Р', соответственно, (4) Построить по 6, грамматику 6,=-(((с, 2, Р„5,): (а) 14, —.
)х, и 5, =-56 (б) Р,— зто множество Р„измененное такс сели Аг а, А, а, ..., Л, а — все правила из Р, с праной частью а, взятые в некотором порядке, и й ) 1, то в Р, они заменяются на А, А„А, А„..., А, Л, 4„-а. Е Пример 8,4. Пусть 6 — грамматика с правилами 5 — Ав А а)Ь В АС С Р Р а Тогда 6, определяется правилами 55 — АЬВ» Лб-а)Ь Вл А»С» Ал а)Ь Сл Рл Р, а На шаге (2) алгоритма 8.3 правило Сл Рл заыеняется на Сл ° а. Символ Рю таким образом, бесполезен: Иа шаге (3) добавляются петерминалы Аб, Лб, Ал, Ал и Сл. Тогда Лб, Лл и Сл становятся бесполезными, и в результате правила грамматики Сл принимают внд 5 Л".В, [ А" В„ А;.-а Лб Ь Вл А»С» ) Ал»С» Ал а А"„Ь Сс а 4 та На шаге (4) растягиваются Аф Ал н Сл, а также А~5 и Алл.
Окончательно правила грамматики С, выглядят так: 58 - Л' Вл~ ЛЬВ» В,! А»С»)А»С» Лт Ал Л;-С; С» а Ал Ал Лл Ь С) Покажем, что 6,— обратимая грамматика (2, !).предшество- вания, доказав предварительно ряд лемы. Лемма 8.!О. В алгоритме 8.3 (Ц Е(6,)=С(6), (2) Сз — граммилш»а (1, ! )-усрсдсссестэооансзя, (3) если при»ила А а и В а лри»одлсжат Р, и ы нэ лэллстся одино»ныл терминальным спмэоло, то А =В.
До к азатэл ьство. Утверждение (!) доказывается простой ипдукцией по длинЕ выводов. Для доказательства утверждения (2) заметим, что если Х и У связаны в 6, одним из отношений ст ' или вл, то Х' и 1", представляя»дйе собой Х и )' с от- брошенными индексами (если они были), связаны тем же отно- шением в 6. Таким образам, 6,— грамматика (1, 1)-предшсство- взнкя, поскольку такова грамматика 6. Чтобы доиазать (3), отметнм, что правила типов 2 и 4 обра- тимы в 6.
Иными словами, если А СХ и В СХ принадле- жат Р, то А = В. Отсюда, таким образом, следует, что сели Лу СуХс н Ву СуХс принадлежа г Р„то Ау. = Ву. Анало- гично, если Х вЂ” терминал, а А,.--.С Х и Ву С>Х принадле- жат Р„то Ау=Ву. Ь!ы должны рассмотреть правила в Р„получаемые из правил типа 3. Дсопустгсм, что у нас есть правила Ах - Сх и В» С». Так как бесполезные правила из 6, исключены, в С должны быть правила с такими правыми частями ХР и ХЕ, что 0~3 Ли и Е=лгвб для некоторых сс и 8. Пусть Х= [44'[, А =[рр'), В=[туг] и С=-[зз'[.
![](https://s.studizba.com/z.php?f=/templates/si/i/noavatar.png&w=100&h=100&t=1"){kind=avatar}
