Регулярные выражения и языки (стр. 24 )

Пример 5.11. На рис. 5.6 представлен пример дерева с терминальной цепочкой в ка­честве кроны и стартовым символом в корне. Оно основано на грамматике для выраже­ний (см. рис. 5.2). Крона этого дерева образует цепочку а * (а + 600), выведенную в при­мере 5.6. В действительности, как мы увидим далее, это дерево разбора представляет по­рождение данной цепочки. □

Е

Е

*

Е

I

Е

Е

а

+

I

Е

I

I

а

О

I

О

4

Рис. 5.6. Дерево разбора для а * (a + b00) в языке для грамматики выражений

5.2.3. Вывод, порождение и деревья разбора

Каждый из способов, определенных ранее для описания работы грамматики, приво­дит по существу к одним и тем же утверждениям о цепочках. Итак, покажем, что при любой грамматике G = (V, T, P,S) следующие утверждения равносильны.

Процедура рекурсивного вывода определяет, что цепочка w принадлежит языку пе­ременной/!.

*

3.

А

=> w. А => w.

w.

Правое порождение

Порождение

Рекурсивный вывод

Рис. 5.7. Доказательство равносильности утверждений о грамматиках

Отметим, что две стрелки весьма просты и не будут обоснованы формально. Если це­почка w имеет левое порождение из А, то она безусловно порождается из А, поскольку левое порождение является порождением. Аналогично, если цепочка w имеет правое по­рождение, то она имеет и порождение. Приступим к доказательству более трудных ша­гов описанной равносильности.

1т

4. А

5. Существует дерево разбора с корнем А и кроной w.

В действительности, за исключением использования рекурсивного вывода, определенно­го только для терминальных цепочек, все остальные условия (существование порожде­ний, левых и правых порождений или деревьев разбора) также равносильны, если w име­ет переменные.

Указанные равносильности доказываются в соответствии с планом, приведенным на рис. 5.7. Для каждой стрелки в этой диаграмме доказывается теорема, которая утвержда­ет, что если w удовлетворяет условию в начале стрелки, то удовлетворяет и условию в ее конце. Например, мы покажем в теореме 5.12, что если w принадлежит языку А в соот­ветствии с рекурсивным выводом, то существует дерево разбора с корнем А и кроной w.

Дерево ^^^^ разбора

Левое порождение

5.2.4. От выводов к деревьям разбора

Теорема 5.12. Пусть G = (V, Т, P, S) — КС-грамматика. Если рекурсивный вывод ут­верждает, что терминальная цепочка w принадлежит языку переменной А, то существует дерево разбора с корнем А и кроной w.

Доказательство. Проведем доказательство индукцией по числу шагов, используемых в выводе того, что w принадлежит языку А.

Базис. Вывод содержит один шаг. В этом случае использован только базис процеду­ры вывода, и в грамматике должна быть продукция A—>w. В дереве на рис. 5.8 сущест­вует лист для каждого символа цепочки w, оно удовлетворяет условиям, налагаемым на дерево разбора для грамматики G, и, очевидно, имеет корень А и крону w. В особом слу­чае, когда w = Ј, дерево имеет только один лист, отмеченный е, и является допустимым деревом разбора с корнем А и кроной w.

Индукция. Предположим, что факт принадлежности w языку переменной А выводит­ся за п + 1 шаг, и что утверждение теоремы справедливо для всех цепочек х и перемен­ных В, для которых принадлежность х языку В была выведена с использованием п или менее шагов вывода. Рассмотрим последний шаг вывода того, что w принадлежит языку А. Этот вывод использует некоторую продукцию для А, например А —> XtX2...Xb где ка­ждый X, есть либо переменная, либо терминал.

Цепочку w можно разбить на подцепочки w, w2. ..Wk, для которых справедливо следующее.

Если Xj является терминалом, то w, = X,, т. е. w, представляет собой один - единственный терминал из продукции.

Если X) — переменная, то w, представляет собой цепочку, о которой уже сделан вы­вод, что она принадлежит языку переменной Xt. Таким образом, этот вывод относи­тельно и>; содержит не более п из п + 1 шагов вывода, что w принадлежит языку А. Этот вывод не может содержать все п+ 1 шагов, поскольку заключительный шаг, использующий продукцию А —>X^-.-Xh, безусловно, не является частью вывода относительно w,. Следовательно, мы можем применить предположение индукции к w, и заключить, что существует дерево разбора с кроной w, и корнем X,.

Рис. 5.8. Дерево, построенное для базиса Рис. 5.9. Дерево, использованное в индуктив - теоремы 5.12        ной части доказательства теоремы 5.12

Далее мы построим дерево с корнем А и кроной w в соответствии с рис. 5.9. Там по­казан корень с отметкой А и сыновьями X), Х2, ..., Хк. Такой выбор отметок возможен, поскольку Л —> Х, Х2.. .Хк является продукцией грамматики G.

Узел для каждого X, становится корнем поддерева с кроной w,. В ситуации 1, где X, — терминал, это поддерево состоит из одного листа, отмеченного X,. Так как в данной си­туации w,=Xi, условия того, что кроной поддерева является w,, выполнены.

Во второй ситуации X, является переменной. Тогда по предположению индукции су­ществует дерево с корнем X, и кроной w,. Оно присоединяется к узлу для X, (см. рис. 5.9).

Построенное таким образом дерево имеет корень А. Его крона состоит из крон под­деревьев, приписанных друг к другу слева направо, т. е. w = wtw2...wk. □

5.2.5. От деревьев к порождениям

Покажем, как построить левое порождение по дереву разбора (метод построения пра­вого порождения аналогичен и не приводится). Для того чтобы понять, каким образом можно построить левое порождение, сначала нужно увидеть, как одно порождение це­почки из переменной можно вставить внутрь другого порождения. Проиллюстрируем это на примере.

Пример 5.13. Рассмотрим еще раз грамматику выражений (см. рис. 5.2). Нетрудно убедиться, что существует следующее порождение.

Ј=>/=> lb ab

Отсюда для произвольных цепочек а и /3 возможно следующее порождение.

аЕ(3 аф=> alb/3 => aab/3 Доказательством служит то, что головы продукций можно заменять их телами в контек­сте а и /3 точно так же, как и вне его.14

Например, если порождение начинается заменами Ј=>Ј + Ј=>Ј + (Ј), то можно было бы применить порождение цепочки ab из второго Ј, рассматривая "Ј+(" в качестве а и ")" — Д Указанное порождение затем продолжалось бы следующим образом. Ј+(Ј)=>Ј + (/)=>Ј + (lb) => Ј + (ab)

□

Теперь можно доказать теорему, позволяющую преобразовывать дерево разбора в левое порождение. Доказательство проводится индукцией по высоте дерева, которая представля­ет собой максимальную из длин путей, ведущих от корня через его потомков к листьям.

Например, высота дерева, изображенного на рис. 5.6, равна 7. Самый длинный из путей от корня к листьям ведет к листу, отмеченному Ь. Заметим, что длины путей обычно учиты­вают ребра, а не узлы, поэтому путь, состоящий из единственного узла, имеет длину 0.

Теорема 5.14. Пусть G = (V, Т, P, S) — КС-грамматика. Предположим, что существу­ет дерево разбора с корнем, отмеченным А, и кроной w, где we 7*. Тогда в грамматике G

существует левое порождение А => w.

lm

Доказательство. Используем индукцию по высоте дерева.

Базис. Базисом является высота 1, наименьшая из возможных для дерева разбора с терминальной кроной. Дерево должно выглядеть, как на рис. 5.8, с корнем, отмеченным А, и сыновьями, образующими цепочку w. Поскольку это дерево является деревом раз­бора, А —> w должно быть продукцией. Таким образом, А => w есть одношаговое левое

lm

порождение w из А.

Индукция. Если высота дерева равна п, где п> 1, то оно должно иметь вид, как на рис. 5.9. Таким образом, существует корень с отметкой А и сыновьями, отмеченными слева направоХ/Х2...Хк. Символы Смогут быть как терминалами, так и переменными.

Если X] — терминал, то определим w, как цепочку, состоящую из одного X,. Если X, — переменная, то она должна быть корнем некоторого поддерева с терми­нальной кроной, которую обозначим w,. Заметим, что в этом случае высота поддере­ва меньше п, поэтому к нему применимо предположение индукции. Следовательно,

•

существует левое порождение X, => w,.

lm

Заметим, что w = и>/и^...и>/;..

Построим левое порождение цепочки w следующим образом. Начнем с шага А => Х, Х2. ■ Хк. Затем для / = 1,2,..., к покажем, что имеет место следующее порождение.

lm

*

А => w, w2...wiX^1Xi+2...Xk

lm

Данное доказательство использует в действительности еще одну индукцию, на этот раз по (. Для базиса /'= 0 мы уже знаем, что А => XjX2.. .Х^ Для индукции предположим, что

lm

существует следующее порождение. А WjW2...w./XX,■!■■ Хк

lm

1. Если X,— терминал, то не делаем ничего, но в дальнейшем рассматриваем X, как терминальную цепочку W/. Таким образом, приходим к существованию следующего порождения. .

А w/w2...wjXi4XM...Xk

2. Если Xi является переменной, то продолжаем порождением vv, из X, в контексте уже построенного порождения. Таким образом, если этим порождением является

Xi => а; =» а2... wh

Im        1т        1т

то продолжаем следующими порождениями. Wiw2...wl4XlXi+,...Xk =>

Im

w, w2...wi-, a, Xi4...Xk =»

Im

W, W2... Wi уСЫС - ,...Xk =>

Im