Контекстно-вільні та LA(1)-граматики, Детальна інформація

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

first ( T*F ) \xF0C7 first ( F ) \xF0B9 \xF0C6 ,

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

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

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

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

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

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

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

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

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