Реферат: Контекстно-вільні та LA-граматики

(1) для кожного нетермінала A з продукціями A ® w ₁ |…|w_k , де w_{i ¹ e} для всіх i =1,…,k , справджується умова

first ( w_i ) Ç first ( w_j ) = Æ при i , j = 1, … , k , i ¹ j ;

(2) для кожного нетермінала A такого, що в P є продукція A ® e , справджується

first ( A ) Ç follow ( A ) = Æ .

Умови (1), (2) називаються LA(1)-умовами .

Не кожна КВ-мова породжується LA(1)-граматикою, але синтаксис практично всіх конструкцій сучасних мов програмування можна задати LA(1)-граматиками. Досить часто мова "природно" задається не LA(1)-граматикою, але таку граматику для неї можна побудувати.

Приклад 9. За продукціями E ® E +T |T , T ® T *F |F , F ® (E )|a граматики G ₀ маємо

first ( (E ) ) = { ( }, first ( a ) = { a }, звідки

first ( F ) = { a , ( }; first ( T *F ) = first ( F ), звідки

first ( T *F ) Ç first ( F ) ¹ Æ ,

тобто G ₀ не є LA(1)-граматикою. Проте мова виразів L(G ₀ ) задається еквівалентною LA(1)-граматикою. Побудуємо її.

Із T виводяться слова F , F *F , F *F *F , … . Додамо нетермінал B та правила B ® e |*FB , T ® FB замість правил T ® F |T *F . Маємо

first ( T ) = first ( F ) = { a , ( }, first ( *FB ) = { * },

first ( B ) = { * }, follow ( B ) = follow ( T ) =

= follow ( E ) = { +, ) }.

Отже, продукції T ® FB і B ® e |*FB не порушують LA(1)-умови. Аналогічно, додавши нетермінал A , а замість правил E ® E +T |T правила E ® TA , A ® e |+EA , одержимо LA(1)-граматику.-

4. Ліворекурсивні та розширені продукції

Правило вигляду A ® Av називається ліворекурсивним . Якщо в граматиці є продукції A ® Av |u , де u ¹ e , то first(Av )=first(u )¹ Æ , і граматика не є LA(1)-граматикою. Але за допомогою цих правил виводяться слова з множини {u , uv , uvv , …}, яка задається регулярним виразом uv * або u {v }. Замість продукцій A ® Av |u запишемо A ® u {v }. Продукції з регулярними виразами в правій частині називаються розширеними , як і граматики з такими продукціями. Неважко переконатися, що розширені правила не збагачують множину мов, породжених КВ-граматиками.

Приклад 10. Розширена граматика G ₀₁ із правилами E ® T {+T }, T ® F {*F }, F ® (E )|a еквівалентна граматиці G ₀ . Фактично РБНФ є іншим записом розширених продукцій, а сукупності РБНФ – іншою формою розширених КВ-граматик.-