Построение автомата с магазинной памятью по q-грамматике

Контекстно-свободная грамматика называется q-грамматикой тогда и только тогда, когда выполняются два условия:

1. Правая часть каждого правила либо представляет собой пустую цепочку e, либо начинается с терминального символа.

2. Множество выбора правил с одной и той же левой частью не пересекаются.

Второе условие следует рассмотреть подробнее, так как необходимо ввести ряд определений. Одно из них – множество выбора. Для демонстрации определений будем использовать пример q-грамматики G_9.4(S):

1. S → aAS

2. S → b

3. A→cAS

4. A → e

О том, что это не S-грамматика говорит правая часть правила 4, которая не начинается с терминального символа. Однако, метод построения НАМП, изложенный для S-грамматики почти подходит и здесь.

Множество терминалов, следующих за данным нетерминалом X (Обозначим через СЛЕД(X)) – множество терминальных символов, которые могут следовать непосредственно за Х в какой-либо промежуточной цепочке, выводимой из S┤, включая и ┤.

Это множество символов называется также множеством следуемых за Х терминалов. Для приведенной грамматики можно определить следующие множества:

СЛЕД(А) = {a, b}

СЛЕД(S) = {a, b}

Терминалы, следующие за A, определяются исходя из того, что за A следует всегда нетерминал S, правая часть правила для которого начинается либо с a, либо с b. Терминалы, следующие за S, выводятся путем подстановки в правило 1 правила 3, которая показывает, что за S всегда следует S, начинающаяся либо с a, либо с b:

S Þ aAS Þ acASS.

Данное понятие используется для того, чтобы показать, когда следует применять правило с пустой правой частью A → e . Если входной символ T_i Ï {a, b}, то есть, является символом c или ┤, a на вершине магазина А, то бесполезно применять A → e . Если это правило будет применено, то А удаляется из стека, а так как за А символы c или ┤ следовать не могут, то в результате процесс останавливается. Представим, что у нас уже есть автомат, соответствующий грамматике G_9.4, и очень похожий на АМП, распознающий S-грамматику. Тогда, применительно к цепочке аасbb, можно получить несколько решений. В начале рассмотрим стратегию, при которой в первую очередь применяется всегда пустое правило.

Номер шага	Содержимое стека	Остаток входной цепочки	Номер применяемого правила	Комментарий
	Ñ S	aacbb┤
	Ñ SA	acbb┤		Иначе, процесс разбора дальше не пойдет
	Ñ S	acbb┤
	Ñ SA	cbb┤		А здесь данный шаг ведет к отказу по отношению к правильной цепочке
	Ñ S	cbb┤	Отвергнуть	Придется осуществлять возврат

Правильным было бы применение на шаге 4 правила 3, в соответствии с ранее рассмотренными рекомендациями о месте и времени применения пустого правила.

Номер шага	Содержимое стека	Остаток входной цепочки	Номер применяемого правила	Комментарий
	Ñ S	aacbb┤
	Ñ SA	acbb┤		Иначе, процесс разбора дальше не пойдет
	Ñ S	acbb┤
	Ñ SA	cbb┤		Пойдем в соответствии с предложенными рекомендациями
	Ñ SSA	bb┤		Иначе, процесс разбора дальше не пойдет
	Ñ SS	bb┤
	Ñ S	b┤
	Ñ	┤	Допустить

Таким способом решается одна из задач детерминированного разбора, связанная с особенностями применения пустого правила. Однако, при разборе, построенном на основе q-грамматики возможна и такая ситуация, когда:

A → bα, A → e и b Î СЛЕД(A).

В этом случае стоит проблема выбора одного из правил с одинаковыми левыми частями. Для ее решения введем понятие множества выбора для данного правила.

Если правило грамматики имеет вид: A → bα, где b – терминал, а α– цепочка терминалов и нетерминалов, то определим множество выбора для правила A → bα равным b. Обозначим данную запись следующим образом:

ВЫБОР(A → bα) = b.

Если правило имеет вид: A → e, то определим:

ВЫБОР(A → e) = СЛЕД(A).

Если p – номер правила, то будем также писать «ВЫБОР(p)» вместо «ВЫБОР(правило)»

ВЫБОР(p) – множество выбора правила p.

Проиллюстрируем построение множества выбора на примере грамматики G_9.4.

ВЫБОР(1) = ВЫБОР(S → aAS) = {a}

ВЫБОР(2) = ВЫБОР(S → b) = {b}

ВЫБОР(3) = ВЫБОР(A→cAS) = {c}

ВЫБОР(4) = ВЫБОР(A → e) = СЛЕД(A) = {a, b}

В соответствии с определением, рассмотренным в начале, имеем q-грамматику, так как:

ВЫБОР(1) È ВЫБОР(2) = Æ,