А. Шень ðòïçòáííéòï÷áîéå ÔÅÏÒÅÍÙ É ÚÁÄÁÞÉ Издание седьмое, дополненное Москва

15.1. Общий алгоритм разбора
269
В этой и следующей главе нас будет интересовать такой вопрос:
дана КС-грамматика; построить алгоритм, который по любому слову
проверяет, выводимо ли оно в этой грамматике.
Пример 1. Алфавит:
( ) [ ] E
(четыре терминальных символа и один нетерминальный символ E). На-
чальный символ: E. Правила:
E
→
(E)
E
→
[E]
E
→
EE
E
→
(в последнем правиле справа стоит пустое слово).
Примеры выводимых слов:
(пустое слово)
()
([ ])
()[([ ])]
[()[ ]()[ ]]
Примеры невыводимых слов:
(
)(
(]
([)]
Эта грамматика встречалась в разделе
6.1
(где выводимость в ней про-
верялась с помощью стека).
Пример 2. Другая грамматика, порождающая тот же язык:
Алфавит: ( ) [ ] T E
Правила:
E
→
E
→
TE
T
→
(E)
T
→
[E]

270
15. Контекстно-свободные грамматики
Начальным символом во всех приводимых далее примерах будем счи-
тать символ, стоящий в левой части первого правила (в данном случае
это символ E), не оговаривая этого особо.
Для каждого нетерминального символа можно рассмотреть множе-
ство всех слов из терминальных символов, которые из него выводятся
(аналогично тому, как это сделано для начального символа в определе-
нии выводимости в грамматике). Каждое правило грамматики можно
рассматривать как свойство этих множеств. Покажем это на примере
только что приведённой грамматики. Пусть 𝑇 и 𝐸 | множества слов
(из скобок), выводимых из нетерминалов T и E соответственно. Тогда
правилам грамматики соответствуют такие свойства:
E
→
𝐸 содержит пустое слово
E
→
TE
если слово 𝐴 принадлежит 𝑇 ,
а слово 𝐵 принадлежит 𝐸, то
слово 𝐴𝐵 принадлежит 𝐸
T
→
[E] если 𝐴 принадлежит 𝐸, то слово
[𝐴] принадлежит 𝑇
T
→
(E) если 𝐴 принадлежит 𝐸, то слово
(𝐴) принадлежит 𝑇
Сформулированные свойства множеств 𝐸, 𝑇 не определяют эти мно-
жества однозначно (например, они остаются верными, если в каче-
стве 𝐸 и 𝑇 взять множество всех слов). Однако можно доказать, что
множества, задаваемые грамматикой, являются минимальными среди
удовлетворяющих этим условиям.
15.1.1. Сформулируйте точно и докажите это утверждение для про-
извольной контекстно-свободной грамматики.
15.1.2. Постройте грамматику, в которой выводимы слова
(а) 00..0011..11 (число нулей равно числу единиц);
(б) 00..0011..11 (число нулей вдвое больше числа единиц);
(в) 00..0011..11 (число нулей больше числа единиц);
(и только они).
15.1.3. Докажите, что не существует КС-грамматики, в которой
были бы выводимы слова вида 00..0011..1122..22, в которых числа
нулей, единиц и двоек равны, и только они.
[Указание. Докажите следующую лемму о произвольной КС-грам-
матике: для любого достаточно длинного слова 𝐹 , выводимого в этой
грамматике, существует такое его представление в виде 𝐴𝐵𝐶𝐷𝐸, что

15.1. Общий алгоритм разбора
271
любое слово вида 𝐴𝐵 . . . 𝐵𝐶𝐷 . . . 𝐷𝐸, где 𝐵 и 𝐷 повторены одинаковое
число раз, также выводимо в этой грамматике. (Это можно устано-
вить, найдя нетерминальный символ, оказывающийся своим собствен-
ным «наследником» в процессе вывода.)]
Нетерминальный символ можно рассматривать как «родовое имя»
для выводимых из него слов. В следующем примере для наглядности
в качестве нетерминальных символов использованы фрагменты рус-
ских слов, заключённые в угловые скобки. (С точки зрения грамматики
каждый такой фрагмент | один символ!)
Пример 3. Алфавит:
терминалы:
+ * ( ) x
нетерминалы:
⟨
выр
⟩ ⟨
оствыр
⟩ ⟨
слаг
⟩ ⟨
остслаг
⟩ ⟨
множ
⟩
Правила:
⟨
выр
⟩ → ⟨
слаг
⟩ ⟨
оствыр
⟩
⟨
оствыр
⟩ →
+
⟨
выр
⟩
⟨
оствыр
⟩ →
⟨
слаг
⟩ → ⟨
множ
⟩ ⟨
остслаг
⟩
⟨
остслаг
⟩ →
*
⟨
слаг
⟩
⟨
остслаг
⟩ →
⟨
множ
⟩ →
x
⟨
множ
⟩ →
(
⟨
выр
⟩
)
Согласно этой грамматике, выражение
⟨
выр
⟩
| это последователь-
ность слагаемых
⟨
слаг
⟩
, разделённых плюсами, слагаемое | это после-
довательность множителей
⟨
множ
⟩
, разделённых звёздочками (знаками
умножения), а множитель | это либо буква x, либо выражение в скоб-
ках.
15.1.4. Приведите пример другой грамматики, задающей тот же
язык.
Ответ. Вот один из вариантов:
⟨
выр
⟩ → ⟨
выр
⟩
+
⟨
выр
⟩
⟨
выр
⟩ → ⟨
выр
⟩
*
⟨
выр
⟩
⟨
выр
⟩ →
x
⟨
выр
⟩ →
(
⟨
выр
⟩
)
Эта грамматика хоть и проще, но в некоторых отношениях хуже,
о чём мы ещё будем говорить.

272
15. Контекстно-свободные грамматики
15.1.5. Дана произвольная КС-грамматика. Постройте алгоритм
проверки принадлежности задаваемому ей языку, работающий поли-
номиальное время (т. е. число действий не превосходит полинома от
длины проверяемого слова; полином может зависеть от грамматики).
Решение. Заметим, что требование полиномиальности исключает
возможность решения, основанном на переборе всех возможных вы-
водов. Тем не менее полиномиальный алгоритм существует. Посколь-
ку практического значения он не имеет (используемые на практике
КС-грамматики обладают дополнительными свойствами, позволяющи-
ми строить более эффективные алгоритмы), мы изложим лишь общую
схему решения.
(1) Пусть в грамматике есть нетерминалы 𝐾
1
, . . . , 𝐾
𝑛
. Построим но-
вую грамматику с нетерминалами 𝐾
′
1
, . . . , 𝐾
′
𝑛
так, чтобы выполнялось
такое свойство: из 𝐾
′
𝑖
выводятся (в новой грамматике) те же слова, что
из 𝐾
𝑖
в старой, за исключением пустого слова, которое не выводится.
Чтобы выполнить такое преобразование грамматики, надо выяс-
нить, из каких нетерминалов исходной грамматики выводится пустое
слово, а затем каждое правило заменить на совокупность правил, полу-
чающихся, если в правой части опустить какие-либо из нетерминалов,
из которых выводится пустое слово, а у остальных поставить штрихи.
Например, если в исходной грамматике было правило
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
(в правой части каждого правила один символ, и эти символы обра-
зуют цикл произвольной длины): это легко сделать, отождествив все
входящие в цикл нетерминалы.

15.1. Общий алгоритм разбора
273
(3) Теперь проверка принадлежности какого-либо слова языку, по-
рождённому грамматикой, может выполняться так: для каждого под-
слова проверяемого слова и для каждого нетерминала выясняем, поро-
ждается ли это подслово этим нетерминалом. При этом подслова прове-
ряются в порядке возрастания длин, а нетерминалы | в таком порядке,
чтобы при наличии правила 𝐾
→
𝐿 нетерминал 𝐿 проверялся раньше
нетерминала 𝐾. (Это возможно в силу отсутствия циклов.) Поясним
этот процесс на примере.
Пусть в грамматике есть правила
K
→
L
K
→
M N L
и других правил, содержащих K в левой части, нет. Мы хотим узнать,
выводится ли данное слово 𝐴 из нетерминала K. Это будет так в одном
из случаев:
•
если 𝐴 выводится из L;
•
если 𝐴 можно разбить на непустые слова 𝐵, 𝐶, 𝐷, для которых
𝐵 выводится из M, 𝐶 выводится из N, а 𝐷 выводится из L.
Вся эта информация уже есть (слова 𝐵, 𝐶, 𝐷 короче 𝐴, а L рассмотрен
до K).
Легко видеть, что число действий этого алгоритма полиномиально.
Степень полинома зависит от числа нетерминалов в правых частях пра-
вил и может быть понижена, если грамматику преобразовать к форме,
в которой правая часть каждого правила не более 2 нетерминалов (это
легко сделать, вводя новые нетерминалы: например, правило K
→
LMK
можно заменить на K
→
LN и N
→
MK, где N | новый нетерминал).
15.1.6. Рассмотрим грамматику с единственным нетерминалом K,
нетерминалами 0, 1, 2, 3 и правилами
K
→
0
K
→
1 K
K
→
2 K K
K
→
3 K K K
Как проверить выводимость слова в этой грамматике, читая слово сле-
ва направо? (Число действий при прочтении одной буквы должно быть
ограничено.)

274
15. Контекстно-свободные грамматики
Решение. Хранится целая переменная n, инвариант: слово выводи-
мо
⇔
непрочитанная часть представляет собой конкатенацию (соеди-
нение) n выводимых слов.
15.1.7. Тот же вопрос для грамматики
K
→
0
K
→
K 1
K
→
K K 2
K
→
K K K 3
15.2. Метод рекурсивного спуска
В отличие от алгоритма предыдущего раздела (представляюще-
го чисто теоретический интерес), алгоритмы на основе рекурсивного
спуска часто используются на практике. Этот метод применим, однако,
далеко не ко всем грамматикам. Мы обсудим необходимые ограничения
позднее.
Идея метода рекурсивного спуска такова. Для каждого нетермина-
ла K мы строим процедуру ReadK, которая | в применении к любому
входному слову 𝑥 | делает две вещи:
•
находит наибольшее начало 𝑧 слова 𝑥, которое может быть нача-
лом выводимого из K слова;
•
сообщает, является ли найденное слово 𝑧 выводимым из K.
Прежде чем описывать этот метод более подробно, договоримся
о том, как процедуры получают сведения о входном слове и как сооб-
щают о результатах своей работы. Мы предполагаем, что буквы вход-
ного слова поступают к ним по одной, т. е. имеется граница, отделя-
ющая «прочитанную» часть от «непрочитанной». Будем считать, что
есть функция (без параметров)
Next: Symbol
дающая первый непрочитанный символ. Её значениями могут быть тер-
минальные символы, а также специальный символ EOI (End Of Input |
конец входа), означающий, что всё слово уже прочитано. Вызов этой
функции, разумеется, не сдвигает границы между прочитанной и не-
прочитанной частью | для этого есть процедура Move, которая сдви-
гает границу на один символ. (Она применима, если Next<>EOI.) Пусть,
наконец, имеется булевская переменная b.

15.2. Метод рекурсивного спуска
275
Теперь мы можем сформулировать наши требования к процедуре
ReadK. Они состоят в следующем:
•
ReadK прочитывает из оставшейся части слова максимальное на-
чало 𝐴, являющееся началом некоторого слова, выводимого из K;
•
значение b становится истинным или ложным в зависимости от
того, является ли 𝐴 выводимым из K или лишь невыводимым на-
чалом выводимого (из K) слова.
Для удобства введём такую терминологию: выводимое из K слово бу-
дем называть K-словом, а любое начало любого выводимого из K слова |
K-началом. Два сформулированных требования вместе будем выражать
словами «ReadK корректна для K».
Начнём с примера. Пусть правило
K
→
L M
является единственным правилом грамматики, содержащим K в левой
части, пусть L, M | нетерминалы и ReadL, ReadM | корректные (для
них) процедуры.
Рассмотрим такую процедуру:
procedure ReadK;
begin
ReadL;
if b then begin
ReadM;
end;
end;
15.2.1. Приведите пример, когда эта процедура будет некорректной
для K.
Ответ. Пусть из L выводится любое слово вида 00..00, а из M выво-
дится лишь слово 01. Тогда из K выводится слово 00001, но процедура
ReadK этого не заметит.
Укажем достаточные условия корректности процедуры ReadK. Для
этого нам понадобятся некоторые обозначения. Пусть фиксированы
КС-грамматика и некоторый нетерминал 𝑁 этой грамматики. Рассмо-
трим 𝑁-слово 𝐴, которое имеет собственное начало 𝐵, также являю-

276
15. Контекстно-свободные грамматики
щееся 𝑁-словом (если такие есть). Для любой пары таких слов 𝐴 и 𝐵
рассмотрим терминальный символ, идущий в 𝐴 непосредственно за 𝐵.
Множество всех таких терминалов обозначим Посл(𝑁). (Если никакое
𝑁-слово не является собственным началом другого 𝑁-слова, то множе-
ство Посл(𝑁) пусто.)
15.2.2. Укажите (а) Посл(E) для примера 1 (с.
269
); (б) Посл(E) и
Посл(T) для примера 2 (с.
269
); (в) Посл(
⟨
слаг
⟩
) и Посл(
⟨
множ
⟩
) для
примера 3 (с.
271
);
Ответ. (а) Посл(E) =
{
[, (
}
. (б) Посл(E) =
{
[, (
}
; Посл(T) пусто (ни-
какое T-слово не является началом другого). (в) Посл(
⟨
слаг
⟩
) =
{
*
}
;
Посл(
⟨
множ
⟩
) пусто.
Кроме того, для каждого нетерминала 𝑁 обозначим через Нач(𝑁)
множество всех терминалов, являющихся первыми буквами непустых
𝑁-слов. Это обозначение | вместе с предыдущим | позволит дать
достаточное условие корректности процедуры ReadK в описанной выше
ситуации.
15.2.3. Докажите, что если Посл(L) не пересекается с Нач(M) и мно-
жество всех M-слов непусто, то ReadK корректна.
Решение. Рассмотрим два случая.
(1) Пусть после ReadL значение переменной b ложно. В этом слу-
чае ReadL читает со входа максимальное L-начало 𝐴, не являющееся
L-словом. Оно является K-началом (здесь важно, что множество M-слов
непусто.). Будет ли оно максимальным K-началом среди начал входа?
Если нет, то 𝐴 является началом слова 𝐵𝐶, где 𝐵 есть L-слово, 𝐶 есть
M-начало и 𝐵𝐶 | более длинное начало входа, чем 𝐴. Если 𝐵 длиннее 𝐴,
то 𝐴 | не максимальное начало входа, являющееся L-началом, что про-
тиворечит корректности ReadL. Если 𝐵 = 𝐴, то 𝐴 было бы L-словом,
а это не так. Значит, 𝐵 короче 𝐴, 𝐶 непусто и первый символ слова 𝐶
следует в 𝐴 за последним символом слова 𝐵, т. е. Посл(L) пересекается
с Нач(M). Противоречие. Итак, 𝐴 максимально. Из сказанного следу-
ет также, что 𝐴 не является K-словом. Корректность процедуры ReadK
в этом случае проверена.
(2) Пусть после ReadL значение переменной b истинно. Тогда прочи-
танное процедурой ReadK начало входа имеет вид 𝐴𝐵, где 𝐴 есть L-сло-
во, а 𝐵 есть M-начало. Тем самым 𝐴𝐵 есть K-начало. Проверим его мак-
симальность. Пусть 𝐶 есть большее K-начало. Тогда либо 𝐶 есть L-на-
чало (что невозможно, так как 𝐴 было максимальным L-началом), либо
𝐶 = 𝐴
′
𝐵
′
, где 𝐴
′
| L-слово, 𝐵
′
| M-начало. Если 𝐴
′
короче 𝐴, то 𝐵
′
не-
пусто и начинается с символа, принадлежащего и Нач(M), и Посл(L),

15.2. Метод рекурсивного спуска
277
что невозможно. Если 𝐴
′
длиннее 𝐴, то 𝐴 | не максимальное L-начало.
Итак, 𝐴
′
= 𝐴. Но в этом случае 𝐵
′
есть продолжение 𝐵, что противоре-
чит корректности ReadM. Таким образом, 𝐴𝐵 | максимальное K-нача-
ло. Остаётся проверить правильность выдаваемого процедурой ReadK
значения переменной b. Если оно истинно, то это очевидно. Если оно
ложно, то 𝐵 не есть M-слово, и надо проверить, что 𝐴𝐵 | не K-слово.
В самом деле, если бы выполнялось 𝐴𝐵 = 𝐴
′
𝐵
′
, где 𝐴
′
| L-слово, 𝐵
′
|
M-слово, то 𝐴
′
не может быть длиннее 𝐴 (ReadL читает максимальное
слово), 𝐴
′
не может быть равно 𝐴 (тогда 𝐵
′
равно 𝐵 и не является
M-словом) и 𝐴
′
не может быть короче 𝐴 (тогда первый символ 𝐵
′
при-
надлежит и Нач(M), и Посл(L)). Задача решена.
Перейдём теперь к другому частному случаю. Пусть в КС-грамма-
тике есть правила
K
→
L
K
→
M
K
→
N
и других правил с левой частью K нет.
15.2.4. Считая, что ReadL, ReadM и ReadN корректны (для L, M и N)
и что множества Нач(L), Нач(M) и Нач(N) не пересекаются, напишите
процедуру, корректную для K.
Решение. Схема процедуры такова:
procedure ReadK;
begin
if (Next принадлежит Нач(L)) then begin
ReadL;
end else if (Next принадлежит Нач(M)) then begin
ReadM;
end else if (Next принадлежит Нач(N)) then begin
ReadN;
end else begin
b := true или false в зависимости от того,
выводимо ли пустое слово из K или нет
end;
end;
Докажем, что ReadK корректно реализует K. Если Next не принадлежит
ни одному из множеств Нач(L), Нач(M), Нач(N), то пустое слово является

278
15. Контекстно-свободные грамматики
наибольшим началом входа, являющимся K-началом. Если Next принад-
лежит одному (и, следовательно, только одному) из этих множеств, то
максимальное начало входа, являющееся K-началом, непусто и читается
соответствующей процедурой.
15.2.5. Используя сказанное, составьте процедуру распознавания
выражений для грамматики (пример 3, с.
271
):
⟨
выр
⟩ → ⟨
слаг
⟩ ⟨
оствыр
⟩
⟨
оствыр
⟩ →
+
⟨
выр
⟩
⟨
оствыр
⟩ →
⟨
слаг
⟩ → ⟨
множ
⟩ ⟨
остслаг
⟩
⟨
остслаг
⟩ →
*
⟨
слаг
⟩
⟨
остслаг
⟩ →
⟨
множ
⟩ →
x
⟨
множ
⟩ →
(
⟨
выр
⟩
)
Решение. Эта грамматика не полностью подпадает под рассмотрен-
ные частные случаи: в правых частях есть комбинации терминалов и не-
терминалов
+
⟨
выр
⟩
и группы из трёх символов
(
⟨
выр
⟩
)
В грамматике есть также несколько правил с одной левой частью и с
правыми частями разного рода, например
⟨
оствыр
⟩ →
+
⟨
выр
⟩
⟨
оствыр
⟩ →
Эти ограничения не являются принципиальными. Так, правило типа
K
→
L M N можно было бы заменить на два правила K
→
L Q и Q
→
M N,
терминальные символы в правой части | на нетерминалы (с един-
ственным правилом замены на соответствующие терминалы). Несколь-
ко правил с одной левой частью и разнородными правыми также можно

15.2. Метод рекурсивного спуска
279
свести к уже разобранному случаю: например,
K
→
L M N
K
→
P Q
K
→
можно заменить на правила
K
→
K
1
K
→
K
2
K
→
K
3
K
1
→
L M N
K
2
→
P Q
K
3
→
Но мы не будем этого делать | а сразу же запишем то, что получится,
если подставить описания процедур для новых терминальных символов
в места их использования. Например, для правила
K
→
L M N
это даёт процедуру
procedure ReadK;
begin
ReadL;
if b then begin
ReadM;
end;
if b then begin
ReadN;
end;
end;
Для её корректности надо, чтобы Посл(L) не пересекалось с Нач(MN)
(которое равно Нач(M), если из M не выводится пустое слово, и равно
объединению Нач(M) и Нач(N), если выводится), а также чтобы Посл(M)
не пересекалось с Нач(N).
Аналогичным образом правила
K
→
L M N
K
→
P Q
K
→

280
15. Контекстно-свободные грамматики
приводят к процедуре
procedure ReadK;
begin
if (Next принадлежит Нач(LMN)) then begin
ReadL;
if b then begin ReadM; end;
if b then begin ReadN; end;
end else if (Next принадлежит Нач(PQ)) then begin
ReadP;
if b then begin ReadQ; end;
end else begin
b := true;
end;
end;
корректность которой требует, чтобы Нач(LMN) не пересекалось с
Нач(PQ).
Читая приведённую далее программу, полезно иметь в виду соот-
ветствие между русскими и английскими словами:
ВЫРажение
EXPRession
ОСТаток ВЫРажения
REST of EXPRession
СЛАГаемое
ADDitive term
ОСТаток СЛАГаемого REST of ADDitive term
МНОЖитель
FACTor
procedure ReadSymb (c: Symbol);
b := (Next = c);
if b then begin
Move;
end;
end;
procedure ReadExpr;
ReadAdd;
if b then begin ReadRestExpr; end;
end;
procedure ReadRestExpr;
if Next = ’+’ then begin
ReadSymb (’+’);
if b then begin ReadExpr; end;
end else begin

15.2. Метод рекурсивного спуска
281
b := true;
end;
end;
procedure ReadAdd;
ReadFact;
if b then begin ReadRestAdd; end;
end;
procedure ReadRestAdd;
if Next = ’*’ then begin
ReadSymb (’*’);
if b then begin ReadAdd; end;
end else begin
b := true;
end;
end;
procedure ReadFact;
if Next = ’x’ then begin
ReadSymb (’x’);
end else if Next = ’(’ then begin
ReadSymb (’(’);
if b then begin ReadExpr; end;
if b then begin ReadSymb (’)’); end;
end else begin
b := false;
end;
end;
Осталось обсудить проблемы, связанные с взаимной рекурсивностью
этих процедур (одна использует другую и наоборот). В паскале это
допускается, только требуется дать предварительное описание проце-
дур («forward»). Как всегда для рекурсивных процедур, помимо доказа-
тельства того, что каждая процедура работает правильно в предполо-
жении, что используемые в ней вызовы процедур работают правильно,
надо доказать отдельно, что работа завершается. (Это не очевидно:
если в грамматике есть правило K
→
KK, то из K ничего не выводится,
Посл(K) и Нач(K) пусты, но написанная по нашим канонам процедура
procedure ReadK;
begin
ReadK;
if b then begin

282
15. Контекстно-свободные грамматики
ReadK;
end;
end;
не заканчивает работы.)
В данном случае процедуры ReadRestExpr, ReadRestAdd, ReadFact
либо завершаются, либо уменьшают длину непрочитанной части входа.
Поскольку любой цикл вызовов включает одну из них, то зацикливание
невозможно.
15.2.6. Пусть в грамматике имеются два правила с нетерминалом K
в левой части, имеющих вид
K
→
L K
K
→
по которым K-слово представляет собой конечную последовательность
L-слов, причём множества Посл(L) и Нач(K) (в данном случае рав-
ное Нач(L)) не пересекаются. Используя корректную для L процеду-
ру ReadL, напишите корректную для K процедуру ReadK, не используя
рекурсии.
Решение. По нашим правилам следовало бы написать
procedure ReadK;
begin
if (Next принадлежит Нач(L)) then begin
ReadL;
if b then begin ReadK; end;
end else begin
b := true;
end;
end;
завершение работы гарантируется тем, что перед рекурсивным вызо-
вом длина непрочитанной части уменьшается.
Эта рекурсивная процедура эквивалентна нерекурсивной:
procedure ReadK;
begin
b := true;
while b and (Next принадлежит Нач(L)) do begin
ReadL;
end;
end;

15.2. Метод рекурсивного спуска
283
Формально можно проверить эту эквивалентность так. Завершаемость
в обоих случаях ясна. Достаточно проверить поэтому, что тело рекур-
сивной процедуры эквивалентно нерекурсивной в предположении, что
её рекурсивный вызов эквивалентен вызову нерекурсивной процедуры.
Подставим:
if (Next принадлежит Нач(L)) then begin
ReadL;
if b then begin
b := true;
while b and (Next принадлежит Нач(L)) do begin
ReadL;
end;
end;
end else begin
b := true;
end;
Первую команду b:=true можно выкинуть (в этом месте и так b ис-
тинно). Вторую команду можно перенести в начало:
b := true;
if (Next принадлежит Нач(L) then begin
ReadL;
if b then begin
while b and (Next принадлежит Нач(L)) do begin
ReadL;
end;
end;
end;
Теперь внутренний if можно выкинуть (если b ложно, цикл while всё
равно не выполняется) и добавить в условие внешнего if условие b
(которое всё равно истинно).
b := true;
if b and (Next принадлежит Нач(L)) then begin
ReadL;
while b and (Next принадлежит Нач(L)) do begin
ReadL;
end;
end;
что эквивалентно приведённой выше нерекурсивной процедуре (из ко-
торой вынесена первая итерация цикла).

284
15. Контекстно-свободные грамматики
15.2.7. Докажите корректность приведённой выше нерекурсивной
программы непосредственно, без ссылок на рекурсивную.
Решение. Рассмотрим наибольшее начало входа, являющееся K-на-
чалом. Оно представляется в виде конкатенации (последовательного
приписывания) нескольких непустых L-слов и, возможно, одного непу-
стого L-начала, не являющегося L-словом. Инвариант цикла: прочитано
несколько из них; b
⇔
(последнее прочитанное является L-словом).
Сохранение инварианта: если осталось последнее слово, это очевид-
но; если осталось несколько, то за первым L-словом (из числа оставших-
ся) идёт символ из Нач(L), и потому это слово | максимальное начало
входа, являющееся L-началом.
На практике при записи грамматики используют сокращения. Если
правила для какого-то нетерминала K имеют вид
K
→
L K
K
→
(т. е. K-слова | это последовательности L-слов), то этих правил не пи-
шут, а вместо K пишут L в фигурных скобках. Несколько правил с одной
левой частью и разными правыми записывают как одно правило, раз-
деляя альтернативные правые части вертикальной чертой.
Например, рассмотренная выше грамматика для
⟨
выр
⟩
может быть
записана так:
⟨
выр
⟩ → ⟨
слаг
⟩ {
+
⟨
слаг
⟩ }
⟨
слаг
⟩ → ⟨
множ
⟩ {
*
⟨
множ
⟩ }
⟨
множ
⟩ →
x
|
(
⟨
выр
⟩
)
15.2.8. Напишите процедуру, корректную для
⟨
выр
⟩
, следуя этой
грамматике и используя цикл вместо рекурсии, где можно.
Решение.
procedure ReadSymb (c: Symbol);
b := (Next = c);
if b then begin Move; end;
end;
procedure ReadExpr;
begin
ReadAdd;

15.3. Алгоритм разбора для LL(1)-грамматик
285
while b and (Next = ’+’) do begin
Move; ReadAdd;
end;
end;
procedure ReadAdd;
begin
ReadFact;
while b and (Next = ’*’) do begin
Move; ReadFact;
end;
end;
procedure ReadFact;
begin
if Next = ’x’ do begin
Move; b := true;
end else if Next = ’(’ then begin
Move; ReadExpr;
if b then begin ReadSymb (’)’); end;
end else begin
b := false;
end;
end;
15.2.9. В последней процедуре команду b:=true можно опустить.
Почему?
Решение. Можно предполагать, что все процедуры вызываются при
b=true.
15.3. Алгоритм разбора для LL(1)-грамматик
В этом разделе мы рассмотрим ещё один метод проверки выводимо-
сти в КС-грамматике, называемый по традиции LL(1)-разбором. Вот
его идея в одной фразе: можно считать, что в процессе вывода мы
всегда заменяем самый левый нетерминал и нужно лишь выбрать одно
из правил; если нам повезёт с грамматикой, то выбрать правило мож-
но, глядя на первый символ выводимого из этого нетерминала слова.
Говоря более формально, дадим такое
Определение. Левым выводом (слова в грамматике) называется вы-
вод, в котором на каждом шаге замене подвергается самый левый из
нетерминалов.

286
15. Контекстно-свободные грамматики
15.3.1. Для каждого выводимого слова (из терминалов) существует
его левый вывод.
Решение. Различные нетерминалы заменяются независимо; если в
процессе вывода появилось слово . . . 𝐾 . . . 𝐿 . . ., где 𝐾, 𝐿 | нетермина-
лы, то замены 𝐾 и 𝐿 можно производить в любом порядке. Поэтому
можно перестроить вывод так, чтобы стоящий левее нетерминал заме-
нялся раньше. (Формально говоря, надо доказывать индукцией по дли-
не вывода такой факт: если из некоторого нетерминала 𝐾 выводится
некоторое слово 𝐴, то существует левый вывод 𝐴 из 𝐾.)
15.3.2. В грамматике с 4 правилами
(1) E
→
(2) E
→
TE
(3) T
→
(E)
(4) T
→
[E]
найдите левый вывод слова 𝐴=[()([ ])] и докажите, что он единствен.
Решение. На первом шаге можно применить только правило (2):
E
→
TE
Что будет дальше с T? Так как слово 𝐴 начинается на [, то может
примениться только правило (4):
E
→
TE
→
[E]E
Первое E должно замениться на TE (иначе вторым символом была бы
скобка ]):
E
→
TE
→
[E]E
→
[TE]E
и T должно заменяться по (3):
E
→
TE
→
[E]E
→
[TE]E
→
[(E)E]E
Далее первое E должно замениться на пустое слово (иначе третьей бук-
вой слова будет ( или [ | только на эти символы может начинаться
слово, выводимое из T):
E
→
TE
→
[E]E
→
[TE]E
→
[(E)E]E
→
[()E]E
и далее
. . .
→
[()TE]E
→
[()(E)E]E
→
[()(TE)E]E
→
[()([E]E)E]E
→
→
[()([ ]E)E]E
→
[()([ ])E]E
→
[()([ ])]E
→
[()([ ])]

15.3. Алгоритм разбора для LL(1)-грамматик
287
Что требуется от грамматики, чтобы такой метод поиска левого
вывода был применим? Пусть, например, на очередном шаге самым
левым нетерминалом оказался нетерминал 𝐾, т. е. мы имеем слово ви-
да 𝐴𝐾𝑈, где 𝐴 | слово из терминалов, а 𝑈 | слово из терминалов
и нетерминалов. Пусть в грамматике есть правила
𝐾
→
𝐿𝑀𝑁
𝐾
→
𝑃 𝑄
𝐾
→
𝑅
Нам надо выбрать одно из них. Мы будем пытаться сделать этот выбор,
глядя на первый символ той части входного слова, которая выводится
из 𝐾𝑈.
Рассмотрим множество Нач(𝐿𝑀𝑁) тех терминалов, с которых на-
чинаются непустые слова, выводимые из 𝐿𝑀𝑁. (Это множество равно
Нач(𝐿), объединённому с Нач(𝑀), если из 𝐿 выводится пустое слово,
а также с Нач(𝑁), если из 𝐿 и из 𝑀 выводится пустое слово.) Что-
бы описанный метод был применим, надо, чтобы Нач(𝐿𝑀𝑁), Нач(𝑃 𝑄)
и Нач(𝑅) не пересекались. Но этого мало. Ведь может быть так, на-
пример, что из 𝐿𝑀𝑁 будет выведено пустое слово, а из слова 𝑈 будет
выведено слово, начинающееся на букву из Нач(𝑃 𝑄). Следующие опре-
деления учитывают эту проблему.
Напомним, что определение выводимости в КС-грамматике было да-
но только для слова из терминалов. Оно очевидным образом обобщается
на случай слов из терминалов и нетерминалов. Можно также говорить
о выводимости одного слова (содержащего терминалы и нетерминалы)
из другого. (Если говорится о выводимости слова без указания того,
откуда оно выводится, то всегда подразумевается выводимость в грам-
матике, т. е. выводимость из начального нетерминала.)
Для каждого слова 𝑋 из терминалов и нетерминалов через Нач(𝑋)
обозначаем множество всех терминалов, с которых начинаются непу-
стые слова из терминалов, выводимые из 𝑋. (В случае, если из любого
нетерминала выводится хоть одно слово из терминалов, не играет роли,
рассматриваем ли мы при определении Нач(𝑋) слова только из терми-
налов или любые слова. Мы будем предполагать далее, что это условие
выполнено.)
Для каждого нетерминала 𝐾 через Послед(𝐾) обозначим множество
терминалов, которые встречаются в выводимых (в грамматике) словах
сразу же за 𝐾. (Не смешивать с Посл(𝐾) предыдущего раздела!) Кроме
того, в Послед(𝐾) включается символ EOI, если существует выводимое
слово, оканчивающееся на 𝐾.

288
15. Контекстно-свободные грамматики
Для каждого правила
𝐾
→
𝑉
(где 𝐾 | нетерминал, 𝑉 | слово, содержащее терминалы и нетерми-
налы) определим множество направляющих терминалов, обозначаемое
Напр(𝐾
→
𝑉 ). По определению оно равно Нач(𝑉 ), к которому добавле-
но Послед(𝐾), если из 𝑉 выводится пустое слово.
Определение. Грамматика называется LL(1)-грамматикой, если для
любых правил 𝐾
→
𝑉 и 𝐾
→
𝑊 с одинаковыми левыми частями мно-
жества Напр(𝐾
→
𝑉 ) и Напр(𝐾
→
𝑊 ) не пересекаются.
15.3.3. Является ли грамматика
K
→
K #
K
→
(выводимыми словами являются последовательности диезов) LL(1)-
грамматикой?
Решение. Нет: символ # принадлежит множествам направляющих
символов для обоих правил (для второго | поскольку # принадлежит
Послед(𝐾)).
15.3.4. Напишите LL(1)-грамматику для того же языка.
Решение.
K
→
# K
K
→
Как говорят, «леворекурсивное» правило заменено на «праворекур-
сивное».
Следующая задача показывает, что для LL(1)-грамматики суще-
ствует не более одного возможного продолжения левого вывода.
15.3.5. Пусть дано выводимое в LL(1)-грамматике слово 𝑋, в ко-
тором выделен самый левый нетерминал 𝐾: 𝑋 = 𝐴𝐾𝑆, где 𝐴 | слово
из терминалов, 𝑆 | слово из терминалов и нетерминалов. Пусть суще-
ствуют два различных правила грамматики с нетерминалом 𝐾 в левой
части, и мы применили их к выделенному в 𝑋 нетерминалу 𝐾, затем
продолжили вывод и в конце концов получили два слова из терминалов,
начинающихся на 𝐴. Докажите, что в этих словах за началом 𝐴 идут
разные буквы. (Здесь к числу букв мы относим EOI.)

15.3. Алгоритм разбора для LL(1)-грамматик
289
Решение. Эти буквы принадлежат направляющим множествам раз-
личных правил.
15.3.6. Докажите, что если слово выводимо в LL(1)-грамматике, то
его левый вывод единствен.
Решение. Предыдущая задача показывает, что на каждом шаге ле-
вый вывод продолжается однозначно.
15.3.7. Грамматика называется леворекурсивной, если из некоторо-
го нетерминала 𝐾 выводится слово, начинающееся с 𝐾, но не совпада-
ющее с ним. Докажите, что леворекурсивная грамматика, в которой из
каждого нетерминала выводится хотя бы одно непустое слово из тер-
миналов и для каждого нетерминала существует вывод (начинающий-
ся с начального нетерминала), в котором он встречается, не является
LL(1)-грамматикой.
Решение. Пусть из 𝐾 выводится 𝐾𝑈, где 𝐾 | нетерминал, а 𝑈 |
непустое слово. Можно считать, что это левый вывод (другие нетерми-
налы можно не заменять). Рассмотрим вывод
𝐾
𝐾𝑈
𝐾𝑈𝑈
. . .
(знак
обозначает несколько шагов вывода) и левый вывод 𝐾
𝐴,
где 𝐴 | непустое слово из терминалов. На каком-то шаге второй вы-
вод отклоняется от первого, а между тем по обоим путям может быть
получено слово, начинающееся на 𝐴 (в первом случае это возможно, так
как сохраняется нетерминал 𝐾, который может впоследствии быть за-
менён на 𝐴). Это противоречит возможности однозначного определе-
ния правила, применяемого на очередном шаге поиска левого вывода.
(Однозначность выполняется для выводов из начального нетермина-
ла, и надо воспользоваться тем, что 𝐾 по предположению встречается
в таком выводе.)
Таким образом, к леворекурсивным грамматикам (кроме тривиаль-
ных случаев) LL(1)-метод неприменим. Их приходится преобразовы-
вать в эквивалентные LL(1)-грамматики | или пользоваться другими
методами распознавания.
15.3.8. Используя сказанное, постройте алгоритм проверки выво-
димости слова из терминалов в LL(1)-грамматике.
Решение. Мы следуем описанному выше методу поиска левого вы-
вода, храня лишь часть слова, находящуюся правее уже прочитанной

290
15. Контекстно-свободные грамматики
части входного слова. Другими словами, мы храним слово S из терми-
налов и нетерминалов, обладающее такими свойствами (прочитанную

жүктеу/скачать 1,66 Mb.

Достарыңызбен бөлісу: