dzhon_khopkroft_radzhiv_motvani_dzheffri _ulman_vvedenie_v_teoriyu_avtomatov_yazy kov_i_vychisleniy_2008 (852747), страница 45

Просмтор этого файла доступен только зарегистрированным пользователям. Но у нас супер быстрая регистрация: достаточно только электронной почты!

Текст из файла (страница 45)

ÊÎÍÒÅÊÑÒÍÎ-ÑÂÎÁÎÄÍÛÅ ÃÐÀÌÌÀÒÈÊÈСтр. 195195б) 1001;в) 00011.5.1.3.Докажите, что каждый регулярный язык является КС-языком. Указание. Постройте КС-грамматику с помощью индукции по числу операторов в регулярном выражении.5.1.4.КС-грамматика называется праволинейной, если тело каждой продукции имеетне более одной переменной, причем она находится на правом краю тела. Такимобразом, продукции праволинейной грамматики имеют вид A → wB или A → w,где A и B — переменные, а w — терминальная цепочка, возможно, пустая:а) докажите, что каждая праволинейная грамматика порождает регулярныйязык. Указание.

Постройте ε-НКА, который имитирует левые порождения,представляя своим состоянием единственную переменную в текущей левовыводимой цепочке;б) докажите, что каждый регулярный язык имеет праволинейную грамматику.Указание. Начните с ДКА, состояния которого представляются переменнымиграмматики.5.1.5.(∗!) Пусть T = {0, 1, (, ), +, *, ∅, e}. T можно рассматривать как множествосимволов, используемых в регулярных выражениях над алфавитом {0, 1}.Единственная разница состоит в том, что во избежание возможной путаницывместо символа ε используется символ e. Постройте КС-грамматику со множеством терминалов T, которая порождает в точности регулярные выраженияв алфавите {0, 1}.5.1.6.Отношение ⇒ было определено с базисом “α ⇒ α” и индукцией, утверждав-***шей: “из α ⇒ β и β ⇒ γ следует α ⇒ γ”.

Есть несколько других способов опре**деления отношения ⇒ , также равнозначных фразе: “ ⇒ есть нуль или несколько шагов отношения ⇒”. Докажите следующие утверждения:*а) α ⇒ β тогда и только тогда, когда существует последовательность из однойили нескольких цепочек γ1, γ2, …, γn где α = γ1, β = γn и для i = 1, 2, …, n – 1имеет место γi ⇒ γi+1;***б) если α ⇒ β и β ⇒ γ, то α ⇒ γ. Указание. Воспользуйтесь индукцией по*числу шагов в порождении β ⇒ γ.5.1.7.(!) Рассмотрим КС-грамматику G, определяемую следующими продукциями:S → aS | Sb | a | b196Стр.

196ÃËÀÂÀ 5. ÊÎÍÒÅÊÑÒÍÎ-ÑÂÎÁÎÄÍÛÅ ÃÐÀÌÌÀÒÈÊÈ È ßÇÛÊÈа) докажите индукцией по длине цепочки, что ни одна цепочка в L(G) не содержит ba как подцепочку;б) дайте неформальное описание L(G). Уточните ответ, используя часть (a).5.1.8.(!!) Рассмотрим КС-грамматику G, определяемую следующими продукциями.S → aSbS | bSaS | εДокажите, что L(G) представляет собой множество всех цепочек, в которых поровну символов a и b.5.2. Äåðåâüÿ ðàçáîðàДля порождений существует чрезвычайно полезное представление в виде дерева.

Этодерево наглядно показывает, каким образом символы цепочки группируются в подцепочки, каждая из которых принадлежит языку одной из переменных грамматики. Возможно, более важно то, что дерево, известное в компиляции как “дерево разбора”, является основной структурой данных для представления исходной программы. В компиляторе древовидная структура исходной программы облегчает ее трансляцию в исполняемый код за счет того, что допускает естественные рекурсивные функции для выполненияэтой трансляции.В данном разделе представлено понятие дерева разбора и показано, что существование дерева разбора тесно связано с существованием порождений и рекурсивных выводов. Далее изучается сущность неоднозначности в грамматиках и языках, являющейсяважным свойством деревьев разбора.

Некоторые грамматики допускают, что терминальная цепочка имеет несколько деревьев разбора. Такое свойство делает грамматику непригодной для описания языков программирования, поскольку в этом случае компиляторне мог бы распознать структуру некоторых исходных программ, и, как следствие, не могбы однозначно определить исполняемый код, соответствующий программе.5.2.1. Ïîñòðîåíèå äåðåâüåâ ðàçáîðàБудем рассматривать грамматику G = (V, T, P, S). Деревья разбора для G — это деревья со следующими свойствами.1.Каждый внутренний узел отмечен переменной из V.2.Каждый лист отмечен либо переменной, либо терминалом, либо ε. При этом, еслилист отмечен ε, он должен быть единственным сыном своего родителя.3.Если внутренний узел отмечен A, и его сыновья отмечены слева направо X1, X2, …,Xk, соответственно, то A → X1X2 ⋅⋅⋅ Xk является продукцией в P.

Отметим, что X может быть ε лишь в одном случае — если он отмечает единственного сына, иA → ε — продукция грамматики G.5.2. ÄÅÐÅÂÜß ÐÀÇÁÎÐÀСтр. 197197Îáçîð òåðìèíîâ, ñâÿçàííûõ ñ äåðåâüÿìèМы предполагаем, что читатель знаком с понятием дерева и основными определениями для деревьев. Тем не менее, напомним их вкратце.• Деревья представляют собой множества узлов с отношением родитель-сын.

Узелимеет не более одного родителя, изображаемого над узлом, и нуль или несколькосыновей, изображаемых под ним. Родителей и их сыновей соединяют линии.Примеры деревьев представлены на рис. 5.4–5.6.• Один узел, корень, не имеет родителя; он появляется на вершине дерева. Узлы безсыновей называются листьями. Узлы, не являющиеся листьями, называютсявнутренними узлами.• Сын сына и так далее узла называется его потомком; соответственно, родитель родителя и так далее — предком. Узлы считаются потомками и предкамисамих себя.• Сыновья узла упорядочиваются слева направо и изображаются в этом порядке.Если узел N находится слева от узла M, то считается, что все потомки узла N находятся слева от всех потомков M.Пример 5.9.

На рис. 5.4 показано дерево разбора, которое использует грамматикувыражений (см. рис. 5.2). Корень отмечен переменной E. В корне применена продукция E → E + E, поскольку три сына корня отмечены слева направо как E, +, E. В левомсыне корня применена продукция E → I, так как у этого узла один сын, отмеченныйпеременной I. †Пример 5.10. На рис. 5.5 показано дерево разбора для грамматики палиндромов (см.рис. 5.1). В корне применена продукция P → 0P0, а в среднем сыне корня — P → 1P1.Отметим, что внизу использована продукция P → ε. Это использование, при котором уузла есть сын с отметкой ε, является единственным случаем, когда в дереве может бытьузел, отмеченный ε. †+εРис. 5.4. Дерево разбора, показывающее порождение I + E из E198Стр.

198Рис. 5.5. Дерево разбора, показы*вающее порождение P ⇒ 0110ÃËÀÂÀ 5. ÊÎÍÒÅÊÑÒÍÎ-ÑÂÎÁÎÄÍÛÅ ÃÐÀÌÌÀÒÈÊÈ È ßÇÛÊÈ5.2.2. Êðîíà äåðåâà ðàçáîðàЕсли мы посмотрим на листья любого дерева разбора и выпишем их отметки слеванаправо, то получим цепочку, которая называется кроной дерева и всегда является цепочкой, выводимой из переменной, отмечающей корень.

Утверждение о том, что кронавыводима из отметки корня, будет доказано далее. Особый интерес представляют деревья разбора со следующими свойствами.1.Крона является терминальной цепочкой, т.е. все листья отмечены терминаламиили ε.2.Корень отмечен стартовым символом.Кроны таких деревьев разбора представляют собой цепочки языка рассматриваемойграмматики.

Мы докажем также, что еще один способ описания языка грамматики состоит в определении его как множества крон тех деревьев разбора, у которых корень отмечен стартовым символом, а крона является терминальной цепочкой.Пример 5.11. На рис. 5.6 представлен пример дерева с терминальной цепочкой в качестве кроны и стартовым символом в корне. Оно основано на грамматике для выражений (см. рис. 5.2).

Крона этого дерева образует цепочку a * (a + b00), выведенную в примере 5.6. В действительности, как мы увидим далее, это дерево разбора представляет порождение данной цепочки. †∗+Рис. 5.6. Дерево разбора для a * (a + b00) в языке для грамматики выражений5.2. ÄÅÐÅÂÜß ÐÀÇÁÎÐÀСтр. 1991995.2.3.

Âûâîä, ïîðîæäåíèå è äåðåâüÿ ðàçáîðàКаждый из способов, определенных ранее для описания работы грамматики, приводит по существу к одним и тем же утверждениям о цепочках. Итак, покажем, что прилюбой грамматике G = (V, T, P, S) следующие утверждения равносильны.1.Процедура рекурсивного вывода определяет, что цепочка w принадлежит языку переменной A.2.A ⇒ w.3.A ⇒ w.4.A ⇒ w.5.Существует дерево разбора с корнем A и кроной w.**lm*rmВ действительности, за исключением использования рекурсивного вывода, определенного только для терминальных цепочек, все остальные условия (существование порождений, левых и правых порождений или деревьев разбора) также равносильны, если w имеет переменные.Указанные равносильности доказываются в соответствии с планом, приведенным нарис.

5.7. Для каждой стрелки в этой диаграмме доказывается теорема, которая утверждает, что если w удовлетворяет условию в начале стрелки, то удовлетворяет и условию в ееконце. Например, мы покажем в теореме 5.12, что если w принадлежит языку A в соответствии с рекурсивным выводом, то существует дерево разбора с корнем A и кроной w.ДереворазбораЛевоепорождениеПорождениеПравоепорождениеРекурсивныйвыводРис. 5.7. Доказательство равносильности утверждений о грамматикахОтметим, что две стрелки весьма просты и не будут обоснованы формально. Если цепочка w имеет левое порождение из A, то она безусловно порождается из A, посколькулевое порождение является порождением.

Характеристики

Список файлов книги