ЕЛЕМЕНТИ СИНТАКСИЧНОГО АНАЛІЗУ

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 граматики G0 маємо

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

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

first ( T*F )  first ( F )   ,

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

Із T виводяться слова F, F*F, F*F*F, … . Додамо нетермінал B та правила B  |*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  |*FB не порушують LA(1)-умови. Аналогічно, додавши нетермінал A, а замість правил E E+T|T правила E TA, A  |+EA, одержимо LA(1)-граматику.

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

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

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

3.1. Правила побудови

Нехай G=(X, N, P, S) – LA(1)-граматика без  -правил, можливо, розширена. Опишемо побудову програми синтаксичного аналізу слів мови L(G). Програма буде містити процедури, іменами яких є відповідні їм нетермінали граматики.

Процедура, відповідна нетерміналу A, описує аналіз ланцюжків, вивідних із A. Цими ланцюжками є слова мови або їхні підслова. Алгоритм процедури такий. Нехай A w1|…|wk – усі продукції з нетерміналом A ліворуч, a1a2…an – ланцюжок, початок якого треба виводити з A. Спочатку визначається, якій із множин first(w1), … , first(wk) належить символ a1. Нехай нею буде first(w1), і в найпростішому випадку w1=Y1Y2…Ym, де Yi – термінал або нетермінал. Початок ланцюжка має виводитися з Y1.

Якщо Y1 – термінал, то перевіряється рівність a1=Y1.