XIX Белоусов А.И., Ткачев СБ. Дискретная математика (1081422), страница 94
Текст из файла (страница 94)
Все выводы данной цепочки иэ данного нетерминала, по которым приведенный выше алгоритм дает одно и то же дерево вывода, будем называть энеиеалемпьнььмп. Среди эквивалентных выводов выделим два — левый вывод, в котором на каждом шаге заменяется самое левое вхождение нетермингльного символа; и правый вывод, когда на каждом шаге, напротив, производится замена самого правого вхождения не- терминала. Это значит, что при построении дерева вывода по левому выводу данной цепочки а из данного нетерминэла А каждый раз враэвертывается" в куст самый левый лист кроны частичного дерева вывода, помеченный нетерминальным символом, а при построении дерева вывода по правому выводу то же совершается с самым правым листом кроны.
Для построенного вьппе в примере 8.2.а дерева вывода левый вывод имеет вид Я1-АВС1-ВВВС~ССВВС~- ~ЬСВВС1-ЬЬВВС~-ЬбаВС1-ЬбааС1- 1- ЬбааАА )-ЬбааАА ~ ЬбааВВ ~ ЬбаааВ 1- Ьбаааа. 596 8. КОНТЕКСТНО-СВОБОДНЫЕ ЯЗЫКИ Правый вывод той же цепочки имеет вид Я 1- АВС 1- АВАА 1- АВАВВ 1- АВАВа 1- 1- АВАаа ~ АВ лаа 1- Аааа )- ВВааа 1- Ваааа ~ 1- ССаааа 1- СЬаааа 1- ЬЬаааа. В обоих выводах полужирным шрифтом выделены заменяемые вхождения нетерминалов, а также удалено возникающее после применения правила А — > А вхождение пустой цепочки Л. Можно показать, что эквивалентные выводы различаются между собой только порядком применения правил. Сами же применяемые правила и вхождения заменяемых нетерминалов у эквивалентных выводов одинаковы.
Мы часто будем использовать условное графическое обозначение дерева вывода А Д Х1Хз...Х,„в виде „треугольника", А одна иэ вершин которого помечена нетерминалом А, а противолежащая этой вершине сторона символизирует всю цепочку а = Х1Хз... Х~п. Иногда будем точками (или штрихами) отме- а чать отдельные символы цепочки а или листья абб с меткой Л (рис. 8.12). Кроме того, по традиции деревья выводов изображаются без стрелок на дугах (хотя понимаются как ориентированные деревья).
Из определения дерева вывода понятно, что в нем дуга из вершины с меткой Х ведет в вершину с меткой У тогда и только тогда, когда на некотором шаге вывода применяется правило вывода Х -~ у1Ууз, где у1 и уз — цепочки в объединенном алфавите (возможно, пустые). Следовательно, число дуг любого путпи ненулевой длины дерева вывода, т.е.
длина этого пути, есть не что иное, как число применений правил вывода заданной КС-грамматики в некотором фрагменте вывода. А так как в КС-грамматике каждое применение правила вывода есть замена вхождения нетерминала некоторой цепочкой в объединен- 8.1. КС-грамматики. Деревьв вывода. Однозначность 597 ном алфавите, то длина пути в дереве вывода равна числу замен нетерминалов в соответствующем фрагменте вывода.
Например, длл дерева, показанного на рис. 8.8, пути Я -+ А -+ В -+ а отвечает фрагмент вывода Я 1- АВС ~ ВВВС ~- ВаВС. Обратим внимание на то, что приведенный фрагмент есть фрагмент одного из множества эквивалентных выводов, имеющих данное дерево. Таким образом, по заданному пути в дереве вывода однозначно восстанавливаетсл фрагмент одного из множества эквивалентных выводов. Более того, по дереву вывода, построенному по одному из множества эквивалентных выводов, можно восстановить все выводы этого множества, в частности левый и правый. Можно показать, что длл этого необходимо задать определенный порядок посещения вершин дерева при поиске в глубпну от корня. Левый (соответственно правый) вывод будет восстановлен, если каждый раз при поиске в глубину от очередной вершины задавать продолжение поиска от самого левого (соответственно самого правого) сына этой вершины.
Замечание 8.2. Длина вывода в общем случае не меньше, чем высота дерева этого вывода. Можно доказать, что для фиксированной КС-грамматики 0 существует такая константа Со, зависящал от С, что длл любого вывода 1) (начинающегосл каким-либо нетерминалом) и дерева Т этого вывода разность между длиной 1р вывода П и высотой Ьт дерева Т не превышает Сбс 1~з - Ьт ( Со. Другими словами, разность между длиной вывода и высотой дерева вывода для фиксированной грамма тики ограничена сверху. Это обусловлено тем, что указанная разность определлется числом нетерминалов в правых частях правил вывода, которое в пределах заданной грамматики всегда ограничено. Это число, говоря неформально, определяет, как сильно „ветвится" дерево вывода в процессе его „роста".
Для линейной грамматики, как нетрудно сообразить, высота дерева вывода равна длине вывода. Однако если не фиксировать грамматику, то разность между длиной вывода и высотой 598 8. КОНТЕКСТНО-СВОБОДНЫЕ ЯЗЫКИ дерева вывода может быть сколь угодно болыпой. Это можно подтвердить таким простым примером. Рассмотрим семейство КС-грамматик ~~п = (Ка~ Жо~ В~ Ро~)~ где т> 1, К„=1а1, ...,а,„), Ф,„=(о',Вм ..., В,„), а множество правил вывода В„имеет вид В~ В1 "Во„В1-+а1>" ~Во,-+ао,. Грамматика 6,о порождает единственную терминальную це- ПОЧКУ а1...ао,. ВЫСОта ДЕРЕВа ВЫВОДа ЭтОй ЦЕПОЧКИ РаВНа 2 и не зависит от т (рис. 8.13), тогда как длина вывода определяется числом т+ 1.
Пусть фиксировано ориентированное дерево Т с корнем В. Выделим в нем произвольно вершину Я, не являющуюся ни листом, ни корнем, В~ Вз ' В, называемую внутренней вершиной дерева. Образуем поддерево дерева Т, объявив его корнем вершину Я. Такое поддерево назовем мана, а - а сима вьным поддеревом, если оно содержит Рис. 8.13 все вершины исходного дерева Т, достаисемме нэ вершины Я. Ясно, что высота любого максимального поддерева больше нуля и меньше высоты дерева Т. Для помеченного дерева Т нетрудно проверить справедливость следующей теоремы.
Теорема 8.1. Крона любого максимального поддерева помеченного дерева есть надцепочка кроны всего дерева. Замечание 8.3. Сформулированное утверждение достаточно прозрачно и означает, что если в помеченном дереве Т фиксировать произвольно внутреннюю вершину Я и рассмотреть крону максимального поддерева с корнем ф то все листья кроны этого поддерева, расположенные между самым В.ь кС-грамматики. деревък вывода. Одиовиачиоетв 599 левым (Ь) и самым правым (Ь') листьями, достижимыми из Я, также достижимы из Я (рис.
8.14). Применяя теорему 8.1 к деревьям выводов в КС-грамматиках, получим следующий результат. Следствие 8.1. Если в дереве вывода некоторой цепочки а вз нетерминала Рис. 6.14 А фиксировать произвольно внутреннюю вершину, помеченную нетерминалом В, то максимааьное поддерево с корнем в фиксированной вершине (с меткой В) является деревом вывода некоторой подцепочки,9 цепочки а из нетерминала В, т.е.
существуют такие цепочки 71 и уг, что а ="Ц37г и А 1-' 71Вуг 1-* "М37г (рис. 8.15). Так, для дерева вывода цепочки 6ААа А из нетерминала А в грамматике Се из примера 8.1 (рис. 8.16), фиксируя макси- в мальное поддерево с корневой вершиной С (вторая вершина слева на первом уровне, У1 6 7в выделена полужирным шрифтом), получим Рис. 8.1о 71 = 6 Р = АА, 7г = а. Соответствующее этому максимальному поддереву разбиение вывода на два фрагмента, может быть, например, таким: А 1- ВВ 1- ССВ ~ 1- 6СВ ~- 6Са (первый фрагмент) и С 1- АА (второй фрагмент). Списанная в следствии 8.1 „декомпозиция" дерева вывода и соответственно вывода, по которому построено это дерево, может быть интерпретирована так: выводя цепочку а из нетерминала А, мы, получив на некотором шаге цепочку, содержащую выделенное вхождение нетерминала В, „замораживаем" этот нетерминал и продолжаем замены нетерминалов слева и '~~ Ф справа от В, выводя начало (подцепочку 600 8.
КОНТЕКСТНО-СВОБОДНЫЕ ЯЗЫКИ у~) и конец (надцепочку 'уз) цепочки а. После этого мы „раэмораживаем" нетерминал В и „довыводим" из него середину цепочки а — подцепочку ~3. Понятие дерева вывода связано с понятием однозначности КС-грамматики. Определение 8.1. КС-грамматику называют одноэначной, если каждая цепочка порождаемого ею языка имеет единственное дерево вывода. Поскольку по дереву вывода цепочки а из нетерминала А однозначно строится как левый, так и правый вывод данной цепочки, то определение 8.1 можно сформулировать иначе: КС-грамматика однозначна, если каждая цепочка порождаемого ею языка имеет единственный левый и единственный правый вывод.
Рассмотрим один хрестоматийный пример неоднозначной грамматики. Пример 8.3. Зададим грамматику СЕ следующим образом: СЕ = ((а, Ь, 11', $1зеп, е1яе), (о'1, о, Я-+ 11' ЫЬеп Я е1ве Я~1Г Ь ФЬеп Я~а). Эта грамматика описывает „абстрактный синтаксис" операторов условного перехода в некотором „паскалеобраэном" языке программирования. Термин „абстрактный синтаксис" в данном случае означает, что мы отвлекаемся от структуры как операторов языка, так и логических условий. Терминальный символ а означает произвольный оператор (или последовательность операторов), а терминальный символ Ь вЂ” призвольное логическое условие.
![](https://s.studizba.com/z.php?f=/templates/si/i/noavatar.png&w=100&h=100&t=1"){kind=avatar}
