Лекция: LR - грамматики
(left — rightmost)
Эти грамматики относятся к восходящим грамматикам (снизу — вверх).
В LR- грамматиках сворачиваются самые правые части правил для самых левых нетерминальных символов и анализируется очередной самый правый символ свертываемой части строки.
К числу LR- грамматик относятся грамматики с предшествованием.
Определим специальные отношения, которые могут возникать между символами стоящими рядом в сентенциальной форме. Здесь правые части грамматических правил будем называть свертками.
1. Если Si и Sj — два рядом стоящие символа входят в одну свертку, то между ними существует отношение: Si = *Sj (назовем его равно);
… Si Sj...
Пример. В сентенциальной форме AbCdEfg при наличии правила K®CdE, существуют отношения
C =* d, d =* E
2. Если Si и Sj два рядом стоящие символа и с Sj начинается какая-то свертка, то между ними существует отношение: Si <*∙Sj ;
Si Sj...
Пример. В сентенциальной форме AbCdEfg при наличии правила L ® dE
Существует отношение
C <* d
3. a) Если Si и Sj два рядом стоящие символа и Si самый правый символ в свертке, то между ними существует отношение: Si *> Sj ;
… Si Sj
Пример. В сентенциальной форме AbCdEfg при наличии правила L ® dE
существует отношение
E *> f
б) Если Si и Sj два рядом стоящие символа и Si самый правый символ в одной свертке, а Sj — самый левый в другой, то между ними существует отношение: Si *> Sj ;
… Si Sj...
Пример.. В сентенциальной форме 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 | =*∙ | <*∙ |
Грамматика называется грамматикой с предшествованиями, если между любыми двумя символами, стоящими рядом в сентенциальной форме, существует строго одно отношение предшествования.