LR - грамматики

(left - rightmost)

Эти грамматики относятся к восходящим грамматикам (снизу - вверх).

В LR- грамматиках сворачиваются самые правые части правил для самых левых нетерминальных символов и анализируется очередной самый правый символ свертываемой части строки.

К числу LR- грамматик относятся грамматики с предшествованием.

Определим специальные отношения, которые могут возникать между символами стоящими рядом в сентенциальной форме. Здесь правые части грамматических правил будем называть свертками.

1. Если S_i и S_j - два рядом стоящие символа входят в одну свертку, то между ними существует отношение: S_i = *S_j (назовем его равно);

... S_i S_j...

Пример. В сентенциальной форме AbCdEfg при наличии правила K®CdE, существуют отношения

C =* d, d =* E

2. Если S_i и S_j два рядом стоящие символа и с S_j начинается какая-то свертка, то между ними существует отношение: S_i <*∙S_j;

S_i S_j...

Пример. В сентенциальной форме AbCdEfg при наличии правила L ® dE

Существует отношение

C <* d

3. a) Если S_i и S_j два рядом стоящие символа и S_i самый правый символ в свертке, то между ними существует отношение: S_i *> S_j;

... S_i S_j

Пример. В сентенциальной форме AbCdEfg при наличии правила L ® dE

существует отношение

E *> f

б) Если S_i и S_j два рядом стоящие символа и S_i самый правый символ в одной свертке, а S_j - самый левый в другой, то между ними существует отношение: S_i *> S_j;

... S_i S_j...

Пример.. В сентенциальной форме AbCdEfg при наличии правил L ® dE и M ® fg

существует отношение E *> f

Для удобства дальнейшей работы составим таблицу левых и правых символов, которые могут оказаться в подставленных вместо этих символов цепочках на месте данных нетерминальных символов. Таблица строится на основе анализа грамматических правил.

A ® BC

B ® lC

B ® CA

C ® d

	левые	правые
A	B l C d	C d
B	l C d	C A d
C	d	d

Выявим отношения:

B =* C l =* C C =* A

B<*∙Л(C) (множество левых для С)

B<*∙Л(C) = {d}

l<* ∙Л(C)

C<*∙Л(C) = {B, l, C, d}

{C, A, d} = П(B)∙*>C

0 = П(l)∙*>C

{d} = П(C)∙*>C (3a)

{C, A, d} = П(B)∙*> Л(C) = {d} (3b)

{d} = П(C)∙*>Л(A)={B, l, C, d}

И сведем их в таблицу - матрицу предшествования.

	A	B	C	d	l
A			∙*>	∙*>
B			=*	<*∙
C	=*∙	<*	*> <*	*> <*	<*
d	*>	*>	*>	∙*>	*>
l			=*∙	<*∙

Грамматика называется грамматикой с предшествованиями, если между любыми двумя символами, стоящими рядом в сентенциальной форме, существует строго одно отношение предшествования.