LR(1)-грамматики

Если для КС-грамматики G функция Action, полученная в результате работы алгоритма 4.11., не содержит неоднозначно определ_нных входов, то грамматика называется LR(1)- грамматикой.

Язык L называется LR(1)-языком, если он может быть порожден некоторой LR(1)-грамматикой.

Иногда используется другое определение LR(1)-грамматики. Грамматика называется LR(1), если из условий

FIRST(w)=FIRST(y)

следует, что uAy = zBx (то есть u = z, A = B и x = y).

Согласно этому определению, если uvw и uvy - правовыводимые цепочки пополненной грамматики, у которых FIRST(w) = FIRST(y) и A

? - последнее правило, использованное в правом выводе цепочки uvw, то правило A

? должно применяться и в правом разборе при свертке uvy к uAy. Так как A дает ? независимо от w, то LR(1)-условие означает, что в FIRST(w) содержится информация, достаточная для определения того, что uv за один шаг выводится из uA. Поэтому никогда не может возникнуть сомнений относительно того, как свернуть очередную правовыводимую цепочку пополненной грамматики.

Можно доказать, что эти два определения эквивалентны. Дадим теперь определение LR(k)-грамматики.

Определение. Пусть G = (N, ?, P, S) - КС-грамматика и G' = (N', ?, P', S') - полученная из нее пополненная грамматика. Будем называть G LR(k)-грамматикой для k

0, если из условий

(1)

(2)

(3)FIRSTk(w) = FIRSTk(y)

следует, что

Ay = ?Bx (т.е.

= ?, A = B и x = y):

Грамматика G называется LR-грамматикой, если она LR(k)-грамматика для некоторого k

Интуитивно это определение говорит о том, что если

?w и

?y - правовыводимые цепочки пополненной грамматики, у которых FIRSTk(w) = FIRSTk(y), и A

? - последнее правило, использованное в правом выводе цепочки

?w, то правило A

? должно использоваться также в правом разборе при свертке

?y к

Ay. Так как A даeт ? независимо от w, то LR(k)-условие говорит о том, что в FIRSTk(w) содержится информация, достаточная для определения того, что

? за один шаг выводится из

A. Поэтому никогда не может возникнуть сомнений относительно того, как свернуть очередную правовыводимую цепочку пополненной грамматики.
Кроме того, работая с LR(k)-грамматикой, мы всегда знаем, допустить ли данную входную цепочку или продолжать разбор.

Пример 4.13. Рассмотрим грамматику G с правилами

S

Sa|a

Согласно определению, G не LR(0)-грамматика, так как из трeх условий

(1)

(3)FIRST0(e) = FIRST0(a) = e

не следует, что S'a = S: Применяя определение к этой ситуации, имеем

= e; ? = S; ? = e; ? = e; A = S', B = S; x = e и y = a. Проблема здесь заключается в том, что нельзя установить, является ли S основой правовыводимой цепочки Sa, не видя символа, стоящего после S (т.е. наблюдая "нулевое" количество символов). В соответствии с интуицией G не должна быть LR(0)- грамматикой и она не будет ею, если пользоваться первым определением. Это определение мы и будем использовать далее.

Пример 4.14. Пусть G - леволинейная грамматика с правилами

Заметим, что G не является LR(k)-грамматикой ни для какого k.

Допустим, что G - LR(k)-грамматика. Рассмотрим два правых вывода в пополненной грамматике G':

Эти два вывода удовлетворяют условию из определения LR(k)- грамматики при

= e, ? = e, ? = akb, ? = e и y = akc: Но так как заключение неверно, т.е. A

B, то G - не LR(k)-грамматика. Более того, так как LR(k)-условие нарушается для всех k, то G - не LR-грамматика.

Если грамматика не является LR(1), то анализатор типа сдвиг-свертка при анализе некоторой цепочки может достигнуть конфигурации, в которой он, зная содержимое магазина и следующий входной символ, не может решить, делать ли сдвиг или свертку (конфликт сдвиг/свертка), или не может решить, какую из нескольких сверток применить (конфликт свертка/свертка).

В частности, неоднозначная грамматика не может быть LR(1). Для доказательства рассмотрим два различных правых вывода

(1)

(2)

Нетрудно заметить, что LR(1) - условие (согласно второму определению LR(1)-грамматики) нарушается для наименьшего из чисел i, для которых un-i

vm-i.

Пример 4.15. Рассмотрим ещe раз грамматику условных операторов:

Если анализатор типа сдвиг-свертка находится в конфигурации, такой, что необработанная часть входной цепочки имеет вид else ... $, а в магазине находится ...

if E then S, то нельзя определить, является ли if E then S основой, вне зависимости от того, что лежит в магазине ниже. Это конфликт сдвиг/свертка. В зависимости от того, что следует на входе за else, правильной может быть свертка по S

if E then S или сдвиг else, а затем разбор другого S и завершение основы if E then S else S. Таким образом нельзя сказать, нужно ли в этом случае делать сдвиг или свертку, так что грамматика не является LR(1).

Эта грамматика может быть преобразована к LR(1)-виду следующим образом:

Основная разница между LL(1)- и LR(1)- грамматиками заключается в следующем. Чтобы грамматика была LR(1)- грамматикой, необходимо распознавать вхождение правой части правила вывода, просмотрев все, что выведено из этой правой части и текущий символ входной цепочки. Это требование существенно менее строгое, чем требование для LL(1)-грамматики, когда необходимо определить применимое правило, видя только первый символ, выводимый из его правой части. Таким образом, класс LL(1)-грамматик есть собственный подкласс класса LR(1)-грамматик.

Справедливы также следующие утверждения [2].

Теорема 4.7. Каждый LR(1)-язык является детерминированным КС-языком.

Теорема 4.8. Если L - детерминированный КС-язык, то существует LR(1)-грамматика, порождающая L.

Теорема 4.9. Для любой LR(k)-грамматики для k > 1 существует эквивалентная ей LR(k \Gamma 1)-грамматика.

Доказано, что проблема определения, порождает ли грамматика LR-язык, является алгоритмически неразрешимой.

Содержание раздела