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

Головною проблемою побудови алгоритмів аналізу в обох випадках є необхідність вибору продукції, застосованої для розгортання чи згортання. Чому, наприклад, у першому виведенні на першому кроці вибирається продукція E E+T, а не E T, а на другому, навпаки, E T ? Чому за оберненого виведення в слові E+T*F, в якому є дві праві частини продукцій E+T і T*F, саме ланцюжок T*F згортається в T, а не E+T в E ? Тут необхідний вибір зроблено тому, що структура термінального слова була відома заздалегідь. Але, взагалі, структура слова до початку його аналізу невідома, і виникає необхідність перебирати продукції для застосування потрібної.

Теоретично, можна розробити алгоритм аналізу на основі перебирання продукцій, але він буде практично неприйнятним внаслідок його оцінки складності. Один із шляхів до ефективних алгоритмів аналізу полягає в обмеженні структури продукцій і позбавленні від перебирання за рахунок звуження множини КВ-граматик. Далі розглядаються саме такі обмежені граматики та побудова алгоритму аналізу для них, складність якого лінійна.

3. LA(1)-граматики

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

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

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

first ( A ) = first ( wi ).

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

follow ( A ) = { a | S  * uAv, a  first ( v ) }.

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

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

first ( wi )  first ( wj ) =  при i, j = 1, … , k, i  j;

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

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 маємо