Языки и трансляции. Мартыненко Б.К. - 155 стр.

UptoLike

ВУЗ: 

СПбГУ | Санкт-Петербург

Составители: 

Рубрика: 

153
Пример 1.6. Пусть T = ({E, T, F}, {a, +,
*
, (, )}, {a, +,
*
}, R, E), где
R = { (1) E → E + T, +ET
(2) E → T, T
(3) T → T
*
F,
*
TF
(4) T → F, F
(5) F → (E), E
(6) F → a, a }.
В соответствии с описанием построений в теореме 1.3 определим
детерминированный магазинный преобразователь, восстанавливающий выход
трансляции по левостороннему анализу входной цепочки:
P = ({q}, {1, 2, 3, 4, 5, 6}, ({E, T, F, a, +,
*
}, {a, +,
*
}, δ, q, E, ∅),
где
1) δ(q, 1, E) = (q, +ET, ε)
2) δ(q, 2, E) = (q, T, ε)
3) δ(q, 3, T) = (q,
*
TF, ε)
4) δ(q, 4, T) = (q, F, ε)
5) δ(q, 5, F) = (q, E, ε)
6) δ(q, 6, F) = (q, a, ε)
7) δ(q, ε, a) = (q, ε, a)
8) δ(q, ε, +) = (q, ε, +)
9) δ(q, ε,
*
) = (q, ε,
*
).
Упражнения
II.1.1. Построить SDTS, которая определяет трансляцию τ = {(x, y) | x —
выражение из a, +,
*
, ^, унарный минус ‘–’ и скобок ‘(’ и ‘)’, а y —
эквивалентное выражение без “лишних” скобок}.
Пояснение. Скобки “лишние”, если они восстановимы по приоритетам операций
или с учётом того, что операции одного приоритета выполняются слева направо.
II-1.2. Построить pdt P, который реализует трансляцию τ
e
(P) = τ (T), где T
— SDTS, построенная в упр. II.1.1 (удаление “лишних” скобок).
II-1.3. По pdt P, построенному в упр. II.1.2, восстановить SDTS T, такую
что
τ (T) = τ
e
(P).
II-1.4.
Построить SDTS, определяющую трансляцию τ = {(x, y) | где x —
инфиксная, а y — постфиксная форма арифметического выражения,
составленного из символов a, +,
*
, и скобок ( и )}.
Пояснение. Использовать входную грамматику схемы, построенной в
задаче II.1.1, в качестве входной грамматики схемы, которую требуется
построить в данной задаче.

Страницы