Теория синтаксического анализа, перевода и компиляции - Том 1 (943928), страница 47
Текст из файла (страница 47)
,Л~ 1оеа ~е!ье И Ь 1ЬВ о Рис. 2.!8. Два дереве вывода. Теорема 2.80. Проблема, однозначна ли КС.граммагпика 6, неразре!мима. Доказательство. Пусть С=!ха у,), ..., (х„, у„) — частный случай проблемы соответствий над алфавитом г'. Возьмем КСграмматику 6=115, А, В), 2 0 2', Р, 5), где !=11, 2, „л) и Р содержит правила 5- А)В А — Х,А1(х;1 для 1(1 =. л В- уВ1!у21 для 1«:.!(н Нетерминалы А и В порождают соответственно языки Е и М,, определенные в равд.
2.8.3. Легко видеть, что не существует цепочки с двумя различными левыми выводами из нетерминала А 232 или из нетерминала В. Следовательно, если существует цепочка с двумя различными левыми выводами нз 5, то один должен начинаться шагом 5=О, А, а другой — шагом 5=О,В. Но по лемме 2,28 некоторая цепочка выводится из А н из В тогда и толька тогда, когда частный случай С проблемы соответствий Паста имеет решение. Таким образом, КС-грамматика 6 неоднозначна тогда и только тогда, когда С имеет решение. Отсюда сразу заключаем„что если бы существовал алгоритм, решающий проблему однозначности для КС-грамматик, то была бы разрешима проблема соответствий. П Определенная нами неоднозначность — зто свойство грамматики, а не языка.
Для некоторых неоднозначных грамматик можно построить эквивалентные им однозначные грамматики. Пример 2.48. Рассмотрим грамматику и язык из предыдущего примера. Грамматика 6 неоднозначна потому, что е)ее можно ассоциировать с двумя разными 112еп, По этой причине языки программирования, в которых разрешаются как операторы вида И вЂ” 112еп, так и операторы вида И вЂ” 112еп — е)ее, могут быть неоднозначными, Неоднозначность можно устранить, если договориться, что е1зе должно ассоциироваться с последним из предшествующих ему Феп, как на рис. 2.18, б. Можно подправить грамматику из примера 2.48, введя два иетерминала 5, н 5, н потребовав, чтобы 5, порождал операторы вида И вЂ” Йеп — е!ее, тогда как 5! может йорождать операторы обоих видов.
Правила новой грамматики таковы: 5, — И Ь 112еп 5, ~ И Ь 1)теп 5, е!зе 5, ) а 5, — И Ь йтеп 5, е)зе 5, ) а Тот факт, что слову е1зе предшествует только 5„гарантирует появление внутри конструкции 1пеп — еЬе либо символа а, либо другого е!ае. Таким образом, структура, изображенная на рис. 2.18, а, не возникнет. В гл. 8 мы изложим детерминированные методы разбора для различных грамматик, в том числе для грамматики этого примера, и там мы сможем доказать, что наша новая грамматика однозначна. сз Хотя нет общего алгоритма, выясняющего, однозначна ли грамматика, можно указать некоторые встречающиеся в пранео вилах, конструкции, приводящие к неоднозначности. Поскольк еоднозначпые грамматики часто анализируются труднее, чем У однозначные, мы назовем здесь несколько наиболее распространенных конструкций такого рода, так что их можно будет распознать на практике, 233 ГЛ.
й. ЭЛЕМЕНТЫ ТЕОРИИ ЯЗЫКОВ Приведенная грамматика, содержащая правила А- АА(а, неоднозначна, так как подцепочка ААА допускает два разных разбора (рис. 2.19). Эта неоднозначность исчезнет, если вместо правил А — АА (а взять правила А — АВ(  — «й или правила' А'- ВА(  — ~а Другой пример неоднозначности — правило А — АаЛ. Пара правил А- аА ~Ай тоже создает неоднозначность, так как цеРис. 2Л9, Два дерева рйвеера.
почка аА6 имеет два разных левых вывода А~иА~аА6 и А~Ар=эаАР. В качестве более тонкого примера пары правил, из-за которых грамматика может стать неоднозначной, приведем А — аА~ аА6А. Другие примеры неоднозначных грамматик можно найти в упражнениях. КС-язык называется неоднозначным (или суи(есйпеенно неоднозначнйы!), если он не порождается никакой однозначной КС- грамматикой. С первого взгляда не видно, существуют ли вообще неоднозначные КС-языки, но нашим следующим примером н будет как раз такой язык. Проблема, .порождает ли данная КС-грамматика однозначный язык (т. е.
существует ля эквивалентная ей однозначная грамматика), на самом деле неразрешима, по для некоторых больших подклассов КС-языков известно, что они однозначны; все придуманные до сих пор языки программирования тоже однозначны. Важнее Всего то, что, как мы увидим в гл. 6, каждый детерминированный КС-язык апре. еелястся„однозначной КС-грамматикой. Пример 2,47, Пусть Т.
= (а'Ьгс! ) !' = 1 или 1 =- 1). Этот КС-язык неоднозначен. Интуитивно это объясняется тем, что цепочки !=1 должны порождаться группой правил, отличных от праВил, порождающих цепочки с 1'=С По крайней мере некоторые Вз цепочек с ! =1=1 должны порождаться обоими механизмами.
234 й.й, СВОЙСТВА КОНТЕКСТНО СВОБОДНЫХ ЯЗЫКОВ Одна из КС-грамматик, порождающих Е, такова:  — ЛВ(РС А — аА(е  — ЬВс)е С- сС1е Р- аРЬ!е Ясно, что она неоднозначна. С помощью леммы Огдена можно показать, что язык Т. неоднозначен, Пусть 6 †произвольн КС-грамматика, порождающая Е, и й — число, связанное с О (см. теорему 2.24).
Можно считать, что й= 3. Рассййотрий!'пепочку г=айЬйсй'.й!, в которой выделены Все символы а. Ее можно записать в виде г=--иойоху. Так "как йо содержит выделенные позиции, то и и о состоят только из символов а. Если х содержит два различных символа, то, конечно, иойп!хйу(1., так что либо ХЕай, либо хбЬ", либо хаев. Если хЕай, то цепочка ной!ох!у имеет вид а"йеЬйсйей! для некоторого ! "р~й и погому не принадлежит Е. Если хЕсй, то ной!ох!у имеет впд ай-ЕЬ'с'"'+е*, где 1~р,<й. Эта цепочка тоже не принадлежит Ь.
ЕСЛИ ХЕЬй, тО исйЮХйу=ай.-е Ьйййеййй!, Гдс 1~рй .й. ЕСЛИ эта цепочка принадлежит Т., то либо р,=р„либо р,Фр, и р,=И. В последнем случае цепочка пой!ох!у=-айййР~Ьй".йе сйййй, конечно, не принадлежит Е. Поэтому заключаем, что р, =р,. Заметийй, что р, =)о! и р,=(х). По теореме 2.24 для любого ой~О найдется вывод (2.6.1) В=>йиАу=-э'иомАхму=-рено иге у Пусть, в частности, т=й(/р1. Так как 1 "р, "й, то т— целпе число.
Тогда ййс"!ох'"у=аййй!Ьй+й!сййй!. Для цепочки а" +'Ъйс" можно показать по симметрии, что существуют !й„о„йо„х„д„где только и, содержит символ а, о, ЕЬ', и что найдется такой нетерминал В, что (2.6.2) В.=>+ и, Вд =>й и йт Вх~' у и ом ~!о хв1~н ай+А!Ьй йй!ей+й! 1 1 1 1 В! Если мы сумеем показать, что этим двум выводам цепочки а +МЬ'йй'сй"й' соответствуют разные деревья, то тем самым докажем, что Т.— неоднозначный язык, поскольку грамматика П была выбрана произвольно и оказалась неоднозначной.
Допустим, что выводам (2.6.1) и (2.6.2) соответствует одно и то же дерево. Так как А порождает цепочки из символов а й' Ь, а В порождает цепочки из символов Ь и с, то А (соотВетственпо В) не может быть меткой вершины, которая является 255 гл. 3, злвмвнты твовии взыкьй х пгхжнения Я =->) а); Я ="~„' и); Я~~" и). (а) (а( (б) (сс) (в) (и 237 потомком вершины, помеченной В (соответственно А). Следовательно, найдется выводимая цепочка (,А(,В1„где 1„1м 1»вЂ” терминальные цепочки. Для всех 1 и 1 цепочка 11с'эх'1»и(ш,х(1» должна по предположению принадлежать Ь. Но (о)=-)х( и (о,( = (х,( и, кроме того, х и о, состоят только из символов Ь, о — из символов а и х, — из сймволов с. Тогда, выбрав 1 н 1 равными, и достаточно большими, можно считать, что в соответствующей цепочке символов Ь больше, чем символов а или с.
Отсюда заключаем, что грамматика 0 неоднозначна, а стало быть, и язык Л неоднозначен. С) упвАжиейия 2.6.1. Пусть ь — КС-язык и )? — регулярное множ в П житО, что следующие языки контекстно-свободны. жество. ока(а) 1Ь(1Т (Е,); (б) Р1Н(й); (в) ЯЗВ(Е); (г) 1.Я; (д) ( () Й. Определения операций (а) — (г) даны перед упр. 2.3,17. 2.6,2. Покажите, что если Š— КС-язык и Ь вЂ” гомоморфизм, то Ь '(~) — КС-язык. Указание; Пусть Р— МП-автомат, допускающий 7..
Постройте МП-автомат Р', который применяет Ь по очереди к каждому входному символу, запасает результат в буфере управляющего устройства и моделирует Р на символах из буфера. Позаботьтесь о том, чтобы Ваш буфер был конечной длины. 2.6,3. Покажите, что следующие языки не контекстно-свободны: ( ) ( 'Ь' '!! < 1)' (б) (а'Ысь11 <1<Ь); ' (в) множества цепочек с одинаковым числом символов а, Ь и с; (г) (аеЬ?а~Ь!/ / - 1); (аиЬ»а~Ь» ((л и > 1) ° (е) (а'Ь?се(все числа 1, 1, й разные); (ж) (лОа'(и~~ 1 — число в десятичной записи).
(Эта конструкция представляет холлеритовы поля в Фортране.) »»2.6.4. Покажите, что каждый КС-язык в однобуквенном алфавите регулярен. Указание: Воспользуйтесь леммой о разрастании. "+2.6.6. Покажите, что следующие языки не всегда являются КС-языками, когда Š— КС-язык: (а) МАХ (~); (б) М1Ь((Ц; (в) 7.п* = (х(хуЕ 1. для некоторого у и ) х(= )у().
*2.6,6. Докажите следующую лемму о разрастании для линейных языков. Если Š— линейный язык, то найдется такая константа Ь, что если гч1- и(г))л, то г — — имсху, где!исху!«Ь, схчЬе и ис'юх'у ЕЕ для всех Е 2,6.7. Покажите, что язык (а"Ь"а Ь") и, т) 1) не линейный.
*2.6.8. МП-автоматом с одним изворотом называется МП- автомат, который для любой входной цепочки сначала только пишет в магазин, а потом только стирает, т. е. начав стирать символы в магазине, ои уже не может сиона записывать (это и есть один поворот в работе с магазином).
Покажите, что КС-язык линееи тогда и только тогда, когда он распознается МП-автоматом с одним поворотом. *2,6,9. Пусть 6--()х, Х, Р, 5) — КС-грамматика. Покажите, что следующие языки контекстно-свободны: 2.6.16, Дайте подробное доказательство следствия из тео- ремы 2.2о. 2.6.11. Дополните доказательство теоремы 2,26. 2.6.12. Дайте более формальное описание ДМП-автоматов, фигурирующих в доказательствах лемм 2.29 (1) и 2.30 (1). *2.6.13.
Покажите, что язык 17с В Рс из равд. 2.6.3 кон- текстно-свободен тогда и только тогда, когда он пуст. 2.6.14. П , Покажите, что следующие проблемы для КС-грамма- тик г' неразрешимы: (а) й(6) — КС-язык? (б) 7.(6) — регулярный язык? Указан (в) 7, (6) — детерминированный КС-язык? казание: Используйте упр. 2.6.13 н рассмотрите КС-грамматику длЯ Языка 1,1с В Р, Докажите, что проблема, порождает ли контекстно- зависимая грамматика КС-язык, неразрешима. 2.6,16. П . Пусть 6, и 6,— КС-грамматики. докажите неразрешимость проблемы „7.(6,) () 7 (В») =~? »2.6.17. П .17. П с 6,— КС-грамматика и 6» праволинейная гр'"' матнка.
Докажите ГЛ. 2. ЭЛЕМЕНТЫ ТЕОРИИ ЯЗЫКОВ (а) неразрешимость проблемы,„1.(6,) =Е(6„)?" (б) разрешимость проблемы „1. (6,) й1 (6,)?" *2.6.18. П сть Р, и Р,— ДМП-автоматы. Докажите неразреу шимость следующих проблем: (а) Е(Р,) (1 Е(Р,) — детерминированный КС-язык? (б) 1. (Р,) Е(Р,) детерминированный КС-язык? (в) 1.
![](https://s.studizba.com/z.php?f=/templates/si/i/noavatar.png&w=100&h=100&t=1"){kind=avatar}
