Студопедия

КАТЕГОРИИ:

АстрономияБиологияГеографияДругие языкиДругоеИнформатикаИсторияКультураЛитератураЛогикаМатематикаМедицинаМеханикаОбразованиеОхрана трудаПедагогикаПолитикаПравоПсихологияРиторикаСоциологияСпортСтроительствоТехнологияФизикаФилософияФинансыХимияЧерчениеЭкологияЭкономикаЭлектроника


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




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

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

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

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

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

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

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

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

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

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

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

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

 

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

 

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

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

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

 

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

 

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

 

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

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

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

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

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


Поделиться:

Дата добавления: 2015-08-05; просмотров: 63; Мы поможем в написании вашей работы!; Нарушение авторских прав





lektsii.com - Лекции.Ком - 2014-2024 год. (0.007 сек.) Все материалы представленные на сайте исключительно с целью ознакомления читателями и не преследуют коммерческих целей или нарушение авторских прав
Главная страница Случайная страница Контакты