Контекстно-свободные грамматики

15.1.4. Привести пример другой грамматики, задающей тот же язык.

Ответ. Вот один из вариантов:$$\begin{align*} \langle{выр}\rangle \to\langle{выр}\rangle\ \hbox{\texttt{+}}\ \langle{выр}\rangle\\ \langle{выр}\rangle \to\langle{выр}\rangle\ \hbox{\texttt{*}}\ \langle{выр}\rangle\\ \langle{выр}\rangle \to \hbox{\texttt{x}}\\ \langle{выр}\rangle \to \hbox{\texttt{(}}\ \langle{выр}\rangle\ \hbox{\texttt{)}} \end{align*}$$

Эта грамматика хоть и проще, но в некоторых отношениях хуже, о чем мы еще будем говорить.

15.1.5. Дана произвольная КС-грамматика. Построить алгоритм проверки принадлежности задаваемому ей языку, работающий полиномиальное время (т.е. число действий не превосходит полинома от длины проверяемого слова; полином может зависеть от грамматики).

Решение. Заметим, что требование полиномиальности исключает возможность решения, основанном на переборе всех возможных выводов. Тем не менее полиномиальный алгоритм существует. Поскольку практического значения он не имеет (используемые на практике КС-грамматики обладают дополнительными свойствами, позволяющими строить более эффективные алгоритмы), мы изложим лишь общую схему решения.

(1) Пусть в грамматике есть нетерминалы $$K_1,\ldots,K_n$$. Построим новую грамматику с нетерминалами $$K_1',\ldots,K_n'$$ так, чтобы выполнялось такое свойство: из $$K_i'$$ выводятся (в новой грамматике) те же слова, что из $$K_i$$ в старой, за исключением пустого слова, которое не выводится.

Чтобы выполнить такое преобразование грамматики, надо выяснить, из каких нетерминалов исходной грамматики выводится пустое слово, а затем каждое правило заменить на совокупность правил, получающихся, если в правой части опустить какие-либо из нетерминалов, из которых выводится пустое слово, а у остальных поставить штрихи. Например, если в исходной грамматике было правило$$\begin{center}\ttfamily K \to L M N, \end{center}$$ причем из L и N выводится пустое слово, а из M нет, то это правило надо заменить на правила$$\begin{align*} \hbox{\texttt{K}}' \to \hbox{\texttt{L}}'\hbox{\texttt{M}}'\hbox{\texttt{N}}'\\ \hbox{\texttt{K}}' \to \hbox{\texttt{M}}'\hbox{\texttt{N}}'\\ \hbox{\texttt{K}}' \to \hbox{\texttt{L}}'\hbox{\texttt{M}}'\\ \hbox{\texttt{K}}' \to \hbox{\texttt{M}}' \end{align*}$$

(2) Итак, мы свели дело к грамматике, где ни из одного нетерминала не выводится пустое слово. Теперь устраним "циклы" вида$$\begin{align*} \texttt{K} \to \texttt{L} \\ \texttt{L} \to \texttt{M} \\ \texttt{M} \to \texttt{N} \\ \texttt{N} \to \texttt{K} \end{align*}$$ (в правой части каждого правила один символ, и эти символы образуют цикл произвольной длины): это легко сделать, отождествив все входящие в цикл нетерминалы.

(3) Теперь проверка принадлежности какого-либо слова языку, порожденному грамматикой, может выполняться так: для каждого подслова проверяемого слова и для каждого нетерминала выясняем, порождается ли это подслово этим нетерминалом. При этом подслова проверяются в порядке возрастания длин, а нетерминалы - в таком порядке, чтобы при наличии правила $$K \to L$$ нетерминал $$L$$ проверялся раньше нетерминала $$K$$. (Это возможно в силу отсутствия циклов.) Поясним этот процесс на примере.

Пусть в грамматике есть правила$$\begin{align*} \texttt{K} \to \texttt{L}\\ \texttt{K} \to \texttt{M N L} \end{align*}$$ и других правил, содержащих K в левой части, нет. Мы хотим узнать, выводится ли данное слово $$A$$ из нетерминала K. Это будет так в одном из случаев:

Вся эта информация уже есть (слова $$B$$, $$C$$, $$D$$ короче $$A$$, а L рассмотрен до K ).

Легко видеть, что число действий этого алгоритма полиномиально. Степень полинома зависит от числа нетерминалов в правых частях правил и может быть понижена, если грамматику преобразовать к форме, в которой правая часть каждого правила не более $$2$$ нетерминалов (это легко сделать, вводя новые нетерминалы: например, правило $$K \to LMK$$ можно заменить на $$K \to LN$$ и $$N \to MK$$, где N - новый нетерминал).

15.1.6. Рассмотрим грамматику с единственным нетерминалом K, нетерминалами 1, 2, 3 и правилами$$\begin{align*} \texttt{K} \to \texttt{0}\\ \texttt{K} \to \texttt{1 K}\\ \texttt{K} \to \texttt{2 K K}\\ \texttt{K} \to \texttt{3 K K K} \end{align*}$$ Как проверить выводимость слова в этой грамматике, читая слово слева направо? (Число действий при прочтении одной буквы должно быть ограничено.)

Решение. Хранится целая переменная n, инвариант: слово выводимо $$\Leftrightarrow$$ непрочитанная часть представляет собой конкатенацию (соединение) n выводимых слов.

15.1.7. Тот же вопрос для грамматики$$\begin{align*} \texttt{K} \to \texttt{0}\\ \texttt{K} \to \texttt{K 1}\\ \texttt{K} \to \texttt{K K 2}\\ \texttt{K} \to \texttt{K K K 3} \end{align*}$$

15.2. Метод рекурсивного спуска

В отличие от алгоритма предыдущего раздела (представляющего чисто теоретический интерес), алгоритмы на основе рекурсивного спуска часто используются на практике. Этот метод применим, однако, далеко не ко всем грамматикам. Мы обсудим необходимые ограничения позднее.

Идея метода рекурсивного спуска такова. Для каждого нетерминала K мы строим процедуру ReadK, которая - в применении к любому входному слову $$x$$ - делает две вещи:

Прежде чем описывать этот метод более подробно, договоримся о том, как процедуры получают сведения о входном слове и как сообщают о результатах своей работы. Мы предполагаем, что буквы входного слова поступают к ним по одной, т.е. имеется граница, отделяющая "прочитанную" часть от quot;непрочитанной". Будем считать, что есть функция (без параметров)$$\begin{center}\ttfamily Next: Symbol \end{center}$$ дающая первый непрочитанный символ. Ее значениями могут быть терминальные символы, а также специальный символ EOI (End Of Input - конец входа), означающий, что все слово уже прочитано. Вызов этой функции, разумеется, не сдвигает границы между прочитанной и непрочитанной частью - для этого есть процедура Move, которая сдвигает границу на один символ. (Она применима, если Next<>EOI.) Пусть, наконец, имеется булевская переменная b.

Теперь мы можем сформулировать наши требования к процедуре ReadK. Они состоят в следующем:

Для удобства введем такую терминологию: выводимое из K слово будем называть K -словом, а любое начало любого выводимого из K слова - K -началом. Два сформулированных требования вместе будем выражать словами " ReadK корректна для K ".

Начнем с примера. Пусть правило$$\begin{center}\ttfamily K \to L M \end{center}$$ является единственным правилом грамматики, содержащим 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. Для этого нам понадобятся некоторые обозначения. Пусть фиксированы КС-грамматика и некоторый нетерминал $$N$$ этой грамматики. Рассмотрим $$N$$ -слово $$A$$, которое имеет собственное начало $$B$$, также являющееся $$N$$ -словом (если такие есть). Для любой пары таких слов $$A$$ и $$B$$ рассмотрим терминальный символ, идущий в $$A$$ непосредственно за $$B$$. Множество всех таких терминалов обозначим Посл(N). (Если никакое $$N$$ -слово не является собственным началом другого $$N$$ -слова, то множество Посл(N) пусто.)

15.2.2. Указать (а) Посл(E) для примера 1 (см. пункт 15.1.); (б) Посл(E) и Посл(T) для примера 2 (см. пункт 15.1.); (в) $$Посл(\langle{слаг}\rangle)$$ и $$Посл(\langle{множ}\rangle)$$ для примера 3 (см. пункт 15.1.);

Ответ. (а) Посл(E) = {[, (}. (б) Посл(E) = {[, (} ; Посл(T) пусто (никакое T -слово не является началом другого). (в) $$Посл(\langle{слаг}\rangle) = \{\hbox{\texttt{*}}\}$$ ; $$Посл(\langle{множ}\rangle)$$ пусто.

Кроме того, для каждого нетерминала $$N$$ обозначим через Нач(N ) множество всех терминалов, являющихся первыми буквами непустых $$N$$ -слов. Это обозначение - вместе с предыдущим - позволит дать достаточное условие корректности процедуры ReadK в описанной выше ситуации.

15.2.3. Доказать, что если Посл(L) не пересекается с Нач(M) и множество всех M -слов непусто, то ReadK корректна.

Решение. Рассмотрим два случая.

(1) Пусть после ReadL значение переменной b ложно. В этом случае ReadL читает со входа максимальное L -начало $$A$$, не являющееся L -словом. Оно является K -началом (здесь важно, что множество M -слов непусто.). Будет ли оно максимальным K -началом среди начал входа? Если нет, то $$A$$ является началом слова $$BC$$, где $$B$$ есть L -слово, $$C$$ есть M -начало и $$BC$$ - более длинное начало входа, чем $$A$$. Если $$B$$ длиннее $$A$$, то $$A$$ - не максимальное начало входа, являющееся L -началом, что противоречит корректности ReadL. Если $$B = A$$, то $$A$$ было бы L -словом, а это не так. Значит, $$B$$ короче $$A$$, $$C$$ непусто и первый символ слова $$C$$ следует в $$A$$ за последним символом слова $$B$$, т.е. Посл(L) пересекается с Нач(M). Противоречие. Итак, $$A$$ максимально. Из сказанного следует также, что $$A$$ не является K -словом. Корректность процедуры ReadK в этом случае проверена.

(2) Пусть после ReadL значение переменной b истинно. Тогда прочитанное процедурой ReadK начало входа имеет вид $$AB$$, где $$A$$ есть L -слово, а $$B$$ есть M -начало. Тем самым $$AB$$ есть K -начало. Проверим его максимальность. Пусть $$C$$ есть большее K -начало. Тогда либо $$C$$ есть L -начало (что невозможно, так как $$A$$ было максимальным L -началом), либо $$C = A'B'$$, где $$A'$$ - L -слово, $$B'$$ - M -начало. Если $$A'$$ короче $$A$$, то $$B'$$ непусто и начинается с символа, принадлежащего и Нач(M), и Посл(L), что невозможно. Если $$A'$$ длиннее $$A$$, то $$A$$ - не максимальное L -начало.

Итак, $$A' = A$$. Но в этом случае $$B'$$ есть продолжение $$B$$, что противоречит корректности ReadM. Итак, $$AB$$ - максимальное K -начало. Остается проверить правильность выдаваемого процедурой ReadK значения переменной b. Если оно истинно, то это очевидно. Если оно ложно, то $$B$$ не есть M -слово, и надо проверить, что $$AB$$ - не K -слово. В самом деле, если бы выполнялось $$AB = A'B'$$, где $$A'$$ - L -слово, $$B'$$ - M -слово, то $$A'$$ не может быть длиннее $$A$$ ( ReadL читает максимальное слово), $$A'$$ не может быть равно $$A$$ (тогда $$B'$$ равно $$B$$ и не является M -словом) и $$A'$$ не может быть короче $$A$$ (тогда первый символ $$B'$$ принадлежит и Нач(M), и Посл(L) ). Задача решена.

Перейдем теперь к другому частному случаю. Пусть в КС-грамматике есть правила$$\begin{align*} \hbox{\texttt{K}}\to\hbox{\texttt{L}}\\ \hbox{\texttt{K}}\to\hbox{\texttt{M}}\\ \hbox{\texttt{K}}\to\hbox{\texttt{N}} \end{align*}$$ и других правил с левой частью 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),то пустое слово является наибольшим началом входа, являющимся K -началом. Если Next принадлежит одному (и, следовательно, только одному) из этих множеств, то максимальное начало входа, являющееся K -началом, непусто и читается соответствующей процедурой.

15.2.5. Используя сказанное, составить процедуру распознавания выражений для грамматики (пример 3, см. пункт 15.1.):$$\begin{align*} \langle{выр}\rangle \to\langle{слаг}\rangle\ \langle{оствыр}\rangle\\ \langle{оствыр}\rangle \to \hbox{\texttt{+}}\ \langle{выр}\rangle\\ \langle{оствыр}\rangle \to \\ \langle{слаг}\rangle \to \langle{множ}\rangle\ \langle{остслаг}\rangle\\ \langle{остслаг}\rangle \to \hbox{\texttt{*}}\ \langle{слаг}\rangle\\ \langle{остслаг}\rangle\to \\ \langle{множ}\rangle \to \hbox{\texttt{x}}\\ \langle{множ}\rangle \to \hbox{\texttt{(}}\ \langle{выр}\rangle\ \hbox{\texttt{)}} \end{align*}$$

Решение. Эта грамматика не полностью подпадает под рассмотренные частные случаи: в правых частях есть комбинации терминалов и нетерминалов$$\begin{center}\ttfamily + \langle{выр}\rangle \end{center}$$ и группы из трех символов$$\begin{center}\ttfamily ( \langle{выр}\rangle\ ) \end{center}$$ В грамматике есть также несколько правил с одной левой частью и с правыми частями разного рода, например$$\begin{align*} \langle{оствыр}\rangle \to \hbox{\texttt{+}}\ \langle{выр}\rangle\\ \langle{оствыр}\rangle \to \end{align*}$$ Эти ограничения не являются принципиальными. Так, правило типа $${\texttt{K}}\to {\texttt{L M N}}$$ можно было бы заменить на два правила $${\texttt{K}} \to {\texttt{L Q}}$$ и $${\texttt{Q}} \to {\texttt{M N}}$$, терминальные символы в правой части - на нетерминалы (с единственным правилом замены на соответствующие терминалы). Несколько правил с одной левой частью и разнородными правыми также можно свести к уже разобранному случаю: например,$$\begin{align*} \hbox{\texttt{K}}\to\hbox{\texttt{L M N}}\\ \hbox{\texttt{K}}\to\hbox{\texttt{P Q}}\\ \hbox{\texttt{K}}\to \end{align*}$$ можно заменить на правила$$\begin{align*} \hbox{\texttt{K}}\to\hbox{\texttt{K}}_1\\ \hbox{\texttt{K}}\to\hbox{\texttt{K}}_2\\ \hbox{\texttt{K}}\to\hbox{\texttt{K}}_3\\ \hbox{\texttt{K}}_1 \to\hbox{\texttt{L M N}}\\ \hbox{\texttt{K}}_2 \to\hbox{\texttt{P Q}}\\ \hbox{\texttt{K}}_3 \to \end{align*}$$ Но мы не будем этого делать - а сразу же запишем то, что получится, если подставить описания процедур для новых терминальных символов в места их использования. Например, для правила$${\texttt{K}} \to {\texttt{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).

Аналогичным образом правила$$\begin{align*} \hbox{\texttt{K}}\to\hbox{\texttt{L M N}}\\ \hbox{\texttt{K}}\to\hbox{\texttt{P Q}}\\ \hbox{\texttt{K}}\to \end{align*}$$ приводят к процедуре

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).

Читая приведенную далее программу, полезно иметь в виду соответствие между русскими и английскими словами:$$\begin{tabular}{ll} ВЫРажение EXPRession \\ ОСТаток ВЫРажения REST of EXPRession\\ СЛАГаемое ADDitive term\\ ОСТаток СЛАГаемого REST of ADDitive term\\ МНОЖитель FACTor \end{tabular}$$

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
| | 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"). Как всегда для рекурсивных процедур, помимо доказательства того, что каждая процедура работает правильно в предположении, что используемые в ней вызовы процедур работают правильно, надо доказать отдельно, что работа завершается. (Это не очевидно: если в грамматике есть правило $${\texttt{K}}\to {\texttt{KK}}$$, то из K ничего не выводится, Посл(K) и Нач(K) пусты, но написанная по нашим канонам процедура

procedure ReadK;
begin
| ReadK;
| if b then begin
| | ReadK;
| end;
end;

не заканчивает работы.)

В данном случае процедуры ReadRestExpr, ReadRestAdd, ReadFact либо завершаются, либо уменьшают длину непрочитанной части входа. Поскольку любой цикл вызовов включает одну из них, то зацикливание невозможно.

15.2.6. Пусть в грамматике имеются два правила с нетерминалом K в левой части, имеющих вид$$\begin{align*} \hbox{\texttt{K}}\to\hbox{\texttt{L K}}\\ \hbox{\texttt{K}}\to \end{align*}$$ по которым 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;

Формально можно проверить эту эквивалентность так. Завершаемость в обоих случаях ясна. Достаточно проверить поэтому, что тело рекурсивной процедуры эквивалентно нерекурсивной в предположении, что ее рекурсивный вызов эквивалентен вызову нерекурсивной процедуры. Подставим:

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;

что эквивалентно приведенной выше нерекурсивной процедуре (из которой вынесена первая итерация цикла).

15.2.7. Доказать корректность приведенной выше нерекурсивной программы непосредственно, без ссылок на рекурсивную.

Решение. Рассмотрим наибольшее начало входа, являющееся K -началом. Оно представляется в виде конкатенации (последовательного приписывания) нескольких непустых L -слов и, возможно, одного непустого L -начала, не являющегося L -словом. Инвариант цикла: прочитано несколько из них; b $$\Leftrightarrow$$ (последнее прочитанное является L -словом).

Сохранение инварианта: если осталось последнее слово, это очевидно; если осталось несколько, то за первым L -словом (из числа оставшихся) идет символ из Нач(L), и потому это слово - максимальное начало входа, являющееся L -началом.

На практике при записи грамматики используют сокращения. Если правила для какого-то нетерминала K имеют вид$$\begin{align*} \hbox{\texttt{K}}\to \hbox{\texttt{L K}}\\ \hbox{\texttt{K}}\to \end{align*}$$ (т.е. K -слова - это последовательности L -слов), то этих правил не пишут, а вместо K пишут L в фигурных скобках. Несколько правил с одной левой частью и разными правыми записывают как одно правило, разделяя альтернативные правые части вертикальной чертой.

Например, рассмотренная выше грамматика для $$\langle{выр}\rangle$$ может быть записана так:

15.2.8. Написать процедуру, корректную для $$\langle{выр}\rangle$$, следуя этой грамматике и используя цикл вместо рекурсии, где можно.

Решение.

procedure ReadSymb (c: Symbol);
| b := (Next = c);
| if b then begin Move; end;
end;

procedure ReadExpr;
begin
| ReadAdd;
| 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)-разбором. Вот его идея в одной фразе: можно считать, что в процессе вывода мы всегда заменяем самый левый нетерминал и нужно лишь выбрать одно из правил; если нам повезет с грамматикой, то выбрать правило можно, глядя на первый символ выводимого из этого нетерминала слова. Говоря более формально, дадим такое

Определение. Левым выводом (слова в грамматике) называется вывод, в котором на каждом шаге замене подвергается самый левый из нетерминалов.

15.3.1. Для каждого выводимого слова (из терминалов) существует его левый вывод.

Решение. Различные нетерминалы заменяются независимо; если в процессе вывода появилось слово $$\ldots K\ldots L\ldots$$, где $$K$$, $$L$$ - нетерминалы, то замены $$K$$ и $$L$$ можно производить в любом порядке. Поэтому можно перестроить вывод так, чтобы стоящий левее нетерминал заменялся раньше. (Формально говоря, надо доказывать индукцией по длине вывода такой факт: если из некоторого нетерминала $$K$$ выводится некоторое слово $$A$$, то существует левый вывод $$A$$ из $$K$$.)

15.3.2. В грамматике с 4 правилами$$\begin{multiple} (1)\quad \hbox{\texttt{E}} \to \\ (2)\quad \hbox{\texttt{E}} \to \hbox{\texttt{TE}}\\ (3)\quad \hbox{\texttt{T}} \to \hbox{\texttt{(E)}}\\ (4)\quad \hbox{\texttt{T}} \to \hbox{\texttt{[E]}} \end{multiple}$$ найти левый вывод слова $$A ={\texttt{[()([\,])]}}$$ и доказать, что он единствен.

Решение. На первом шаге можно применить только правило (2):$${\texttt{E}} \to {\texttt{TE}}$$ Что будет дальше с T? Так как слово $$A$$ начинается на [, то может примениться только правило (4):$${\texttt{E}} \to {\texttt{TE}}\to {\texttt{[E]E}}$$ Первое E должно замениться на TE (иначе вторым символом была бы скобка ] ):$${\texttt{E}} \to {\texttt{TE}}\to{\texttt{[E]E}} \to{\texttt{[TE]E}}$$ и T должно заменяться по (3):$${\texttt{E}}\to{\texttt{TE}}\to{\texttt{[E]E}} \to{\texttt{[TE]E}}\to{\texttt{[(E)E]E}}$$ Далее первое E должно замениться на пустое слово (иначе третьей буквой слова будет ( или [ - только на эти символы может начинаться слово, выводимое из T ):$${\texttt{E}}\to{\texttt{TE}}\to{\texttt{[E]E}}\to{\texttt{[TE]E}}\to{\texttt{[(E)E]E}}\to{\texttt{[()E]E}}$$ и далее$$\begin{multiline*} \ldots\to \hbox{\texttt{[()TE]E}} \to\hbox{\texttt{[()(E)E]E}} \to\hbox{\texttt{[()(TE)E]E}} \to\hbox{\texttt{[()([E]E)E]E}}\to{}\\ % \to\hbox{\texttt{[()([\,]E)E]E}} \to\hbox{\texttt{[()([\,])E]E}} \to\hbox{\texttt{[()([\,])]E}} \to\hbox{\texttt{[()([\,])]}} \end{multiline*}$$

Что требуется от грамматики, чтобы такой метод поиска левого вывода был применим? Пусть, например, на очередном шаге самым левым нетерминалом оказался нетерминал $$K$$, т.е. мы имеем слово вида $$AKU$$, где $$A$$ - слово из терминалов, а $$U$$ - слово из терминалов и нетерминалов. Пусть в грамматике есть правила$$\begin{align*} K\to L M N\\ K\to P Q\\ K\to R \end{align*}$$ Нам надо выбрать одно из них. Мы будем пытаться сделать этот выбор, глядя на первый символ той части входного слова, которая выводится из $$KU$$.

Рассмотрим множество Нач(LMN) тех терминалов, с которых начинаются непустые слова, выводимые из $$LMN$$. (Это множество равно Нач(L), объединенному с Нач(M), если из $$L$$ выводится пустое слово, а также с Нач(N), если из $$L$$ и из $$M$$ выводится пустое слово.) Чтобы описанный метод был применим, надо, чтобы Нач(LMN), Нач(PQ) и Нач(R) не пересекались. Но этого мало. Ведь может быть так, например, что из $$LMN$$ будет выведено пустое слово, а из слова $$U$$ будет выведено слово, начинающееся на букву из Нач(PQ). Следующие определения учитывают эту проблему.

Напомним, что определение выводимости в КС-грамматике было дано только для слова из терминалов. Оно очевидным образом обобщается на случай слов из терминалов и нетерминалов. Можно также говорить о выводимости одного слова (содержащего терминалы и нетерминалы) из другого. (Если говорится о выводимости слова без указания того, откуда оно выводится, то всегда подразумевается выводимость в грамматике, т.е. выводимость из начального нетерминала.)

Для каждого слова $$X$$ из терминалов и нетерминалов через Нач(X) обозначаем множество всех терминалов, с которых начинаются непустые слова из терминалов, выводимые из $$X$$. (В случае, если из любого нетерминала выводится хоть одно слово из терминалов, не играет роли, рассматриваем ли мы при определении Нач(X) слова только из терминалов или любые слова. Мы будем предполагать далее, что это условие выполнено.)

Для каждого нетерминала $$K$$ через Послед(K) обозначим множество терминалов, которые встречаются в выводимых (в грамматике) словах сразу же за $$K$$. (Не смешивать с Посл(K) предыдущего раздела!) Кроме того, в Послед(K) включается символ EOI, если существует выводимое слово, оканчивающееся на $$K$$.

Для каждого правила$$K \to V$$ (где $$K$$ - нетерминал, $$V$$ - слово, содержащее терминалы и нетерминалы) определим множество направляющих терминалов, обозначаемое $$Напр(K\to V)$$. По определению оно равно $$Нач(V)$$, к которому добавлено $$Послед(K)$$, если из $$V$$ выводится пустое слово.

Определение. Грамматика называется LL(1)-грамматикой, если для любых правил $$K\to V$$ и $$K\to W$$ с одинаковыми левыми частями множества $$Напр(K\to V)$$ и $$Напр(K\to W)$$ не пересекаются.

15.3.3. Является ли грамматика$$\begin{align*} \hbox{\texttt{K}}\to\hbox{\texttt{K \#}}\\ \hbox{\texttt{K}}\to \end{align*}$$ (выводимыми словами являются последовательности диезов) LL(1)- грамматикой?

Решение. Нет: символ # принадлежит множествам направляющих символов для обоих правил (для второго - поскольку # принадлежит $$Послед(K)$$ ).

15.3.4. Написать LL(1)-грамматику для того же языка.

Решение.$$\begin{align*} \hbox{\texttt{K}}\to\hbox{\texttt{\# K}}\\ \hbox{\texttt{K}}\to \end{align*}$$

Как говорят, "леворекурсивное" правило заменено на "праворекурсивное".

Следующая задача показывает, что для LL(1)-грамматики существует не более одного возможного продолжения левого вывода.

15.3.5. Пусть дано выводимое в LL(1)-грамматике слово $$X$$, в котором выделен самый левый нетерминал $$K$$: $$X=AKS$$, где $$A$$ - слово из терминалов, $$S$$ - слово из терминалов и нетерминалов. Пусть существуют два различных правила грамматики с нетерминалом $$K$$ в левой части, и мы применили их к выделенному в $$X$$ нетерминалу $$K$$, затем продолжили вывод и в конце концов получили два слова из терминалов, начинающихся на $$A$$. Доказать, что в этих словах за началом $$A$$ идут разные буквы. (Здесь к числу букв мы относим EOI.)

Решение. Эти буквы принадлежат направляющим множествам различных правил.

15.3.6. Доказать, что если слово выводимо в LL(1)-грамматике, то его левый вывод единствен.

Решение. Предыдущая задача показывает, что на каждом шаге левый вывод продолжается однозначно.

15.3.7. Грамматика называется леворекурсивной, если из некоторого нетерминала $$K$$ выводится слово, начинающееся с $$K$$, но не совпадающее с ним. Доказать, что леворекурсивная грамматика, в которой из каждого нетерминала выводится хотя бы одно непустое слово из терминалов и для каждого нетерминала существует вывод (начинающийся с начального нетерминала), в котором он встречается, не является LL(1)-грамматикой.

Решение. Пусть из $$K$$ выводится $$KU$$, где $$K$$ - нетерминал, а $$U$$ - непустое слово. Можно считать, что это левый вывод (другие нетерминалы можно не заменять). Рассмотрим вывод$$K \leadsto KU \leadsto KUU \leadsto \ldots$$ (знак $$\leadsto$$ обозначает несколько шагов вывода) и левый вывод $$K \leadsto A$$, где $$A$$ - непустое слово из терминалов. На каком-то шаге второй вывод отклоняется от первого, а между тем по обоим путям может быть получено слово, начинающееся на $$A$$ (в первом случае это возможно, так как сохраняется нетерминал $$K$$, который может впоследствии быть заменен на $$A$$ ). Это противоречит возможности однозначного определения правила, применяемого на очередном шаге поиска левого вывода. (Однозначность выполняется для выводов из начального нетерминала, и надо воспользоваться тем, что $$K$$ по предположению встречается в таком выводе.)

Таким образом, к леворекурсивным грамматикам (кроме тривиальных случаев) LL(1)-метод неприменим. Их приходится преобразовывать к эквивалентным LL(1)-грамматикам - или пользоваться другими методами распознавания.

15.3.8. Используя сказанное, построить алгоритм проверки выводимости слова из терминалов в LL(1)-грамматике.

Решение. Мы следуем описанному выше методу поиска левого вывода, храня лишь часть слова, находящуюся правее уже прочитанной части входного слова. Другими словами, мы храним слово S из терминалов и нетерминалов, обладающее такими свойствами (прочитанную часть входа обозначаем через A ):

Эти свойства вместе будем обозначать "(И)".

Вначале A пусто, а S состоит из единственного символа - начального нетерминала.

Если в некоторый момент S начинается на терминал t и $${\texttt{t}} = {\texttt{Next}}$$, то можно выполнить команду Move и удалить символ t, являющийся начальным в S, поскольку при этом AS не меняется.

Если S начинается на терминал t и $${\texttt{t}}\neq{\texttt{Next}}$$, то входное слово невыводимо - ибо по условию любой его вывод должен проходить через AS. (Это же справедливо и в случае $${\texttt{Next}} = {\texttt{EOI}}$$.)

Если S пусто, то из условия (И) следует, что входное слово выводимо тогда и только тогда, когда $${\texttt{Next}} = {\texttt{EOI}}$$.

Остается случай, когда S начинается с некоторого нетерминала K. По доказанному выше все левые выводы из S слов, начинающихся на символ Next, начинаются с применения к S одного и того же правила - того, для которого Next принадлежит направляющему множеству. Если таких правил нет, то входное слово невыводимо. Если такое правило есть, то нужно применить его к первому символу слова S - при этом свойство (И) не нарушится. Приходим к такому алгоритму:

s := пустое слово;
error := false;
{error => входное слово невыводимо;}
{not error => (И)}
while (not error) and not ((Next=EOI) and (S пусто))
| |  do begin
| if (S начинается на терминал, равный Next) then begin
| | Move; удалить из S первый символ;
| end else if (S начинается на терминал, не равный Next)
| |   then begin
| | error := true;
| end else if (S пусто) and (Next <> EOI) then begin
| | error := true;
| end else if (S начинается на нетерминал и Next входит в
| |    направляющее множество одного из правил для этого
| |    нетерминала) then begin
| | применить это правило
| end else if (S начинается на нетерминал и Next не входит
| |  в направляющее множество ни одного из правил для этого
| |  нетерминала) then begin
| | error := true;
| end else begin
| | {так не бывает}
| end;
end;
{входное слово выводимо <=> not error}

Алгоритм заканчивает работу, поскольку при появлении терминала в начале слова S происходит чтение со входа или остановка, а бесконечный цикл сменяющих друг друга нетерминалов в начале S означал бы, что грамматика леворекурсивна. (А мы можем предполагать, согласно предыдущей задаче, что это не так: нетерминалы, не встречающиеся в выводах, а также нетерминалы, из которых не выводится непустого слова, несложно удалить из грамматики.)

Замечания.

15.3.9. При проверке того, относится ли данная грамматика к типу LL(1), необходимо вычислить $$Послед(T)$$ и $$Нач(T)$$ для всех нетерминалов $$T$$. Как это сделать?

Решение.Пусть, например, в грамматике есть правило $$K\to L\,M\,N$$. Тогда$${\setlength{\tabcolsep}{0pt} %%%%%\hbox to\textwidth{\hss \begin{tabular}{rcll} {Нач}\,(L) \subset {Нач}\,(K),\quad \\ {Нач}\,(M) \subset {Нач}\,(K),\quad \text{если из L выводимо пустое слово,}\\ {Нач}\,(N) \subset {Нач}\,(K),\quad \text{если из L и M выводимо пустое слово,}\\ % {Послед}\,(K) \subset {Послед}\,(N),\quad \\ {Послед}\,(K) \subset {Послед}\,(M),\quad \text{если из N выводимо пустое слово,}\\ {Послед}\,(K) \subset {Послед}\,(L),\quad \text{если из M и N выводимо пустое слово,}\\ % {Нач}\,(N) \subset {Послед}\,(M),\quad \\ {Нач}\,(M) \subset {Послед}\,(L),\quad \\ {Нач}\,(N) \subset {Послед}\,(L),\quad \text{если из M выводимо пустое слово.} %%%%%\end{tabular}\hss} \end{alignat*}$$ Подобные правила позволяют постепенно шаг за шагом порождать множества Нач( $$T$$ ), а затем и Послед( $$T$$ ), для всех терминалов и нетерминалов $$T$$. При этом началом служит$${EOI} \in {Послед}\,(K)$$ для начального нетерминала $$K$$ и$$z \in {Нач}\,(z)$$ для любого терминала $$z$$. Порождение заканчивается, когда применение правил перестает давать новые элементы множеств Нач(T) и Послед(T).