КС-грамматика (грамматика второго типа) называется 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----------+-----------+---------+----------+---------+----------
Контрольная цепочка распознается построенным МП-распознавателем.