Хопкрофт, Джон, Э., Мотвани, Раджив, Ульман, Джеффри, Д. - Введение в теорию автоматов, языков и вычислений (1082271), страница 46
Текст из файла (страница 46)
и „, для которых справедливо следующее. 1. Если Х, является терминалом, то ле, =Х, т.е. и, представляет собой одинединственный терминал из продукции. Если Х вЂ” переменная, то и, представляет собой цепочку, о которой уже сделан вывод, что она принадлежит языку переменной Х. Таким образом, этот вывод относительно ли, содержит не более н из п+ 1 шагов вывода, что лв принадлежит языку А. Этот вывод не может содержать все п+ 1 шагов, поскольку заключительный шаг, использующий продукцию А — ьХХз...Хл, безусловно, не является частью вывода относительно ин Следовательно, мы можем применить предположение индукции к и, и заключить, что существует дерево разбора с кроной н, и корнем Х. Г/~ ЛЛ Л Рис.
5.9 Дерево, использованное в индуктив ной части доказательства теоремы 5.! 2 Рис. 5.8. Дерево, настроенное длл базиса теоремы 5.12 201 5.2. ДЕРЕВЬЯ РАЗБОРА Далее мы построим дерево с корнем А и кроной н в соответствии с рис. 5.9. Там показан корень с отметкой А и сыновьями Хп Хл ..., Х». Такой выбор отметок возможен, поскольку А — > ХХ,...Х» является продукцией грамматики б. Узел для каждого Х становится корнем поддерева с кроной жг В ситуации 1, где Х— терминал, это поддерево состоит из одного листа, отмеченного Х.
Так как в данной ситуации н, =Х, условия того, что кроной поддерева является н „выполнены. Во второй ситуации Х является переменной. Тогда по предположению индукции существует дерево с корнем Х и кроной ив Оно присоединяется к узлу для Х (см. рис. 5.9). Построенное таким образом дерево имеет корень А. Его крона состоит из крон поддеревьев, приписанных друг к другу слева направо, т.е. зк = н ~зкь .. зк».
П 5.2.5. От деревьев к порождениям Покажем, как построить левое порождение по дереву разбора (метод построения правого порождения аналогичен и не приводится). Для того чтобы понять, каким образом можно построить левое порождение, сначала нужно увидеть, как одно порождение цепочки из переменной можно вставить внутрь другого порождения. Проиллюстрируем это на примере. Пример 5.13.
Рассмотрим еще раз грамматику выражений (см. Рис. 5.2). Нетрудно убедиться, что существует следующее порождение. Е =о У ~ 1Ь =о аЬ Отсюда для произвольных цепочек а и )з возможно следующее порождение. аЕ,) =о а7)3 =е а!ЬД ~ ааЬД Доказательством служит то, что головы продукций можно заменять их телами в контексте а и Д точно так же, как и вне его.' Например, если порождение начинается заменами Е=» Е ь Е =о Е+(Е)„то можно было бы применить порождение цепочки аЬ из второго Е, рассматривая "Е»(*' в качестве а и ")" — ~3.
Указанное порождение затем продолжалось бы слелующим образом. Е ь (Е) =о Е ь (l) =е Е ь (1Ь) ~ Е в (аЬ) П Теперь можно доказать теорему, позволяющую преобразовывать дерево разбора в левое порождение. Доказательство проводится индукцией по высоте дерева, которая представляет собой максимальную из длин путей, ведущих от корня через его потомков к листьям. В действительности, именно зта возможность подстановки строки вместо переменной независимо от контекста н породила название "контекстно-свободная*' (соп»аггее).
Существует более мощный класс грамматик, называемых "контекстно-зависимыми" (соп»ехьзепзйгве), в которых подстановки разрешены, только если определенные строки находятся слева н!нлн справа от заменяемой переменной. В современной практике контекстно-завнснмые грамматики большого значе- ння не имеют. 202 ГЛАВА б. КОНТЕКСТНО-СВОБОДНЫЕ ГРАММАТИКИ И ЯЗЫКИ Нц»ример, высота дерева, изображенного на рис. 5.6, равна 7. Самый длинный из путей от корня к листьям ведет к листу, отмеченному Ь.
Заметим, что длины путей обычно учитыюют ребра, а не узлы, поэтому путь, состоящий из единственного узла, имеет длину О. Теорема 5.14. Пусть П = (1», Т, Р, .9) — КС-грамматика. Предположим, что существует дерево разбора с корнем, отмеченным А, и кроной и, где и ц Т . Тогда в грамматике»г существует левое порождение А =»»г. ! Доказательство. Используем индукцию по высоте дерева.
Базис. Базисом является высота 1, наименьшая из возможных для дерева разбора с терминальной кроной. Дерево должно выглядеть, как на рис. 5.8, с корнем, отмеченным А, и сыновьями, образующими цепочку ж. Поскольку это дерево является деревом разбора, А — » ж должно быть продукцией. Таким образом, А =ь ж есть одношаговое левое / порождение»г из А. Индукция. Если высота дерева равна л, где л > 1, то оно должно иметь вид, как на ряс.
558 Таким образом, существует корень с отметкой А и сыновьями, отмеченными слева направо ХХ,...Х». Символы Х могут быть как терминалами, так и переменными. !. Если Х вЂ” терминал„то определим н, как цепочку, состоящую из одного Х. 2. Если Х, — переменная, то она должна быть корнем некоторого поддерева с терминальной кроной, которую обозначим и;. Заметим, что в этом случае высота поддерева меньше п, поэтому к нему применимо предположение индукции.
Следовательно, существует левое порождение Х =ь и,. !т Залегши, ятом=и,и ...»». Построим левое порождение цепочки»г следующим образом. Начнем с шага А =» ХХ,...Х». Затем для» = 1, 2, ..., I» покажем, что имеет место следующее порождение. ь А =» и»»гг...и',Х~-»Х-»...Х» Данное доказательство использует в действительности еще одну индукцию, на этот раз по!. Для базиса» = О мы уже знаем, что А =» Х,Хг...Х». Для индукции предположим, что м существует следующее порождение.
А =»»г,»гг...и, »ХХ, »...Х» I 1. Если Х вЂ” терминал, то не делаем ничего, но в дальнейшем рассматриваем Х как терминальную цепочку н» Таким образом, приходим к существованию следующего порождения. А ~ »г»»гг...иХ,.»Х,-»...Х» 203 5.2.ДЕРЕВЬЯ РАЗБОРА 2. Если Х является переменной, то продолжаем порождением и, из Х, в контексте уже построенного порождения.
Таким образом, если этим порождением является Х =» а, =» а, ... =»»»„ й, й ! то продолжаем следующими порождениями. гггн'г...г» -гХЛ'-!".Хг =» и игиг...ийгагХ.!...Хг ~ и и'ги'г...и', гагЛ,. г...Х» =» ! и'ги'г...и',Л,-гХ г...Х» Результатом является порождение А =»»»гггг...г»,Х гХ г...Х». и Когда ! = Ц результат представляет собой левое порождение гг из А. С) Пример 5.15.
Рассмотрим левое порождение для дерева, изображенного на рис. 5.6. Продемонстрируем лишь заключительный шаг, на котором строится порождение по целому дереву из порождений, соответствующих поддеревьям корня. Итак, предположим, что с помощью рекурсивного применения техники из теоремы 5.14 мы убедились, что поддерево, корнем которого является левый сын корня дерева, имеет левое порождение Е =» У =» а, а поддерево с корнем в третьем сыне корня имеет следующее ! и левое порождение. Е =» (Е) =» (Е+ Е) =» (У+ Е) =» (а+ Е) ~ ! и ! ! (а+У) =» (а+10) =» (а+100) =» (а»ЬОО) /ю и й Чтобы построить левое порождение для целого дерева, начинаем с шага в корне: А =» Е * Е. Затем заменяем первую переменную Е и в соответствии с ее порождением приписываем на каждом шаге *Е, чтобы учесть контекст, в котором это порождение ис- пользуется.
Левое порождение на текущий момент представляет собой следующее. Е =» Е Е » 1» Е » а» Е ! и и Символ * в продукции, использованной в корне, не требует порождения, поэтому указанное левое порождение также учитывает первые два сына корня. Дополним левое по- рождение, используя порождение Е =» (а+ ЬОО), левый контекст которого образован це! почкой а», а правый пуст. Это порождение в действительности появлялось в примере 5.6 и имело следующий вил. 204 ГЛАВА 6. КОНТЕКСТНО-СВОБОДНЫЕ ГРАММАТИКИ И ЯЗЫКИ Е ~ Е "' Е =» 1» Е =» а» Е =» а*(Е) =» а" (Е+Е) =» а*(1+Е) =» а*(а»Е) =» / / / / а * (а + 1) =» а» (а + 10) ~ а ' (а + 100) ~ а * (а + ЬОО) м / /ю Аналогичная теорема позволяет нам преобразовать дерево в правое порождение. Пас/роение правого порождения по дереву почти такое же, как и построение левого.
Здесь, однако, после первого шага А =» Х/Х/...Х/ мы заменяем сначала Хь используя правое порождение, затем Х,, и так далее до Х/. Таким образом, примем без доказательства следующее утверждение. Теорема 5.16. Пусть С = (//, 7; Р, Е) — КС-грамматика. Предположим, что существует дерево разбора с корнем, отмеченным А, и кроной /г, где /г и 7». Тогда в грамматике С существует правое порождениеА =» н. 52.6. От порождений к рекурсивным выводам Теперь завершим цикл, представленный на рис. 5.7, доказав, что если существует по- рождение А =» и для некоторой КС-грачматики, то факт принадлежности и языку А доказывается путем процедуры рекурсивного вывода. Перед тем как приводить теорему и ее доказательство, сделаем важные замечания о порождениях.
Предположим, у нас есть порождение А ~ Х/Х/...Х» =» и. Тогда и можно разбить на подцепочки и = и,и/,..ин где Х =» н,. Заметим, что если Х является терминалом, то н,=Х„и порождение имеет 0 шагов. Доказать это замечание несложно. Вы можете дока- зать индукцией по числу шагов порождения, что если ХХ,...Х„=» а, то все позиции в а„ происходящие от расширения Х, находятся слева от всех позиций, происходящих от расширенияХ, если / < 1. Если Х является переменной, то можно получить порождение Х =» и„начав с поро- жденияА ~ /г и отбрасывая следующее: а) все шаги, не относящиеся к порождению /г/ из Х; б) все позиции выводимой цепочки, которые находятся либо справа, либо слева от позиций, порождаемых из Хь Этот процесс поясняется примером. Пример 5.17. Используем грамматику выражений и рассмотрим следующее порождение.
![](https://s.studizba.com/z.php?f=/templates/si/i/noavatar.png&w=100&h=100&t=1"){kind=avatar}
