Теория и реализация языков программирования



         

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


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

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

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

  1. S' \Rightarrow^*_r uAw \Rightarrow_r uvw
  2. S' \Rightarrow^*_r zBx \Rightarrow_r uvy
  3. 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)

S' \Rightarrow^*_{G^{'r}} \alpha A \omega \Rightarrow_{G^{'r}} \alpha \beta \omega

(2)

S' \Rightarrow^*_{G^{'r}} \gamma B x \Rightarrow_{G^{'r}} \alpha \beta y

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

следует, что

Ay = ?Bx (т.е.
= ?, A = B и x = y):

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

0:

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

?w и
?y - правовыводимые цепочки пополненной грамматики, у которых FIRSTk(w) = FIRSTk(y), и A
? - последнее правило, использованное в правом выводе цепочки
?w, то правило A
? должно использоваться также в правом разборе при свертке
?y к
Ay. Так как A даeт ? независимо от w, то LR(k)-условие говорит о том, что в FIRSTk(w) содержится информация, достаточная для определения того, что
? за один шаг выводится из
A. Поэтому никогда не может возникнуть сомнений относительно того, как свернуть очередную правовыводимую цепочку пополненной грамматики.


Содержание  Назад  Вперед