dzhon_khopkroft_radzhiv_motvani_dzheffri _ulman_vvedenie_v_teoriyu_avtomatov_yazy kov_i_vychisleniy_2008 (852747), страница 52
Текст из файла (страница 52)
(Необходимость) Внимательно рассмотрим построение левого порождения по дереву разбора в доказательстве теоремы 5.14. В любом случае, если у двухдеревьев разбора впервые появляется узел, в котором применяются различные продукции, левые порождения, которые строятся, также используют разные продукции и, следовательно, являются различными.(Достаточность) Хотя мы предварительно не описали непосредственное построениедерева разбора по левому порождению, идея его проста.
Начнем построение дерева скорня, отмеченного стартовым символом. Рассмотрим порождение пошагово. На каждомшаге заменяется переменная, и эта переменная будет соответствовать построенномукрайнему слева узлу дерева, не имеющему сыновей, но отмеченному этой переменной.По продукции, использованной на этом шаге левого порождения, определим, какие сыновья должны быть у этого узла. Если существуют два разных порождения, то на первомшаге, где они различаются, построенные узлы получат разные списки сыновей, что гарантирует различие деревьев разбора. 5.4.4.
Ñóùåñòâåííàÿ íåîäíîçíà÷íîñòüКонтекстно-свободный язык L называется существенно неоднозначным, если все егограмматики неоднозначны. Если хотя бы одна грамматика языка L однозначна, то L является однозначным языком. Мы видели, например, что язык выражений, порождаемыйграмматикой, приведенной на рис. 5.2, в действительности однозначен. Хотя даннаяграмматика и неоднозначна, этот же язык задается еще одной грамматикой, которая однозначна — она изображена на рис.
5.19.Мы не будем доказывать, что существуют неоднозначные языки. Вместо этого рассмотрим пример языка, неоднозначность которого можно доказать, и объясним неформально, почему любая грамматика для этого языка должна быть неоднозначной:L = {a n b n c m d m | n ≥ 1, m ≥ 1} U {a n b m c m d n | n ≥ 1, m ≥ 1}.Из определения видно, что L состоит из цепочек вида a+b+c+d+, в которых поровну символов a и b, а также c и d, либо поровну символов a и d, а также b и c.L является КС-языком. Очевидная грамматика для него показана на рис. 5.22. Для порождения двух видов цепочек в ней используются два разных множества продукций.226Стр. 226ÃËÀÂÀ 5.
ÊÎÍÒÅÊÑÒÍÎ-ÑÂÎÁÎÄÍÛÅ ÃÐÀÌÌÀÒÈÊÈ È ßÇÛÊÈЭта грамматика неоднозначна. Например, у цепочки aabbccdd есть два следующихлевых порождения.1.S ⇒ AB ⇒ aAbB ⇒ aabbB ⇒ aabbccBd ⇒ aabbccdd2.S ⇒ C ⇒ aCd ⇒ aaDdd ⇒ aabDcdd ⇒ aabbccddlmlmlmlmlmlmlmlmlmlmСоответствующие деревья разбора показаны на рис. 5.23.S→AB | CA→aAb | abB→cBd | cdC→aCd | aDdD→bDc | bcРис. 5.22. Грамматика для существенно неоднозначного языкаa)б)Рис. 5.23. Два дерева разбора для aabbccddДоказательство того, что все грамматики для языка L неоднозначны, весьма непросто,однако сущность его такова.
Нужно обосновать, что все цепочки (за исключением конечного их числа), у которых поровну всех символов, должны порождаться двумя различнымипутями. Первый путь — порождение их как цепочек, у которых поровну символов a и b, атакже c и d, второй путь — как цепочек, у которых поровну символов a и d, как и b и c.Например, единственный способ породить цепочки, у которых поровну a и b, состоитв использовании переменной, подобной A в грамматике, изображенной на рис.
5.22. Ко5.4. ÍÅÎÄÍÎÇÍÀ×ÍÎÑÒÜ Â ÃÐÀÌÌÀÒÈÊÀÕ È ßÇÛÊÀÕСтр. 227227нечно же, возможны варианты, но они не меняют картины в целом, как это видно из следующих примеров.• Некоторые короткие цепочки могут не порождаться после изменения, например,базисной продукции A → ab на A → aaabbb.• Мы могли бы организовать продукции так, чтобы переменная A делила свою работу с другими, например, используя переменные A1 и A2, из которых A1 порождает нечетные количества символов a, а A2 — четные: A1 → aA2b | ab;A2 → aA1b | ab.• Мы могли бы организовать продукции так, чтобы количества символов a и b, порождаемые переменной A, были не равны, но отличались на некоторое конечноечисло.
Например, можно начать с продукции S → AaB и затем использоватьA → aAb | a для порождения символов a на один больше, чем b.В любом случае, нам не избежать некоторого способа порождения символов a, при котором соблюдается их соответствие с символами b.Аналогично можно обосновать, что должна использоваться переменная, подобная B,которая порождает соответствующие друг другу символы c и d. Кроме того, в грамматике должны быть переменные, играющие роль переменных C и D, порождающих соответственно парные a и d и парные b и c. Приведенные аргументы, если их формализовать,доказывают, что независимо от изменений, которые можно внести в исходную грамматику, она будет порождать хотя бы одну цепочку вида anbncndn двумя способами, как играмматика, изображенная на рис.
5.22.5.4.5. Óïðàæíåíèÿ ê ðàçäåëó 5.45.4.1.Рассмотрим грамматику S → aS | aSbS | ε. Она неоднозначна. Докажите, что дляцепочки aab справедливо следующее:а) для нее существует два дерева разбора;б) она имеет два левых порождения;в) она имеет два правых порождения.5.4.2.(!) Докажите, что грамматика из упражнения 5.4.1 порождает те, и только тецепочки из символов a и b, у которых в любом префиксе символов a не меньше, чем b.5.4.3.(∗!) Найдите однозначную грамматику для языка из упражнения 5.4.1.5.4.4.(!!) В грамматике из упражнения 5.4.1 некоторые цепочки имеют только однодерево разбора. Постройте эффективную проверку, является ли цепочка однойиз указанных. Проверка типа “проверить все деревья разбора, чтобы увидеть,сколько их у данной цепочки” не является достаточно эффективной.228Стр.
228ÃËÀÂÀ 5. ÊÎÍÒÅÊÑÒÍÎ-ÑÂÎÁÎÄÍÛÅ ÃÐÀÌÌÀÒÈÊÈ È ßÇÛÊÈ5.4.5.(!) Воспроизведем грамматику из упражнения 5.1.2:S → A1BA → 0A | εB → 0B | 1B | εа) докажите, что данная грамматика неоднозначна;б) найдите однозначную грамматику для этого же языка и докажите ее однозначность.5.4.6.(∗!) Однозначна ли ваша грамматика из упражнения 5.1.5? Если нет, измените еетак, чтобы она стала однозначной.5.4.7.Следующая грамматика порождает префиксные выражения с операндами x и y иоператорами +, - и *:E → + EE | * EE | - EE | x | yа) найдите левое и правое порождения, а также дерево разбора для цепочки+*–xyxy;б) (!) докажите, что данная грамматика однозначна.Ðåçþìå♦ Контекстно-свободные грамматики. КС-грамматика — это способ описанияязыка с помощью рекурсивных правил, называемых продукциями.
КС-грамматикасостоит из множества переменных, терминальных символов, стартовой переменной, а также продукций. Каждая продукция состоит из головной переменной и тела — цепочки переменных и/или терминалов, возможно, пустой.♦ Порождения и языки. Начиная со стартового символа, мы порождаем терминальные цепочки, повторяя замены переменных телами продукций с этими переменными в голове.
Язык КС-грамматики — это множество терминальных цепочек,которые можно породить; он называется КС-языком.♦ Левые и правые порождения. Если мы всегда заменяем крайнюю слева (крайнююсправа) переменную, то такое порождение является левым (правым). Каждая цепочка в языке КС-грамматики имеет, по крайней мере, одно левое и одно правоепорождения.♦ Выводимые цепочки. Любой шаг порождения дает цепочку переменных и/илитерминалов. Она называется выводимой цепочкой. Если порождение является левым (правым), то цепочка называется левовыводимой (правовыводимой).♦ Деревья разбора. Дерево разбора — это дерево, показывающее сущность порождения. Внутренние узлы отмечены переменными, листья — терминалами или ε.ÐÅÇÞÌÅСтр.
229229Для каждого внутреннего узла должна существовать продукция, голова которойявляется отметкой узла, а отметки сыновей узла, прочитанные слева направо, образуют ее тело.♦ Эквивалентность деревьев разбора и порождений. Терминальная цепочка принадлежит языку грамматики тогда и только тогда, когда она является кроной, покрайней мере, одного дерева разбора. Таким образом, существование левых порождений, правых порождений и деревьев разбора является равносильным условием того, что все они определяют в точности цепочки языка КС-грамматики.♦ Неоднозначные грамматики. Для некоторых грамматик можно найти терминальную цепочку с несколькими деревьями разбора, или (что равносильно) с несколькими левыми или правыми порождениями.
Такая грамматика называется неоднозначной.♦ Исключение неоднозначности. Для многих полезных грамматик, в частности, описывающих структуру программ в обычных языках программирования, можно найти эквивалентные однозначные грамматики. К сожалению, однозначная грамматика часто оказывается сложнее, чем простейшая неоднозначная грамматика дляданного языка. Существуют также некоторые КС-языки, обычно специально сконструированные, которые являются существенно неоднозначными, т.е.
все грамматики для этих языков неоднозначны.♦ Синтаксические анализаторы. Контекстно-свободная грамматика является основным понятием для реализации компиляторов и других процессоров языковпрограммирования. Инструментальные средства, вроде YACC, получают на входКС-грамматику и порождают синтаксический анализатор — часть компилятора,распознающую структуру компилируемых программ.♦ Определения типа документа.
Развивающийся стандарт XML для распределенияинформации посредством Web-документов имеет нотацию, называемую DTD, дляописания структуры таких документов. Для этого в документ записываются вложенные семантические дескрипторы. DTD является, по существу, КС-грамматикой,язык которой — это класс связанных с этим определением документов.ËèòåðàòóðàКонтекстно-свободная грамматика была впервые предложена Хомским как способописания естественных языков в [4].
Бэкус и Наур вскоре использовали подобную идеюдля описания машинных языков Фортран [2] и Алгол [7]. В результате КС-грамматикииногда называются “формами Бэкуса-Наура”, или БНФ.230Стр. 230ÃËÀÂÀ 5. ÊÎÍÒÅÊÑÒÍÎ-ÑÂÎÁÎÄÍÛÅ ÃÐÀÌÌÀÒÈÊÈ È ßÇÛÊÈНеоднозначность в грамматиках была выделена в качестве проблемы почти одновременно Кантором [3] и Флойдом [5]. Существенная неоднозначность была впервые указана Гроссом [6].О приложениях КС-грамматик в компиляции рекомендуем прочитать в [1]. DTD описаны в документе о стандартах XML [8].1.A. V.
![](https://s.studizba.com/z.php?f=/templates/si/i/noavatar.png&w=100&h=100&t=1"){kind=avatar}
