МП-преобразователи

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

Определение. МП - преобразователем называют восьмерку вида

Q - конечное множество состояний преобразователя;

- конечный входной алфавит;

Г - конечный магазинный алфавит;

- конечный выходной алфавит;

- отображение множества (Q * ( * Г) в множество всех подмножеств множества (Q * Г** *), т.е.

q_о - начальное состояние преобразователя, q₀ Q;

Z_o - начальное содержимое магазина, Z_o Г;

F - множество заключительных состояний преобразователя, F Q.

Определение. Конфигурация МП - преобразователя — это четверка (q,w, , у) (Q х * х Г* х *). Начальная конфигурация — (q₀,w, Z_o, ), заключительная конфигурация — (q, , , у), где q F. Если од­ним из значений функции (q, a, Z) является (q^’, , r), то шаг ра­боты преобразователя можно представить в виде отношения на конфигурациях

(q, aw, Za, у) |- (q^’,wо, а, уr) для любых w *, Г*, у *.

Строка у будет выходом МП - преобразователя для строки w, если существует путь от начальной до заключительной конфигу­рации

(q_о, w, Z_o, ) |-* (q, , , у) для некоторых q F и Г*.

Определение. Переводом (преобразованием) , определяемым МП - преобра­зователем Р, называется множество

(Р) = {(w,у) | (q₀,w, Z_o, )|-* (q, , ,у) для q F, Г*.

Определение. МП - преобразователь будет детерминированным, если, как и МП - автомат, он имеет не более одной возможной очередной кон­фигурации. Расширенный МП - преобразователь отличается от рассмотренного только магазинной функцией

: (Q х () х Г*) -> P(Q х Г* х *).

Теперь обратимся к двум результатам теоретических исследо­ваний, имеющим чрезвычайно важное практическое значение. Они состоят в следующем.

1. Если T={V_T, V_N, ,R,S) - простая СУ-схема с входной грамматикой LL(k), то СУ-перевод (Т) можно осуществить детерминированным МП - преобразователем.

2. Если T={V_T, V_N, ,R,S) - простая постфиксная СУ-схема с входной грамматикой LR(k), то перевод (T) можно выполнить детерминированным МП - преобразователем.

Существуют алгоритмы, позволяющие построить детерми­нированный МП - преобразователь по заданной СУ-схеме пере­вода. В их основе лежат алгоритмы построения таблиц разбора.

Простые СУ-переводы образуют важный класс переводов, поскольку для каждого из них можно построить детерминиро­ванный МП - преобразователь, отображающий входную строку (цепочку) в выходную строку (цепочку). Такие переводы иногда называют цепочечными.