3.2. Модели простейших трансляторов

3.2.1. Конечные преобразователи

Введем простейший транслятор - конечный преобразователь.

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

Рис.3.1

Для большей общности рассмотрим в качестве основы конечного преобразователя недетерминированный конечный автомат, способный делать е - такты.

Определение. Конечным преобразователем называется шестерка

где Q - конечное множество состояний;

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

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

d - отображение множества в множество конечных подмножеств множества Q;

- начальное состояние;

- множество заключительных состояний. ¨

Определим конфигурацию преобразователя М как тройку (q,x,y),

где - текущее состояние управляющего устройства;

^*- оставшаяся непрочитанной часть входной цепочки;

y - часть выходной цепочки, выданная вплоть до текущего момента.

Определим бинарное отношение _м (или , когда ясно о каком М идет речь) на конфигурациях, соответствующее одному такту работы преобразователя М , следующим образом:

для всех таких, что , будем писать

Обычным образом определяются отношения .

Цепочку у назовем выходом для цепочки х, если (q₀,x,e) ^*(q,e,y) для некоторого .

Переводом, определяемым преобразователем M (обозначается ), называется множество

^*(q,e,y), qÎF}.

Для представления функции переходов конечного преобразователя удобно использовать графы переходов, как это делалось для представления КА. На каждой дуге графа кроме входного указывается и выходной символ, соответствующий данному переходу.

Пример 3.2. Построим конечный преобразователь, который распознает арифметические выражения, порождаемые правилами

S ® a+S|a-S|+S|-S|a ,

и устраняет из этих выражений избыточные унарные операции.

Пусть M = ({q₀,q₁,q₂,q₃,q₄},{a,+,-},{a,+,-}, d,q₀,{q₁}),

где d определяется графом (рис. 3.2).

Рис. 3.2

Д ля входа -а+-а-+-а последовательность тактов преобразователя М такова:

(q₀,- a + - a - + - a,e) (q₄, a + - a - + - a,e)

(q₁,+ - a - + - a,- a)

(q₂,- a - + - a,- a)

(q₃, a - + - a,- a )

(q₁,- + - a,- a- a)

(q₃,+ - a,- a - a)

(q₃, - a,- a - a)

(q₂, a,- a - a)

(q₁,e,- a - a + a)

Отсюда ясно, что М отображает цепочку -а+-а-+-а в цепочку -а-а+а, поскольку q₁- заключительное состояние.

3.2.2. Преобразователи с магазинной памятью

Теперь введем другой важный класс трансляторов, называемых преобразователями с магазинной памятью. Эти преобразователи получаются из автоматов с магазинной памятью, если их снабдить выходом и разрешить на каждом такте выдавать выходную цепочку конечной длины (рис.3.3).

Рис. 3.3

Определение. Преобразователем с магазинной памятью (МП - преобразователем) называется восьмерка P=(Q,S,G,D,d,q₀,Z₀,F), где все символы имеют тот же смысл, что и при определении МП -автомата, за исключением того, что D - конечный выходной алфавит, а d - отображение множества в множество конечных подмножеств множества Q´G ^*´D^* . ¨

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

Если d(q,a,Z) содержит (r,a,z), то будем писать :

(q,ax,Zg, у ) (r,x, ag, уz)

Это бинарное отношение представляет такт работы МП-преобра-зователя.

Пример.3.3 Рассмотрим МП - преобразователь

,

где d - определяется равенствами:

Для входа +*ааа МП - преобразователь Р сделает такую последовательность тактов:

Таким образом, Р переводит цепочку +*ааа в цепочку аа*а+, опустошая магазин. Можно показать, что t(P)={(x,y) | x - префиксная польская запись арифметического выражения, y - соответствующая постфиксная польская запись}

МП - преобразователь является наглядной моделью синтаксического анализатора.