Специальная математика. Соловьев А.Е. - 86 стр.

UptoLike

ВУЗ: 

ПНИПУ | Пермь

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

Рубрика: 

7.15. LR - грамматики
(left - rightmost)
Эти грамматики относятся к восходящим грамматикам (снизу - вверх).
В LR- грамматиках сворачиваются самые правые части правил для самых левых
нетерминальных символов и анализируется очередной самый правый символ свертываемой
части строки.
К числу LR- грамматик относятся грамматики с предшествованием.
Определим специальные отношения, которые могут возникать между символами стоящими
рядом в сентенциальной форме. Здесь правые части грамматических правил будем называть
свертками.
1. Если S
i
и S
j
- два рядом стоящие символа входят в одну свертку, то между ними
существует отношение : S
i
= *S
j
(назовем его равно);
... S
i
S
j
...
Пример. В сентенциальной форме AbCdEfg при наличии правила KCdE, существуют
отношения
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
— 86 —
                                7.15. 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
                                         — 86 —

Страницы