На головну

LR - граматики

  1.  LL (1) - граматики.
  2.  S і q - граматики
  3.  атрибутних граматики
  4.  Граматики історичні, а не тільки нормативні.
  5.  Граматики простого передування. відносини передування
  6.  Найбільш важкі випадки граматики

(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      = * •  <* •  

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




 L-числення |  Поняття формальної граматики |  дерева виведення |  Класифікація мов по Хомського |  розпізнають автомати |  поняття транслятора |  детермінованого |  Перехід від праволінейной граматики до автоматної |  Детерміновані автомати з магазинною пам'яттю |  S і q - граматики |

© um.co.ua - учбові матеріали та реферати