Формальные грамматики и языки - Гладкий А.В.
Скачать (прямая ссылка):
Полезно заметить, что среди размеченных выводов, отвечающих данному дереву вывода, всегда есть один и только один упорядоченный. С другой стороны, упорядочиваемому выводу в Б-грамматике отвечает единственный упорядоченный размеченный вывод. Таким образом, между деревьями вывода и упорядочиваемыми выводами в Б-грамматике имеется взаимно однозначное соответствие.
Пример. Пусть Б-грамматика Г содержит правила А -*? аВА, В -* ВВ, А -> В A, B-+D, B-*b, D->cd, А->а. Тогда размеченному выводу (* А *, а* В* А, аВВ * А*, аВ * В * В А, а* В* DBA, ab* D * В A, abed * В * А, abedb * А *, abedba) будут отвечать дерево вывода, изображенное на рис. 3 (стр. 81), и растянутое дерево вывода на рис. 2; это последнее дерево соответствует следующей допустимой последовательности невисячих узлов первого (обозначенных цифрами, стоящими на рис. 3 в скобках): 1, 2, 3, 5, 4, 8, 6, 7. Другой допустимой последовательности: 1, 3, 7, 6, 2, 5, 4, 8 — отвечают растянутое дерево на рис. 5 и размеченный вывод (* А *, аВ * А*, аВВ * А*, аВ * В * а, а* В* Ьа, аВ * В * Ьа, а* В* Dba, ab* D * ba, abedba).
Приведем еще несколько простых соображений, относящихся к деревьям вывода.
Лемма 4.4. Пусть D — вывод в Ъ-грамматике Г, Г — его дерево, k — длина D, s — высота Tug — максимум длин правых частей правил Г. Тогда
&S — 1
у , если g > 1, и s — k, если g = 1.
Доказательство. Первое неравенство очевидно; второе следует из того, что k равно числу невисячих узлов Г и из каждого узла Т исходит не более g дуг. Равенство s = k при g — 1 очевидно.
Будем называть (В, со)-дерево простым, если в нем никакие два различных невисячих узла, лежащих
120 Б-ГРАММАТИКИ И МАШИНЫ С МАГАЗИННОЙ ПАМЯТЬЮ [ГЛ. 4
на одном пути, не помечены одним и тем же символом, (В, со)-дерево, всякое собственное полное поддерево которого простое, будем называть квазипростым.
А
а в
а В в/ \а
а В в а
а В ъ а
а в/\в ь ч
а в в ь а
а ъ В b а,
а ь c/\d b а
Рис. 5.
(Полное (6-)поддерево Pi-дерева Г—-это Л-подде-рево Т, образованное всеми узлами, в которые идут пути из данного узла б,)
Очевидна следующая
Лемма 4.5. Высота простого (квазипростого) (В, со) -дерева в Б-грамматике Г не превосходит р (соответственно р + 1), где р — мощность вспомогательного словаря Г.
В заключение введем операцию над деревьями вывода, которая будет нам весьма полезна при изучении Б-грамматик. Пусть Т = (М\ <(, g) есть (А, со)-де-
рево, р — какой-либо узел Т, Е — составляющая цепочки со, соответствующая узлу р (в системе составляющих, определяемой деревом Т), и |*cp*ri — соответствующее этой составляющей вхождение подцепочки в со. Пусть, кроме того, g(p) = В. Обозначим через Тi полное Л-поддерево дерева Т с корнем в р; очевидно, Ti есть (В, ф)-дерево. Рассмотрим теперь произвольную цепочку a]v выводимую из В, и произвольное {В, г^-дерещс}
§ 4.2] РАСПОЗНАВАНИЕ ПУСТОТЫ И КОНЕЧНОСТИ Б-ЯЗЫКА
Гг, и обозначим через Sub (Г, Ти Т2) Pi-дерево, полученное из Г «вырезанием» поддерева 7\ и подстановкой на его место Г2. Ясно, что Sub (Г, Г4, Гг) является (/4, gopri)-деревом, и в соответствующей системе составляющих для цепочки gapri узел р дает составляющую, отвечающую вхождению подцепочки ар.
§ 4.2. Распознавание пустоты и конечности Б-языка. Проекции
Пусть Г = (V, W, I, R)—Б-грамматика, А е W, ае е V U W. Будем говорить, что а зависит от А, если из А выводима в Г хотя бы одна цепочка, содержащая вхождение а.
Лемма 4.6. Существует алгоритм, позволяющий по любой Ъ-грамматике T={V,W,I,R) и любым двум символам А е U7, ае VU ^ распознать, зависит ли а от А.
Доказательство. Пусть в Б-грамматике Г = *=(V,W,I,R) существуют выводы вида (А = «о, ... ..., coft = iari). Возьмем тот из этих выводов, чье дерево содержит меньше всего узлов (если таких деревьев несколько, берем любое из них), и обозначим это дерево через То- Среди висячих узлов То хотя бы один помечен символом а. Пусть у0, уь • • •. Ys — путь из корня Т0 в этот узел. Все узлы То, не лежащие на этом пути, являются висячими. Действительно, в противном случае для некоторого i, i = О, ..., s—1, какой-либо узел б, подчиненный у* и отличный от уж, будет невисячим; но тогда дерево Sub (Го, V, Т"), где Т' — полное б-подде-рево Го и Т" — дерево, состоящее из одного узла б, будет деревом некоторого вывода, начинающегося символом А и заканчивающегося цепочкой, содержащей вхождение а, и это дерево будет содержать меньше узлов, чем Т0. Далее, при i < / узлы у* и у, не могут быть помечены одним и тем же символом, иначе дерево Sub (Г0, Г1', Р), где Т* и Р —полные у г и угподдеревья Г0 соответственно, также было бы деревом вывода из А цепочки, содержащей а, и имело бы меньше узлов, чем Т0. Поэтому s^n,(l^); но s есть как раз число невисячих вершин Го, т. е. длина соответствующего вывода. Теперь искомый алгоритм очевиден — достаточно
122 Б-ГРАММАТИКИ И МАШИНЫ С МАГАЗИННОЙ ПАМЯТЬЮ [ГЛ. 4
перебрать все выводы в Г, длины которых не превосходят ц(№).
Назовем вспомогательный символ Б-грамматики Г бесплодным, если из него не выводима никакая цепочка в основном словаре Г.
