Формальные порождающие грамматики

Для описания языков программирования и других искусственных языков с успехом используется теория формальных грамматик, разработанная А. Н. Хомским. Вкратце ее суть заключается в следующем. Рассматривается конечный алфавит Л (множество символов) и язык над этим алфавитом. Здесь язык — это просто множество последовательностей символов алфавита (цепочек). Другими словами, среди всех возможных цепочек (которых заведомо бесконечно много) нужно иметь возможность выделить те и только те, которые являются цепочками языка (еще говорят «входят в язык», «принадлежат языку», «являются выражениями языка»).

Для описания (бесконечного) множества цепочек Хомский предложил использовать формальную порождающую грамматику — конечное множество правил вида, а -" р, где аир конечные цепочки, составленные из символов алфавита А (которые называются терминальными символами) и из символов некоторого дополнительного алфавита Л^г(эти символы принято называть нетерминальными). В левую часть правила (т.е. в цепочку а) обязательно должен входить хотя бы один нетерминальный символ. Среди всех нетерминальных символов выделяется один, который называется начальным символом (или аксиомой) грамматики.

Далее все очень просто. Взяв за основу аксиому грамматики, разрешается строить новые цепочки, заменяя в уже построенной цепочке любое вхождение левой части любого правила на правую часть этого правила^[1]. И так до тех пор, пока в цепочке не останутся одни терминальные символы. Всякая цепочка терминальных символов, которую можно построить таким процессом, по определению входит в язык, а если цепочку нельзя гак построить, то она не входит в язык.

Разумеется, все это так просто, пока не поставлены разные каверзные вопросы. Всякий ли язык может быть определен таким способом? Если даны грамматика и конкретная терминальная цепочка, то как узнать, принадлежит она языку или нет? Однозначен ли процесс порождения цепочки? Зависят ли ответы на предыдущие вопросы от вида (формы) правил?

Но если основная идея ясна, то можно оставить эти (весьма трудные) вопросы математикам и принять тот факт, что синтаксис подавляющего большинства языков программирования легко описывается подклассом формальных грамматик, которые называются контекстно-свободными (левая часть всех правил состоит из одного нетерминального символа). Для этого подкласса грамматик все вопросы, связанные с распознаванием принадлежности цепочки языку (это называется синтаксическим анализом, или разбором), надежно решены.

Аврам Ноам Хомский (Avram Noam Chomsky), родился в 1928 г., — американский лингвист, политический публицист и теоретик.

Автор классификации формальных языков, называемой иерархией Хомского.

Его работы о порождающих грамматиках внесли значительный вклад в развитие наук о языке, содействовали упадку бихевиоризма и развитию когнитивных наук.

Помимо лингвистических работ, Хомский широко известен своими радикально-левыми политическими взглядами, а также критикой внешней политики правительств США.

«Если преподаватель на протяжении пяти лет рассказы вает студентам одно и то же, значит, либо наука, которой он занимается, умерла, либо он ничего о ней не знает».

Выводы:

• • системы продукций — это исторически первый и до сих пор часто применяемый способ представления знаний;
• • системы продукций эффективно реализуемы программно и являются основой многих практических программных систем;
• • использование систем продукций может принести пользу только при полном понимании всех сопутствующих им ограничений и особенностей.

• [1] Полезно сопоставить это с нормальными алгорифмами Маркова.