Головна

S і q - граматики

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

s-граматикою будемо називати таку контекстно-вільну граматику, праві частини правил, якою починаються з термінальних символів, причому для одного і того ж лівого символу праві частини починаються з різних символів.

Чи не s-граматика:

S ® aT - починається з нетермінального. T ® bT.

S ® TbS

T ® bT

Aналогічная s-граматика (розпізнає теж)

:

S ® abR

S ® bRbS

R ® a

R ® bR

q-граматикавідрізняється від s-граматики наявністю анулюється правила (в правій частині є порожній символ) a ? e.

1. S ® aAS

2. S ® b

3. A ® cAS

4. A ® e

Через анулюють правил для q-граматики вводиться поняття наступного символу. N (A) - множина термінальних наступних (Next) за А символів.

В даному випадку за А можуть слідувати a або b - {a, b}.

S ? aAS ? aAaAS ? aAaAb

E (1) = {a} - безліч вибору для першого правила.

E (2) = {b}

E (3) = {c}

E (4) = N (A) = {a, b}

 Дана граматика може бути розпізнана МП-автоматом, в який додана операція заміни a. В цьому випадку автомат починає працювати на непустому стеком.

  S A N
a  1 AS ®  4> < ?
b  2 ®  4> < ?
c ?  3 AS ® ?
+ ? ? +



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

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