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

UptoLike

ВУЗ: 

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

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

Рубрика: 

203
Пример 3.3. Пусть грамматика G содержит следующие правила:
1) S → C
| D; 2) C → aC | b; 3) D → aD | c.
Спрашивается, является ли она LR(0)-грамматикой.
Отметим прежде всего, что грамматика G — праволинейна. Это значит,
что любая сентенциальная форма содержит не более одного нетерминала,
причём правый контекст для него всегда пуст. Очевидно также, что любая
сентенциальная форма имеет вид a
i
C, a
i
b, a
i
D, a
i
c, где i ≥ 0.
Пополненная грамматика содержит ещё одно правило:
(0)
.SS
′
→
В роли нетерминала A могут быть при сопоставлении с образцом
определения LR(k)-грамматик нетерминалы
S
′
либо C, либо D. Отметим, что
нетерминал S в роли нетерминала A нас не интересует, поскольку не
существует двух разных правосентенциальных форм, в которых участвовал бы
нетерминал S. В любом случае в роли цепочек w и x будет выступать пустая
цепочка ε из-за праволинейности грамматики G.
Принимая все это во внимание, проверим, отвечает ли данная грамматика
определению LR(0)-грамматики. В данном конкретном случае LR(0)-условие
состоит в том, что если существуют два правосторонних вывода вида
1)
2)
то должно быть B = A и γ = α. Другими словами, любая сентенциальная форма
должна быть выводима единственным способом. Легко убедиться в том, что
любая из указанных возможных сентенциальных форм рассматриваемой
грамматики обладает этим свойством, и потому LR(0)-условие выполняется и,
следовательно, G — LR(0)-грамматика.
Очевидно, что данная грамматика G не LL(k)-грамматика ни при каком k.
Пример 3.4. Рассмотрим грамматику G с правилами:
1) S → Ab
| Bc; 2) A → Aa | ε; 3) B → Ba | ε.
Эта
леволинейная грамматика порождает тот же самый язык, что и
грамматика предыдущего примера, и она не является LR(k)-грамматикой ни
при каком
k. Действительно, рассмотрим, например, два таких правосторонних
вывода:
1)
2)
Здесь цепочки a
i
b и a
i
c являются правыми контекстами для пустой основы,
которая в одном случае сворачивается в нетерминал A, а в другом — в
нетерминал B. В какой нетерминал сворачивать основу, можно определить
лишь по последнему символу (если он — b, то сворачивать в нетерминал A,
если он — c, то сворачивать в нетерминал B), который может отстоять от неё
на сколько угодно большое расстояние (в зависимости от выбора i).
Следовательно, каким бы большим
ни было k, всегда найдётся такое i, что
FIRST ( ) FIRST ( ),
GG
ii
kk
ab ac=
но A ≠ B.
rm rm
*
,SB
′
⇒γ ⇒αβ
rm rm
*
,SA
′
⇒α ⇒αβ
rm rm rm rm
*
,
ii
S S Ab Aa b a b
′
⇒⇒ ⇒ ⇒
rm rm rm rm
*
.
ii
S S Bc Ba c a c
′
⇒⇒ ⇒ ⇒

Страницы