Теория синтаксического анализа, перевода и компиляции - Том 2 (943929), страница 29
Текст из файла (страница 29)
Полученную грамматику обозначим 6„ = (Х„ Х, Р„ 5). (4) Пусть Х, для всех а нз Х будет новым негерминальным символом. Положим Х= Х,() (Х„)а Е Х) Пусть Р образовано из Р, заменой всех (кроме самых левых) вхождений терминала а на Х„ и добааленисл1 правил Х а, Обозначим 6= (Х, Х, Р, 5). 6 — грамыагнка в нормальной форме Грейбах. гл к теОРия дгтгьминиьонлнного сдзхоьд зл, твоьия ьл языков Теорема 8,6. Каждый Щй).язык порождается ЕЕ(й+1)-грамматикой в норнадьна) форме Грсйбах.
Доказательство. Достаточно показап, что грэмлгатнка 6, построенная алгоритмом 8 3, является ЕЕ(й -1- 1)-грамматикой, сслн 6,— Щй)-грамматика. По лемме 8.4 б„— 1.1.(й, 1)-гоам. матнка. Мы утверждаем, что правые части всех правил в 6, начннаюгся с терминалов. Поскольку б, пе леворекурсивна, зто доказлсаается точно так же, как в алгоритме 2.14. Легко покааать, что все операции плага (4) солраняют ЕЕ(й + 1)-свойство н не изменяют порождаемого грамматикой языка. Ясно также, что 6 в грамматика в нормальной форме Грейбах.
Доказательства этих утверждений оставляем в качестве упражнении. 0 6.4.3. Пробнемв анвиевпентиоети дпя ЕЕ-грвммвтик Теперь мы уже подготовлены к тому, чтобы изложить алгоритм, проверяющий, экннвалентны ли две Щй)-грамматики. Однако иапо ввести одно вспомогательное понятие. Определение. Пусть 6 =-(5, Х, Р, 5) -КС-грамматика.
Для а из ()4 ОХ)* определим мощность' ) цепочки а в 6 (и обозначнч ее ТНо(а)) как длин> кратчайшей цепочки шЕ2', выводиыой из а. В качестве упражнения предлагаем читателю убедиться в том, что ТНо(сф) = ТНо(а) -1- ТНоф) и если а ~ф, то ТНо(а) ( =ТН ф). Определим далее ТН2(а, ю), где аб ()(ОХ)* и юЕХ ь, как длину кратчайшей цепочки хб 2*, для которой а~'„-х и ш.- в Г(КВТь(х). Если такой цепочки х нет, то значснис ТНьо(а, ш) ае определено.
Когда ясно, о чем идет речь, символы й и 6 в обозначениях ТНьо или ТНг булем опускать. Алгоритм, проаерялощий, эквивалентны ли две Щй)-грамматики, основан на следующей лемме. Лемма 8.о. Пусть 6, =(Но Х, Ро 5,) и 67=(Р(„Х, Р,, 5,) — две 1.1 ф)-грамматики в нормальоной форме Грсйбах и Е(6,) =Цб,) Тогда оущсгтвуст лнахая константа р (з7мисящая от б, и 6,), что ссдн 5,=ьо 7ша=лвс их, 5,боои иф=>асму, где а и 6 — нгзаконжннив части цепочек юа и цф, и Г185Т (х]=Г!Гтбул(у), то (ТНо (а) — ТН" (д))( р '). '1 В орнгннаде 871сбнелз.— Прим, лсрм. ') Всртнкьлннымн нрнмымн 1 1 здесь обозначена гбсол~отнэя эеднчннв числа, с не дснш неночкн.
лзб Доказательство. Пусть 1 — большее из чисел ТНо (у) н ТНв (у), где у — правая часть правила из Р, и Р, соответственно. Положим р=-((й+1) и допустим, что вопреки утверждению леммы (8.1.91 ТНг (а) — ТНо*(8) р Покажем, что при таком доп)шепни Цб,) =гьЕ(бь). Обозначим г = Г! Д5Т(х) = Р(65Т(у). Тогда ТНоф, г) ~ (тно ф) —,р. действительно, существует вывод дсэо„гу, и, следовательно, поскольку б, †граммати в нормальной форме Грейбах, для некоторой цепочки 6 найдется вывод 6 ~го7гд„ состоящий не Поясе чем из й плагов. Легко показатть что ТНо(6)(ТНс(6) ! й! так как „в худшем случае" 6 — это цепочка 6, к которой добавлены правые части й правил.
Отсюда заксцочаем, что (8.! 1О) Т На ф, г) ( й 4- ТНо (6) ( ТНоф) 4- р Легко наказать, что ТНо (а, г)':ТНо (а), и потому нз (8.1.9) и (8.1.10) вытекает, что (8 ! 11) ТНо (а, г) ) ТНо ф, г) Обозначим через и кратчайшую цепочку, выводимую из 6; тогда "! Но ф, г) щ(ги). (Тенорка шги принадлежит Цб,), так как 5=огни()~о,шгд=ьй юги. Но а~с,ги неверно, потому что, согласно (8.1.!1), Тйо(а, г) ) (ги). Так как 6,— щй)грамматика, то если в б, есть какой-то левый вывод цепочки юги, оц начинается с вывода 5,~6,7иа.
Таким образом, юги не при. надлежит Цб,) вопреки лб словлгю Е(б,) = Е(6 ). Отсюда получаем, что ТЙо(а) — ТН (6)(р=((й-1-!) Случай ТНоф)— — ТНо (а) ) р рассматривается симметрично. Лемма 8.6. Для ДМП-автомата Р нроблсма, допускает ди Р все цепочки над своим алфавитом, разрешима. Доказательство. По теореме 2.23 дополнение Е(Р) языка Е(Р) является детерминированным языком и, значит, КС-языком. Далее, можно эцлфектггвно построить такую КС.грамматику 6, что Е.(б)=1.(Р).
Для проверки равенства Цб)=.8 можно применить алгоритм 25. Таким образом, можно узнать, доаускает ли Р все цепочки пад своим входным алфавитом. :„3 Наконец, мы готовы к тому, чтобы описать аслгорнтлг проверки двух ЕЕ(й)-грамматик аа эквивалентность.
Теорема 8.6. Для двух Щй)-гром.нигних 6, = (147, Х,, Р„5,) и 6,=(К„Хм Р„5,1 ггроблема,ф(67) =Цб,)7" рллзрелсшми. 757 гл э. теогия детеРминнговинного РхзвоР* а.>. теОРия ьь-языков Д о к аз ах ел ь ст во. Сначала построим по алгоритму 8.3 грамматики 6, и 6; в нормальной форме Грейбах, эквивалентные 0, н О, соответственно (за исключепнелг, возможно, пустой цепочки, которую несложно учесть). Затем построим ДМП-автомат Р, допускающий входную цепочку ш нэ (Х, 0 Хз)* тогда и только тогда, когда (1) ш принадлежит как Х(6>), так н Ц0,), нли (2) ш не принадлежит нн й(6>), ни Х(0,).
Следовательно, Е(6,) =- Х(0,) тогдв и только тогда, когда Х(Р) = =.(Х, 0 Х,)". Для проверки этого условия можно аоспользова>ься леммой 8.8. Таким образом, для завершения доказательства осталось показать, как строится ДМП-автомат Р. (бго магазин состоит Ряс 88. Праха>явление леаазмвчляиих цепочек аа я мй вэ лвух параллельных доро>хек. Р обрабатывает вхолную цепочку, разбирая ее одновременно в соответствии с 0; и 6,.
Разбор проводится сверху вниз. Предположим, что входная цепочка автомата Р имеет вид юх. После выполнения )ш) шагов левого вмвода в 6, н в 0; в его магазвне будет записано годержимое каждого нз магазинов й-предсказывающих анализаторов для 6; и 0„, как показано на рис. 8.6, Из описания алгоритма Б.З известно, что содержимое магазина в каждом случае представляет собой незаконченные '!асти двух текущих левоаыводимых цепочек, а также некоторую дополнительную информацию, записываемую вместе с нетерми- >58 иалами для управления разбором. Можно счвтатть таким образов, что магазин содержит символы грамматик 6; н 0',.
Дополнительная информация добавляется автоматически Заметим, что эти две незаконченные части могут занимать нс одинаковый объем. Однако при Ц0>)р 8(0,) мы можем, исходя из сказанного выше, считать, что разность их мощностей ограничена, а тогда Р может моделировать оба вывода, производя считывание и запись в магазин на фиксированное число ячеек ниже его верхушки.
Так нак 0; и 6; †граммати в нормальной форме Грейбах, Р чередует шаги вывода в 6; н 6;, а затем сдвигает свою входную головку на одну позипию. Если в одном из разборов достигается оп>ибочная конфигурация, то разбор велется в соответствии с оставшсйся грамматикой и продолягается до тех пор, пока не достигается Ошвбогная нлн допускающая конфигурация. Йеобходямо только объяснить, как, предположив, что Ц0>) = Ц6>), поместить в магазин обе незаконченные части так, чтобы они имели приблизительно одинаковую длину.
По лемме 8.8 найдетсп такая константа р, что мощности двух незаконченных частей, возникающих при разборе префикса произвольной вхолной цепочки, различаются не более чем на р. Для каждого символа грамматики мощности ! автомат Р резервирует ! ячеек на соответствующей дорожке своего магазина, помещая этот символ в одну из них. Поскольку 0; и 0;— грамматики в нормальной форме Грейбах, пи в одной из них нет исчезающих символов и в любом случае Г х(. Так как дае цепочки и и 8, показанные на рис.
8.8, различаются по моп!. ности самое большее на р, их представления а магазине автомата Р различаются по длине самое большее па р ячеек. Для завер>пения доказательства примем, что Р отвергает входную цепочку, если две незаконченные части, записанные в ' его магазин, различаются по мощности более чем на р. По лемме 8.8 в юом случае Ц6,)чьЦ0,). Кроме того, если мощности никогда не различаются более чем на р, автомат Р допускает входную цепочку тогда и только тогда, когда он находит разбор входной цепочки как а соответствии с граэшатикой 6;, так и в соответствии с грамматикой 6; или же не находит его ни в 6;, ни в 6;.
Таким Образом, Р допускает все цепочки над своим вхолпым алфавитом тогда н только тогда, когда Х(0>) =ЦГ>,). 8.!.4. Иерархия О.-языивв Покажем, что ЕГ(й)-Языки для каждою й)0 образуют собственное подмножество множества 1.1.(й-)-1)-языков. Как мы увидим, эта ситуация прямо противоположна ситуации с Ей-язь>. ками„где для каждого 1(1-языка можно найти Е)((1)-грамматику. >59 тгогия детеемннигов»нного у»звоу» е.», теОРия»с-языков Рассмотрим последовательность языков Ем ! „ ..., Е, ..., где Е,=(а ю(я) ! и шЕ (Ь, с, Ь д)") В этом разделе мы покажем, что Е является ЕЕ(Ь)-языком и не является Щ!г — 1)-яаыком, и тем самым докажем существование бесконечной последовательности вложенных классов ЕЕ(й)-языков.
Язык Е порождается ЕЕ(й)-грамматикой 5- аТ Т 5А!А А ЬВ)с В Ь» 'д)е Докажем, что каждая ЕЕ(й).грамматика, порождающая язык Е, должна содержать хотя бы одно е-правило Лемма 8.7. Язык Е» яе порождается никакой Щй)-грамма»»»икай беэ е-правил. Доказательство. Допустим противное.
Тогда, вссполь. эовавнгись шагамн (2) — (4) алгоритма 8.3, можно найти такую ЕЕ(й)-грамматику 6=-(Х, (а, Ь, с, д), Р, 5) в нормальной форме Грейбах, что Е(б)=Е». Докажем, что всякая такал грамматика порождает слова, не принадлежащие Е». Рассмотрим таную носледоватегшность цепочек а„! = 1, 2... „ что 5=ь)ааг=ь)-'а»»»- б для неноторой цепочки б. Так как 6 — ЕЕ(Ь).гран»гатнка в нор. малыюй форме Гревбах, то а, для каждого» определяется однозначно.
В свмом деле, если это не так, положим и,— аг Тогда легко показатсч что а'"»Ь!"»ЕЕ(6), а этого не может бйть при (ча). Значит, можно найти такое», что )аг(»2й — 1. Выберем такое значение 1, что и, =-.!)Ву для некоторых )> и 7 из Х* и ВЕХ, причем )д) и )7( равны по меныпей мере й — 1. Поскольку б — Е)(Ь)-грамматика, вывод слова а'" 'Ь'"-' имеет вид 5~)а$В7~)а»- Ьт»- Так как 6 †граммати в нормальной форме Грейбах и )д)жй — 1, то д~'а» 'Ы, В~'Ь' н 7~'Ь"' для некоторых ) увб, !) 1 и тивй — 1, причем»+й — 1=-! Р1+т, Если рассмотреть вывод слова а' » 'с'"» ', можно также заключить, что Вж»'с" для некоторого я ~ !.
Наконец, рассмотрев вывод слова а' " 'Ы+"» *дЬ»Е находим, что 5~) а дду=~)аг»-»Ь»ВТ=»; а!»»-»Ы "Тж»)а'"-»Ь' '+'-'дЬ Существование последнего вывода вытекает из того, что у слов а' »»Ы»'+»-'йй" и а' » 'Ь'+» ' совпадают (»-,'-й — 1) + + (!+!л-й — !) символов Поэтому у=ь" Ь» 'АЬ . Объединяя зти частичные выводы, получаем вывод 5=»!а(!Ву~)а"» 'ЬГВ7~;а' " 'Ьгс"ТЫ»,'ит» 'Ыс»Ь»-'йй» Но его результат не принадлежит Е, так как он содержит под. цепочку вида сЬ» 'й. (Перед й должно стоять й символов Ь.) Итак, язык Е, не порождается никакой Щйрграь»мазиной без е-правил.
![](https://s.studizba.com/z.php?f=/templates/si/i/noavatar.png&w=100&h=100&t=1"){kind=avatar}
