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

UptoLike

ВУЗ: 

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

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

Рубрика: 

175
1. Построим Ã — множество необходимых LL(k)-таблиц для грамматики G.
2. Положим A = (Σ, Γ∪{$}, ∆, M, T
0
, $), где Σ = V
T
, ∆ = {1, 2,…, #P}, Γ = Ã ∪V
T
,
где T
0
= T
S,{ε}
.
3. Управляющую таблицу M определим на множестве (Γ∪{$}) ×Σ
*
k
следующим образом:
3.1.
M(T
A,L
, u) = (x
0
T
B
1
,Y
1
x
1
T
B
2
,Y
2
…T
B
m
,Y
m
x
m
, i), если T
A,L
(u) = (A→x
0
B
1
x
1
B
2
… B
m
x
m
,
·Y
1
, Y
2
,…, Y
m
Ò), и A → x
0
B
1
x
1
B
2
…B
m
x
m
является i-м правилом в P.
3.2. M(a, av) = pop для всех a
∈Σ, v ∈Σ
*
k
.
3.3. M($,
ε) = accept.
3.4. M(X, u) = error для всех (X, u)
∈(Γ∪{$}) ×Σ
*
k
, для которых значения
элементов, остались не определенными по пп. 1–3.
Пример 2.9. Рассмотрим ещё раз LL(2)-грамматику, обсуждавшуюся в
примере 2.3, с правилами
1) S
→ aAaa, 2) S → bAba, 3) A → b, 4) A → ε.
Используя уже построенные для неё LL(2)-таблицы легко собрать
управляющую таблицу для этой грамматики (см. табл. 2.4).
Таблица 2.4
Аванцепочки
Маг.
сим-ы
aa ab ba bb a b
ε
T
0
aT
1
aa, 1 aT
1
aa, 1 bT
2
ba, 2
T
1
ε, 4
b, 3
T
2
ε, 4
b, 3
a pop pop pop
b pop pop pop
$ accept
Например, на входной цепочке bba этот 2-предсказывающий алгоритм
анализа проходит следующие конфигурации:
(bba, T
0
$, ε) (bba, bT
2
ba$, 2) (ba, T
2
ba$, 1) (ba, ba$, 24)
(a, a$, 24) (
ε, $, 24).
В то же время, посредством правил 1 и 2, получаем S
bAba
bba.
Теорема 2.5. Алгоритм 2.3 производит правильный k-предсказывающий
алгоритм анализа для любой LL(k)-грамматики.
Доказательство аналогично доказательству предыдущей теоремы. Пусть
G = (V
N
,V
T
,P, S) — LL(k)-грамматика и A — k-предсказывающий алгоритм
анализа для грамматики G, построенный посредством алгоритма 2.2.
−−
−
−
−
−
−−
−−
2
l m
⇒
4
l m
⇒
−
−
*
−−
l m
π
⇒

Страницы