XIX Белоусов А.И., Ткачев СБ. Дискретная математика (1081422), страница 95
Текст из файла (страница 95)
Кроме того, терминалами грамматики являются также лексемы 11; ФЬеп и е1ве, формирующие „скелет" любого оператора условного перехода. В.д. КС-грамматики. Деревьв вывода. Одиоэвачвоеть 601 Определенная таким образом грамматика неоднозначна, что усматривается из такого примера: цепочка 1Е 6 ФЬеп 11' Ь ФЬеп а е1ве а имеет два дерева вывода (рис. 8.17 и 8.18).
11 Ь дДдеи В едае В о о Рис. 8.18 Рис. 8.17 Заметим (неформально), что наличие нескольких деревьев вывода одной и той же цепочки имеет отношение к семаипдиие рассматриваемого языка. В данном конкретном примере понятно, что каждому дереву вывода приведенной вьппе цепочки отвечает свое смысловое прочтение этой цепочки: в первом случае е1ве мы относим к первому ФЬеп, а во втором — ко второму. В итоге получаем две совершенно разные интерпретации оператора условного перехода. Данный пример неоднозначности известен поэтому под названием „кочующее е1яе". Исходную грамматику, однако, можно „исправить", построив эквивалентную ей однозначную грамматику: СЖд = Яа, 6, И', ФЬеп, е1ве), (Яд Яг), Яд Яд -+ 1Г 6 реп Ьз е1ве Яд ~ 11' Ь ФЬеп Ьд ~ а, Яз -+ Ье Ь вЬеп Яз е1ве Яз !а).
В общем случае алгоритма преобразования произвольной неоднозначной КС-грамматики к эквивалентной однозначной не существует. ф 602 8. КОНТЕКСТНО- СВОБОДНЫЕ ЯЗЫКИ Рассмотрим в заключение интересный пример неоднозначности в естественном языке (точнее, в художественном тексте). В известном стихотворении А.С. Пушкина „К вельможе", адресованном князю Юсупову, владельцу Архангельского, есть такая строка: Посланник молодой увенчанной жены...
(Речь идет о том, что князь был послан Екатериной Великой к Вольтеру, великому французскому философу и писателю, состоявшему с Екатериной в переписке.) Процитированную строчку можно прочитать двояко: 1) посланник (молодой увенчанной жены), 2) (посланник молодой) увенчанной жены, т.е. в первом случае эпитет „молодой" отнесен к „жене", а во втором — к „посланнику". Чисто синтаксически эта коллизия неразрешима, но внеязыковый контекст данной фразы, учитывающий совершенно определенные биографические обстоятельства персонажей, позволяет с высокой долей вероятности предположить, что правильным будет второе прочтение.
В то же время следующую анекдотическую фразу нельзя рассматривать как пример неоднозначности, ибо она не соответствует грамматическим нормам русского литературного языка: Сдавайте мусор дворнику, который накопился. Приведенные примеры, между прочим, обнаруживают, что понятие однозначности необходимо анализировать в связи с семантикой языка и что „смысл" следует придавать не цепочке языка, а дереву ее вывода (см. Д.8.2). 8.2. Приведенная форма КС-грамматики При изучении свойств КС-грамматик и КС-языков иногда бывает целесообразно преобразовать КС-грамматику к эквивалентной КС-грамматике, правила вывода которой удовлетворяют определенным дополнительным ограничениям.
В этом В.2. Приведеиияя форме КС-грамматики бОЗ разделе мы рассмотрим алгоритмы некоторых таких преобра- зований. Определение 8.2. Правило вывода КС-грамматпики С = = (У, Ф, Я, Р) называют: 1) Л-правилом, если его правая часп1ь — пусп1ая пеночка; 2) иепнььм, если оно имеет вид А -> В, где А и В— нетврминаяы грамматики. Теорема 8.2. Любая КС-грамматика 6 = (У, Ф, Я, Р) может быть преобразована к эквивалентной КС-грамматике, множество правил вывода которой не содержит Л-правил, кроме, может быть, правила Я -+ Л, и не содержит цепных правил. Мы опишем алгоритмы удаления Л-правил и цепных правил из множества правил КС-грамматики, опуская строгое обоснование этих алгоритмов.
Алгоритм удаления Л-правил. Предположим, что нам известно множество Фе всех нетерминалов грамматики С, из которых выводится пустая цепочка, т.е. Же = (А: А 1-' Л) . Тогда в правой части каждого правила А -+ ~ выделяются все вхождения нетерминвлов из множества Ме (если таких вхождений нет, то правило пропускаетсл) так, что цепочка ( представляется в виде С = се1В1се2В2 ° ° ° оеяВтяотя+1~ где ВМ В2, ..., Ви, — все нетерминалы из Ф~, входящие в ~.
Заметим, что они не обязаны быть различными, так как мы выделяем все вхождения таких нетерминвлов в правую часть правила. После этого к рассматриваемому правилу добавляются все правила вида А ~ СЕ1Х1СЕ2Х2 ° ° ° ФялтСЬп+1~ 604 В. КОНТЕКСТНО-СВОБОДНЫЕ ЯЗЫКИ где для каждого 1 = 1, т Х; есть или символ В;, или пустая цепочка. Иначе говоря, к любому правилу исходной грамматики, правая часть которого содержит нетерминалы из множества Ж, добавляются все правила, которые могут быть получены из исходного путем замены (в его правой части) любого числа вхождений нетерминзлов из Ф~ пустой цепочкой.
При зтом сохраняется и само исходное правило и появляется, в частности, правило А-+а1аз...о а +м вовсе не содержащее вхождений указанных нетерминаяов в правой части. Подчеркнем еще раз, что каждое правило исходной грамматики, правал часть которого не содержит вхождений не- терминалов из Ф„без всяких изменений переносится в систему правил новой грамматики.
Если в процессе описанного вьппе преобразования системы правил исходной грамматики получаются правила вида А + А или А -+ Л (при А ~ В), то они игнорируются. Остается обсудить метод вычисления множества Ф,. Это множество вычисляется рекуррентно, а именно на первом шаге вычисляют множество Фе таких нетерминалов А грамматики С, что существует в Р Л-правило А -+ Л. Таким образом, множество Ие — зто множество всех нетерминалов грамматики, из которых пустел цепочка выводится за один шаг.
На следующем шаге вычисляем множество Фм включая в него, во-первых, все нетерминалы множества Ие и, во-вторых, все такие нетерминалы В, что в Р имеется правило вывода В -+ у, где у — непустая В~ ' В цепочка нетерминалов из множества Ме, т.е. у Е ! Е Лз . Это означает, что Ж1 состоит нз всех таких нетерминалов А грамматики 6', что дерево вывода пустой цепочки нз А, имеет высоту, не большую 2 (рис. 8.19). 8.2.
Првведеиная форма КС-грамматики 605 В общем случае множество М; С Ф вычисляют по формуле Мо = (А: в Р есть правило А — ~ Ц, Ф; = Ф, 1 0 (В: в Р есть правило В -+ ~, где ( Е Ж+, 1. Множество М; — зто множество всех таких нетерминаюв А грамматики ся, что дерево вывода пустой цепочки Л из А имеет высоту, не большую л'+ 1.
Так как множество Ж всех нетерминаюв грамматики С конечно, то описанный выше рекуррентый процесс оборвется на некотором шаге, т.е. для некоторого у > 0 получим Фу —— = Му+в Тогда полагаем Мс = Ф. для наименьшего у, такого, что Фу — — Му+1. Далее, если аксиома Я принадлежит множеству Фе, то в системе правил Р оставляют правило Я -+ Л, остальные Л-правила удаляют', а множество правил вывода исходной грамматики преобразуют согласно описанному вьппе алгоритму. Можно доказать, что полученная таким образом КС-грамматика без Л-правил эквивалентна исходной грамматике ся. Это объясняется тем, что „потерю" вывода пустой цепочки из нетерминала А е Ме (посредством применения Л-правил) мы „компенсируем" добавлением к множеству правил вывода всех таких правил, что замена А на Л уже произведена прямо в их правых частях. Пример 6.4.
Рассмотрим грамматику с множеством правил Я-+аБЬТ~ЬТаТ~аЬ, Т-+ЬааБТ~ТТ~Л. В данном случае Фо = (Ту. Так как единственное правило вывода этой грамматики, правая часть которого — непустая 'Исключение длл Л-правила, левой частью которого служат аксиома грамматики, связано с тем, чтобы при переходе к новой грамматике не „потерять" пустую цепочку, которую порождает исходнал грамматика.
606 8. КОНТЕКСТНО-СВОБОДНЫЕ ЯЗЫКИ цепочка нетерминалов из Ме, есть правило Т -~ ТТ, то Ж =.ЬЪ ~ (Т) = (Т) = Д~е, т.е. Ф, = Щ, и наша грамматика принимает вид Б -+ аБЬТ ~ аБЬ ~ ЬТаТ ~ ЬТа ~ ЬаТ ~ Ьо ~ аЬ, Т вЂ” ~ ЬааБТ~ ЬааБ~ ТТ. Алгоритм удаления цепных правил. Этот алгоритм во многом аналогичен алгоритму удаления А-правил. Пусть существует вывод нетер- В»-, минала У из нетерминала Т, в котором применяютсл только цепные ~~~А ~- А а правила. Тогда такой вывод назовем цепным выводом. Предположим теперь, что для каждого нетерминала А грамматики С известно множество ИА всех таких нетерминалов В, что существует цепной вывод А из В. Тогда, удалив все цепные правила, мы должны предусмотреть непосредственную замену всех нетерминалов из ФА любой цепочкой а, которая служит правой частью некоторого правила А ~ о (рис.
8.20). Это соображение лежит в основе алгоритма преобразования множества правил КС-грамматики с целью удаления цепных правил. Вычислив множество ФА для каждого А Е Л, удалить все цепные правила, добавив при этом для каждой цепочки а, такой, что в Р есть правило А -+ а, и для каждого В е ФА правило В -> а. После этого вместо каждого вывода вида В1-... 1-А ~- о (при В Е ФА) в исходной грамматике в новой деп~ы ~л грамматике получим вывод В 1- а. Множества нетерминалов МА для каждого А Е Ф вычисляются рекуррентно (как и в рассмотренном вьппе алгоритме 607 В.2.
Пряеедеянее форма КС-грамматики удаления А-правил вычислялось множество Ф ): М~~ = (В: в Р есть правило В -+ А); Ф~ —— Ф,'~ 1 О (С: в Р есть правило С -~ Р, где Р Е Ф,'~ ) . Таким образом, множество Ж,'~ — это множество всех таких нетерминзлов В, что существует цепной вывод длины не больше е+1 нетерминала А из В. еНасьпцение" этой рекуррентной процедуры происходит для первого номера у, такого, что И~у = И~у, и тогда принимают Фл = Ж~~. у г+~ Пример 8.5. Дана грамматика с множеством правил Е -> Е+Т~Т, Т-+Т*Р~Р, Р-+ (Е) ~а, аксиомой Е и терминальным алфавитом (а, (, ), +,*).
Имеем Ф~н = ю, следовательно, и Ин = ю (множество нетерминвлов данной грамматики, из которых применением одних цепных правил выводится нетерминал Е, пусто). Далее, Фте —— (Е), а так как нет ни одного цепного правила с правой частью Е, то Хт1 = Ите = Ит1 И~ ~= (Т)' И~1 = (Т Е) = И~ Удаляя цепные правила, необходимо, согласно описанному выше алгоритму, ко всем правилам с левой частью Е добавить правило Е -+ Т е Р, чтобы, сокращая вывод Е 1- Т ~- Т * Р и убирая ю него применение цепного правила Е -+ Т, сразу вывести ю Е цепочку Т е Р. Аналогично к правилам с левой частью Р надо добавить правила Т-+ (Е), Т-~ а, Е-~ (Е) и Е~ а. В итоге получим грамматику Е -+ Е+Т~Т*Р~(Е) ~а, Т-+Т Р(а~(Е), Р ~ (Е) ~ а.
![](https://s.studizba.com/z.php?f=/templates/si/i/noavatar.png&w=100&h=100&t=1"){kind=avatar}
