Контекстно-свободные грамматики. Общий алгоритм разбора.

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

(а) указать конечное множество A, называемое алфавитом; его элементы называют символами; конечные последовательности символов называют словами (в данном алфавите);

(б) разделить все символы алфавита A на две группы: терминальные («окончательные») и нетерминальные («промежуточные»);

(в) выбрать среди нетерминальных символов один, называемый начальным;

(г) указать конечное число правил грамматики, каждое из которых должно иметь вид

K -> X где K —некоторый нетерминальный символ, а X —слово (в него могут входить и терминальные, и нетерминальные символы).

Пусть фиксирована КС-грамматика (мы часто будем опускать приставку «КС‑», так как других грамматик у нас не будет). Выводом в этой грамматике называется последовательность слов X[0], X[1],..., X[n], в которой X[0] состоит из одного символа, и этот символ —начальный, а X[i+1] получается из X[i] заменой некоторого нетерминального символа K на слово X по одному из правил грамматики. Слово, составленное из терминальных символов, называется выводимым, если существует вывод, который им кончается. Множество всех выводимых слов (из терминальных символов) называется языком, порождаемым данной грамматикой.

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

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

( ) [ ] E

(четыре терминальных символа и один нетерминальный символ E). Начальный символ: e.

Правила:

E -> (E)

E -> [E]

E -> EE

E ->

(в последнем правиле справа стоит пустое слово).

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

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

()

([])

()[([])]

[()[]()[]]

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

(

)(

(]

([)]