Кук Д., Бейз Г. - Компьютерная математика (1048841), страница 42
Текст из файла (страница 42)
У,- У»У«... У„ У»1 « ° ° ° У«У»У«У« °,, Уе У,У,...У,,У,-. У,У,...У,,У,. Все эти продукции имеют вид»хЛр - а7'р. Новые нетерминалы У», ..., У, вынуждают приме- пять эти продукции в написанном порядке так, чтобы никакие иэ предложений, не входящих в исходный язык, не могли быть соэданы. «' В эаключеяие етого параграфа обсудим понятие неодноэяачности. Классическим примером неодновначного предложения является предложение «ТЬеу аге Пу1пй р1апев». Мы имеем две интерпретации этого предложения, эависящне от того, рассматриваем мы «аге 11у!вйэ как скаэуемое или же «Ву1па р1апеэ» как дополнение. Это приводит яас непосредственно к точному ооределснн»о неодвоввачности.
Яэык наэывается н«одно«начиым, если ои содержит неодноэначное предлоя»ение. Предло>кение является синтаксически я«одно«наемы»в, если оно имеет более одного канонического вывода, и семантически неоднозначна»м, если для ваданного канонического вывода оно имеет более одной интерпретации. (Выводы относятся не непосредственно к яэыку, а к грамматике, порождающей его.
Следовательно, м»а долл»вы ссылаться на»»«одное»»очную грамматику; однако существуют существенно неоднозначные яэыки, которые могут порождаться только неодноэначными грамматиками.) Для более подробного 273 изучения семантических веодвовначностей рекомендуем обратиться в специальной литературе о языках программирования, а сейчас проиллюстрнруем синтаксические неодновначноств двумя примерами.
Пример 25. 1. Пусть 6 ((Е), (1, -), (Е- Е-Е(1), Е). Тогда а) Е.«Е-Е « «1-Е». ~ 1 — 1-Е»" ° » 1-1-1; Из втвх последовательностей следует, что два указанных вывода являются различными, и, следовательно, хотелось бы придать им различные значения. В примере а) Х вЂ” Е 1 1 Ь а Рвс. 8Л второй знак»минус», вычисляемый вначале, дает 1; в примере б) первый знак «минусэ, выполняемый первым, дает -1. (Диаграммы ва рис, В.2 иллюстрируют различные структуры. 18 д, кгс, г, в»а» 818 б) Е»Е-Е»- ° «Е Е Еа« ~ 1-Е-Е».
° «1 — 1-Е « ° «1 — 1 — 1. И Ф Ф Я ~ 2. рассмотрим хорошо иэвестный пример из первой специ$якацни яэыка Алгол-60. Сужая грамматику до относящегося к делу подъязыка, будем иметь продукции Я - И В Жеп Я е1ае Я ~ И В $Ьеп Я 1 У, где Я вЂ” утверждение,  — булево ° выражение, У вЂ” без- Рве. 8.3 условное утверждение. Теперь рассмотрим выражение И В~ 4Ьеп И Вэ 1Ьсп У~ е1ве Ут.
Мы не внаем, принадлежит ли е1ае Ут к И В~ или к И Вв Формально мы можем вывести это предложение, рассматривая В и У как терминалы, следующим обрааом (рис. 8.3,а, Ь соответственно1: а1 Я =ь И В йеп Я *= ь И В 1йеп И В 1Ьеп Я е1ае Я ~- 274 » И В йеп И В йеп У е)ве Я *г» И В йеп И В (Ьеп И е)ве С; б) Я» И В йеп Ю е)ве 5-"" .» И В 1Ьеп И В 1)геп Я е)ве Я ': ч И В йеп И В $Ьеп 6 е!ве Я =г. ° ' И В 1Ьеп И В (Ьеп <г' е)ве <г. в" У п р а яг н е н и е 2.2. 1. Выразить явно языки, определенные следующими грамматикамн: а) 6 ((<число>, (О, 1, 2, ..., 9), Р, <число>), где Р - (<число> - О 1 1 1 2 1 3 ! 4 1 5 1 б 1 7 1 8 1 9); б) 6 ((<Р>, <Е>, <В>), (О, 1, 2, ..., 9), Р, (Р>), где Р ((Р> - <Т><(» 1(Ь>, (Т>- 11213.„819, (В>- <В>, <Р>- 0).
2. Определить грамматику 6' (М', Т', Р', В'), экви- валентную 6 ((А,В,С,Й,(х,у,з),Р,Я), где Р Б- АВгС АВ- ВАз, зВ- А'Вх, А- х, В- у,С- з), с продукциями вида аЯ - и"(б для Дю)у', '( (У'0 Т'), а, б (Лг'О Т')», 3. Определить класс Хомского грамматики, определенной следующим образом: 6 ((А,В,Т,В),(х,у,з),Р,Ю), где Р ° (Я- хТВ1хВ, Т- хТА 1хА, В- уз, Ау- уА, Аз- узз), Используя свойство класса, к которому принадлежит 6, установить, принадлежат или нет Ь(6) следующие строки: хгухз, хгугзг хухз, 18» 275 4. Определить последовательность разрезов представленного здесь производящего дерева, соответствующую самому правому выводу предложения х+ х их.
Д «Т т у ~ т х г 5. Определить порядок в»>ножестве продукций Р та- ким образом, чтобы была воэможность канонического вы- вода, определяющего последовательность целых чисел в Х. Продемонстрировать две такие последовательности для предложения «аэа» в 5(6>), где б> дано ниже. Вы- вести также строку над Х, описывающую все выводы в языке 5(О»), т. е. показать, что А="'А подразумева- ет неоднозначность.
Здесь С>=(Д>, Т, Р, Е), С» (Д>, Т, Р, А), где Л = (А, В, С, Е, В), Т (а, д, е, х, з) и Р (А В!СЫ,В- Вх!еС!С, С- А!хВ,Е- аЕ!Еа!В,В- з). 6. Выяснить, являются ли следующие грамматики неоднозначными: а) С ((А, В, Е), (а, Ь, с), Р, Е), где Р=(Е- АВ, А - а. ! аЬ, В - с ! Ьс); б) 6 =((<целое беэ знака>, <число>), В, Р, <целое беэ анака>), где В =(О, 1, ..., 9) н Р = (<целое без знака> — <число>, <число> -~ <чвсло> <число>, <чнсло> -+ О ! 1 ! 2 ...! 9). 3 3. Контекстно-свободные языки ЗЛ. Основные определения.
Контекстно-свободные грамматики (КСГ) и контекстно-свободкые языки (КСЯ) важны для практических вычислений, так как, хотя большинство языков является некоторым расширением конте>:тно зависимых языков, их легче изучать как контекстно свободные яаыкн, а затем по другим (семанти- гтэ ческим) критериям отбросить некоторые нз предложений.
В зтих случаях на КЗГ моя~но ссылаться как на грамматики, специфицированные связанным синтаксисом, а на КСà — как специфицированные несвязаннамсинтаксисом. КСГ такзке дают возможность прояснить вопросы, содержащие (синтаксическую) неоднозначность. Последовательность вывода аж Ь(6) может быть изображена как упорядоченное дерево (см. ниже).
Корень » дерева обозначен через Е, и если Е=;.а~ Т* и а а~...а„, то выходы помечены по порядку аь ..., а„, Предисловиям, что о'=з-р=».у=з.гз и что (( 7 достигается в результате применения продукции С- Ъ ...7, где 7,ю У. В дереве это представляется пометкой вершины С и т ее преемников (точек, из которых С достигается за один шаг) уь ..., т . Поэтому метки могут быть одинаковыми. П р н м е р 3.1. Рассмотрим грамматику с продук- циями Е- Т~Е+Т, Т- 1!1»Т,1- (Е)!х. Обычно в случае контекстно-свободных грамматик мы будем опускать другие элементы грамматики; первое правило специфицирует ис- ,Г точник, а нетерминалами яв- х ляются только символы в левой стороне продукций.
В этом случае вывод предложения х+ х» х может быть изображен так, как это сделано ва рис. 8.4. У С конструктивной точки х ! х Ю Рве. 8.4 зрения это изображение называется деревом вывода. (Когда это дерево используют для того, чтобы проанализировать, могут или не могут строки содержаться в Ь(6), оно называется деревом грамматичесзоео разбора,) Легко видеть, что предложение является неоднозначным, если оно имеет два пеизоморфных дерева вывода, и что для контекстно-свободкых грамматик канонический грамматический разбор изоморфен любой другой схеме обхода дерева. Мы уже установили тот очевидный факт, что КСГ являются более ограниченными, чем КЗГ, но тем не ме- 277 нее они все же облада«от весьма широкими изобравительными возможностями.
Пример 3,2, Используя контекстно-свободные правила, можно породить: 4) все последовательности из символов А: Я АЯ(Л; 2) все непустые списки из символов А, отделенные друг от друга символами В: Я- А«АВЯ; 3) те «ке списки, что и в примере 3.2,2, однако до пускается возможность пустого списка: Б- Т! Л, Т- А! АВТ; 4) все строки, начинающиеся с последовательности символов А илн В и онанчивающнеся символами С или Р соответственно: Я- АЯС«ВЮР(Х; например, Я- (Я((Я)(Х.
В этих примерах А, В, С, Р и Х могут быть определены дополнительно. г 3.2. Характеристические свойства. Особенностью рассмотренных выше примеров, о которых вскоре мы сможем сказать несколько больше, является свойство рекурсии (однн шаг рекурсии при каждом пж«(). Трудности возникают тогда, когда требуется наложить некоторые ограничения на глубину рекурсии, не придумывая новых правил для каждой допустимой глубины рекурсии, Поскольку Л« и Р конечны, то очевидно, что если не разрешать никаких рекурсий, то Ь(С) также будет конечен, и этот случай не очень интересен. Прежде чем идти дальше, введем необходимую терминологию.
Говорят, что грамматика 6: а) леворекурсивнац если в ней имеются выводы вида Х =~ Ха, где Х ен Л«, а я У+; б) пряаорекурсивная, если в ней име«отея выводы вида Х=;.аХ, где Х и и такие «««е, как н выше; 273 в) самовключающая, если она имеет выводы вида Х: иХ~, где ХяУ и сс,~)виу+, Говорят, что КСГ рекуреиена, если имеется один из случаев а) — в).
Иэ сделанных выше замечаний ясно, что желательно бы иметь в грамматике епетлиэ, однако не произвольного типа. К этому вопросу мы вернемся в 9 4. Сформулируем результат о возможностях КСГ. В теории КСЯ это, вероятно, наиболее известный результат. Его доказательство использует рекурсивные свойства КСГ и структуру деревьев. Этот результат известен как лемма о разрастании для КСЯ или же как пои»ху теорема.
Теорема. Если Ь вЂ” контекстно-свободный язык, то существует ны>» такое, что если хы> и Ь! >и, то х может быть записано в виде иои»ху, еде и, и, и», х, у >в Те, охт" Л и для любого $»и>» выиолняется условие но»и»х»у ш Ь. Доказательство. Поскольку Б — контекстно-свободный язык, то он может быть порожден некоторой грамматикой 6 (>У, Т, Р, 8) и не имеет продукций, за исключением, возможно, д- Л (если Лгпи(6)), уменьшающих длину сентенциальных форм.
(Если ЛыЬ, то д также исключают из правых частей продукций для того, чтобы не уменыпалась длина сентенциальных форм. В $4 показано, что такая грамматика 6 может быть найдена.) Если 6 не рекурсивна, то, поскольку Л» и Р конечны, >'(б) также конечен, и, следовательно, теорема справедлива, если взять п большим, чем длина самой длинной строки в Ь(6).
С другой стороны, если С рекурсивна, то существует дерево вывода, в котором некоторый истер»иках, например А, встречается дважды на пути от корня к листу. Эта ситуация изображена на рис. 8.5. (Сюда включены лишь необходимые пам свойства.) Более того, поскольку б рекурсивиа, то мы можем добиться выполнения соотношения !>пои»ху! > и, где я больше длины самого длинного предложения, полученного путем нерекурсивного вывода ((й", где й — длина самой длинной продукции Р, а л»»У!). Таким образом, если гыЬ и Ь! >я, то з должно иметь требуемый вид + для некоторых пяти строк. Тогда А=>.оАх (охеьЛ, по- 279 В этому )иАх! ) !А!) и А=:-и. Следовательно, А =~- и'Ах'=~- и'и~х Ф для любого 1 ы Х.
Отсюда, так как Я=~ иАу, имеем Я=а ни~им у для любого ! ы Ь! и, таким образом, пи'юх'у 1в т для любого $ ы Ь!. Х Этот результат может быть использован для проверки того, что некоторые конструкции в языках программирования не могут быть определены с помошью КСГ.
Дадим более реальный пример, который не требует знания конкретного языка. Пример 3.3. Грамматика на примера 2.4 порождает язык 1х"у"г": пы%. Сейчас мы можем показать, что Рвс. 8.5 этот язык является контекстно-зависимым н не может быть порожден КСГ. Из теоремы следует, что существует некоторое достаточно большое и, при котором х"у"г" может быть записано в виде аЬсд~ (требуется очевидная замена символов) для некоторых строк а, ..., ~, Поскольку х и г в строке разделены, то очевидно, что строки а н Ь не могут содержать все символы х, у и г; аналогично н для всех других пар нз (а, Ь, с, Й, ~).
В частности, по крайней мерв один нз символов х, у и г не может быть одновременно в строках Ь и Н; таким образом, строка аЬзсд9, которая по теореме содержится в г', содержит не все свмволы х, у и г (онв также могут быть распо- 280 ложены в другом порядке, однако в дальнейшем мы не будем рассматривать эту возможность).
![](https://s.studizba.com/z.php?f=/templates/si/i/noavatar.png&w=100&h=100&t=1"){kind=avatar}
