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

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

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

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

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

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

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

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", тобто "вираз", "доданок", "множник". Вони позначають вирази зі знаками операцій +, *, доданки та множники в них відповідно.

Виведення слова a+a*a в G0 з розгортанням нетерміналів, перших ліворуч у проміжних ланцюжках, має вигляд:

E  E+T  T+T  F+T  a+T  a+T*F  a+F*F  a+a*F 

 a+a*a

Тут нетермінали, що розгортаються, підкреслені. Аналіз ланцюжка, що відтворює такі розгортання від початкового символу до термінального слова, називається низхідним, або аналізом "від верху до низу".

Тепер розглянемо виведення слова a+a*a з розгортанням нетерміналів, останніх праворуч:

E  E+T E+T*F  E+T*a  E+F*a  E+a*a  T+a*a  F+a*a

 a+a*a

Проміжні слова в цьому виведенні, записані у зворотному порядку, дістаються згортаннями правих частин продукцій, починаючи з термінального слова. Такі згортання від ланцюжка терміналів до початкового нетермінала граматики відтворюються в процесі висхідного аналізу, або аналізу "від низу до верху".