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

Контекстно-вільні та LA(1)-граматики
Тип документу: Реферат
Сторінок: 3
Предмет: Комп`ютерні науки
Автор: Олексій
Розмір: 11.2
Скачувань: 985




\x02C6

ue



(

*

4

6

B

AE

\x00D0

ue

9ки

LA(1)-граматики дозволяють вибирати необхідну для розгортання продукцію при низхідному аналізі за першим символом ще не розпізнаної частини слова. "LA(1)" позначає речення "Look Ahead 1 symbol", тобто "подивитися спереду на 1 символ".

Нехай G=(X, N, P, S) – КВ-граматика, і за словом w треба визначити, чи належить воно до L(G). Нехай S\xF0AE v1|…|vp – усі продукції з нетерміналом S ліворуч. Потрібну для розгортання S продукцію S\xF0AE vi можна визначити безпосередньо за першим символом слова w, якщо множини перших символів ланцюжків, вивідних із v1, v2, … , vp, не перетинаються. Взагалі, нехай am…an – нерозпізнана частина слова, початок якої має виводитися з нетермінала A, і A\xF0AE w1|…|wk – усі продукції з A ліворуч. Тоді потрібна для розгортання A продукція A\xF0AE wi визначається за першим символом am, якщо множини перших символів ланцюжків, вивідних з w1, w2, … , wk, не перетинаються.

Отже, для кожного нетермінала A та кожної правої частини wi продукцій A \xF0AE w1 | w2 | … | wk означимо множини

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 }, звідки

The online video editor trusted by teams to make professional video in minutes