Построение нисходящего автомата

 

Рассмотренные понятия и методы их использования приводят к небольшой корректировке правил порождения АМП по S-грамматике, чтобы получить процедуру создания автомата по q-грамматике. Эта корректировка касается только пункта 5. Можно, конечно, полностью переписать исправленный алгоритм создания автомата, но лучше воспользуемся авторским текстом [16]. Пятое правило заменяется двумя следующими:

 

5.1. Правило грамматики применяется всякий раз, когда магазинный символ является его левой частью, а входной символ принадлежит его множеству выбора. Для того чтобы применить правило вида:

 

A → bα,

используется переход:

 

Заменить (α^r), Сдвиг

 

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

 

A → b,

 

то используется:

 

Вытолкнуть, Сдвиг.

 

Для того чтобы применить правило:

 

A → e

 

используется переход

 

Вытолкнуть.

 

5.2. Если имеется правило с нетерминалом A в левой части и элемент, соответствующий магазинному A и входному символу b не был создан по правилу 5.1, то таким элементом может быть или применение пустого правила (A → α) или операция «Отвергнуть».

 

Примеры построения АМП по q-грамматике

 

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

 

Магазинные символы	Входные символы
a	b	c	┤
S	↕ SA,→	↑,→	Отвергнуть	Отвергнуть
A	↑	↑	↕ SA,→	Отвергнуть
Ñ	Отвергнуть	Отвергнуть	Отвергнуть	Допустить

 

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

1. S → aA

2. S → b

3. A → cSa

4. A → e

Множества выбора для каждого из правил будут выглядеть следующим образом:

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

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

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

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

Полученные данные использованы для построения таблицы переходов. Ячейка, содержащая альтернативные правила, находится на пересечении строки с магазинным символом A и столбце с входным символом b.

 

Магазинные символы	Входные символы
a	b	c	┤
S	↕ A,→	↑,→	Отвергнуть	Отвергнуть
A	↑	1)↑или 2)Отвергнуть	↕ aS,→	↑
a	↑,→	Отвергнуть	Отвергнуть	Отвергнуть
Ñ	Отвергнуть	Отвергнуть	Отвергнуть	Допустить

 

Для того чтобы проверить, как действуют эти правила, необходимо ввести неправильную цепочку. Возьмем, например, цепочку ab. В первом случае используем выталкивание, которое ведет к отвержению цепочки на третьем шаге.

Номер шага	Содержимое стека	Остаток входной цепочки	Применяемый переход	Комментарий
	ÑS	ab┤	↕ A,→
	ÑA	b┤	↑	Использовано выталкивание
	Ñ	b┤	Отвергнуть	Все равно отвергли

Во втором варианте цепочка отвергается уже на втором шаге.

 

Номер шага	Содержимое стека	Остаток входной цепочки	Применяемый переход	Комментарий
	ÑS	ab┤	↕ A,→
	ÑA	b┤	Отвергнуть	На шаг раньше