Теория алгоритмов, формальных языков, грамматик и автоматов. Бильгаева Н.Ц. - 44 стр.

UptoLike

Составители: 

3) команды сравнения и поглощения символа с входной ленты и символа в верхушке
магазина:
p
1
, a, a p
1
, ε
p
1
, +, + p
1
, ε
p
1
, /, / p
1
, ε
p
1
, (, ( p
1
, ε
p
1
, ), ) p
1
, ε;
4) команда завершения разбора:
p
1
, ε, B
0
f, B
0.
Процесс разбора цепочки представлен в таблице 2.
5.5. Выводы
Рассмотренные выше МП-автоматы работают недетерминированно, то есть если цепочка
принадлежит языку, порождаемому заданной грамматикой, то какой-то из вариантов
функционирования автомата осуществит правильный разбор. Если же цепочка не
принадлежит языку, то никакой из вариантов разбора не приведет к цели.
Отсутствие детерминированного эквивалентного автомата для произвольной КС-
грамматики означает невозможность построения универсальной простой однопроходной
программы синтаксического анализа. Поэтому для эффективного разбора необходимо
выделять специальные классы КС-грамматик, удовлетворяющие требованиям конкретных
типов анализаторов.
Если требуется выполнить разбор для произвольной КС-грамматики, то придется
использовать детерминированную программную модель недетерминированного МП-
автомата.
5.6. Понятие преобразователей
Автоматы с выходом называются преобразователями. В зависимости от вида функции,
отображающей множество состояний и входных символов в множество выходных символов
и новых состояний, а также от типа рабочей ленты различают разные виды
преобразователей. Рассмотрим конечные автоматы-преобразователи.
Конечным преобразователем называется шестерка вида
P = (К, X, Y, f, g, q
0
), где
K - конечное множество состояний;
X - входной алфавит;
Y - выходной алфавит;
f - функция переходов;
g - функция выходов;
q
0
- начальное состояние.
Типы отображений f и g определяют различные виды автоматов. Если g - отображение
K X в Y, то конечный преобразователь называется синхронным. В общем случае это
отображение имеет вид K X Y
*
.
Пусть P = (К, X, Y, f, g, q
0
) - конечный преобразователь. Тогда отображение S(x) = g(q
0
,
x), определенное для любой цепочки x X
*
, называется конечным преобразователем.
Заметим, что для того чтобы выходную цепочку y можно было считать переводом
входной цепочки x, цепочка x должна перевести преобразователь из начального состояния в
заключительное.