Хопкрофт, Джон, Э., Мотвани, Раджив, Ульман, Джеффри, Д. - Введение в теорию автоматов, языков и вычислений (1082271), страница 45
Текст из файла (страница 45)
КС-грамматика называется нравалинейнай, если тело каждой продукции имеет не более одной переменной, причем она находится на правом краю тела. Таким образом, продукции праволинейной грамматики имеют вид А — » и В или А — » н, где А и  — переменные, а зг — терминальная цепочка, возможно, пустая: а) докажите, что каждая праволинейная грамматика порождает регулярный язык. Указание. Постройте в-НКА, который имитирует левые порождения, представляя своим состоянием единственную переменную в текущей лево- выводимой цепочке; б) докажите, что каждый регулярный язык имеет праволинейную грамматику. Указание. Начните с ДКА, состояния которого представляются переменными грамматики.
5.1.5. (»!) Пусть Т= (О, 1, (, ), +, *, !а, е). Т можно рассматривать как множество символов, используемых в регулярных выражениях над алфавитом (О, 1). Единственная разница состоит в том, что во избежание возможной путаницы вместо символа в используется символ е. Постройте КС-грамматику со мцожеством терминалов Т, которая порождает в точности регулярные выражения в алфавите (О, 1). 5.1.6. Отношение =» было определено с базисом "а~ и' и индукцией, утверждавшей: "из а =» Д и Д ~ у следует гг =» У'. Есть несколько других способов опре- деления отношения ~, также равнозначных фразе; "=» есть нуль или несколь- ко шагов отношения ~".
Докажите следующие утверждения: а) а =» (! тогда и только тогда, когда существует последовательность из одной или нескольких цепочек ун у„ ..., у„ где п= уь )3 = у, и для ! = 1, 2, ..., и — ! имеет место у ~ у, ~', б) если а =» !В и (з =» у то а =» у. Указание, Воспользуйтесь индукцией по числу шагов в порождении Д =» у. 5.1.7. (1) Рассмотрим КС-грамматику б, определяемую следующими продукциями:  — эао!В»!а~а ГЛАВА 5. КОНТЕКСТНО-СВОБОДНЫЕ ГРАММАТИКИ И ЯЗЫКИ 196 а) докажите нндукцией по длине цепочки, что ни одна цепочка в ЦС) не содержит Ьа как подцепочку; б) дайте неформальное описание А(С). Уточните ответ, используя часть (а).
5.1.8. (11) Рассмотрим КС-грамматику С, определяемую следующими продукциями, о -з аЯЬБ ~ Ьоаб ( 8 Докажите, что ЦС) представляет собой множество всех цепочек, в которых поровну символов а и Ь. 5.2. Деревья разбора Для порождений существует чрезвычайно полезное представление в виде дерева. Это дерево наглядно показывает, каким образом символы цепочки группируются в подцепочки, каждая из которых принадлежит языку одной из переменных грамматики. Возкожно, более важно то, что дерево, известное в компиляции как "дерево разбора", является основной структурой данных для представления исходной программы. В компилязере древовидная структура исходной программы облегчает ее трансляцию в исполняеяый код за счет того, что допускает естественные рекурсивные функции для выполнения ззой трансляции.
В данном разделе представлено понятие дерева разбора и показано, что существование дерева разбора тесно связано с сушествованием порождений и рекурсивных выводов. Далее изучается сушность неоднозначности в грамматиках и языках, являюшейся южным свойством деревьев разбора. Некоторые грамматики допускают, что терминачьязя цепочка имеет несколько деревьев разбора. Такое свойство делает грамматику непригодной для описания языков программирования, поскольку в этом случае компилятор не мог бы распознать структуру некоторых исходных программ, н, как следствие, не мог 6ы однозначно определить исполняемый код, соответствующий программе. 5.2.1. Построение деревьев разбора Будем рассматривать грамматику С = (г', Т, Р, Е).
Деревья рпзбора для С вЂ” это дереяья со следующими свойствами. 1. Каждый внутренний узел отмечен переменной из К Каждый лист отмечен либо переменной, либо терминалом, либо д При этом, если лист отмечен л, он должен быть единственным сыном своего родителя. 3. Если внутренний узел отмечен А, и его сыновья отмечены слева направо Хо Хл ..., Хь соответственно, то А — эХХ, - Хя является продукцией в Р.
Отметим, что Х может быть к лишь в одном случае — если он отмечает единственного сына, и А — з я — продукция грамматики С, 666 ДЕРЕВЬЯ РАЗБОРА 197 Обзор терминов, связанных с деревьями Мы предполагаем, что читатель знаком с понятием дерева и основными определениями лля деревьев. Тем не менее, напомним их вкратце. ° Деревья представляют собой множества узлов с отношением родитель-сын.
Узел имеет не более одного родителя, изображаемого над узлом, и нуль нли несколько сыновей, изображаемых под ним. Родителей и нх сыновей соединяют линии, Примеры деревьев представлены на рис. 5,4-5.6. ° Один узел, корень, не имеет родителя; он появляется на вершине дерева. Узлы без сыновей называются листьями. Узлы, не являющиеся листьями, называются внутренн им и узлами.
° Сын сына и так далее узла называется его потомколн соответственно, родитель родителя и так далее — предком. Узлы считаются потомками и предками самих себя. ° Сыновья узла упорядочиваются слева направо и изображаются в этом порядке. Если узел Ю находится слева от узла М, то считается, что все потомки узла Ф находятся слева от всех потомков М. Рис. 5.4. Дерево разбора, показы- вающее порождение ! е Е из Е Рис. 5.5.
Дерево разбора, показы- воющее порождение Р ~ 03!О ГЛАВА б. КОНТЕКСТНО-СВОБОДНЫЕ ГРАММАТИКИ И ЯЗЫКИ Пример 5.9. На рис. 5.4 показано дерево разбора, которое использует грамматику выражений (см. рис. 5.2). Корень отмечен переменной Е. В корне применена продукция Е з Е + Е, поскольку три сына корня отмечены слева направо как Е, +, Е. В левом сыне корня применена продукция Š— з Е так как у этого узла один сын, отмеченный переменной Е П Пример 5.10. На рис. 5.5 показано дерево разбора для грамматики палиндромов (см. рис.
5.!). В корне применена продукция Р— з ОРО, а в среднем сыне корня — Р— з 1Р1. Отметим, что внизу использована продукция Р— з е. Это использование, при котором у узла есть сын с отметкой е, является единственным случаем, когда в дереве может быть узел, отмеченный а П 5.2.2. Крона дерева разбора Если мы посмотрим на листья любого дерева разбора и выпишем их отметки слева лвправо, то получим цепочку, которая называется кроной дерева и всегда является цепочкой, выводимой из переменной, отмечающей корень. Утверждение о том, что крона выводима из отметки корня, будет доказано далее.
Особый интерес представляют деревья разбора со следующими свойствами. Е Крона является терминальной цепочкой, т.е. все листья отмечены терминалами лли н 1. Корень отмечен стартовым символом. Кроны таких деревьев разбора представляют собой цепочки языка рассматриваемой грамматики. Мы докажем также, что еше один способ описания языка грамматики совтоит в определении его как множества крои тех деревьев разбора, у которых корень отмечен стартовым символом, а крона является терминальной цепочкой. Пример 5.11. На рис. 5.6 представлен пример дерева с терминальной цепочкой в калестве кроны и стартовым символом в корне. Оно основано на грамматике для выражеялй (см.
рис. 5.2). Крона этого дерева образует цепочку а * (а в ЬОО), выведенную в примере 5.6. В действительности, как мы увидим далее, это дерево разбора представляет порождение данной цепочки. П Рис. 5.б. Дерево разбора для а е ~а л ЬОО) в языке для грамматики выражений 199 1.2. ДЕРЕВЬЯ РАЗБОРА 5.2.3. Вывод, порождение и деревья разбора Каждый из способов, определенных ранее для описания работы грамматики, приводит по существу к одним и тем же утверждениям о цепочках.
Итак, покажем, что при любой грамматике б = (е', Т, Р, 5) следующие утверждения равносильны. 1. Процедура рекурсивного вывода определяет, что цепочка зе принадлежит языку переменной А. 3. А =» ю. м 4. А~и. 5. Существует дерево разбора с корнем А и кроной зв. В действительности, за исключением использования рекурсивного вывода, определенного только для терминальных цепочек, все остальные условия (супгествование порождений, левых и правых порождений нли деревьев разбора) также равносильны, если зе име- ет переменные.
Указанные равносильности доказываются в соответствии с планом, приведенным на рнс. 5.7. Для каждой стрелки в этой диаграмме доказывается теорема, которая утвержда- ет, что если зе удовлетворяет условию в начале стрелки, то удовлетворяет и условию в ее конце. Например, мы покажем в теореме 5.12, что если и принадлежит языку А в соответствии с рекурсивным выводом, то существует дерево разбора с корнем А и кроной м. Дерево ~ разбора Левое порождение Правое Рвкурсивный вывод рис. 5 7 доказательство ровноскльности утвержденна О ералсматикал Отметим, что две стрелки весьма просты и не будут обоснованы формально. Если цепочка зе имеет левое порождение из А, то она безусловно порождается из А, поскольку левое порождение является порождением.
Аналогично, если цепочка зе имеет правое порождение, то она имеет и порождение. Приступим к доказательству более трудных шагов описанной равносильности. ГЛАВА б. КОНТЕКСТНО-СВОБОДНЫЕ ГРАММАТИКИ И ЯЗЫКИ 200 5.2.4. От выводов к деревьям разбора Теорема 5.12. Пусть О = (1; Т, Р, 5) — КС-грамматика. Если рекурсивный вывод утверждает, что терминальная цепочка ли принадлежит языку переменной А, то существует дерево разбора с корнем А и кроной н. Доказательство.
Проведем доказательство индукцией по числу шагов„используемых а выводе того, что и принадлежит языку А. Базис. Вывод содержит один шаг. В этом случае использован только базис процедуры вывода, и в грамматике должна быть продукция А — ь ли. В дереве на рис. 5.8 существует лист для каждого символа цепочки ли, оно удовлетворяет условиям, налагаемым на дерево разбора для грамматики лз, и, очевидно, имеет корень А и крону ли. В особом случае, когда ли = а, дерево имеет только один лист, отмеченный а и является допустимым перелом разбора с корнем А и кроной и. Иидукцня.
Предположим, что факт принадлежности ги языку переменной А выводится за и+ 1 шаг, и что утверждение теоремы справедливо для всех цепочек х и переменвых В, для которых принадлежность х языку В была выведена с использованием и нли менее шагов вывода. Рассмотрим последний шаг вывода того, что ли принадлежит языку А. Этот вывод использует некоторую продукцшо для А, например А — ь ХХ,...Хь где ка- ждый Х, есть либо переменная, либо терминал. Цепочку и можно разбить на подцепочки и ~и з...
![](https://s.studizba.com/z.php?f=/templates/si/i/noavatar.png&w=100&h=100&t=1"){kind=avatar}
