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

UptoLike

ВУЗ: 

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

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

Рубрика: 

208
Заметим, что цепочка z является префиксом цепочки x, а не её окончанием,
так как именно цепочка y является окончанием всей сентенциальной формы
αβy. Два разных разбиения одной и той же сентенциальной формы γδx = αβy
представлено на риc. 3.2.
Условие γδx = αβy можно переписать как γδzy = αβy, и потому
γδz = αβ. (3.1)
Второй вывод разметим по образцу первого с учётом равенства x = zy, а
первый разметим по образцу второго с учётом равенства (3.1):
rm
rm
*
1 ) ,S B zy zy
′′
⇒γ ⇒γ δ
rm
rm
*
2) .SAwwzw
′′
⇒α ⇒αβ =γδ
Эти два вывода обладают следующими особенностями:
а ) FIRST ([ ]) FIRST ([ ]),
GG
kk
wy
′
=
так как [w]=zy, [y]=zw и
FIRST ( ) FIRST ( ),
GG
kk
wy=
б )
′
[γ][B][x] ≠ [α][A][y], так как [γ]=α, [B]=A, [x]=w, [α] = γ, [A]=B, [y] = zw,
поскольку [γ][B][x] = αAw и [α][A][y] = γBzw, а цепочки αAw и γBzw не могут
быть равными, так как их терминальные окончания w и zw не равны между
собой, ибо |z| > 0.
Наконец, выполняется условие
в )
′
|[γδ]| > |[αβ]|, ибо [γδ] = αβ, [αβ] = γδ и |γδ| < |αβ| по предположению.
Итак, исходная пара правосторонних выводов 1 и 2, которые обменялись
ролями, представлены в требуемом виде 1
’
и 2
’
, которые удовлетворяют всем
трем условиям а
’), б
’
) и в’). Что и требовалось доказать.
Введём функцию
EFF
G
k
(α), где α∈(V
N
∪V
T
)
*
, необходимую для построения
LR(k)-анализатора. Она будет помогать при определении, является ли ε-це-
почка основой для данной сентенциальной формы, подлежащей свертке.
Определение 3.7. Пусть G = (V
N
, V
T
, P, S) — cfg и α∈ (V
N
∪V
T
)
*
. Положим
Говоря неформально, функция
EFF
G
k
(α) ничем не отличается от функции
FIRST
G
k
(α), если α начинается с терминала, а если α начинается с нетерминала,
то при правостороннем выводе именно он является последним нетерминалом,
FIRST
G
k
(α), если α начинается на терминал, а иначе
{w∈ V
T
*
k
|∃α
β
wx, где β≠Awx, A∈V
N
, |w|= k или |w|< k и x =ε}.
[
γ
]
[B] [x]
[
α
β
]
[y]
[α]
[A]
[w]
[α]
[
β
]
[w]
γδ
z
y
x
αβ
Рис. 3.2.
rm
*
⇒
rm
⇒
EFF ( )
G
k
α=

Страницы