Праволинейной называется контекстно-свободная грамматика, вправых частях правил которой имеется не более одного нетерминала и этот нетерминал заканчивает правило. В праволинейных грамматиках допускаются эпсилон-правила вида X -> @ (т.е. нетерминал преобразуется в пустую цепочку).
Праволинейную грамматику всегда можно преобразовать в автоматную, для которой построение КА-распознавателя рассмотрено в предыдущем разделе. Алгоритм преобразования правил следующий: а) преобразовать правила вида A -> xyzB, где xyz - цепочка терминалов произвольной длины (в данном случае ¦ xyz ¦ = 3 ); вводят дополнительные нетерминалы по следующему принципу:
A -> x<yzB>; <yzB> -> y<zB>; <zB> -> zB (в угловых скобках записаны цепочки, для обозначения которых вводят новые нетерминалы);
Таким образом происходит замена исходного правила несколькими, которые сответствуют правилам автоматной грамматики. В нашем случае:
¦ A -> xM
A -> xyzB ==========> ¦ M -> yN
¦ N => zB
б) преобразовть правила вида A -> xyz, где xyz - цепочка терминалов произвольной длины (в данном случае ¦ xyz ¦ = 3 ); вводят дополнительный нетерминал F, который в КА будет служить финишным состоянием (см. разд. 3.1), а в преобразованной грамматике добавить правило F -> @
¦ A -> xyzF ===> ¦ см. пункт а)
A -> xyz ====> ¦
¦ F -> @
В результате таких преобразований получим автоматную грамматику, эквивалентную исходной праволинейной, для которой КА-распознаватель строится, как описано в разделе 3.1.
Примечания
1.При построении таблицы переходов в последнем столбце ставить
"доп." для всех состояний КА, для которых в полученной грамматике
есть эпсилон-правила.
2.Полученный КА обязательно проверить на достижимость и эквивалентность состояний; при необходимости выполнить процедуру преобразования в минимальный КА (переименование состояний КА не изменит множества распознаваемых цепочек).
8.3 Построение МП-распознавателей для S-грамматик
КС-грамматика (грамматика второго типа) называется S-грамматикой, если правые части всех правил этой грамматики начинаются стерминальных символов и для правил с одинаковыми левыми частями правые части начинаются с различных терминалов.
Правила имеют вид Х -> y&, где y - терминал; & - любая цепочка терминалов и нетерминалов, возможно пустая (S-грамматика несодержит эпсилон-правил).
Для S-грамматики существует формальная процедура построения МП-распознавателя с одним состоянием S по следующему алгоритму:
1.Входной алфавит МП-распознавателя V = {VT,-+}.
2.Множество магазинных символов { VN, VT1, /}, где VT1 -часть терминальных символов грамматики, которые встречаются в цепочках & множества правил.
3.Начальная конфигурация - в магазине находится начальный символ грамматики (например для грамматики G[Z] - Z /).
Замечание: условимся запись содержимого магазина вести так, чтобы верхний символ (тот, с которым работает МП-автомат) занимал самую левую позицию.
4.Управляющая таблица строится так: столбцы таблицы - символы входного алфавита (последний символ -+);строки таблицы - магазинные символы.
Заполнение управляющей таблицы:
а) для правил грамматики вида Х -> y& (& не пустая цепочка)
.... ¦ y ¦
¦ ¦ ....
............
-----+--------+----------
¦Зам.& /¦
X ¦ / ¦ ....
¦S / П¦
-----+---/---+----------
............
.... ¦ ..... ¦ ....
б) для правил грамматики вида Х -> y (& пустая цепочка)
.... ¦ y ¦
¦ ¦ ....
..............
-----+--------+----------
¦Выт.Х /¦
X ¦ / ¦ ....
¦S / П¦
-----+---/---+----------
............
.... ¦ ..... ¦ ....
В соответствии с п.п. а) и б) обрабатывается все множество Р правил грамматики.
в) клетки таблицы на пересечении терминал-магазинный символ и тот же терминал-входной алфавит:
.... ¦ y ¦
¦ ¦ ....
.............
------+--------+----------
¦Выт.y /¦
y ¦ / ¦ ....
¦S / П¦
------+---/---+----------
.............
.... ¦ ..... ¦ ....
г) все клетки последнего столбца таблицы (-+) заполняются "отв." кроме клетки на пересечении со строкой /, в которой ставится"доп."
д) оставшиеся клетки заполняются буквой Е-"состояние ошибки".
Пример Задана грамматика G[S] =(VT={a,b};VN={S,R}; S; P);
P={S->abR (1); S->bRbS (2); R->a (3); R->bR (4)}.
Построить МП-распознаватель для языка, порождаемого этой грамматикой.
Решение
1.Проверка нетерминалов на достижимость и продуктивность
S достижим (начальный символ); R достижим (правило 1);
R продуктивен (правило 3); S продуктивен (правило 1).
2.Построение МП-распознаватель(по виду правил делаем заключение, что это S-грамматика):
- входной алфавит V={a,b,--+};
- множество магазинных символов {S,R,b,/};
- начальное содержимое магазина S,/;
- управляющая таблица имеет вид:
г======T========T========T=======¬
¦ ¦ a ¦ b ¦ -+ ¦
¦ ¦ ¦ ¦ ¦
¦------+--------+--------+-------¦
¦ / ¦ E ¦ E ¦ доп. ¦
¦ ¦ ¦ ¦ ¦
¦------+--------+--------+-------¦
¦ ¦ Зам. /¦ Зам. /¦ ¦
¦ S ¦ bR / ¦ RbS / ¦ отв. ¦
¦ ¦ / П¦ / П¦ ¦
¦------+---/---+---/---+-------¦
¦ ¦ Выт. /¦ Зам. /¦ ¦
¦ R ¦ R / ¦ R / ¦ отв. ¦
¦ ¦ / П¦ / П¦ ¦
¦------+---/---+---/---+-------¦
¦ ¦ ¦ Выт. /¦ ¦
¦ b ¦ E ¦ b / ¦ отв. ¦
¦ ¦ ¦ / П¦ ¦
L======¦========¦===/===¦=======-
Примечание: поле для состояний осталось незаполненным, т.к.заполнять его нет смысла (состояние только одно).
3.Проверка работы МП-распознавателя.
Получим контрольную цепочку на основании правил грамматики:
2 1 4 3 3
S -> bRbS -> bRbabR -> bRbabbR -> bRbabba -> bababba
Работу МП-распознавателя по разбору цепочки bababba предста-
вим в виде таблицы:
-------------T-----------T-----------T------------T------------¬
¦ Необработ.¦ Обраб. вх.¦Верхн.симв.¦Содержимое ¦ Действие ¦
¦ цепочка ¦ символ ¦магазина ¦магазина ¦ с магаз. ¦
+---------T--+-----------+-----------+------------+------------+
¦ bababba-+ ¦ b ¦ S ¦ S / ¦ Зам. RbS ¦
¦ ababba-+ ¦ a ¦ R ¦ RbS/ ¦ Выт. R ¦
¦ babba-+ ¦ b ¦ b ¦ bS/ ¦ Выт. b ¦
¦ abba-+ ¦ a ¦ S ¦ S/ ¦ Зам. bR ¦
¦ bba-+ ¦ b ¦ b ¦ bR/ ¦ Выт. b ¦
¦ ba-+ ¦ b ¦ R ¦ R/ ¦ Зам. R ¦
¦ a-+ ¦ a ¦ R ¦ R/ ¦ Выт. R ¦
¦ -+ ¦ -+ ¦ / ¦ / ¦ допустить ¦
L------------+-----------+-----------+------------+-------------
- 28 -
Контрольная цепочка распознается построенным МП-распознавателем.
Работу МП-распознавателя можно трактовать так: на каждом шаге процесса обработки цепочки магазин представляет следующее утверждение о цепочке необработанных символов (включая и текущий) "вся цепочка будет допущена тогда и только тогда, когда оставшаяся необработанной цепочка входных символов выводима из цепочки
символов, находящихся в магазине".