Елементи синтаксичного аналізу, Детальна інформація

\x00B4

\x00BA

1/4

A

Ae

E

I

\x00D0

Oe

e

i

i

o

oe

o

u

C означимо множини

first ( wi ) = { a | a \xF0CE X* і wi \xF0DE az для деякого слова z },

first ( wi ).

Граматика може мати так звані \xF065 -продукції вигляду A\xF0AE \xF065 . У такому разі, якщо Av\xF0DE *b1…bn, то b1 може починати слово, вивідне як з A, так і з v. Визначити за символом b1 , з чого саме виводиться слово, можна за умови, що first(A) не містить перших символів слів, вивідних із v. Множину цих перших символів ланцюжків, що виводяться з усіх можливих правих контекстів нетермінала A, позначимо follow (A):

follow ( A ) = { a | S \xF0DE * uAv, a \xF0CE first ( v ) }.

Граматика називається LA(1)-граматикою, якщо:

(1) для кожного нетермінала A з продукціями A\xF0AE w1|…|wk , де wi\xF0B9 \xF065 для всіх i=1,…,k, справджується умова

first ( wi ) \xF0C7 first ( wj ) = \xF0C6 при i, j = 1, … , k, i \xF0B9 j;

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

first ( A ) \xF0C7 follow ( A ) = \xF0C6 .

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

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

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

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