Як бачимо, продукції граматики дуже схожі на БНФ як за формою, так і за змістом – лише замість знака "::=" вживається "? ". Проте в лівій частині їх продукцій може бути не поодинокий нетермінал, а цілий ланцюжок, у якому обов'язково є нетермінал. За рахунок такого узагальнення граматики виявляються більш потужним засобом задання мов, ніж системи БНФ, тобто існують мови, які задаються граматиками, але не задаються БНФ. Тепер опишемо спосіб, у який граматика G = (X, N, P, S) задає мову.

1. На множині слів об'єднаного алфавіту (X? N)* означається відношення безпосередньої виводимості, позначене знаком ? G (або ? , коли відомо, якою саме є G):

v ? G w, якщо v = x1 u x2 , w = x1 y x2 , u ? y ? P.

При цьому кажуть, що w безпосередньо виводиться з v застосуванням продукції u? y. Наприклад, у граматиці G1 із прикладу 21.3 BC? aC застосуванням продукції B? a, aC? a1застосуванням C? 1.

2. На множині (X? N)* означається відношення виводимості, позначене ? *G (або ? *, коли відомо, якою саме є G): v? *w, якщо v=w або існує послідовність w1, w2, … , wn слів, де n? 1, така, що v? w1, w1? w2, … , wn-1? wn, wn=w. Так, у граматиці G1 BC? *a1, оскільки BC? aC, aC? a1. Послідовність v? w1? w2? …? wn називається виведенням wn із v, а n – довжиною виведення. Інколи довжину записують замість '*' таким чином: v? nw, наприклад, BC ? 2a1.

3. Якщо S? G*w, то послідовність S? …? w називається виведенням слова w у граматиці G, а слово w – вивідним. Так, слова A, BC, aC, a1 вивідні в граматиці G1.

4. Вивідні слова в алфавіті X називаються породжуваними, а множина їх усіх – мовою, що задається (породжується) граматикою G: L(G) = {w | w? X* та S ? * w }.

Приклади

4. Граматика G1 із прикладу 21.3 задає мову { a, a1, a2 }.

5. Граматика

G2 = ( { a, …, z, 0, …, 9 }, { I, L, D },

{ I ? L | IL | ID, L ? a | … | z, D ? 0 | ... | 9 },

I )

породжує множину ідентифікаторів.

6. Граматика G3 = ( { (, ) }, { S }, { S ? ? | ( S ) }, S ) задає множину "вкладених дужок" { (n)n | n ? 0 }.?

21.7. Граматика

G4 = ( { a, b, c }, { S, A, B, C},

{ S ? aSBC | abC, CB ? BC, bB ? bb, bC ? bc, cC ? cc },

S )

визначає мову { anbncn | n ? 1 }.?

Граматики називаються еквівалентними, якщо задають ту саму мову. Наприклад, граматика

( { a, 1, 2 }, { A }, { A ? a [ 1 | 2 ] }, A )

еквівалентна граматиці G1, граматика

( {a, …, z, 0, …, 9}, {I, C}, {I ? (a|…|z)C, C ? ? |C(a |…|z|0|…|9)}, I )–

граматиці G2.

Є два види граматик з продукціями обмеженого вигляду, якими задаються регулярні мови, – це праволінійні та ліволінійні граматики. Праволінійною (ліволінійною) називається граматика, всі продукції якої мають вигляд A? w або A? wB (відповідно, A? w або A? Bw), де A, B – нетермінали, w? X*. Усі можливі праволінійні та ліволінійні граматики з термінальним алфавітом X породжують в точності клас регулярних мов над X. Це доводиться, наприклад, в [АУ].

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

2.1. Контекстно-вільні граматики

Контекстно-вільною, або КВ-граматикою, називається граматика, в якій ліві частини всіх продукцій є нетерміналами. Зміст терміну "контекстно-вільна" полягає в тім, що застосування продукції A? w до ланцюжка uAv не залежить, тобто є вільним від сусідніх з A символів, які утворюють контекст uv.

Зазначимо, що БНФ вигляду A::=w цілком аналогічна продукції A? w. Отже, сукупності БНФ є просто іншою формою КВ-граматик.

Контекстно-вільною мовою (КВ-мовою) називається мова, що може бути задана КВ-граматикою.

Прикладами КВ-граматик та КВ-мов є граматики з прикладів 21.3, 21.5, 21.6 у попередньому параграфі й задані ними мови. Граматика з прикладу 21.7 не є КВ-граматикою. До речі, мова, задана нею, не є КВ-мовою, оскільки не існує КВ-граматики, яка б її задавала.

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

2.2. Дві ідеї аналізу

Заміна нетермінала з лівої частини продукції на її праву називається розгортанням нетермінала, а зворотна заміна – згортанням правої частини. Розглянемо дві стратегії аналізу, основані на згортаннях та на розгортаннях, за допомогою наступного прикладу.

Приклад 8. Нехай

G0 = ( { a, +, *, (, ) }, { E, T, F },

{ E ? E + T | T, T ? T * F | F, F ? (E ) | a },

E )–

граматика. Нетермінали E, T, F відповідно є скороченнями слів "Expression", "Term", "Factor", тобто "вираз", "доданок",