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

UptoLike

ВУЗ: 

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

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

Рубрика: 

176
Требуется
доказать, что S
x тогда и только тогда, когда (x,T
0
$,ε) (ε, $, π).
По индукции докажем вспомогательное утверждение, общий смысл
которого состоит в том, что анализатор в своем магазине воспроизводит
последовательность образов открытых частей сентенциальных форм
левостороннего вывода входной цепочки, если она выводима в данной
грамматике G, причём если
π — последовательность номеров правил,
участвующих в её выводе, то
π образуется на выходе анализатора. Связь между
открытыми частями сентенциальных форм и их образами в магазине LL(k)-
анализатора описывается следующим гомоморфизмом:
Область определения h легко расширить до
Γ
*
, и мы будем в дальнейшем
предполагать, что это сделано.
I. Докажем сначала, что если
где x — закрытая, а
α — открытая
часть данной сентенциальной формы, то для любой цепочки y
∈Σ
*
, такой, что
FIRST
G
k
( y )⊆
FIRST
G
k
(α), анализатор совершает переход (xy, T
0
$, ε) (y, α
$, π),
где
() .h α=α
Попросту говоря, если в
α
заменить LL(k)-таблицы на нетерми-
налы, с которыми они ассоциированы, то получится
α.
Индукция по l =
|π|.
База. Пусть l =1, т.е.
π = i, где i — номер некоторого правила грамматики.
Пусть
и y
∈Σ
*
, такая, что На единственном
шаге этого вывода применяется правило вида S
→ xα, имеющее номер i.
Согласно алгоритму 2.3 M(S, u) = (x
α
, i) для всех
() {}
FIRST
G
k
k
x
u
α⊕ ε
∈
.
Посмотрим,
как будет действовать LL(k)-анализатор, начиная с конфигура-
ции
(xy, T
0
$, ε).
Очевидно, что аванцепочка
() () () {}
FIRST FIRST FIRST
GGG
k
kkk
xy x x
u
⊆α=α⊕ε
∈
и,
следовательно, M(T
0
, u) = (x
α
, i).
Поэтому (xy, T
0
$, ε) (xy, x
α
$, i) (y,
α
$,ε), причём последний переход
происходит посредством pop-движений.
База доказана.
Индукционная
гипотеза. Предположим, что утверждение выполняется
для всех l ≤ n (n ≥ 1).
Индукционный переход. Докажем утверждение для l= n +1.
Пусть
имеется левосторонний вывод длиной n +1:
Здесь , iA z
′′
π=π α = γ, βγ= α,
где
*
*
TN
, , , , .zV x xzAV V
′
∈= ∈βγ∈
На послед-
нем шаге вывода применялось i-е правило A
→β — из множества P.
Согласно алгоритму 2.3
h(x) =
a, если X = a, a ∈V
T
,
A
, если X = T
A
,
L
∈
Ã
.
l m
Sx
π
⇒α,
*
−−
()
l m
i
Sx⇒α
*
−
−
−−
l m l m
()
i
Sx xA x x
π
′′ ′ ′
⇒α= γ⇒βγ=α.
'
() ().
FIRST FIRST
GG
kk
y ⊆α
,(,)()AL
M
Tu i=β,
() ,
FIRST
G
k
k
uL∈β⊕ FIRST ( ).
G
k
L
γ

Страницы