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

UptoLike

ВУЗ: 

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

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

Рубрика: 

167
1)
M(A, a)=(α, i), если A → α является i-м правилом во множестве правил P,
и
1
FIRST ( ), .
G
aa∈α≠ε
1 1
Если FIRST ( ), то (,) (,) для всех FOLLOW ( );
G G
M
Ab i b Aε∈ α = α ∈
2) M(a, a) = pop для всех a ∈Σ;
3) M($, ε) = accept;
4) M(X, a) = error для всех (X, a) ∈(Γ∪{$}) × (Σ∪{ε}), для которых значе-
ния элементов, остались не определенными по пп. 1–3.
Пример 2.6. Посредством алгоритма 2.1 построим LL(1)-анализатор для
LL(1)-грамматики G =
({E, E
’
, T, T
’
, F}, {a, +,
*
, (, )}, P, E), где
P = {(1) E → TE
’
, (2) E
’
→ +TE
’
, (3) E
’
→ ε, (4) T → FT
’
,
(5) T
’
→
*
FT
’
, (6) T
’
→ ε, (7) F → (E), (8) F → a}.
Положим
A = ({a, +,
*
, (, )}, {E, T, F, a, +,
*
, (, ), $}, {1, 2, 3, 4, 5, 6, 7, 8}, M, E, $),
где M дана в виде табл. 2.2. В ней пустые клетки соответствуют значениям error.
Таблица 2.2
Аванцепочки
Маг.
сим-ы
a +
*
( )
ε
E
TE
’
, 1
TE
’
, 1
E
’
+TE
’
, 2
ε, 3 ε, 3
T
FT
’
, 4
FT
’
, 4
T
’
ε, 6
*
FT
’
, 5
ε, 6 ε, 6
F a, 8 (E), 7
a pop
+ pop
*
pop
( pop
) pop
$ accept
1-Предсказывающий алгоритм анализа, использующий эту управляющую
таблицу, проанализировал бы входную цепочку (a + a), совершив следующую
последовательность движений:
((a + a), E$, ε) ((a + a), TE
’
$, 1) ((a + a), FT
’
E
’
$, 14)
((a + a), (E)T
’
E
’
$,147) (a + a), E)T
’
E
’
$, 147) (a + a), TE
’
)T
’
E
’
$,1471)
(a + a), FT
’
E
’
)T
’
E
’
$, 14714) (a + a), aT
’
E
’
)T
’
E
’
$, 147148)
(+ a),T
’
E
’
)T
’
E
’
$, 147148) (+ a), E
’
)T
’
E
’
$, 1471486)
(+ a),+TE
’
)T
’
E
’
$, 14714862) (a), TE
’
)T
’
E
’
$, 14714862)
(a), FT
’
E
’
)T
’
E
’
$, 147148624) (a), aT
’
E)T
’
E
’
$, 1471486248)
( ), T
’
E
’
)T
’
E
’
$, 1471486248) ( ), E
’
)T
’
E
’
$, 14714862486)
( ), )T
’
E
’
$, 147148624863) (ε, T
’
E
’
$, 147148624863)
(ε, E
’
$, 1471486248636) (ε, $, 14714862486363).
−−
−
−
−
−
−−
−−
−−
−−
−−
−−
−−
−−
−−
−
−
−
−
−
−
−
−
−
−
−
−
−
−
−
−
−
−
−−
−
−
−−
−−
−−
−
−

Страницы