Теория синтаксического анализа, перевода и компиляции - Том 2 (943929), страница 36
Текст из файла (страница 36)
ьз Теорема 8.20. Клиссьг 1 .языков и языков просшого яргдшесшяоаииил несриянилы. Доказательство. 5!Бык 6., нз теоремы 8.19 представляет собой СЕ(1).язык, не являющийся языком простого предшествования. Естествепнан грамматика для 67 такова; 8 иА(ЬВ А - ОА((01 В-ОРА((011 Легко видеть, что это Е!,(2)-грамматика. Леван факторизация превращает ее в 1.1.(1).грамматику. Язык Е,=(О а!" (п ) 1) 0(ОЬ2" (гг) 1) не является Ы..язы. кол1 (см.
упр, 8.3.2]. 1.,— это язык простого предшествования с грамматикой простого прсдшестаования В А)В А — ОА1(и В 082(Ь гат ГЛ З ТСОРИЯ ДГТЕРМНННРОЗХННОГО РХЗВОРХ г 3. теОРия языков пРОстОГО пРедшссгвОВхния 8.3.3. Патин операторного предшвстваванни Исс,яедуем класс языков, порождаемых грамматиками операторного предшествозапия. Мы покажем, что хотя существуют неоднозначные грамматнки операторного предшествовання (простым примером такой грамматики служит грамматика 5 — А(В, А о,  — а), нзыки операторного предшествовання образуют собственное полмножество множштва языков простого предшествозания. Начпем с того, что покажем, что каждый язык операторного предшествоваиня порождается обратимои операторной грамматикой без цепных правил.
Лемма 8.13. Всякая (нг облет!слало обратимал) гра,клотика операторного пргдшеслмогаяия зкзиголенгпна грамматике операторного пргдшестгогиния без цепных привил. Доказательство. Легко видеть, что алгоритм 2.!1, устрзияющий цепные правила, сохраняет отношения операторного предшествованпя между терминалами. ) Дадим теперь алгоритм, преврашакнций произвольную КС- грамматику без цепных правил в Обратимую грамматику без цепных правил. Алгоритм 8 6.
Превращение КС грамматики, не с одержашей цепных правил, в эквивалентную обратимую грамматику. Вход. КС-грамматика 6=.(Х, 2, Р, 5) без цепных правил. Выход. Эквивалентная обратимая грамматика 6, = (Кн т, Р„5,]. Метод. (1) Нетерминаламя новой грамматики будут пецустые подмножества множества ЬЕ Формальтго положим Ы;=(М(М=В' 3(~О)6(5,).
(2) Для всех ш„тон ..,, ш из ХЯ и М„..., ГИЯ нз Ы; вкл~очить в Р; правила М н,М,ш,... Мять, где М = (А ) в Р существует правило А ш„Втшт...дяшя, В,6МГ для 1<! Й), Мть сд. Заметим, что таким способом поРождаетсЯ только ко. вечное число правил. [3) Для всех М ~:К, содержзптнх 5, включить в Р; правила 5, М. (4) Устранить все бесполезные ветерминалы и правила.
Полученные полезные подмножества множеств Ы; и Р; обсаначить КГ н Р, соответственно. Ц Пример 8.5. Рассмотрим грамматику 5- - и)аАЬ5 А-- а(а5ЬА твв На шаге (2) включаем в Р; правила (5) а (А) Ь (5) ( а (5, А) Ь (5) (а (А) Ь (5, А) !А) а(5)Ь(А)(а(5, А)Ь(А)(а(5)Ь(5,А) (5,А) а(а(5, А) Ь(5, А) На шаге (3) добавлием 5 -(5)((5 А) На шаге (4) обнаруживаем, что все (5)- и (А)-правила бесполезны, и получаем, таким образом, грамматику 5, (5, А) (5, А) а)а(5, А) Ь(5, А) Лемма 8.!4. Граггиотика 6О построгияал по 6 о слгоригцкг 8.6, обратима, если 6 не содержит цгпшхх правил, и явлнстпся грамматикой операторного и редшегтзояания, гслп 6 — граммшника операторного лра]шгслмогания.
Кроме того, Е(6,) =6(6). Доказательство. Обратимость гарантируется шагам (2], а поскольку 6 пе содержит цепных правил, на лаге (3) не могут появитьси необратимые правые части. Доказтельсгво того, что алгоритм 8.6 сохраняет отношения операторного прелшествования межпу терминалами, очевидно; мы оставляем его в качестве упражнении. Наконец, легко проверить иидукцией по длине вывода, что если А 6 М, то А ~3 м тогда и только тогда. когда М -Гд ш. Итак, язык операторного предшествоваиия порождается грамматикои в следуюшей нормальной форме, Теорема 8.2!.
Если Š— язык операторного пргдшгстгогиния, то )ы=Е(6) для некоторой грамматики операторного прся]шгслг- зогаяил 6=-(К, 2, Р, 5), яшкой, что (!] 6 — обратилач гронлатика, (2] 5 нг встречается г правых частях правил, (3] цгггныг прогала обязательно имеют 5 в левой насти. Доказательство. Достаточно применить алгоритмы 2.!! и 8.6 к произвольной грамматике операторного предшестиоаания. [) П ревратим теперь грамматику операторного предшествонания 6 в нормальной форме, описанной в теореме 8.21, в обратимую грамматику слабого предшсствования 6„ для которой Е(6Г)= =ЕЕ(6], где à †лев концевой маркер.
Потом построим Обратимую грамматик у слабого предшествовання 6Н для коюрой Е(6т] —.- ТВР гл и теояия детегмнниговлиного яхзвогх г г, теОРия языков пгостого пгедшгсгэоехния — Ц6). Тем самым мы покаткем, что множество языков операторного предшествования является подмножеством множества языков простого предшествовапия. Алгоритм 8 7. Превращение грамматики о не рата р- ного предшествоввния в грамматику слабого предшествоиания.
Вход. Обратимая грамматика операторного предшествовання 6 (Ы, 2, Р, 5), удовлтворяющая условиям теорсл!ы 8.21. Выход Обратимая грамматика слабого предшесгвоиання 6,= = (Ко Е () (г], Ро 5,), длЯ кето(юй Ц6,)=И46), гЛе УЦ2. Мгпюд. (1) Пусть К; состоит из всех таких символов [ХА], что ХЕЕО(Ф) и ЛЕД.
(2) Положим 5, — [15] (3) зададим гомоморфизм ь из ы;()2()(к) в м()е равенст- вами (а) Ь(а) = а лля а Е 2 ()(у], [б) Ы[ А])=.А Й '(и) определено только для цепочек аЕ ((т' 62)г, начинающих- ся символом из 2() (р) и не имеющих рядом стоящих кетерми- иалов. Кроме того, если значение Ь '(и) определено, то оно един- ственно.
Другими словами, Ь ' обьединяст нетерминал со стоя. щвм слева от него терминалом. Пусть Р; состоит из всех таких прав?т [аА] Ь '(аа), что А аЕР и аЕЕО(Ф]. (4) Полечныс подмножества множеств 1(; и Р; обозначим 1(, и Р, соответственно. Е) Пример 8.8. Пусть 6 определяется правилами 5 А А аАЬАг(аЛй]а Образуем только полезные подмиожссгва множеств Н) н Р( из алгоритма 8.7. Начнем с нетермннала [г5] Ему отвечает пра- вило [Е5] [гА] Пряниками лля [КЛ] будут [КЛ] б[аА][ЬА)с, [(А]- р[аА]й и [(А] (А. Правила для [аА) и [ЬА] стро- ятся аналогично.
Таням образом, правиламн грамматики 6, будут [15]- [ел] [рЛ) р[аА][ЬЛ]г(г[аА]й(уа [аА] а[аА][ЬА]г(а[иА)й(аи [ЬА] — Ь[аА][ЬА)с[Ь[аА)й(Ьа 0 Лемма 8.13. Грал!.каинска 6, из алгоритма 8.7 лггягтгл об. ратимой граммапшлои слабого пргдшггтеогалил и Ц6,) =-ФЦ6). Доказательство. Обратимость доказать легко, н мы ие дулен этого делать. Чтобы показать, что 6,— грамматика сла- бого предшествовання, надо установить, гто отношения ст п в 6, не пересекаются с уг'). Зададим гомоморфизм й равенст- вами (П й(а) =а для всех аЕ 2, (2) й(б) = Щ (3) 8([аА)]=-а. Достаточно показать, что (1) если Ха[У в 6о то й(Х) сТд(У) или й(Х) — 'й(У) в 6, (2) если Х ' У в 6„то й(Х)ц й(У) или й(Х) — 'Ей(?') в 6, (3) если Х ТгУ в 6„то а(Х) Тгй(1') в 6. Сгулий 1: Пусть Х ел ?' в 6„где ХФб и Хчь 5.
Тогда в Р, есть правило с такой правой частью, скажем аХ[аА]д, что [аА)=:хг, Уу для некоторой цепочки у. Если а чье, легко пока- зать, что в Р есть правило с правой частью, содержа?цей я ка- честве надцепочки Ь(Х[аА])'), и значит, й(Х) ' и в 6. Но из вида правил в Р, следует, что д(У)=а. Таким образоч, й(Х) ° 8(У). Если сг= — г и Х ЕЕ, то левая часть правила с правой частью аХ[аА]8 имеет вид [ХВ) для некоторого ВЕЫ. В этом случае в Р должно быть правило, правая часть которого содержит в качестве надцепочки ХВ. Более того, В аЛЬ(8) — правило из Р.
Следовательно, Х се а в 6. Так как в этом случае 8(Х) = Х, мы заключаем, что й(Х)(й(У). Если а — --г и Х=[ЬВ) для некоторых 8 ЕЕ и В Ей?, обозначим левую часть, соответствую- щую правой части аХ[аА]б, черев [ЬС). Тогда в Р есть пра- вило с правой частью, содержащей в качестве подцепочка ЬС„ и С вЂ” ВаАЬ(8) принадлежит Р. Поэтому ЬсТа в 6 и, зиа!ит, й(Х)гдд(У). Случай а=г и Х=[(В] для некоторого ВЕН (а также Х дй или Х.==й) .легко анализируется, Случай 2: Случай Х вЂ ' 1' рассматривается аналогично случаю 1. Случай 3; Х э У.
Предположим, что У~3. Тогда в Р, есть правило с такой правой частью, скажем а[аА]73, чтп [аЛ) ~г, ТХ и 7.~г, Уб длн некоторых у и б. Внд правил в Р, таков, что либо 2=:У и оба принадлежат 20 (3), либо 7.=[иВ) п У=[аС] или У=а для некоторых В и С нз Х В любом слу- чае й(7) =й(У).
Б Р должно быть правило с правой частью, содержащей надцепочку Ад(2), поскольку а[аА]78 служит правой частью В плесь н лягте символы гю и э, ебегягюют егмешеияя еэергтер. нога врглшгстееегвгя е 0 и лтялшсяяя прглшестэлвгяяя Вирта — Вебера в аг. ') Э вЂ” гоиеяорфигн„ опрея леячмй в глгергтяе З.т. !э! 7 л,л*е,д,л'л аа,т.а 1ез тш гл. в. тяогия днтгрминипоаднного пдзьорд некоторого правила из Рм Так как 6 не содержит лепных праепл, за исключеапем начального, уте г, и значит, в выводе [аА)=эа,уХ л(Х) выеодится не из а, а из А. Поэтому д(Х) ) л(2) и а(Х) я)д(г'] н 6. Поучай у.—.б не вызывает аатроднений. Для завершения доказатег!ьстаэ того, что 6, — грамлгатнка слабого прешцестпоаааия, нужно показать, что есчи правила А аХО и  — й принадлежат Рм то не выполняется нн одна из соотношений Х сТВ н Х ' В.
Положим В =[аС1 и временно допустим, что СФВ. Тогда, поскольку 6 не содержит цепных правил, у ко!орых а левай части стоит сил!зол, отличный от 5, ыожно УтвеРждать, что й=-)гб' длн некотоРой цепочки 6'тье, где Ь(1')=и. Так как 6'чьг, то Ьф') содержит хотя бы один терминал. Пусть Ь вЂ” самый левый из этих терминалов.
Тогда, поскольку а может встретиться в праэовыводимой н 6 цепочке слева от С, можно считать, что асей е 6. Но так как аХ6 служит правой частью некоторого правила нз Р„то Ь (6) — надцепочка правой части некоторого правила из Р, и значит, а — Ь н 6. Тем самым возможность С~В исключается. Если С вЂ” 5, то по теореме 8.21(2) должно быть а =-1. Но в этом случае, поскольку аХΠ— правая часть некоторого правала из Р„ г должно встретиться в правой части некоторого правила из Р, что по на!нему допушению нееерно. Отсюда заключаем, что 6,— грамматика слабого предшестао. ваниЯ.
Доказательство Равенства С (6т) =ГЦ6) очевидно, и мы его опускаем. Е) Теорема 8.22. Всякий язык операторного лргдилествояанмя явдяетсл языком простого предтгспгвованат Доказательство. Согласно теореме 8 21 и лемме 8.16, если Е = В' †яз операторного предп!естеоваиия, то ге †обратимый язык слабого предшестэования, рай 2, Легко обобщить алгоритм 8А так, чтобы устранить из грамматики языка ф., построенной алгоритмом 8.7, левый конпеяой маркер. (Вид правил э алгоритме 8.7 гарантирует, что полученная грамматика буд т приведенной н обратимой.) Детали доказптсльстп оставляем читателю в качестве упражнения.
![](https://s.studizba.com/z.php?f=/templates/si/i/noavatar.png&w=100&h=100&t=1"){kind=avatar}
