Хомский, человек, который ввел понятие генеративной грамматики, определил ее как множество G={N,T,P,S} из четырех элементов: N — нетерминальные символы? T — терминальные, P — правила и S — начальный символ грамматики. Терминальные смиволы это слова языка, в си++ это, различные лексемы, типа идентификатор, слово, которое начинается с буквы и потом может идти ряд цифр или букв, ри этом символ подчеркивания считается буквой, и т.д. В стандарте все эти лексемы определены. нетерминальные мимволы явно в языке не существуют, они как бы нызывают некие совокупности слов, т.е. терминалов языка. Например, описание функции можно назвать нетерминалом Function_Description. Правила, понятно, позволяют задать соответствие между нетерминальными символами и терминалами языка, например: Function_Description --> Type ID '(' list_of_parameters ')' ';' Здесб все — терминалы языка, за исключением нетерминала list_of_parameters. Хомский также ввел различные типы грамматик, нас здесь как раз интересуют грамматики типа 1 и 2, т.е. контекстно-зависимые (КЗ) и контекстно-независимые или контекстно-свободные (КС) типы. КН задается правилами вида: alpha A beta --> alpha B beta, где alpha и beta строки, состоящие как из терминалов, так и из нетерминалов языка. Они могут быть пустыми. Смысл здесь состоит в том, что нетерминал A может значить либо, например B, как в нашем правиле, либо какой-нибудь C, как в правиле alpha1 A beta1 --> alpha1 С beta1, в зависимости от строк alpha и beta, т.е. от контекста, в котором этот нетерминал встретился. А в КС-грамматиках такого нет, нетерминал всегда значит одно и то же, поэтому там все правила имеют вид A --> alpha B beta, что можно обозначить просто как A --> alpha, т.к. alpha это строка нетерминальных и терминальных символов.
Си++, как и большинство других языков программирования, контекстно зависим. Любая операция, где присутствует тип, является контестно зависимой. Действительно, если мы определяем функцию как void foo( int, char ) и потом вызываем foo( a, b ), то этот вызов будет законным только тогда, когда типы фактических параметров подходят под типы формальных. А это как раз контекстная зависимость. Просто, обычно все КЗ вещи убирают из грамматики языка, не давая работать с ними синтаксическому анализатору. КЗ конструкции языка тогда называют семантикой языка и разрешают эти проблемы вручную. Если язык достаточно сложный, как си++, то это сделать сложно, приходится извращаться изменяя грамматику, подгоняя ее под какй-либо алгоритм синтаксического анализа и, в результате, исходная грамматика, та, что в стандарте, изменяется очень сильно. Для конкретной конструкции x(); можно задать правила:
Fun_call --> ID '(' list_of_params ')' ';'
Constructor --> ID '(' list_of_params ')' ';'
Эта конструкция неоднозначна, надо как-то решить при вызове x(); что это есть. Можно идти от типа x, и разрешить все на семантическом уровне, задавая правила:
Type ID '(' list_of_params ')' ';' --> Type Fun_name '(' list_of_params ')' ';'
И для Type_name то же самое, только целую кучу правил, как для встроенных типов, так и для определяемых самыми различными способами, программистом. Вот это правило как раз и есть КЗ.
Вопрос для языка также состояит в том, что, так как для конкретного языка, существует куча разных грамматик, которые этот язык определяют, то есть ли КС грамматика, которая этот язык определяет? Интуитивно должно быть понятно, что в случае описываемой выше конструкции, такая КС-грамматика не найдется. В си мы могли бы увести вызов функции на семантический уровень, а в си++, ввиду неоднозначности конструкции x(); приходится вытаскивать эту конструкцию обратно на синтаксический уровень. Доказать это формально не просто, но можно, существуют специальные методы для этого.
Вообще, интересно, на кокой стадии усложнения язык становится настолько сложным, что его нельзя описать КС-грамматикой? Известно, что естественные языки типа русского и английского — КЗ языки. Си++ получается тоже КЗ язык. Что надо убрать из языка, чтобы он стал КС языком?
