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

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

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

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

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