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

UptoLike

ВУЗ: 

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

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

Рубрика: 

177
для
всех где (2.2)
Посмотрим, как будет действовать анализатор из своей начальной конфигу-
рации
000
( , $, ) ( , $, ) ( , $, ),xyTxzyTxyT
′′′
ε
=ε=ε где
.yzy
′
=
Применим к имеющемуся выводу
индукционную гипотезу с це-
почкой ,yzy
′
=
поскольку
() () ( )
FIRST FIRST FIRST
( ) ( ) ( ).
FIRST FIRST FIRST
GG G
kk k
GGG
kkk
yzyz
A
′
=⊆α=
′
=
βγ ⊆ γ = α
Как следствие получаем
000
,
*
( , $, ) ( , $, ) ( , $, ) ( , $, ) ( , , $, ). (2.3)
AL
xyTxzyTxyT y zyT−−
′′′′′′ ′
ε= ε= ε α π = γ π

Вычислим аванцепочку
() ( ) ()
FIRST FIRST FIRST
() () () ,
FIRST FIRST FIRST
GGG
kkk
GGG
kk
kkk
zy z
u
L
⊆α=βγ=
∈
=β⊕ γ=β⊕
а для таких аванцепочек, как показывает (2.2), M(T
A, L
, u ) = (
β
, i). Поэтому сле-
дующее движение и завершающие pop-движения: продолжают процесс (2.3)
следующим образом:
,
*
( , $, ) ( , $, ) ( , $, ) ( , $, ).
AL
zy T zy i zy z i y−− −−
′′′
γπ γπ= απ απ
β

Что и требовалось.
II. Докажем теперь, что если LL(k)-анализатор совершает переход вида
0
*
( , $, ) ( , $, )xy T y−−εαπ
для
любой цепочки y∈Σ
*
, такой, что
() (),
FIRST FIRST
GG
kk
y ⊆α
где
α = h( α
), то
где x — закрытая, а
α — открытая часть данной сентенциальной
формы x
α.
Индукция по l =
|π|.
База. Пусть l = 1, т.е.
π = i.
Тогда
0
*
(,$,) (,$,).
x
yT y i−−εα
Анализатор пишет на выходную ленту номер
правила только при движении типа 1, а оно совершается только при наличии
LL(k)-таблицы на вершине магазина. Следовательно, это — первое движение, и
только оно пишет номер i на выход. Поэтому фактически имеем
0
*
( , $, ) ( , $, ) ( , $, ),
x
yT xy y i−− −−εβεα
причём все остальные движения — это pop-движения.
Очевидно, что только при достижима завершающая конфигурация
посредством одних только pop-движений.
Первое движение обеспечивалось элементом таблицы где
а это подразумевает существование правила S
→ β, в котором
β = xα, под номером i. Тогда
l m
Sx
π
′
′
⇒α
'
()
l m
i
Sx⇒α.
0
(, ) (,),
Tu i=
β
(),
FIRST
G
k
x
y
u
∈
l m
Sx
π
⇒α,
x
=
α
β

Страницы