вается выводимым, если существует вывод, который им кончается.
Множество всех выводимых слов (из терминальных символов) называ-
ется языком, порождаемым данной грамматикой.
В этой и следующих главах мы будем ходить вокруг да около
такого вопроса: дана КС-грамматика; построить алгоритм, который
по любому слову проверяет, выводимо ли оно в этой грамматике.
Пример 1. Алфавит:
( ) [ ] E
(четыре терминальных символа и один нетерминальный символ E).
Начальный символ: e.
Правила:
E -> (E)
E -> [E]
E -> EE
E ->
(в последнем правиле справа стоит пустое слово).
Примеры выводимых слов:
(пустое слово)
()
([])
()[([])]
[()[]()[]]
Примеры невыводимых слов:
(
)(
(]
([)]
Эта грамматика встречалась в разделе 00 (где выводимость в ней
проверялась с помощью стека).
Пример 2. Другая грамматика, порождающая тот же язык:
Алфавит: ( ) [ ] T E
Правила:
E ->
E -> TE
T -> (E)
T -> [E]
Начальным символом во всех приводимых далее примерах будем счи-
тать символ, стоящий в левой части первого правила (в данном
случае это символ T), не оговаривая этого особо.
Для каждого нетерминального символа можно рассмотреть мно-
жество всех слов из терминальных символов, которые из него выво-
дятся (аналогично тому, как это сделано для начального символа в
определении выводимости в грамматике). Каждое правило грамматики
можно рассматривать как свойство этих множеств. Покажем это на
примере только что приведенной грамматики. Пусть SetT и SetE -
множества слов (из скобок), выводимых из нетерминалов T и E со-
ответственно. Тогда правилам грамматики соответствуют такие
свойства:
E -> SetE содержит пустое слово
E -> TE если слово A принадлежит SetT,
слово B принадлежит
SetE, то слово AB принадлежит SetE
T -> [E] если A принадлежит
SetE, то слово [A] принадлежит SetT
T -> (E) если A принадлежит
SetE, то слово (A) принадлежит SetT
Сформулированные свойства множеств SetE, SetT не определяют эти
множества однозначно (например, они остаются верными, если в ка-
честве SetE и SetT взять множество всех слов). Однако можно до-
казать, что множества, задаваемые грамматикой, являются мини-
мальными среди удовлетворяющих этим условиям.
13.1.1. Сформулируйте точно и докажите это утверждение для
произвольной контекстно-свободной грамматики.
13.1.2. Постройте грамматику, в которой выводимы слова
(а) 00..0011..11 (число нулей равно числу единиц);
(б) 00..0011..11 (число нулей вдвое больше числа единиц);
(в) 00..0011..11 (число нулей больше числа единиц);
(и только они).
13.1.3. Доказать, что не существует КС-грамматики, в кото-
рой были бы выводимы слова вида 00..0011..1122..22, в которых
числа нулей, единиц и двоек равны, и только они.
Указание. Докажите следующую лемму о произвольной КС-грам-
матике: для любого достаточно длинного слова F, выводимого в
этой грамматике, существует такое его представление в виде
ABCDE, что любое слово вида AB..BCD..DE, где B и D повторены
одинаковое число раз, также выводимо в этой грамматике. (Это
можно установить, найдя нетерминальный символ, оказывающийся
своим собственным "наследником" в процессе вывода.)
Нетерминальный символ можно рассматривать как "родовое имя"
для выводимых из него слов. В следующем примере для наглядности
в качестве нетерминальных символов использованы фрагменты
русских слов, заключенные в угловые скобки. (С точки зрения
грамматики каждое такое слово - один символ!)
Пример 3. Алфавит:
терминалы: + * ( ) x
нетерминалы: <выр>, <оствыр>, <слаг>, <остслаг>, <множ>
правила:
<выр> -> <слаг> <оствыр>
<оствыр> -> + <выр>
<оствыр> ->
<слаг> -> <множ> <остслаг>
<остслаг> -> * <слаг>
<остслаг> ->
<множ> -> x
<множ> -> ( <выр> )
Согласно этой грамматике, выражение (<выр>) - это последова-
тельность слагаемых (<слаг>), разделенных плюсами, слагаемое -
это последовательность множителей (<множ>), разделенных звездоч-
ками (знаками умножения), а множитель - это либо буква x, либо
выражение в скобках.
13.1.4. Приведите пример другой грамматики, задающей тот же
язык.
Ответ. Вот один из вариантов:
<выр> -> <выр> + <выр>
<выр> -> <выр> * <выр>
<выр> -> x
<выр> -> ( <выр> )
Эта грамматика хоть и проще, но в некоторых отношениях хуже, о
чем мы еще будем говорить.
13.1.5. Дана произвольная КС-грамматика. Построить алгоритм
проверки принадлежности задаваемому ей языку, работающий полино-
миальное время (т.е. число действий не превосходит полинома от
длины проверяемого слова; полином может зависеть от грамматики).
Решение. Заметим, что требование полиномиальности исключает
возможность решения, основанном на переборе всех возможных выво-
дов. Тем не менее полиномиальный алгоритм существует. Поскольку
практического значения он не имеет (используемые на практике
КС-грамматики обладают дополнительными свойствами, позволяющими
строить более эффективные алгоритмы), мы изложим лишь общую схе-
му решения.
(1) Пусть в грамматике есть нетерминалы K1,...,Kn. Построим
новую грамматику с нетерминалами K1',...,Kn' так, чтобы выполня-
лось такое свойство: из Ki' выводятся (в новой грамматике) те же
слова, что из Ki в старой, за исключением пустого слова, которое
не выводится.
Чтобы выполнить такое преобразование грамматики, надо выяс-
нить, из каких нетерминалов исходной грамматики выводится пустое
слово, а затем каждое правило заменить на совокупность правил,
получающихся, если в правой части опустить какие-либо из нетер-
миналов, из которых выводится пустое слово, а у остальных поста-
вить штрихи. Например, если в исходной грамматике было правило
K -> L M N,
причем из L и N выводится пустое слово, а из M нет, то это пра-
вило надо заменить на правила
K'-> L'M'N'
K'-> M'N'
K'-> L'M'
K'-> M'
(2) Итак, мы свели дело к грамматике, где ни из одного не-
терминала не выводится пустое слово. Теперь устраним "циклы" ви-
да
K -> L
L -> M
M -> N
N -> K
(в правой части каждого правила один символ, и эти символы обра-
зуют цикл произвольной длины): это легко сделать, отождествив
все входящие в цикл нетерминалы.
(3) Теперь проверка принадлежности какого-либо слова языку,
порожденному грамматикой, может выполняться так: для каждого
подслова проверяемого слова и для каждого нетерминала выясняем,
порождается ли это подслово этим нетерминалом. При этом подслова
проверяются в порядке возрастания длин, а нетерминалы - в таком
порядке, чтобы при наличии правила K -> L нетерминал L проверял-
ся раньше нетерминала K. (Это возможно в силу отсутствия цик-
лов.) Поясним этот процесс на примере.
Пусть в грамматике есть правила
K -> L
K -> M N L
и других правил, содержащих K в левой части, нет. Мы хотим уз-
нать, выводится ли данное слово A из нетерминала K. Это будет
так в одном из случаев: (1) если A выводится из L; (2) если A
можно разбить на непустые слова B, C, D, для которых B выводится
из M, C выводится из N, а D выводится из L. Вся эта информация
уже есть (слова B, C, D короче A, а L рассмотрен до K).
Легко видеть, что число действий этого алгоритма полиноми-
ально. Степень полинома зависит от числа нетерминалов в правых
частях правил и может быть понижена, если грамматику преобразо-
вать к форме, в которой правая часть каждого правила содержит 1
или 2 нетерминала (это легко сделать, вводя новые нетерминалы:
например, правило K -> LMK можно заменить на K -> LN и N -> MK,
где N - новый нетерминал).
13.1.6. Рассмотрим грамматику с единственным нетерминалом
K, нетерминалами 1, 2, 3 и правилами
K -> 0
K -> 1 K
K -> 2 K K
K -> 3 K K K
Как проверить выводимость слова в этой грамматике, читая слово
слева направо? (Число действий при прочтении одной буквы должно
быть ограничено.)
Решение. Хранится целая переменная n, инвариант: слово вы-
водимо <-> непрочитанная часть представляет собой конкатенацию
(соединение) n выводимых слов.
13.1.7. Тот же вопрос для грамматики
K -> 0
K -> K 1
K -> K K 2
K -> K K K 3
13.2. Метод рекурсивного спуска.
В отличие от алгоритма предыдущего раздела (представляющего
чисто теоретический интерес), алгоритмы на основе рекурсивного
спуска часто используются на практике. Этот метод применим, од-
нако, далеко не ко всем грамматикам. Мы обсудим необходимые ог-
раничения позднее.
Идея метода рекурсивного спуска такова. Для каждого нетер-
минала K мы строим процедуру ReadK, которая - в применении к лю-
бому входному слову x - делает две вещи:
(1) находит наибольшее начало z слова x, которое может быть
началом выводимого из K слова;
(2) сообщает, является ли найденное слово z выводимым из K.
Прежде чем описывать этот метод более подробно, договоримся
о том, как процедуры получают сведения о входном слове и как со-
общают о результатах своей работы. Мы предполагаем, что буквы
входного слова поступают к ним по одной, т.е. имеется граница,
отделяющая "прочитанную" часть от "непрочитанной". Будем счи-
тать, что есть функция (без параметров)
Next: Symbol
дающая первый непрочитанный символ. Ее значениями могут быть
терминальные символы, а также специальный символ EOI (End Of
Input - конец входа), означающий, что все слово уже прочитано.
Вызов этой функции, естественно, не сдвигает границы между про-
читанной и непрочитанной частью - для этого есть процедура Move,
которая сдвигает границу на один символ. (Она применима, если
Next <> EOI.) Пусть, наконец, имеется булевская переменная b.
Теперь мы можем сформулировать наши требования к процедуре
ReadK. Они состоят в следующем:
(1) ReadK прочитывает из оставшейся части слова макси-
мальное начало A, являющееся началом некоторого слова, выводимо-
го из K;
(2) значение b становится истинным или ложным в зависимости
от того, является ли A выводимым из K или лишь невыводимым нача-
лом выводимого (из K) слова.
Для удобства введем такую терминологию: выводимое из K сло-
во будем называть K-словом, а любое начало любого выводимого из
K слова - K-началом. Требования (1) и (2) вместе будем выражать
словами "ReadK корректна для K".
Начнем с рассмотрения частного случая. Пусть правило
K -> L M
является единственным правилом грамматики, содержащим K в левой
части, пусть L, M - нетерминалы и ReadL, ReadM - корректные (для
них) процедуры.
Рассмотрим такую процедуру:
procedure ReadK;
begin
| ReadL;
| if b then begin
| | ReadM;
| end;
end;
13.2.1. Привести пример, когда эта процедура будет некор-
ректной для K.
Ответ. Пусть из L выводится любое слово вида 00..00, а из M
выводится лишь слово 01. Тогда из K выводится слово 00001, но
процедура ReadK этого не заметит.
Укажем достаточноые условия корректности процедуры ReadK.
Для этого нам понадобятся некоторые обозначения. Пусть фиксиро-
ваны КС-грамматика и некоторый нетерминал N этой грамматики.
Рассмотрим N-слово A, которое имеет собственное начало B, также
являющееся N-словом (если такие есть). Для любой пары таких слов
A и B рассмотрим терминальный символ, идущий в A непосредственно
