Общий алгоритм разбора

Чтобы определить то, что называют контекстно-свободной грамматикой (КС-грамматикой), надо:

указать конечное множество A , называемое алфавитом; его элементы называют символами; конечные последовательности символов называют словами (в данном алфавите);
разделить все символы алфавита A на две группы: терминальные (<< окончательные>>) и нетерминальные (<< промежуточные>>);
выбрать среди нетерминальных символов один, называемый начальным;
указать конечное число правил грамматики, каждое из которых должно иметь вид $K \to X$ ,где K -- некоторый нетерминальный символ, а X -- слово (в него могут входить и терминальные, и нетерминальные символы).

Пусть фиксирована КС-грамматика (мы часто будем опускать приставку << КС->>, так как других грамматик у нас не будет). Выводом в этой грамматике называется последовательность слов $X_0, X_1,\ldots,X_n$ , в которой X₀ состоит из одного символа, и этот символ -- начальный, а X_i+1 получается из X_i заменой некоторого нетерминального символа K на слово X по одному из правил грамматики. Слово, составленное из терминальных символов, называется выводимым, если существует вывод, который им кончается. Множество всех выводимых слов (из терминальных символов) называется языком, порождаемым данной грамматикой.

В этой и следующей главе нас будет интересовать такой вопрос: дана КС-грамматика; построить алгоритм, который по любому слову проверяет, выводимо ли оно в этой грамматике.

Пример 1. Алфавит:

( ) [ ] E

(четыре терминальных символа и один нетерминальный символ E). Начальный символ: E. Правила: $\begin{eqnarray*} \mbox{\tt E} & \to & \mbox{\tt (E)}\\ \mbox{\tt E} & \to & \m... ...E]}\\ \mbox{\tt E} & \to & \mbox{\tt EE}\\ \mbox{\tt E} & \to &\end{eqnarray*}$ (в последнем правиле справа стоит пустое слово).

Примеры выводимых слов:

(пустое слово) () ([]) ()[([])] [()[]()[]]

Примеры невыводимых слов:

( )( (] ([)]

Эта грамматика встречалась в разделе 6 (где выводимость в ней проверялась с помощью стека).

Пример 2. Другая грамматика, порождающая тот же язык: Алфавит: ( ) [ ] T E

Правила: $\begin{eqnarray*} \mbox{\tt E} &\to&\\ \mbox{\tt E} &\to&\mbox{\tt TE}\\ \mbox{\tt T} &\to&\mbox{\tt (E)}\\ \mbox{\tt T} &\to&\mbox{\tt [E]}\end{eqnarray*}$ Начальным символом во всех приводимых далее примерах будем считать символ, стоящий в левой части первого правила (в данном случае это символ E), не оговаривая этого особо.

Для каждого нетерминального символа можно рассмотреть множество всех слов из терминальных символов, которые из него выводятся (аналогично тому, как это сделано для начального символа в определении выводимости в грамматике). Каждое правило грамматики можно рассматривать как свойство этих множеств. Покажем это на примере только что приведенной грамматики. Пусть T и E -- множества слов (из скобок), выводимых из нетерминалов T и E соответственно. Тогда правилам грамматики соответствуют такие свойства:

=10000 $\begin{displaymath} \begin{tabular} {lp{.5\textwidth}} \mbox{\tt E} $\to$\space ... ...во {\hbox{\tt (}}$A${\hbox{\tt )}} принадлежит $T$\end{tabular}\end{displaymath}$

Сформулированные свойства множеств E , T не определяют эти множества однозначно (например, они остаются верными, если в качестве E и T взять множество всех слов). Однако можно доказать, что множества, задаваемые грамматикой, являются минимальными среди удовлетворяющих этим условиям.

$\scriptstyle{\blacktriangleright}$ 13.1.1. Сформулируйте точно и докажите это утверждение для произвольной контекстно-свободной грамматики. $\scriptstyle\blacktriangleleft$

$\scriptstyle{\blacktriangleright}$ 13.1.2. Постройте грамматику, в которой выводимы слова

(а) 00..0011..11 (число нулей равно числу единиц);

(б) 00..0011..11 (число нулей вдвое больше числа единиц);

(в) 00..0011..11 (число нулей больше числа единиц);

(и только они). $\scriptstyle\blacktriangleleft$

$\scriptstyle{\blacktriangleright}$ 13.1.3. Доказать, что не существует КС-грамматики, в которой были бы выводимы слова вида 00..0011..1122..22, в которых числа нулей, единиц и двоек равны, и только они.

[Указание. Докажите следующую лемму о произвольной КС-грамматике: для любого достаточно длинного слова F , выводимого в этой грамматике, существует такое его представление в виде ABCDE , что любое слово вида $AB\ldots BCD\ldots DE$ ,где B и D повторены одинаковое число раз, также выводимо в этой грамматике. (Это можно установить, найдя нетерминальный символ, оказывающийся своим собственным << наследником>> в процессе вывода.)] $\blacktriangleleft$

Нетерминальный символ можно рассматривать как << родовое имя>> для выводимых из него слов. В следующем примере для наглядности в качестве нетерминальных символов использованы фрагменты русских слов, заключенные в угловые скобки. (С точки зрения грамматики каждый такой фрагмент -- один символ!)

Пример 3. Алфавит:

    терминалы:   + * ( ) x
    нетерминалы:   32970 32971 32972 32973 32974
    правила:

$\begin{eqnarray*} \vyrazh &\to&\slag \ \ostvyr \\ \ostvyr &\to& \hbox{\tt +}\ \... ... \hbox{\tt x}\\ \mnozh &\to& \hbox{\tt(}\ \vyrazh \ \hbox{\tt )}\end{eqnarray*}$ Согласно этой грамматике, выражение 32992 -- это последовательность слагаемых 32993, разделенных плюсами, слагаемое -- это последовательность множителей 32994, разделенных звездочками (знаками умножения), а множитель -- это либо буква x, либо выражение в скобках.

$\scriptstyle{\blacktriangleright}$ 13.1.4. Приведите пример другой грамматики, задающей тот же язык.

Ответ. Вот один из вариантов: $\begin{eqnarray*} \vyrazh &\to&\vyrazh \ \hbox{\tt +}\ \vyrazh \\ \vyrazh &\to&... ... \hbox{\tt x}\\ \vyrazh &\to& \hbox{\tt(}\ \vyrazh \ \hbox{\tt)}\end{eqnarray*}$ Эта грамматика хоть и проще, но в некоторых отношениях хуже, о чем мы еще будем говорить. $\scriptstyle\blacktriangleleft$

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

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

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

Чтобы выполнить такое преобразование грамматики, надо выяснить, из каких нетерминалов исходной грамматики выводится пустое слово, а затем каждое правило заменить на совокупность правил, получающихся, если в правой части опустить какие-либо из нетерминалов, из которых выводится пустое слово, а у остальных поставить штрихи. Например, если в исходной грамматике было правило

K L M N,

причем из L и N выводится пустое слово, а из M нет, то это правило надо заменить на правила $\begin{eqnarray*} \hbox{\tt K}' &\to&\hbox{\tt L}'\hbox{\tt M}'\hbox{\tt N}'\\ ... ...& \hbox{\tt L}'\hbox{\tt M}'\\ \hbox{\tt K}' &\to& \hbox{\tt M}'\end{eqnarray*}$

(2) Итак, мы свели дело к грамматике, где ни из одного нетерминала не выводится пустое слово. Теперь устраним << циклы>> вида

K L L M M N N K

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

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

Пусть в грамматике есть правила

K L K M N L

и других правил, содержащих K в левой части, нет. Мы хотим узнать, выводится ли данное слово A из нетерминала K. Это будет так в одном из случаев:

если A выводится из L;
если 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 -- новый нетерминал). $\scriptstyle\blacktriangleleft$

$\scriptstyle{\blacktriangleright}$ 13.1.6. Рассмотрим грамматику с единственным нетерминалом K, нетерминалами 1, 2, 3 и правилами

K 0 K 1 K K 2 K K K 3 K K K

Как проверить выводимость слова в этой грамматике, читая слово слева направо? (Число действий при прочтении одной буквы должно быть ограничено.)

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

$\scriptstyle{\blacktriangleright}$ 13.1.7. Тот же вопрос для грамматики

K 0 K K 1 K K K 2 K K K K 3

pvv
1/8/1999