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

UptoLike

ВУЗ: 

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

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

Рубрика: 

202
Использование в определении LR(k)-грамматики пополненной грамматики
существенно для однозначного определения конца анализа. Действительно,
если грамматика использует S в правых частях правил, то свертка основы в S не
может служить сигналом приёма входной цепочки. Свертка же в
S
′
в
пополненной грамматике служит таким сигналом, поскольку
S
′
нигде, кроме
начальной сентенциальной формы, не встречается.
Существенность использования пополненной грамматики в определении
LR(k)-грамматик продемонстрируем на следующем конкретном примере.
Пример 3.2. Пусть пополненная грамматика имеет следующие правила:
0)
,SS
′
→
1) S
→ Sa,
3) S
→ a.
Если игнорировать 0-е правило, то, не заглядывая в правый контекст
основы Sa, можно сказать, что она должна сворачиваться в S. Аналогично
основа a безусловно должна сворачиваться в S. Создаётся впечатление, что
данная грамматика без 0-го правила есть LR(0)-грамматика.
С учётом же 0-го правила имеем:
1)
2)
Сопоставив
эти два вывода с образцом определения (образец приведён в
рамке),
Если существуют правосторонние выводы
1)
rm rm
*
,SAw w
′
⇒α ⇒αβ
в которых
() (),
FIRST FIRST
GG
kk
wy=
2)
то должно быть αAy = γBx
получаем
α = ε, β = S, w = ε, A =
S
′
, γ = ε, B = S, x = ε, y = a, и при k = 0
а так как
,Sa S
′
≠
то требование αAy = γBx не выполняется.
Итак, данная грамматика не является LR(0)-грамматикой.
Лемма 3.1. Пусть G = (V
N
, V
T
, P, S) — LR(k)-грамматика и
G
′
—
пополненная грамматика для G. Если существуют правосторонние выводы в
G
′
вида
1) 2)
в которых то γ = α, B = A, x = y,
′
β
=β.
Доказательство. Заметим, что первые три равенства непосредственно
следуют из определения 3.2 и остаётся установить только, что
′
β=β.
Если то в силу первых трёх равенств имеем
Следовательно,
′
β=β.
Что и требовалось доказать.
rm rm
.SSSa
′
⇒⇒
rm
,SS
′
⇒
rm rm
*
,SBx y
′
⇒γ ⇒αβ
rm rm
*
,SBx x y
′′
⇒γ ⇒γβ =αβ
rm rm
*
,SAw w
′
⇒α ⇒αβ
() (),
FIRST FIRST
GG
kk
wy=
00 00
FIRST ( ) FIRST ( ) { },FIRST ( ) FIRST ( ) { }, , ,
GG GG
wyaAySaBxS
′
=ε=ε = =εα=γ=
,
x
y
′
γβ = αβ
.
x
yy
′′
γβ = αβ = αβ

Страницы