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

 

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

 

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

 

A,

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

 

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

 

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

 

Ab,

 

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

 

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

 

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

 

Ae

 

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

 

Вытолкнуть.

 

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┤ Отвергнуть На шаг раньше