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

UptoLike

ВУЗ: 

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

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

Рубрика: 

190
предсказывающего алгоритма анализа в k-предсказывающий алгоритм
трансляции, реализующий трансляцию, специфицируемую простой семанти-
чески однозначной SDTS с входной грамматикой класса LL(k). Это устройство
отличается от LL(k)-анализатора лишь тем, что имеет ещё один тип движений,
состоящий в том, чтобы перенести верхний символ магазина, являющийся
дубликатом выходного символа, на выходную ленту, превратив его в
настоящий выходной символ (как в лемме 1.1 этой пособия части). Детали
прояснятся из описания алгоритма 2.8.
Алгоритм 2.8: построение k-предсказывающего алгоритма трансляции.
Вход: T =(N, Σ, ∆, R, S) — простая семантически однозначная схема
синтаксически управляемой трансляци с входной грамматикой G
i
класса LL(k).
Выход: ℑ — k-предсказывающий алгоритм трансляции, реализующий
трансляцию τ(T).
Метод.
1. Предполагая, что множество LL(k)-таблиц, необходимых для анализа в
грамматике G
i
, уже построено, положим ℑ = (Σ, Γ∪{$}, ∆, M, X
0
, $), где Σ и ∆ —
такие же, как в схеме T; Γ = T ∪Σ∪∆’; ∆’ ={b’
| b’ = h(b), b ∈∆}; Σ∩∆’ = ∅;
X
0
= T
0
= T
S,{ε}
— начальный символ магазина; $ — маркер “дна” магазина;
M: (Γ ∪ {$}) × Σ
*
k
→ (Σ ∪ ∆’)
*
∪ {pop, pass, accept, error} — управляющая таблица,
которая строится по следующим шагам:
2. M(T
A , L
,u)=x
0
y
0
’
T
A
1
,L
1
x
1
y
1
’
T
A
2
,L
2
x
2
y
2
’
T
A
3
,L
3
…T
A
m
,L
m
x
m
y
m
’
, если
T
A, L
(u)=(A → x
0
A
1
x
1
A
2
x
2
A
3
…A
m
x
m
, ·Y
1
, Y
2
, Y
3
, …, Y
m
Ò), и
A → x
0
A
1
x
1
A
2
x
2
A
3
…A
m
x
m
, y
0
A
1
y
1
A
2
y
2
A
3
...
A
m
y
m
∈R — i-е правило схемы.
Здесь y
i
’
= h(y
i
), i =0,1,2,…, m.
3. M(a, u) = pop, если a ∈Σ, u = av, v ∈Σ
*
k–1
.
4. M(b’, u)=pass для всех u ∈Σ
*
k
. Такой управляющий элемент определяет
переход между конфигурациями: (x, b
’
α$, y) (x, α$, yb).
5. M($, ε) = accept.
6. M(X, u) = error для всех (X, u) ∈(Γ∪{$}) ×Σ
*
k
, для которых элементы M
не определены по пп. 2–5.
Пример 2.13. Пусть T =({S, A}, {a, b}, {a, b, e, ·, Ò}, R, S), где
R = {(1) S → aAaa, aAaa; (2) S → bAba,
·AÒa; (3) A → b, b; (4) A →ε, e}.
Входная грамматика этой схемы — не сильная LL(2)-грамматика,
рассматривавшаяся в предыдущих примерах. В примере 2.9 для неё был
построен 2-предсказывающий алгоритм анализа. Применяя алгоритм 2.8 к
данной схеме, получаем следующий 2-предсказывающий алгоритм трансляции,
реализующий определяемую ею трансляцию:
ℑ = ({a, b},
{T
0
, T
1
, T
2
, a, b, a
’
,
b’, e, ·, Ò, $}, {a, b, e, ·, Ò}, M, T
0
, $),
где M представляется управляющей табл. 2.7.
−
−

Страницы