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

UptoLike

ВУЗ: 

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

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

Рубрика: 

206
Таблица 3.3
f(u) g(X)
LR(1)-
таблицы
a b
ε
S
a b
T
0
reduce 2
reduce 2 T
1
T
1
shift
accept
T
2
T
2
reduce 2 reduce 2 T
3
T
3
shift shift T
4
T
5
T
4
reduce 2 reduce 2 T
6
T
5
reduce 1 reduce 1
T
6
shift shift T
4
T
7
T
7
reduce 1 reduce 1
Рассмотрим действия этого анализатора на входной цепочке aabb:
(T
0
, aabb, ε)
−
−
(T
0
ST
1
, aabb, 2)
−
−
(T
0
ST
1
aT
2
, abb, 2)
−
−
−−
(T
0
ST
1
aT
2
ST
3
, abb, 22)
−
−
(T
0
ST
1
aT
2
ST
3
aT
4
, bb, 22)
−
−
−−
(T
0
ST
1
aT
2
ST
3
aT
4
ST
6
, bb, 222)
−
−
(T
0
ST
1
aT
2
ST
3
aT
4
ST
6
bT
7
, b, 222)
−−
−−
(T
0
ST
1
aT
2
ST
3
, b, 2221)
−
−
(T
0
ST
1
aT
2
ST
3
bT
5
, ε, 2221)
−
−
(T
0
ST
1
, ε, 22211).
Итак, цепочка aabb принимается, и π
R
= 22211 — её правосторонний
анализ.
§ 3.4. Свойства LR(k)-грамматик
Рассмотрим некоторые следствия из определения LR(k)-грамматик,
подводящие нас к механизму анализа.
Определение 3.4. Пусть G = (V
N
, V
T
, P, S) — контекстно-свободная
грамматика и — некоторый правосторонний вывод в грамма-
тике G, где α,β∈ (V
N
∪V
T
)
*
, w ∈ V
T
*
.
Активным
префиксом сентенциальной формы αβw называется любая
начальная часть (префикс) цепочки αβ, включая, в частности, ε и всю эту
цепочку.
Определение 3.5. Пусть G = (V
N
, V
T
, P, S) — контекстно-свободная грам-
матика и A →β
1
β
2
∈ P. Композицию [A → β
1
.β
2
, u], где u ∈ V
T
*
k
, назовем
LR(k)-ситуацией.
Определение 3.6. Пусть G = (V
N
, V
T
, P, S) — контекстно-свободная
грамматика
и — правосторонний вывод в грамматике G, где
β = β
1
β
2
, β
1
,β
2
∈ (V
N
∪V
T
)
*
. Назовем [A →β
1
.β
2
,u], где FIRST ( ),
G
k
uw∈ LR(k)-
ситуацией, допустимой для активного префикса αβ
1
.
Пример 3.7. Обратимся ещё раз к LR(0)-грамматике из примера 3.3,
которая содержит следующие правила:
1) S → C
| D, 2) C → aC | b, 3) D → aD | c.
rm rm
*
SAw w⇒α ⇒αβ
rm rm
*
SAw w⇒α ⇒αβ

Страницы