Алгоритм построения МП-автомата по произвольной КС-грамматике

Эквивалентность МП-автоматов и КС-грамматик

Лемма: Для любой КС-грамматики можно построить соответствующий
МП-автомат и наоборот.

Построим естественный (недетерминированный) «нисходящий» распознаватель, эквивалентный данной КС-грамматике.

Вход: - произвольная КС-грамматика.

Выход: - МП-автомат, допускающий цепочки опустошением магазина, такой, что .

Метод:

1. Множество состояний МП-автомата примет вид ;

2. Входной алфавит МП-автомата совпадает с алфавитом терминальных символов исходной грамматики;

3. Алфавит магазинных символов будет следующим ;

4. Начальным состоянием будет единственное состояние, т.е. ;

5. Начальным магазинным символом будет целевой символ КС-грамматики ;

6. Множество заключительных состояний МП-автомата можно сделать либо пустым, либо оно будет содержать одно единственное состояние. Для определенности положим ;

7. Определим множество результирующего МП-автомата следующим образом:

a. Если множество правил исходной грамматики содержит правило вида , , , то во множество функций перехода автомата добавляется функция перехода вида для , , ;

b. Во множество функций перехода автомата добавляются все переходы вида для , .

Пример:

1. Построить МП-автомат, распознающий язык, заданный множеством , и порождающийся КС-грамматикой с правилами вида ;

2. Построить последовательность тактов работы МП-автомата для цепочек , .

Решение:

1. МП-автомат будет иметь вид

где функции перехода будут следующие

,

,

.

2. Теперь построим последовательность тактов работы автомата для различных цепочек

a. Последовательность тактов работы автомата для цепочки будет иметь вид

b. Последовательность тактов работы автомата для цепочки будет иметь вид

Домашнее задание: П остроить для нижеследующей грамматики МП-автомат

.

И построить последовательность тактов работы МП-автомата для цепочки

.

Домашнее задание (убрать в практику): П остроить для нижеследующей грамматики МП-автомат

,

где

.

И построить последовательность тактов работы МП-автомата для цепочки

.

Тип синтаксического анализа, проводимого для КС-грамматики МП автоматом, построенном выше, называется «нисходящим анализом» («анализом сверху вниз») или «предсказывающим анализом», потому что при этом дерево вывода строится по существу сверху (от корня) вниз, а каждый такт вида можно трактовать как предсказание очередного шага левого вывода.

Можно построить расширенный МП-автомат, который работает «сверху-вниз» как «восходящий анализатор», моделируя в обратном порядке правые выводы в КС-грамматике.

По произвольной КС-грамматике можно построить эквивалентный расширенный МП-автомат . Здесь удобно представить себе магазин в виде цепочки, верхним символом которой является самый правый, а не самый левый символ. В силу этого соглашения конфигурации расширенного МП-автомата определяются точно так же, как и раньше, а отношение несколько иначе. Если , то будем писать для , .

Видно, что обозначение МП-автомата в виде семерки можно интерпретировать как два различных МП-автомата в зависимости от того, какой из символов – правый или левый – считается верхним. Можно заметить, что удобство обозначений, создаваемое этими двумя соглашениями, перевешивает возможность путаницы в исходных понятиях. В дальнейшем, если не оговорено противное, будем считать, что у обычного МП-автомата верх магазина расположен слева, а у расширенного – справа.

Лемма: Для любой КС-грамматики можно построить соответствующий
расширенный МП-автомат и наоборот.

Дата добавления: 2014-01-07