Построение КА-распознавателей для праволинейных грамматик

Праволинейной называется контекстно-свободная грамматика, вправых частях правил которой имеется не более одного нетерминала и этот нетерминал заканчивает правило. В праволинейных грамматиках допускаются эпсилон-правила вида 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 -

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

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

символов, находящихся в магазине".