Головна

LL (1) - граматики.

  1.  Різновиди нормативної граматики.

(Left - leftmost)

LL (1) - граматики відносяться до тих, що сходять граматика (зверху - вниз).

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

У LL (1) - граматиках розгортаються ліві нетермінальні символи сентенціальной форми і аналізується черговий найлівіший термінальний вхідного рядка. Можливий аналіз k самих лівих символів вхідного рядка, Тоді граматику називають LL (k) - граматикою. Але, оскільки граматики LL (k) і LL (1) еквівалентні в плані породжуваних мов, зупинимося на розгляді тільки останньої.

F (a) - множина термінальних символів, що стоять першими (First)) в ланцюжках, що виводяться з рядка a.

N (А) - множина термінальних символів, таких (Next) в ланцюжках за даними нетермінальним символом А.

Безліч вибору для кожного правила формується з урахуванням безлічі перших і безлічі наступних символів.

LL (1) - це така граматика, у якій для правил з однаковими лівими частинами безлічі вибору не перетинаються.

1. S ® AbB E (1) = F (AbB) = {a, b, c, e}

2. S ® d E (2) = {d}

3. A ® CAb E (3) = F (CAb) = {a, e}

4. A ® B E (4) = F (B) E N (A) = {c} E {b} = {c, b}

5. B ® cSd E (5) = F (cSd) = {c}

6. B ® e E (6) = F (e) E N (B) = {?} E {b, d, +}

7. C ® a E (7) = {a}

8. C ® ed E (8) = {e}

S A B C b D N
a  1 AbB  3 CAB> <        
b  1 AbB  4 B> <  > <        
c  1 AbB  4 B> <  5 Sd        
d      > <        
e  1 AbB  3 CAB    8 d      
+      > <        

 




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

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