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

UptoLike

ВУЗ: 

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

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

Рубрика: 

169
Посмотрим, как будет действовать анализатор из своей начальной
конфигурации ( , $, ) ( , $, ) ( , $, ),xySxzySxyS
′
′′
ε= ε= ε где .yzy
′
=
Применим к имеющемуся выводу индукционную гипотезу с це-
почкой y
’
, поскольку
11 1
111
() () ( )
FIRST FIRST FIRST
( ) ( ) ( ).
FIRST FIRST FIRST
GG G
GGG
yzyz
Ay
⊆
=α=
=
βγ ⊆ γ = α
'
'
Как следствие получаем
*
( , $, ) ( , $, ) ( , $, ) ( , $, ) ( , $, ).xySxzySxyS y zyA−−
′′′′′′ ′
ε= ε= ε α π = γ π
Вычислим аванцепочку от zy:
11
111
() ( )
FIRST FIRST
() ( ()),
FIRST FIRST FOLLOW
GG
GGG
uzy z
A
⊆
∈α=
⊆
=γ
β
β
а для таких аванцепочек, как показывает (2.1), M(A, u) = (β, i). Поэтому следу-
ющее движение и завершающие pop-движения продолжают процесс таким
образом:
*
(, $,) (, $, )(, $, ) (,$,).zy A zy i zy z i y−− −−
′′′
γπ γπ = απ απ
β
Что и требовалось.
II.
Докажем теперь, что если анализатор совершает переход вида
(xy,S$, ε) (y, α$, π)
для любой цепочки y ∈Σ
*
, такой, что
1
FIRST
G
(y)⊆
1
FIRST
G
(α), то S
xα, где x
— закрытая часть, а α — открытая часть данной сентенциальной формы.
Индукция по l = |π|.
База. Пусть l =1, т.е. π = i.
Имеем (xy, S$, ε)
(y, α$, i). Анализатор пишет на выходную ленту номер
правила только при движении типа 1, а оно совершается только при наличии
нетерминала на вершине магазина. Следовательно, это — первое движение, и
только оно пишет номер i на выход. Поэтому фактически имеем
(xy, S$, ε) (xy, β$, ε) (y, α$, i),
причём все остальные движения — это pop-движения. Очевидно, что только
при β = xα достижима завершающая конфигурация. Первое движение обеспе-
чивается элементом таблицы M(S, a)=(β, i), где , а это подра-
зумевает существование правила S → β = xα под номером i.
Чтобы первое движение могло произойти, необходимо, чтобы
И это действительно так,
поскольку
а тогда
Индукционная гипотеза. Предположим, что утверждение выполняется
для всех l ≤ n (n ≥ 1).
*
−
−
*
−−
l m
π
⇒
*
−
−
−
−
()
lm
i
Sx⇒α.
l m
Sx
π
′
′
⇒α
'
1
()
FIRST
G
x
y
u
=
11
FIRST ( FOLLOW ( )).
GG
ux S∈α
11 1 1
FIRST ( ) FIRST ( ) FIRST ( FOLLOW )),
GG G G
uxy x x S
⊆
∈∈αε α(

Страницы