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

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

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

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

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

1. SaAS

2. Sb

3. AcAS

4. Ae

О том, что это не 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.

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

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

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

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

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

Ab?, Ae и b I СЛЕД(A).

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

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

ВЫБОР(Ab?) = b.

Если правило имеет вид: Ae, то определим:

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

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

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

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

ВЫБОР(1) = ВЫБОР(SaAS) = {a}

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

ВЫБОР(3) = ВЫБОР(AcAS) = {c}

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

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

ВЫБОР(1) E ВЫБОР(2) = ?,

ВЫБОР(3) E ВЫБОР(4) = ?.

Статьи к прочтению:

ork Maksim Sen 2016 HD Avtomat KucekOfficial Video HD

Похожие статьи: