Построение МП-распознавателей для q-грамматик

КС-грамматика (грамматика второго типа) называется q-граммаикой, если правые части всех правил этой грамматики начинаются стерминальных символов и для правил с одинаковыми левыми частями множества "ВЫБОР" попарно не пересекаются.

Правила имеют вид Х -> y&, где y - терминал; & - любая це-почка терминалов и нетерминалов, возможно пустая (q-грамматика может содержать эпсилон-правил т.е. правила вида Х -> @).

Замечание: q-грамматика отличается от S-грамматики только наличием в множестве Р эпсилон-правил; этот факт существенно осложняет построение МП-распознавателя.

Дадим определение ряду унарных отношений, которые можно построить на множестве {VT, -+}.

Отношение "СЛЕД Y" (следующий за Y) - подмножество множества

входных символов МП-распознавателя, которые могут следовать за нетерминалом Y в любых сентенциальных формах, получаемых из множества Р правил грамматики.

Отношение "ВЫБОР Y" - подмножество множества входных символов МП-распознавателя, c которых могут начинаться цепочки, выводимые из нетерминала Y в любых сентенциальных формах, получаемых из множества Р правил грамматики.

Отношение "ВЫБОР Y" для конкретной грамматики строится как объединение таких отношений, построенных для всех правил, содержащих в левых частях Y.

Для правил вида Y -> x& (1) и Y -> z (2) множество "ВЫБОР Y" всегда равно первому терминалу правой части правила:

для правила 1 "ВЫБОР Y1" ={x}

для правила 2 "ВЫБОР Y2" ={z}

Если в множестве Р правил грамматики нет больше правил для нетерминала Y, то отношение "ВЫБОР Y" = "ВЫБОР Y1" U "ВЫБОР Y2"

"ВЫБОР Y" = {x,z}.

Для правил вида Y -> @ (3) отношение "ВЫБОР Y3" = "СЛЕД Y" и определять его нужно, анализируя все правила грамматики.

Для q-грамматики попарное пересечение множеств "ВЫБОР" для правил с одинаковыми левыми частями должно быть пусто. Это условие гарантирует однозначность работы МП-распознавателя (правило грамматики применяется всякий раз, когда магазинный символ является его левой частью, а входной символ принадлежит множеству

"ВЫБОР" этого правила).

Рассмотрим на примере процедуру проверки КС-грамматики на предмет ее принадлежности к классу q-грамматик.

Пусть задана грамматика G[S]=(VT={a,b,c}; VN={S,A}; S; P);

P={S -> aA(1); S -> b(2); A -> cSa(3); A -> @ (4)}.

Доказать, что заданная грамматика относится к классу q-грамматик.

Решение

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

1. Для нетерминала S:

"ВЫБОР S1" = {a}; "ВЫБОР S2" = {b}.

"ВЫБОР S1" П "ВЫБОР S2" = { } (пересечение пусто).

2. Для нетерминала A:

"ВЫБОР A3" = {c}; "ВЫБОР A4" = "СЛЕД A"

После нетерминала A могут следовать -+ (правило 1) и a в выводе

1 3 1 (номера правил)

S -> aA -> acSa -> acaAa ->... символ a,

отсюда "СЛЕД A" = { -+, a}.

"ВЫБОР A3" П "ВЫБОР A4" = {c} П {-+,a}={ }(пересечение пусто).

Вывод: заданная грамматика G[S] является q-грамматикой.

Построим для этой грамматики МП-распознаватель.

Для q-грамматики существует формальная процедура построения МП-распознавателя с одним состоянием по следующему алгоритму:

1.Входной алфавит МП-распознавателя V = {VT,-+}.

2.Множество магазинных символов { VN, VT1, \/}, где VT1 часть терминальных символов грамматики, которые встречаются в цепочках & множества правил.

3.Начальная конфигурация - в магазине находится начальный символ грамматики (например для грамматики G[S] - S \/).

Замечание: условимся запись содержимого магазина вести так, чтобы верхний символ (тот, с которым работает МП-автомат) занимал самую левую позицию.

4.Управляющая таблица строится так: столбцы таблицы - символы входного алфавита (последний символ -+);строки таблицы - магазинные символы. Заполнение управляющей таблицы:

а) для правил грамматики вида Х -> y& (& не пустая цепочка)

.... ¦ y ¦

............

-----+--------+----------

¦\Зам.& /¦

X ¦ \ / ¦....

¦ \ / П¦

-----+---\/---+----------

............

.... ¦..... ¦....

б) для правил грамматики вида Х -> y (& пустая цепочка)

.... ¦ y ¦

..............

-----+--------+----------

¦\Выт.Х /¦

X ¦ \ / ¦....

¦ \ / П¦

-----+---\/---+----------

............

.... ¦..... ¦....

В соответствии с п.п. а) и б) обрабатывается все множество Р правил грамматики (кроме эпсилон правил).

в) клетки таблицы на пересечении терминал-магазинный символ и тот же терминал-входной алфавит:

.... ¦ y ¦

.............

------+--------+----------

¦\Выт.y /¦

y ¦ \ / ¦....

¦ \ / П¦

------+---\/---+----------

.............

.... ¦..... ¦....

г) каждая клетка таблицы на пересечении нетерминала Z и входных символов МП-распознавателя из множества "СЛЕД Z" ={y,...-+}:

.... ¦ y ¦.... ¦ --+ ¦

¦ ¦.... ¦ ¦

..........................

------+--------+---... ----+--------+

¦\Выт.Z /¦ ¦\Выт.Z /¦

Z ¦ \ / ¦ ¦ \ / ¦

¦ \ / Д¦ ¦ \ / Д¦

------+---\/---+----... ----+---\/---+

..........................

.... ¦..... ¦........ ¦..... ¦

г) все оставшиеся клетки последнего столбца таблицы (-+) заполняются "отв."кроме клетки на пересечении со строкой \/, в которой ставится "доп.";

д) оставшиеся незаполненными клетки управляющей таблицы заполняются буквой Е-"состояние ошибки".

Построим МП-распознаватель для языка, порождаемого G[S]

грамматикой из предыдущего примера.

Пусть задана q-грамматика G[S]=(VT={a,b,c}; VN={S,A}; S; P);

P={S -> aA(1); S -> b(2); A -> cSa(3); A -> @ (4)}.

Решение

1.Проверка нетерминалов на достижимость и продуктивность

S достижим (начальный символ); A достижим (правило 1);

S продуктивен (правило 2); A продуктивен (правило 1).

2.Построение МП-распознаватель(ранее доказано, что это q-грамматика):

- входной алфавит V={a,b,c,-+};

- множество магазинных символов {S,A,a,\/};

- начальное содержимое магазина S,\/;

- управляющая таблица имеет вид:

г======T========T========T========T========

¦ ¦ a ¦ b ¦ c ¦ -+ ¦

¦------+--------+--------+--------+--------¦

¦ \/ ¦ E ¦ E ¦ E ¦ доп. ¦

¦ ¦ ¦ ¦ ¦ ¦

¦------+--------+--------+--------+--------¦

¦ ¦\ Зам. /¦\ Выт. /¦ ¦ ¦

¦ S ¦ \ А / ¦ \ S / ¦ Е ¦ отв. ¦

¦ ¦ \ / П¦ \ / П¦ ¦ ¦

¦------+---\/---+---\/---+--------+--------¦

¦ ¦\ Выт. /¦ ¦\ Зам. /¦\ Выт. /¦

¦ A ¦ \ А / ¦ Е ¦ \ Sa / ¦ \ А / ¦

¦ ¦ \ / Д¦ ¦ \ / П¦ \ / Д¦

¦------+---\/---+--------+---\/---+---\/---¦

¦ ¦\ Выт. /¦ ¦ ¦ ¦

¦ a ¦ \ а / ¦ Е ¦ Е ¦ отв. ¦

¦ ¦ \ / П¦ ¦ ¦ ¦

L======¦===\/===¦========¦========¦========-

Примечание: поле для состояний осталось незаполненным, т.к. заполнять его нет смысла (состояние только одно).

3.Проверка работы МП-распознавателя.

Получим цепочку на основании правил грамматики:

1 3 1 3 1 4

S -> aA -> acSa -> acaAa -> acacSaa -> acacaAaa -> acacaaa

Работу МП-распознавателя по разбору цепочки acacaaa представим в виде таблицы:

-----------T-----------T---------T----------T---------T---------

¦Необработ.¦ Обраб. вх.¦Верх.симв¦Содержимое¦Действие ¦Действие ¦¦цепочка ¦ символ ¦магазина ¦магазина ¦с магаз. ¦с вх.симв¦

+--------T-+-----------+---------+----------+---------+---------+

¦acacaaa-+ ¦ a ¦ S ¦ S \/ ¦ Зам. A ¦ П ¦

¦ cacaaa-+ ¦ c ¦ A ¦ A\/ ¦ Зам. Sa¦ П ¦

¦ acaaa-+ ¦ a ¦ S ¦ Sa\/ ¦ Зам. A ¦ П ¦

¦ caaa-+ ¦ c ¦ A ¦ Aa\/ ¦ Зам. Sa¦ П ¦

¦ aaa-+ ¦ a ¦ S ¦ Saa\/ ¦ Зам. A ¦ П ¦

¦ aa-+ ¦ a ¦ A ¦ Aaa\/ ¦ Выт. А ¦ Д ¦

¦ аa-+ ¦ a ¦ а ¦ aa\/ ¦ Выт. а ¦ П ¦

¦ а-+ ¦ а ¦ а ¦ а\/ ¦ Выт. а ¦ П ¦

¦ -+ ¦ -+ ¦ \/ ¦ \/ ¦допустить¦ - ¦

L----------+-----------+---------+----------+---------+----------

Контрольная цепочка распознается построенным МП-распознавателем.