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

UptoLike

ВУЗ: 

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

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

Рубрика: 

226
Поскольку
A
3
={[S → SaS.b, ε | a], [S → S.aSb, a | b]}, то T
3
=(f
3
, g
3
) имеет
следующий табличный вид:
f
3
(u) g
3
(X )
a b
ε
S a b
shift shift error error T
4
T
5
Поскольку A
4
={[S → Sa.Sb, a | b], [S → .SaSb, a|b], [S →., a | b]}, то T
4
= (f
4
, g
4
)
имеет следующий табличный вид:
f
4
(u) g
4
(X )
a b
ε
S a b
reduce 2 reduce 2 error T
6
error error
Поскольку A
5
= {[S → SaSb., ε | a}, то T
5
= ( f
5
, g
5
) имеет следующий табличный
вид:
f
5
(u) g
5
(X )
a b
ε
S a b
reduce 1 error reduce 1 error error error
Поскольку A
6
= {[S → SaS.b, a | b], [S → S.aSb, a | b]}, то T
6
=(f
6
, g
6
) имеет
следующий табличный вид:
f
6
(u) g
6
(X )
a b
ε
S a b
shift shift error error T
4
T
7
Поскольку A
7
= {[S → SaSb., a | b]}, то T
7
=(f
7
, g
7
) имеет следующий
табличный вид:
f
7
(u) g
7
(X )
a b
ε
S a b
reduce 1 reduce 1 error error error error
Все эти LR(k)-таблицы сведены в управляющую таблицу 3.1 канонического
LR(k)-анализатора, которая была приведена в примере 3.6.
Итак, LR(k)-анализаторы обладают следующими свойствами:
1. Диагностичностью. Простой индукцией по числу шагов анализатора
можно показать, что каждая LR(k)-таблица, находящаяся в его магазине,
соответствует цепочке символов, расположенной слева от таблицы. Именно:
если в цепочке, о которой идёт речь, отбросить символы LR(k)-таблиц, то
получим активный префикс грамматики, которому эта LR(k)-таблица
соответствует. Поэтому LR(k)-анализатор сообщает об ошибке при первой же
возможности в ходе чтения входной цепочки слева направо.
2.
Пусть T
j
=(f
j
, g
j
). Если f
j
(u)=shift и анализатор находится в конфигурации
(T
0
X
1
T
1
X
2
...X
j
T
j
, x, π), то найдется LR(k)-ситуация [B →β
1
.β
2
, v ], β
2
≠ε, допу-
стимая для активного префикса X
1
X
2
... X
j
, такая, что u ∈
EFF
G
k
(β
2
v), где
то по теореме 3.1 правый конец основы цепочки X
1
X
2
...X
j
uy должен быть где-то
справа от символа X
j
.
*
*
12
rm
FIRST ( ). Поэтому, если ... при некоторой цепочке ,
G
kjk
ux SXXXuy yV
′
∈⇒ ∈

Страницы