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

Конечные преобразователи. (Простейший транслятор)

Алгоритм работы синтаксически управляемого перевода

Вход: СУ – схема с входной грамматикой Gi {N, S, Pi, S}и дерево вывода D.

Выход: Дерево D’ в грамматике G0 {N, D, P0, S}.

Шаг 1: Применять шаг 2 начиная с корня D.

Шаг 2: Пусть этот шаг (2) применяется к вершине n, внутренней в дереве D, и пусть n1, nk – прямые потомки. Пусть А:=a - правило из Pi, соответствующее вершине n.

Цепочка a образуется конкатенацией меток n1…nk.

Выбрать из R правило А:=a, b и переставить вершины согласно соответствию, установленному этими правилами.

Применять шаг 2 к вершинам, не являющимся листьями.

Рассмотрим следующий пример, поясняющий алгоритм синтаксически управляемого перевода:

T= {(S,A), (0,1), (a,b), R, S};

СУ – схема, у которой в правилах соответствия нетерминалов, однозначное называется простой.

S

S A a

A S a

S A a

b

b

b

b

S

0 A S1

0 S A1

0 A S1

D: D’:

000111 bbbbaaa

S=> 0AS, SAa =>00SAS, SASaa =>000ASAS, SASAaaa => 0001111, bbbbaaa.

Необходима индексация.

Простые СУ – переводы образуют важный класс трансляторов, так как легко реализуются преобразованиями с магазинной памятью.

В его основе лежит конечный автомат.

Конечный преобразователь:

M= {Q, S, D, d₀, q₀, F},

где Q – множество состояний;

СУ

Только читать

Только писать

S - входной алфавит;

D - выходной алфавит;

d₀ – функция отображения;

q₀ – начальное состояние;

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

Q * Sие -> Q*D^*.

Конфигурация определяется: (q, x, y).

Если d(q₀, a)= d(q₁, b), то (q₀, ax, y)|- (q₁, x, yb).

Цепочка y называется выходом цепочки x, если имеет место следующее:

+

(q₀, x, y)|--- (q₁, x, y), где x Î S^*, y Î A^*, q₁ Î F

+

|--- вывод за какое-то количество шагов.

Перевод, определяемый конечными преобразованиями, называется регулярным («правильным»): S:= a + S |a-S| -a | +a | a.

Любое арифметическое выражение может содержать любое количество операторов - + - - + + - - а - + - - а, то есть ошибки при трансляции не будет. Транслятор сделает так, чтобы выдавался один оператор. Это происходит следующим образом.

Количество состояний:

S {+, -, а}.

D {+, -, а}.

Функцию отношения зададим диаграммой:

q1

q4

q2

q3

q0

+ / e

+ / e

a / a

+ / e

a / +a

- / e

- / e

a / - a

- / e

- / e

- / e

+ / e

a / - a

- / e

+ / e

+ / e

Для первого идентификатора, Для оставшихся идентификаторов

так как не ставим знак «+»;

(a + a - a) = итог.

(q₀,- + - - + - a + - - a + + - - - +a,e)|→ (q₁, + - - + - a + - - a + + - - - +a,e)| |→

(q₁, - - + - a + - - a + + - - - +a,e) |→ (q₀, - + - a + - - a + + - - - +a,e) |→

(q₁, + - a + - - a + + - - - +a,e) |→ (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+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₄,a, a+a) |→ (q₂,e, a+a-a)

Конечный преобразователь назовем детерминированным, если:

"q Î Q, |d(q,a)| £ 1, где |d(q,a)|- мощность;

d (q,e)=0.

q1

a / b

e / b

q0

a

Рассмотрим автомат: (íq₀, q₁ý, íaý, íbý, d, q₀, q₁, e);

d(q₀, a) = (q₀, b);

d(q₀, e) = (q₀, b);

(q₀, a, e) |→ (q₁, e, b) |→ (q₁, e, b)

Нужно в заключительном состоянии запретить е – такты.

Они могут быть получены путем добавления автомату с магазинной памятью выходной цепочки.

МП – преобразователь содержит 8 символов:

{Q, S, Г, D, d, q₀, Z, F}, где все элементы означают то же, что и раньше, кроме функции отображения:

d: Q*S*Г -> Q₁*Г^**D^*, где S - входной символ, Г – магазинный символ.

Конфигурация содержит 4 символа:

(q, aw, z, y),

где q – состояние;

aw – входная цепочка;

z – магазин;

y - входная цепочка.

d (q, a, gz) = (q₁, az, b) – функция отображения;

(q, aw, gz, y)|¾ (q₁, w, az, yb) Записывают только верх магазина (gz, az), дно не пишут.

+

Цепочку y называют выходом цепочки x, если:

+

(q, х, z, y)|¾ (q₁, w, a, y).

Преобразователь переводит цепочку х в цепочку у опустошением магазина только тогда, когда имеет место следующее: (q, x, a, e)|¾ (q₁, e, e, y).

Расширенный МП – преобразователь определяется аналогично расширенному МП – автомату.

Пример: Переведем польскую запись в некоторую цепочку. Используем все ту

же грамматику.

Запишем автомат:

{(q₀,q₁), (*,+,(,),i), (N T $), (*,+,(,),i), (d, q₀, $, q₁)}

(*,+,(,),i) – терминальные символы. (N – нетерминальные, T – терминальные).

Q*E*Г -> Q*Г^**D^*.

1. (q₀, e, E) = (q₀, e+T, ET+);

2. (q₀, e, E) = (q₀, T, T);

3. (q₀, e, T) = (q₀, T*F, TF*);

4. (q₀, e, T) = (q₀, F, F);

5. (q₀, e, F) = (q₀, (E), E);

6. (q₀, e, F) = (q₀, i, i);

7. (q₀, a, a) = (q₀, e, e);

8. (q₀, e, e) = (q₀, e, y).

i*(i+i) в этом случае мы должны получить iii+*.

(q₀, i*(i+i), E, e) |¾ (q₀, i*(i+i), T, T) |¾

(q₀, i*(i+i), T*F, TF*) |¾ (q₀, i*(i+i), T*(E), TE*) |¾

(q₀, i*(i+i), T*(E+T), TET+*) |¾ (q₀, i*(i+i), T*(E+F), TEF+*) |¾

(q₀, i*(i+i), T*(E+i), TEi+*) |¾ (q₀, i*(i+i), T*(T+i), TTi+*) |¾

(q₀, i*(i+i), T*(i+i), Tii+*) |¾ (q₀, i*(i+i), F*(i+i), Fii+*) |¾

(q₀, i*(i+i), i*(i+i), iii+*) |¾ (q₀, e, e$, iii+*) |¾ (q₀, e, e, iii+*)

7 – сравнение выходной цепочки со входной.