dzhon_khopkroft_radzhiv_motvani_dzheffri _ulman_vvedenie_v_teoriyu_avtomatov_yazy kov_i_vychisleniy_2008 (852747), страница 46
Текст из файла (страница 46)
Аналогично, если цепочка w имеет правое порождение, то она имеет и порождение. Приступим к доказательству более трудных шагов описанной равносильности.200Стр. 200ÃËÀÂÀ 5. ÊÎÍÒÅÊÑÒÍÎ-ÑÂÎÁÎÄÍÛÅ ÃÐÀÌÌÀÒÈÊÈ È ßÇÛÊÈ5.2.4. Îò âûâîäîâ ê äåðåâüÿì ðàçáîðàТеорема 5.12. Пусть G = (V, T, P, S) — КС-грамматика. Если рекурсивный вывод утверждает, что терминальная цепочка w принадлежит языку переменной A, то существуетдерево разбора с корнем A и кроной w.Доказательство. Проведем доказательство индукцией по числу шагов, используемыхв выводе того, что w принадлежит языку A.Базис.
Вывод содержит один шаг. В этом случае использован только базис процедуры вывода, и в грамматике должна быть продукция A → w. В дереве на рис. 5.8 существует лист для каждого символа цепочки w, оно удовлетворяет условиям, налагаемым надерево разбора для грамматики G, и, очевидно, имеет корень A и крону w. В особом случае, когда w = ε, дерево имеет только один лист, отмеченный ε, и является допустимымдеревом разбора с корнем A и кроной w.Индукция. Предположим, что факт принадлежности w языку переменной A выводится за n + 1 шаг, и что утверждение теоремы справедливо для всех цепочек x и переменных B, для которых принадлежность x языку B была выведена с использованием n илименее шагов вывода. Рассмотрим последний шаг вывода того, что w принадлежит языкуA. Этот вывод использует некоторую продукцию для A, например A → X1X2…Xk, где каждый Xi есть либо переменная, либо терминал.Цепочку w можно разбить на подцепочки w1w2…wk, для которых справедливо следующее.1.Если Xi является терминалом, то wi = Xi, т.е.
wi представляет собой одинединственный терминал из продукции.2.Если Xi — переменная, то wi представляет собой цепочку, о которой уже сделан вывод, что она принадлежит языку переменной Xi. Таким образом, этот вывод относительно wi содержит не более n из n + 1 шагов вывода, что w принадлежит языку A.Этот вывод не может содержать все n + 1 шагов, поскольку заключительный шаг,использующий продукцию A → X1X2…Xk, безусловно, не является частью выводаотносительно wi. Следовательно, мы можем применить предположение индукции кwi и заключить, что существует дерево разбора с кроной wi и корнем Xi.Рис.
5.8. Дерево, построенное для базисатеоремы 5.125.2. ÄÅÐÅÂÜß ÐÀÇÁÎÐÀСтр. 201Рис. 5.9. Дерево, использованное в индуктивной части доказательства теоремы 5.12201Далее мы построим дерево с корнем A и кроной w в соответствии с рис. 5.9. Там показан корень с отметкой A и сыновьями X1, X2, …, Xk. Такой выбор отметок возможен,поскольку A → X1X2…Xk является продукцией грамматики G.Узел для каждого Xi становится корнем поддерева с кроной wi.
В ситуации 1, где Xi —терминал, это поддерево состоит из одного листа, отмеченного Xi. Так как в данной ситуации wi = Xi, условия того, что кроной поддерева является wi, выполнены.Во второй ситуации Xi является переменной. Тогда по предположению индукции существует дерево с корнем Xi и кроной wi. Оно присоединяется к узлу для Xi (см. рис. 5.9).Построенное таким образом дерево имеет корень A.
Его крона состоит из крон поддеревьев, приписанных друг к другу слева направо, т.е. w = w1w2…wk. 5.2.5. Îò äåðåâüåâ ê ïîðîæäåíèÿìПокажем, как построить левое порождение по дереву разбора (метод построения правого порождения аналогичен и не приводится). Для того чтобы понять, каким образомможно построить левое порождение, сначала нужно увидеть, как одно порождение цепочки из переменной можно вставить внутрь другого порождения.
Проиллюстрируемэто на примере.Пример 5.13. Рассмотрим еще раз грамматику выражений (см. рис. 5.2). Нетрудноубедиться, что существует следующее порождение.E ⇒ I ⇒ Ib ⇒ abОтсюда для произвольных цепочек α и β возможно следующее порождение.αEβ ⇒ αIβ ⇒ αIbβ ⇒ αabβДоказательством служит то, что головы продукций можно заменять их телами в контексте α и β точно так же, как и вне его.1Например, если порождение начинается заменами E ⇒ E + E ⇒ E + (E), то можнобыло бы применить порождение цепочки ab из второго E, рассматривая “E+(” в качествеα и “)” — β. Указанное порождение затем продолжалось бы следующим образом.E + (E) ⇒ E + (I) ⇒ E + (Ib) ⇒ E + (ab)Теперь можно доказать теорему, позволяющую преобразовывать дерево разбора в левоепорождение.
Доказательство проводится индукцией по высоте дерева, которая представля-1В действительности, именно эта возможность подстановки строки вместо переменной независимо от контекста и породила название “контекстно-свободная” (context-free). Существует болеемощный класс грамматик, называемых “контекстно-зависимыми” (context-sensitive), в которыхподстановки разрешены, только если определенные строки находятся слева и/или справа от заменяемой переменной.
В современной практике контекстно-зависимые грамматики большого значения не имеют.202Стр. 202ÃËÀÂÀ 5. ÊÎÍÒÅÊÑÒÍÎ-ÑÂÎÁÎÄÍÛÅ ÃÐÀÌÌÀÒÈÊÈ È ßÇÛÊÈет собой максимальную из длин путей, ведущих от корня через его потомков к листьям.Например, высота дерева, изображенного на рис. 5.6, равна 7. Самый длинный из путей откорня к листьям ведет к листу, отмеченному b. Заметим, что длины путей обычно учитывают ребра, а не узлы, поэтому путь, состоящий из единственного узла, имеет длину 0.Теорема 5.14.
Пусть G = (V, T, P, S) — КС-грамматика. Предположим, что существует дерево разбора с корнем, отмеченным A, и кроной w, где w ∈ T*. Тогда в грамматике G*существует левое порождение A ⇒ w.lmДоказательство. Используем индукцию по высоте дерева.Базис. Базисом является высота 1, наименьшая из возможных для дерева разбора стерминальной кроной. Дерево должно выглядеть, как на рис. 5.8, с корнем, отмеченнымA, и сыновьями, образующими цепочку w. Поскольку это дерево является деревом разбора, A → w должно быть продукцией. Таким образом, A ⇒ w есть одношаговое левоеlmпорождение w из A.Индукция. Если высота дерева равна n, где n > 1, то оно должно иметь вид, как нарис. 5.9. Таким образом, существует корень с отметкой A и сыновьями, отмеченнымислева направо X1X2…Xk. Символы X могут быть как терминалами, так и переменными.1.Если Xi — терминал, то определим wi как цепочку, состоящую из одного Xi.2.Если Xi — переменная, то она должна быть корнем некоторого поддерева с терминальной кроной, которую обозначим wi.
Заметим, что в этом случае высота поддерева меньше n, поэтому к нему применимо предположение индукции. Следовательно,*существует левое порождение Xi ⇒ wi.lmЗаметим, что w = w1w2…wk.Построим левое порождение цепочки w следующим образом.
Начнем с шагаA ⇒ X1X2…Xk. Затем для i = 1, 2, …, k покажем, что имеет место следующее порождение.lm*A ⇒ w1w2…wiXi+1Xi+2…XklmДанное доказательство использует в действительности еще одну индукцию, на этот разпо i. Для базиса i = 0 мы уже знаем, что A ⇒ X1X2…Xk. Для индукции предположим, чтоlmсуществует следующее порождение.*A ⇒ w1w2…wi–1XiXi+1…Xklm1.Если Xi — терминал, то не делаем ничего, но в дальнейшем рассматриваем Xi кактерминальную цепочку wi.
Таким образом, приходим к существованию следующегопорождения.5.2. ÄÅÐÅÂÜß ÐÀÇÁÎÐÀСтр. 203203*A ⇒ w1w2…wiXi+1Xi+2…XklmЕсли Xi является переменной, то продолжаем порождением wi из Xi в контексте ужепостроенного порождения. Таким образом, если этим порождением является2.Xi ⇒ α1 ⇒ α2 … ⇒ wi,lmlmlmто продолжаем следующими порождениями.w1w2…wi–1XiXi+1…Xk ⇒lmw1w2…wi–1α1Xi+1…Xk ⇒lmw1w2…wi–1α2Xi+1…Xk ⇒lm…w1w2…wiXi+1Xi+2…Xk*Результатом является порождение A ⇒ w1w2…wiXi+1Xi+2…Xk.lmКогда i = k, результат представляет собой левое порождение w из A. Пример 5.15.
Рассмотрим левое порождение для дерева, изображенного на рис. 5.6. Продемонстрируем лишь заключительный шаг, на котором строится порождение по целому дереву из порождений, соответствующих поддеревьям корня. Итак, предположим, что с помощьюрекурсивного применения техники из теоремы 5.14 мы убедились, что поддерево, корнем которого является левый сын корня дерева, имеет левое порождение E ⇒ I ⇒ a, а поддерево сlmlmкорнем в третьем сыне корня имеет следующее левое порождение.E ⇒ (E) ⇒ (E + E) ⇒ (I + E) ⇒ (a + E) ⇒lmlmlmlmlm(a + I) ⇒ (a + I0) ⇒ (a + I00) ⇒ (a + b00)lmlmlmЧтобы построить левое порождение для целого дерева, начинаем с шага в корне:A ⇒ E * E.
Затем заменяем первую переменную E и в соответствии с ее порождениемlmприписываем на каждом шаге *E, чтобы учесть контекст, в котором это порождение используется. Левое порождение на текущий момент представляет собой следующее.E ⇒ E*E ⇒ I*E ⇒ a*ElmlmlmСимвол * в продукции, использованной в корне, не требует порождения, поэтому указанное левое порождение также учитывает первые два сына корня. Дополним левое по*рождение, используя порождение E ⇒ (a + b00), левый контекст которого образован цеlmпочкой a*, а правый пуст. Это порождение в действительности появлялось в примере 5.6и имело следующий вид.204Стр.
![](https://s.studizba.com/z.php?f=/templates/si/i/noavatar.png&w=100&h=100&t=1"){kind=avatar}
