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

UptoLike

ВУЗ: 

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

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

Рубрика: 

209
который замещается терминальной цепочкой на последнем шаге вывода.
Функция
EFF
G
k
отличается от функции
FIRST
G
k
тем, что
в значение первой не
включаются префиксы терминальных цепочек, если эти цепочки получены
посредством ε-правила, применённого на последнем шаге вывода.
Пример 3.8. Рассмотрим контекстно-свободную грамматику со
следующими правилами:
1) S → AB, 2) A → Ba | ε, 3) B → Cb | C, 4) C → c | ε.
Вычислим функцию
2
EFF
G
(S). Поскольку аргумент начинается на нетер-
минал, то согласно определению 3.7 необходимо построить всевоз-можные
правосторонние выводы, начинающиеся с нетерминала S и дающие терминаль-
ные цепочки, в которых на последнем шаге не применяется ε-правило. В
искомое множество нужно включить префиксы этих терминальных цепочек
длиной 2 символа, а если они короче, то включить их целиком.
Любой вывод имеет единственное начало: S
AB. Любое продолжение даст
результат вида S AB
Aw, где w∈ V
T
*
— некоторая терминальная цепочка.
Далее возможны следующие продолжения:
Таким образом,
2
EFF ( ) { , },
G
Scbca= тогда как
2
FIRST
G
(S)={ε, a, b, c, ab, ac,
ba, ca, cb}.
Теорема 3.1. Чтобы контекстно-свободная грамматика G=(V
N
, V
T
, P, S)
была LR(k)-грамматикой,
необходимо и достаточно, чтобы выполнялось
следующее условие: если [A →β., u] — LR(k)-ситуация, допустимая для
активного префикса αβ правосентенциальной формы αβw пополненной
грамматики
,G
′
где
FIRST ( ),
G
k
uw∈
то не существует никакой другой LR(k)-
ситуации [A
1
→β
1
.β
2
, v], которая отличается от данной и допустима для
активного префикса αβ при условии, что u∈
EFF
G
k
(β
2
v) (в частности, и при
β
2
= ε).
Доказательство.
Необходимость.
Предположим, что G — LR(k)-грамматика. Докажем, что
тогда условие выполняется.
По определению [A →β., u] — LR(k)-ситуация, допустимая для активного
префикса αβ правосентенциальной формы αβw пополненной грамматики
,G
′
если существует правосторонний вывод вида
и
FIRST ( ).
G
k
uw∈
rm
*
⇒
rm
rm rm
*
SABAw⇒⇒⇒
rm
⇒
rm
⇒
Caw
rm
⇒
— недопустимо (
ε
-правило);
Cbaw
caw,
aw
w — недоп
у
стимо
(
ε
-п
р
авило
)
.
cbaw,
baw — недопустимо (
ε
-правило);
rm
⇒
rm
⇒
rm
⇒
rm
⇒
rm
⇒
rm rm
*
1) SAw w
′
⇒α ⇒αβ

Страницы