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

UptoLike

ВУЗ: 

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

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

Рубрика: 

229
В частности, если α = ε, т.е. то (T
0
, x, ε)
(T
0
ST, ε, π
R
). Достигну-
тая конфигурация является принимающей по тем же причинам, что и в базовом
случае.
II. Индукцией по l — числу движений LR(k)-анализатора, покажем, что
если (T
0
, w, ε) (T
0
X
1
T
1
X
2
...X
m
T
m
, x, π
R
),
то αx w, где α = X
1
X
2
... X
m
, X
j
∈ V
N
∪ V
T
, j =1, 2, … , m; x,w ∈ V
T
*
.
Другими словами, покажем, что магазинная цепочка (без учёта LR(k)-
таблиц) и конкатенированная с ней входная цепочка представляют право-
сентенциальную форму, из которой выводится анализируемое предложение
посредством последовательности правил π.
База. Пусть l =1: имеется одно движение.
Случай 1
: shift-движение.
Пусть (T
0
, w, ε) = (T
0
, X
1
x, ε)
(T
0
X
1
T, x, ε). Здесь w = X
1
x, где X
1
∈V
T
, x∈V
T
*
.
Первый символ цепочки w переносится в магазин, на вершине оказывается
некоторая LR(k)-таблица T, в выходную цепочку ничего не пишется. Следует
показать, что существует вывод без использования каких-либо пра-
вил грамматики. Но это возможно лишь в случае, когда w = X
1
x, что как раз и
имеет место.
Случай 2
: reduce i -движение.
Это движение предполагает свертку какой-то цепочки в верхней части
магазина в нетерминал по правилу номер i. Поскольку в начальной
конфигурации (T
0
, w, ε) магазин пуст (T
0
не считается), то основа магазинной
цепочки тоже пуста. Именно она и сворачивается к некоторому нетерминалу.
Формально это движение обусловлено тем, что T
0
=(f
0
, g
0
), f
0
(u) = reduce i для
u∈
FIRST
G
k
(w).
Наряду с этим согласно алгоритму построения LR(k)-анализатора T
0
= T(A
0
),
A
0
=
V
G
k
(ε), [A → ε., u]∈ A
0
, что и обусловливает движение:
(T
0
, w, ε)
(T
0
AT, w, ε), где T = g
0
(A).
Остаётся проверить, что Aw w. Но это очевидно, поскольку данное дви-
жение обусловлено существованием правила A → ε ∈ P, номер которого есть i.
База доказана.
Индукционная гипотеза. Предположим, что утверждение II
выполняется для всех l ≤ n (n ≥ 1).
Индукционный переход. Покажем, что утверждение II выполняется для
l = n +1. Пусть первые n движений дают (T
0
, w, ε)
(T
0
X
1
T
1
X
2
...X
m
T
m
,, ).
R
x
′′
π
По индукционной гипотезе немедленно получаем X
1
X
2
...X
m
x w. Затем сове-
ршается последнее, (n +1)-е, движение.
Случай 1
: shift-движение.
Это движение происходит следующим образом:
(T
0
X
1
T
1
X
2
...X
m
T
m
,, )
R
x
′′
π =
=(T
0
X
1
T
1
X
2
...X
m
T
m
, X
m +1
x, )
R
′
π
(T
0
X
1
T
1
X
2
...X
m
T
m
X
m +1
T
m +1
, x, )
R
′
π , т.е.
X
m +1
переносится в магазин, в выходную цепочку ничего не пишется.
rm
,Sx
π
⇒
1
rm
*
X
xw⇒
rm
′
π
⇒
rm
π
⇒
()
rm
i
⇒
_
_
A
_
_
A
*
_
_
A
_
_
l
A
_
_
n
A
_
_
A

Страницы