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

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

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

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 {+, -, а}.

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

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

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

(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.

Р ассмотрим автомат: (í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)

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

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

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

МП – преобразователь содержит 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*) |¾

(

2

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+*) |¾

(

7

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 – сравнение выходной цепочки со входной.