Теория синтаксического анализа, перевода и компиляции - Том 1 (943928), страница 97
Текст из файла (страница 97)
Е. Если же устранить из 6 правило Р а(Е), сделав подстановку вместо Е, как в лемме 2.14, то получится эквивалентная грамматика 6 с правилами Так как Е больше ие встречается слева от ), то в этой грамматике уже нет Е:). Легко проверить, что 6' — грамматика слабого предшествования. й' Небольшое обобщение этих приемов позволит преобразовагь каждую обратимую грамматику слабого предшествования в эквивалентную грамматику простого предшествования. Следовательно, по своей порождающей способности обратимые грамматики слабого предшествования не превосходят грамматики простого пред- шествования, хотя, как мы видели на примере 5.37„ среди нкх есть такие, которые не являются грамматиками простого пред- шествования. Теорема 5.19, Язык определяется обратимой грамлиипикой слабого предшествования тогда и только тогда, когда он является языком простого предшествовиния, Д о к а з а т е л ь с т в о.
Достаточность. Пусть б = (Х, г., Р, В)— грамматика простого предшествования. Очевидно, что условие (1) определения грамматики слабого преснпествования удовлетзо. ряется. Допустим, что условие (2) нарушено, т. е. в Р есть такие правила А — аХ)'(1 и  — )'5,что либо Х(В, либо Х В. Тогда по лемме 5.3 Х(У.
Но Х У из-за правила А аХ1'р. Такая ситуация невозможна, поскольку 6 — грамматика пред- шествования. Необходимость. Пусть 6=.. (М, г., Р, В) — обратимая грамматика слабого предшествования. Построим грамматику просто~о предшествования б'=-(М', м, Р', В), для которой Е(6')=Е(б). (!) Пусть )х' — это )з плюс новые символы вида [а], где це. почка а ~ е такова, что в Р есть правило вида Л вЂ” ра.
(2) Пусть Р' состоит из правил (а) [Х] — Х для каждого [Х] Е И', для которого Х Е Х () Е (б) [Ха] — Х[а] для каждого [Ха]ЕХ', для которого ХЕо(()г' и аде, (а) А — [а~ для каждого А — а из Р. Покажем, что отношения (, ° и ) для грамматики 6' попарно не пересекаются. Концевой маркер не может вызвать конфликта, поэтому рассмотрим Х и )' из г)'()г.. Заметим, что (1) если Х(1', то ХЕ 7) 1) Х; (2) если Х " г', то ХЕ)х)04. и УЕВ)' — г), так как только пункт (2б) построения грамматики 6' дает правила, у которых правая часть содержит больше одного символа; (3) если Х)у', то Х Е )х)'0 В и КЕ г..
Докажем, что пересечение каждой пары отношений пусто. Нервая пари: В)=Я. Если Х У, то у'Ер)' — 1М. Если Х.>У, то УЕХ. Ясно, что '.П) Впорая пара: (В) — 14). Допустим, то Х(у н Х)у. Тогда Х 511 0 Т и УЕг.. Так как Х(У в грамматике б', то в Р' есть правило вида [Ха,] —. Х[а1], причем [а,]=ось 1'а, для некоторой цепочки а, Е()~'() В)'. Но цепочка Ха, должна быть суффиксом некоторого правила А — а,Ха, из Р.
Тогда а,=Чьим.,' для некоторой цепочки а,'Е (М 11 В)'. Таким образом, для 6 имеем Х А У или Х ( 1'. Рассмотрим теперь Х)У для грамматики б'. В Р' должно быть такое правило [В(),] — В[(),], что В=;>в'р,Х и ф,]=хьв Щ для некоторых (), Е( в () Х)" и р, Е(йР ()л)'. В грамматике б цепочка Вй, является суффиксом некоторого правила С вЂ” уВ()г из Р. Кроме того, В~ф,Х и (),=4ьоур; для некоторой цепочки ();Е(~м04')*. Таким образом, Х)У для грамматики 6.
Мы показали, что если Х(У' и Х) У' для 6', то для б либо Х(У и Х >У, либо Х ' У и Хз)У. В любом случае получается противоречие с предположением о том, что б — грамматика слабого предшествонания. Таким образом, <' 1) ) = йу для грамматики 6'. Третья пара: <" () ° == ьо. Предположим, что Х( [У'а] и Х ' [)'сс] для некоторых ХЕМОМ и [Уа]Ег)' — г).
Тогда в Р' есть такие правила [ХАр] — Х[АЯ и  — [1'а], что [Ар]~о Ву~:",>в,[у'а]ур для некоторых уЕ(Х'112'.)* и Л, ВЕ)в. Отсюда следует, что в Р есть такие правила С вЂ” 6ХАр н  — 1'сс, что А =ой Ву' для некоторой цепочки у' Е (г) 0 л)'. Таким образом, для 6 получается Х ( В или Х ' В. (Последнее может произойти тогда и только тогда, когда В =- А.) Теперь рассмотрим Х,' [Уа]. В Р' есть правило [ХУа]— Х[1'а], и потому в Р есть правило 0 — еХУа. Следовательно, если Х ( [Уа] н Х [У'а] для грамматики 6', то в Р найдутся два правила вида  — )'а н Е7 — еХУа и для б будет Х -'В или Х В, что нарушает условие (2) определения грамматики слабого предшествования. УПРАЖНЕНИЯ (г УПРАЖНЕНИЯ 477 , 476 ГЛ.
3. ОДНОПРОХОДНЫЙ СИ)!ТАКСИЧЕСКНЙ АНАЛИЗ БЕЗ ВОЗВРАТОВ Вид правил множества Р' позволяет сразу заключить, что грамматика 6' обратима, если обратима 6. Следовательно, Е(6')— язык простого пред1пествования. Легко доказать, что Е (6') = Е (6). Мы оставляем это в качестве упражнения. ~ Следствие. Каждая обратимая грамматика слабого предигествования однозначна.
Д о к а з а т е л ь с т в о. Если бы у какой-нибудь цепочки оказалось два разных правых вывода в грамматике 6 теоремы 5.19, то можно было бы построить разные правые выводы той же цепочки в грамматике 6'. Построение, приведенное в доказательстветеоремы 5.19, больше подходит для целей теории, чем в качестве практического инструмента. На практике можно применить гораздо менее изнурительный подход. Мы дадим простой алгоритм преобразования обратимой грамматики слабого предшествования в эквивалентную грамматику простого предшествования. В качестве упражнения предлагаем доказать, что этот алгоритм работает корректно. Алгоритм 5,15. Переход от обратимого слабого предшествования к простому предшествованию, Вход. Обратимая грамматика слабого предшествования 6 = (1т), й, Р, В). Выход. Грамматика простого нредшествования 6', для которой Е(6') =1 (6). Метод. (1) Допустим, что в )т'(!г.
нашлись такие Х и У, что Х ' У и Хсе 1' для грамматики 6. Устраним из Р каждое правило вида А — аХУ() и заменим его на А — аХ[Ур], где [Ур] — новый нетермииал. (2) Для каждого символа [Ур], введенного на шаге (!), заменим правило Вида  — У|т на В [У)1] и добавим |Уй] У(). (3) 11овторим шаг (!) столько раз, сколько он окажется применимым.
Если он больше неприменим, остановимся. Результатом будет грамматика 6'. г] Пример 5.40. Пусть 6 — грамматика из примера 5.37, С помощью алгоритма 5.15 получаем грамматику 6' с правилами Е. Е+[Т]|-, [ТШТ] Т вЂ” ТеР|РР— ([Е)] | а |Т|-Т [Е)]-Е) Шаг (1) применяется к парам Х=-(, У=Е и Х=+, У=Т. Отношения предшествования для грамматики 6' приведены на рис. 5.15. Е Т и (Т] [Е)] а ! ) э * ф Рис. 6.16. Матрииа простого предшествоваяия. 5.3.1.
Какие из следующих грамматик являются грамьгатнкамн простого предшествования? (.) 6„ (б) В если Е, то Ь' иначе Ь'|а Е Е нли Ь!Ь (в) В- АВ|А А — (Ь') |() (г) В Ь'А |А (В)|() 5.3.2, Какие из грамматик упр. 5.3.1 являются грамматиками слабого предшествования? 5.3.3. Какие из грамматик упр. 5.3.1 являются грамматикамн (2,1)-предшествоваиия? 5.3.4. Приведите примеры грамматик предшествования, для которых гл. к однопгоходныя сингл ксичвскип лнллиз вез возвглтов (а) отношение ' не рефлексивно, не симметрично н не трапзитивно; (б) отношение <' не иррефлексивно и не транзитивно; (в) отношение ) не иррефлексивно и не транзитивно. "5.3.5. Покажите, что каждое регулярное множество определяется грамматикой простого предшествования.
Указание: Убедитесь в том, что Ваша грамматика обратима. *5.3.6. Покажите, что каждая обратимая грамматика (т„п)- предшествовання является 1 1?-грамматикой. "5.3.7. Покажите, что каждая грамматика слабого предшествования является 11?-грамматикой. 5.3.8.
Докажите, что алгоритм 5.12 правильно производит правый разбор. 5.3.9. Докажите, что 6 — грамматика предшествоваиия тогда и только тогда, когда она — грамматика (1,1)-предшествования. 5.3.10. Докажите лемму 5.3(1). 5.3.11. Докажите, что алгоритм 5.14 правильно производит правый разбор. 5.3.12. Постройте алгоритм правого разбора для обратимых грамматик (т, и)-предшсствоваиия. 5.3.13. Докажите следствие теоремы 5.17.
*5.3.14. Покажите, что алгоритм 5.15 строит грамматику простого предшествования, эквивалентную исходной грамматике. 5.3.15. Для тех грамматик из упр. 5.3.1, которые являются грамматиками слабого предшествования, постройте эквивалентные грамматики простого предшествования. *5.3.16. Докажите, что язык Е =-(аО" Р (п-"!) (! (ЬО" 1'"(п~ Ц не является языком простого предшествования. Указание: Подумайте о том, как вел бы себя на цепочках вида аО"1'* и ЬО"1" правый анализатор, построенный алгоритмом 5.12, если бы язык Ь определялся грамматикой простого предшествования.
*5.3.17. Постройте грамматику (2,1)-предшествования для языка из упр. 5.3,16. э5.3.18. Постройте грамматику простого предшествования для языка (О"а!" ) и ~ 1) () (ОчЫ'" ~ и Ъ 1). "5.3.19. Покажите, что каждую КС-грамматику без е-правил можно преобразовать в эквивалентную грамматику (1,1)-пред- шествования. 5.3.20. Для КС-грамматики 6=(Ь(, л, Р, Я) определим отношения 7, р, и р: 476 Упглжиения (1) ?1?.Х, если в Р есть правило А Хя, где я — какая-нибудь цепочка; (2) Х)1)', если в Р есть правило А- яХу5 для некоторых я и !3 кроме того 5)л5 и Ь!л5. (3) ХРА, если в Р есть правило А яХ, где я — какая-нибудь цепочка. Покажите, что эти отношения и отношения предшествовання Вирта — Вебера связаны следующим образом: (а) - !л? ", (б) =' 0 ((5, 5), (8, 3) ) — !л, (в) >=-р"!л)*П((~ОХ)кХ) ( (- обозначает трапзитивное, а л — рефлексивное н транзитивное замыкание).
*"5.3.21. Докажите неразрешимость проблемы; является ли данная грамматика грамматикой расширенного предшествования (т. е. грамматикой (т, и)-предшествовання для некоторых т и и)? "5.3.22. Докажите, что если 6 — грамматика слабого предшествования, то 6 — грамматика расширенного предшествовання (для некоторых т и п). 5.3. 23.
Покажите, что а Е РО1.1ОЪ; (А) тогда и только тогда, когда А < ° а, А а илн А >а. 5.3.24. Обобщите лемму 5.3 на грамматики расширенного предшествования. 5.3.25. Предположим, что условия расширенного предшествования ослаблены так, что допускается конфликт я.сти и я ш, если ои порождается только пунктамп (1б) и (2б). Разработайте алгоритм разбора типа „перенос — свертка" для грамматик, удовлетворяющих этому ослабленному определению.
![](https://s.studizba.com/z.php?f=/templates/si/i/noavatar.png&w=100&h=100&t=1"){kind=avatar}
