Хомский, человек, который ввел понятие генеративной грамматики, определил ее как множество 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, и разрешить все на семантическом уровне, задавая правила:

Fun_call --> Fun_name '(' list_of_params ')' ';'
Constructor --> Type_name '(' list_of_params ')' ';'

Type ID '(' list_of_params ')' ';' --> Type Fun_name '(' list_of_params ')' ';'

И для Type_name то же самое, только целую кучу правил, как для встроенных типов, так и для определяемых самыми различными способами, программистом. Вот это правило как раз и есть КЗ.


Вопрос для языка также состояит в том, что, так как для конкретного языка, существует куча разных грамматик, которые этот язык определяют, то есть ли КС грамматика, которая этот язык определяет? Интуитивно должно быть понятно, что в случае описываемой выше конструкции, такая КС-грамматика не найдется. В си мы могли бы увести вызов функции на семантический уровень, а в си++, ввиду неоднозначности конструкции x(); приходится вытаскивать эту конструкцию обратно на синтаксический уровень. Доказать это формально не просто, но можно, существуют специальные методы для этого.

Вообще, интересно, на кокой стадии усложнения язык становится настолько сложным, что его нельзя описать КС-грамматикой? Известно, что естественные языки типа русского и английского — КЗ языки. Си++ получается тоже КЗ язык. Что надо убрать из языка, чтобы он стал КС языком?

С уважением,
Владимир.

АТ>Ну это уже зависит от того, что же понимать под термином "грамматика" языка С++. Если то и только то, что приводится в соответствующем разделе стандарта ("грамматика" в узком толковании термина) — то эта грамматика очевидным образом КС.

АТ>Затем можно досыпать к этому еще набор очевидно чисто грамматических правил, которые в стандарте языка изложены "на словах", и получить "грамматику" в широком толковании термина. Например, правило, запрещающее пустые декларации. В принципе, я думаю, такие правила можно было внести в грамматику (в узком толковании) и при этом сохранить ее как КС, но это черезмерно бы ее усложнило. Поэтому эти дополнительные правила было решено изложить "на словах" (что, как известно, привело к тому, что многие компиляторы забывают эти правила проверять).

АТ>Ну и наконец ко всему этому можно еще обавить еще и такие правила, как требования объявления перед использованием и контроля типов, и получить "грамматику" в супершироком толковании термина (ни о каком КС при этом, разумеется, уже речи быть не может), но мне это кажется уже перебором.

Привет Андрей,

Попытаюсь пояснить свою позицию, так сказать, с самого начала.

Начнем с того, что такое язык в теории формальных языков. Имея дело с языком, мы прежде всего задаем алфавит, некотрое КОНЕЧНОЕ множество символов — слов. Под языком понимается множество строк (предложений, цепочек), составленных из символов алфавита. Очевидно, что предложений языка, в общем случае, может быть бесконечно (счетно) много. Под предложением языка мы понимаем не любую цепочку, составленную из символов алфавита, а только некоторые из таких цепочек. Второй вопрос, который сразу же возникает, это: каким образом можно задать язык? Есть два принципиально различных способа задания языка: создать устройство, которое генерирует (выписывает) цепочки символов языка — предложения языка, т.е. устройство генерации, и создать устройство, на вход которого подаются всевозможные строки, составленные из символов алфавита, и это устройство говорит о каждой поданной на вход строке, принадлежит она языку или нет, это называется устройством равспознавания. Заметим, что человек совмещает в себе оба типа устройств, так сказать, два в одном — сила природы.

Хомский предложил в качестве устройства распознавания использовать так называемую генеративную или порождающую грамматику. Таким образом, порождающая грамматика по Хомскому это устройство (!) для порождения правильных цепочек языка (предложений). Порождающая грамматика не является алгоритмом, так как в ней нет детерминированости, но предписанием. Что такое порождающая грамматика как устройство? Это четверка множеств G={N,T,P,S}, где N — множество нетерминальных символов грамматики, которые, вообще говоря, никакого отношения к языку не имеют, T — множество терминальных символов грамматики, которое совпадает с алфавитом языка, который данной грамматикой порождается, P — множество так называемых правил вывода вида (N U T)* N+ (N U T)* --> (N U T)*. Т.е. это правила переписывания, где строка в левой части заменяется на строку в правой части правила, при этом слева должен присутствовать хотя бы один нетерминал. Кстати, это ограничение не является фундаментальным, вполне возможно определить правила так, чтобы слева только терминалы языка находились, и такая грамматика будет порождать тот же язык, что и исходная, так определены правила, например, в книжке Гладкого по формальным языкам. S — это множество из одного символа S, принадлежащего N. каким же образом происходит порождение предложений языка L(G), т.е. языка, определяемого грамматикой G? Очень просто, начиная со стартового символа грамматики S, затем меняем его в соответствии с правилами языка на строку в правой части, затем меняем все нетерминалы в получившейся строке и т.д... Конечно, в этом процессе можно зациклиться, кроме того, если у нас, для данной строки в левой части правила, есть несколько альтернатив, то надо выбрать какую альтернативу применить. Вот поэтому мы и говорим о том, что порождающая грамматика Хомского не является алгоритмом, а лишь предписанием. этот способ порождения предложений языка называется выводом.

Итак, имея порождающую грамматику G={N,T,P,S}, мы, таким образом, задаем некоторый язык L(G). Хомский выделил несколько типов грамматик, причем не произвольно, с бухты-барахты, а произвел абстракцию от существующих в языке человека сущностей. Потом оказалось, что для каждого типа порождающей грамматики можно задать соответствующее по вычислительной мощности устройство рапознавания, т.е. использовать второй способ задания языка. Хомский вводил все это для описания человеческих языков и эта абстракция, как потом выяснилось, слишком формальна, чтобы охватить все стороны человеческого языка. Поэтому Хомский после ввел ограничения-дополнения к этому определению, потом их наши лингвисты опровергли, Хомский ввел еще большие ограничения и т.д. В общем, наука в развитии, от теории к теории. Кстати, теория Хомского в СССР не прижилась как противоречащая принципам диалектического материализма, была целая компания, охота на ведьм, на которой многие себе капитал нажили. Но это все не имеет отношения к программированию. В программирование эта теория пришла в начале 60-х, когд заметили, что способ задания языка, известный как форма Бакуса-Наура, представляет собой ни что иное, как порождающую грамматику Хомского. Что было важно для этой грамматики, это тот факт, что по грамматике Хомского можно построить алгоритм гененерации\распознавания, детерминированно моделируя недетерминированные правила порождения. Были также математически выведены методы разбора предложений языка, основанные только на входной грамматике и, что самое главное, их корректность была математически доказана. Все это вместе превратило посторение компилятора из шаманского камлания в относительно простую, можно сказать, рутинную опреацию. Из теории же формальных языков пришли в программирование такие понятия как контекстно-свободный (КС) язык и контекстно-зависимый (КЗ) язык. Заметим, что до сих пор мы не упоминали такого понятия как сеантика языка потому, что в теории формальных языков его просто нет. Итак, язык называется КС, если существует хотя-бы одна КС-грамматика, порождающая данный язык. Порождающая в сымысле, котрый мы определили выше. Аналогично, язык называется КЗ, если существует хотя бы одна КЗ-грамматика, порождающая данный язык и не существует КС-грамматики, порождающей этот язык. Прцедурные языки программирования не являются КС, из-за требования предварительного объявления имен до их использования. Мощности КС-грамматики не хватает, чтобы это свойство определить. Это доказано математически. Но существует также много хороших методов, созданных для разбора КС языков, как их использовать? Очень просто, для данного языка выделить его подмножество, которое можно описать с помощью КС-грамматики, т.е. КС подможество, а точнее говоря, надмножесто, потому что КС язык, получаемый в результате, чаще всего содержит исходный. Остальную часть языка реализовать вручную, без помощи такого понятия как порождающая грамматика. Все это, очевидно, не делает сам язык КС, так как грамматики, которая его порождает, мы так и не определили. Таким образом, понятие "семантика языка" пришло из другой теории, которая по отношению к теории формальных языков является метатеорией. Понятие же КС и КЗ языка есть понятие теории формальных языков и, следовательно, пытаясь применить оперировать этими понятиями, мы должны оставаться в рамках искомой теории.

Ну вот, кажется, все изложил,
Владимир.

Здравствуйте, mefrill, Вы писали:

M>Си++, как и большинство других языков программирования, контекстно зависим. Любая операция, где присутствует тип, является контестно зависимой.

M>...

M>Вопрос для языка также состояит в том, что, так как для конкретного языка, существует куча разных грамматик, которые этот язык определяют, то есть ли КС грамматика, которая этот язык определяет? Интуитивно должно быть понятно, что в случае описываемой выше конструкции, такая КС-грамматика не найдется. В си мы могли бы увести вызов функции на семантический уровень, а в си++, ввиду неоднозначности конструкции x(); приходится вытаскивать эту конструкцию обратно на синтаксический уровень. Доказать это формально не просто, но можно, существуют специальные методы для этого.

Все это хорошо, но тем не менне не имеет никакого отношения к исходному вопросу. Вопрос был о том, является ли грамматика языка С++ контекстно зависимой. Ответ однозначен — не является. Грамматика языка С++ является контекстно свободной по определению, т.к. в левой части каждого правила этой грамматики стоит ровно один нетерминал. Все.

Все остальные рассуждения и примеры, которые тут обильно привдятся, на самом деле не имеют никакого отношения к грамматике языка С++.

А>А ничего и не надо убирать! Грамматика С++ — контекстно-свободная грамматика, и потому, этот язык сам и является контекстно-свободным.

А>

А>variable-declaration ::= type identifier; |
А>                                type identifier(argument-list);
А>function-call        ::= identifier(argument-list);
А>

А>Курсивом выделены нетерминалы, темным — терминалы. Из этой, частичной граматики, неужели нельзя понять где обьявляется обьект а где вызывается функция? Для простоты, argument-list выводит как минимум один аргумент.

Нет, конечно нельзя понять. Где здесь указано, что x является типом или именем функции или переменной? В самой грамматике этого нет. Я же постарался объяснить почему нет. А нет потому, что типизированные конструкции, вместе с их объявлениями и определениями, КЗ по своей природе. Именно поэтому эти конструкции синтаксически не описаны, а перенесены на "семантический" уровень. Если попытаться описать си++ грамматикой (не его КС подмножество, или даже LARL(1) подмножество, как это делается в Bison например), то придется как-то отличать друг от друга имена пременных, функций, их типы и т.д. А сейчас у нас есть один лексический ID и таблица имен (точнее их несколько), которая эту контекстную зависимость и обрабатывает. Говорить же о грамматике языка си++ что она КС на основании приведенной выше иерархии, это все равно, что говорить, что грамматика си++ регулярная, на основании следующей "грамматики":

Программа --> Текст_Программы точка_с_запятой

Где и Текст_Программы и точка_с_запятой явяляются терминальными символами языка, а весь разбор происходит на этапе лексичекого (читай семантического!) анализа.

На остальные аргументы я не считаю нужным отвечать просто потому, что это не аргументы. Мы сами с Вами говорим на разных языках . Относительно сложности реализации компилятора си++ через КС грамматику я могу отослать Вас к двум диссертациям Зуева и Кротова, посвященным как раз проблемам реализации языка. Но Вы, к сожалению, врядли их прочитаете. И могу Ва уверить также, что под неоднозначностью я понимал именно то, что имеется ввиду в теории формальных языков.

Ну и написано, однако! Я так и не осилил.
M>Си++, как и большинство других языков программирования, контекстно зависим. Любая операция, где присутствует тип, является контестно зависимой. Действительно, если мы определяем функцию как void foo( int, char ) и потом вызываем foo( a, b ), то этот вызов будет законным только тогда, когда типы фактических параметров подходят под типы формальных. А это как раз контекстная зависимость.
Не путайте контекстную зависимость в теории формальных языков, с требованием, чтобы типы данных аргументов и параметров совпадали. Это разные вещи. Грамматика всего лишь пораждает предложения языка и за их смысловую нагрузку не отвечает! Согласно грамматике, мы можем передать в функцию ноль, один, два, ..., тысячу аргументов, и синтаксический анализатор все равно найдет нужную продукцию, согласно которой было выведено это предложение. Другое дело семантические рутины, которые как раз и заявят о несоответствии типов, количиств аргументов и т.д.

M>Просто, обычно все КЗ вещи убирают из грамматики языка, не давая работать с ними синтаксическому анализатору. КЗ конструкции языка тогда называют семантикой языка и разрешают эти проблемы вручную. Если язык достаточно сложный, как си++, то это сделать сложно, приходится извращаться изменяя грамматику, подгоняя ее под какй-либо алгоритм синтаксического анализа и, в результате, исходная грамматика, та, что в стандарте, изменяется очень сильно.
Это что ж там меняется?

M>Для конкретной конструкции x(); можно задать правила:
M>Fun_call --> ID '(' list_of_params ')' ';'
M>Constructor --> ID '(' list_of_params ')' ';'

M>Эта конструкция неоднозначна, надо как-то решить при вызове x(); что это есть. Можно идти от типа x, и разрешить все на семантическом уровне, задавая правила:

M>Fun_call --> Fun_name '(' list_of_params ')' ';'
M>Constructor --> Type_name '(' list_of_params ')' ';'

M>Type ID '(' list_of_params ')' ';' --> Type Fun_name '(' list_of_params ')' ';'

M>И для Type_name то же самое, только целую кучу правил, как для встроенных типов, так и для определяемых самыми различными способами, программистом. Вот это правило как раз и есть КЗ.
Это неверно и продукции какие-то кривые.

M>Вопрос для языка также состояит в том, что, так как для конкретного языка, существует куча разных грамматик, которые этот язык определяют, то есть ли КС грамматика, которая этот язык определяет? Интуитивно должно быть понятно, что в случае описываемой выше конструкции, такая КС-грамматика не найдется.
Опять рассуждения основаны на неправильных продукциях.

M>В си мы могли бы увести вызов функции на семантический уровень, а в си++, ввиду неоднозначности конструкции x(); приходится вытаскивать эту конструкцию обратно на синтаксический уровень. Доказать это формально не просто, но можно, существуют специальные методы для этого.
Да уж! Конструкция х() "неоднозначна" (кстати, поосторожнее с этим термином — в теории формальных языков это не то, что Вы имеете здесь в виду), поэтому мы "опять возвращаемся на синтаксический уровень и там ее разбираем!" Вы хоть думаете, что говорите?

M>Вообще, интересно, на кокой стадии усложнения язык становится настолько сложным, что его нельзя описать КС-грамматикой? Известно, что естественные языки типа русского и английского — КЗ языки. Си++ получается тоже КЗ язык. Что надо убрать из языка, чтобы он стал КС языком?
А ничего и не надо убирать! Грамматика С++ — контекстно-свободная грамматика, и потому, этот язык сам и является контекстно-свободным.

variable-declaration ::= type identifier; |
                                type identifier(argument-list);
function-call        ::= identifier(argument-list);

Курсивом выделены нетерминалы, темным — терминалы. Из этой, частичной граматики, неужели нельзя понять где обьявляется обьект а где вызывается функция? Для простоты, argument-list выводит как минимум один аргумент.

Здравствуйте, davenger, Вы писали:

D>Здравствуйте, Sergey J. A., Вы писали:

SJA>>Здравствуйте, _Winnie, Вы писали:

_W>>>Здравствуйте, Sergey J. A., Вы писали:

SJA>>>>Является ли грамматика С++ контекстнозависимой ? Если да, то можно простенький пример ?
SJA>>>>Мне кажется, что да, и пример — x(); неясно вызов это функции x или создание объекта типа x. Но я не уверен...

_W>>>Я думаю, что нет... вот сходу еще придумалось.
SJA>>"Нет" — то есть граматика С++ контекстно не зависима ?

SJA>>

_W>>>int main()
_W>>>{
_W>>>  X x(); <- декларация фунции или переменная x ?
_W>>>}
SJA>>

SJA>>Может я неправильно понимаю термин контекстнозависимый, но мне казалось, что данный пример как раз и говорит о контекстной зависимости:
SJA>>в зависимости от контекста строка может быть декларацией фунции или переменной.

D>Нет, это всегда декларация функции.

Эта строка является объявлением функции только тогда, когда она появляется в Global Scope, иначе это — вызов конструктора по умолчанию для объекта класса.

Здравствуйте, WolfHound, Вы писали:

WH>Здравствуйте, <Аноним>, Вы писали:

А>>А вообще, откройте Страуструпа и убедитесь, что непонравившаяся Вам функция выводится грамматикой С++!
WH>Ты сам то его читал?
Читал, и только в оригинале приведенное тобой издание!

Зачем влазить в разговор, не имея ни малейшего понятия о теории формальных языков?!! Владимир хоть знает теорию да просто заблуждается в одном месте... Ты же совсем не знаешь теории, судя по твоим ответам!

Это тебе не классы на С++ штамповать. Это именно те знания, которые делают программиста программистом!

WH>Итого: Это утверждение строится на отрициании того что множество всех well-formed программ на языке С++ является множеством всех предложений языка С++.
WH>Также вы отрицаете оговорки приведенные в стандарте, у Страуструпа и в красном драконе что их грамматики не являются точными грамматиками языка С++. И как следствие используя их нельзя породить все предложения языка С++ и только предложения языка С++.
Нет. Это утверждение строится на знании теории, которую Вы, к сожалению, не знаете. Я Вам уже указал глупые ошибки в Ваших утверждениях про стандарт и Страуструпа, я вывел при помощи грамматики ту функцию, что Вам не понравилась, показал, что при помощи грамматики можно обьявить переменную void var; . Вы же все проигнорировали!!!

Вы же с мефриллом основывали свои факты только на ГОЛОСЛОВНЫХ утверждениях. Вы НЕ показали мне правил в грамматике, которые требуют, чтобы переменная была обьявлена до использования. Вы НЕ показали мне правила, которое требует, чтобы main() была в программе! И до сих пор ВЫ утверждаете, что в стандарте по С++ приведена "какая-то другая грамматика, которое порождает надмножество предложений С++." Ну-ну...

Выше, Андрей Тарасевич кратко сказал почему грамматика С++ — КС грамматика. Лаптев, преподаватель в ВУЗе, подтвердил, что языки программирования описываются КС грамматиками. После этого Вы будете продолжать спорить?

WH>Думаю разговор на этом можно считать оконченым.
Да. Невозможно говорить с тем, кто не понимает основ. No further responses are necessary or required!

LVV>Я! Я прочитаю! Пошлите меня, пожалуйста по указанному адресу!!!

Зуевская диссертация лежит здесь: http://www.interstron.ru/publications.html. А насчет диссертации Александра Кротова надо наверное попростить его самого или кого-то из Интерстрона, чтобы выслали.

Очень хорошо все изложено, но в конце последнего параграфа у Вас заблуждение. "Прцедурные языки программирования не являются КС, из-за требования предварительного объявления имен до их использования." Кто Вам такое сказал? Каким тогда должен быть язык, чтобы выполнялось требование, чтобы имя было обьявлено только один раз (и не более)?

Как Вы сами уже заметили, граматика выводит предложения языка, и понятия семантики в теории формальных языков нет. Это верно. Подумайте сами. Граматика только выводит предложения языка согласно установленым правилам, но насколько осмыслены эти предложения она не отвечает. Этим занимается семантика. Граматика только отвечает за синтаксически-корректные предложения, которые могут и не иметь смысла (семантики).

Мы можем написать

void f()
{
     int i;
     int i;
     int i;
       .
       .
       .     // И так много обьявлений одной и той же переменной
     i = 0;
}

или так

void f()
{
     i = 0;  // Ни одного обьявления переменной
}

и оба фрагмента кода будут синтаксические корректны, но некорректны семантически! Синтаксис языка, как Вам уже говорили, очень хорошо поддается формализации, а вот семантика — нет. Все что мы можем тут сделать, это неформально выразиться: "каждое имя в программе должно быть обьявлено перед использованием."

M>Прцедурные языки программирования не являются КС, из-за требования предварительного объявления имен до их использования. Мощности КС-грамматики не хватает, чтобы это свойство определить. Это доказано математически. Но существует также много хороших методов, созданных для разбора КС языков, как их использовать? Очень просто, для данного языка выделить его подмножество, которое можно описать с помощью КС-грамматики, т.е. КС подможество, а точнее говоря, надмножесто, потому что КС язык, получаемый в результате, чаще всего содержит исходный. Остальную часть языка реализовать вручную, без помощи такого понятия как порождающая грамматика. Все это, очевидно, не делает сам язык КС, так как грамматики, которая его порождает, мы так и не определили. Таким образом, понятие "семантика языка" пришло из другой теории, которая по отношению к теории формальных языков является метатеорией. Понятие же КС и КЗ языка есть понятие теории формальных языков и, следовательно, пытаясь применить оперировать этими понятиями, мы должны оставаться в рамках искомой теории.
Компилятор это нечто большое чем простой распознователь цепочек языка, и это сбивает Вас с толку.

Вот относительно семантики языка я, кажется, в пылу спора немного палку перегнул. Под семантикой языка можно понимать две вещи: первая, это то, о чем мы говорили, в процессе описания языка некоторые его свойства, которые трудно или невозможно описать КС-грамматикой, описываются другими способами. Вторая — это понимание языковых структур людьми, т.е. как мы говорим, смысл языка, как мы его пониманием. Различие между этими двумя трактовками иногда очень небольшое и зависит только от точки зрения, с которорой мы данное свойство рассматриваем. Мы говорили о КЗ и КС языках и поэтому рассматривали языки в терминах теории Хомского, поэтому и трактовали семантику таким образом. Лингвисты часто спрашивают: изобретено ли колесо в лингвистике? Т.е. в природных способах передвижения колеса нет, его придумал человек и колесо неплохо выполняет свои функции, хотя не имеет никакого отношения к тому, как сам человек передвигается. В лингвистике роль колеса играет как раз порождающая грамматика Хомского. С помощью этой теории мы можем производить разбор (слушать и понимать речь собеседника) и генерировать предложения языка (разговаривать), но все таки это никакого отношения к тому, как сам человек это делает, не имеет. Не знаю относительно других, но мне, когда я впервые понял идею Хомского о гененрации языка посредством порождающей грамматики, стало как-то не по себе. Какое-то ощущение неживого, чуждого, копируещего поведение живого... Жутко как-то стало. Я задумался, почему я так себя ощущал и, кажется понял. Видимо, здесь дело в том, что человеческая мысль многомерна по своей сути, но, так как выражается посредством языка, как бы каждый раз ужимается в одномерную последовательность. Мы к этому явлению привыкли и воспринимаем его как должное, мы априори подразумевавем, что собеседник эту нашу выраженную последовательность знаков разложит в многомерную субстанцию, необходимую ему для понимания. Хотя предложения и одномерны, плоски, по факту они таковыми не являются, это как-бы проекции многих координат нашего мышления на линию предложений языка. А вот если этого не происходит, как в случае порождающей грамматики Хомского и мы пытаемся это явление в себе воспроизвезти, то наше сознание вынуждено ужиматься. От этого и возникает неприятное ощущение. Здесь как раз и проявляется различие между тек как мы понимаем себя и окружающую действительность (а этого мы сами не знаем) и как мы выражаем это понимание посредством языка. Это выражение плоско по своей сути и имеет мало отношения к нашему действительному пониманию. Вот, наверное, в этом и проявляется отличие живого от неживого.

Вообще, не каждый язык может быть выражен порождающей грамматикой. Это легко доказать: так как алфавит языка конечен, то всевозможных последовательностей, которые можно из этого алфавита составить, счетное множество, т.е. множество мощности алеф нуль или мощности множества натуральных чисел. Это множество есть язык и есть также максимальный по количеству строк язык. Каждый язык, как множество строк символов этого алфавита, есть некоторое подмножество максимального языка. Поэтому, множество всех языков, которые могут быть образованы от данного алфавита, можно рассматривать как совокупность всех подмножеств множества мощности алеф нуль. Т.е. множество всех языков над данным алфавитом имеет мощность два в степени алеф нуль, т.е. несчетно. А вот множество всех грамматик, которые могут генерировать язык от данного алфавита, очевидно, счетно. Получается, что грамматик меньше чем языков, и не каждый язык можно описать соответствующей грамматикой. Но си++ конечно можно описать порождающей грамматикой.

Грамматики подразделены на типы в ссответствии с их выразительной мощностью. Самые выразительные это грамматики типа 0, потом типа 1 и т.д. В великолепной книге двух голландских авторов (фамилий не помню, в их голландских именах сам черт ногу сломит), называется она Parsing Technics, есть четыре рисунка розы, в сооветствии с типами грамматик, использованных для рисования. Эти рисунки отличаются по выразительным возможностям. При использовании грамматики типа 3 имеется только грубый рисунок, где только угадывается силуэт розы. при использовании КС-грамматики та же роза изображена более точно, некорые линии прочерчены тоньше, силуэт выглядит изящнее. Но, точное изображение получается только при использовании грамматики типа 0. Относительно си++ эту мысль также можно выразить следующим образом: под корректными предложениями языка можно, с некоторым упрощением, понимать программу написанную на языке си++. Таким образом, если грамматика языка си++ и существует, то она должна уметь генерировать любую корректную программу на си++ и, кроме того, не должна генерировать ни одной некорректной программы. КС-грамматика, описывающая си++, генерирует множество корректных программ на си++, но также генерирует и некорректные. Например, как это было указано выше


А>void f()
А>>{
А>> i = 0; // Ни одного обьявления переменной
А>>}

таким образом, нам необходимо наложить некоторые дополнительные ограничения, чтобы выразить в грамматике свойство обязательного объявления имени до его использования в программе, т.е. чтобы грамматика не генерировала программы описанного выше вида. Так вот, КС-грамматикой это сделать не удается. Здесь полная аналагия с рисунком розы, какие-то тонкие свойства языка не выразимы посредством КС-грамматики. Конечно, еще вопрос, можно ли эти свойства выразить с помощью Кз-грамматики, но оказывается можно. Чтобы уидеть это, лучше всего использовать более близкие человеческому мышлению автоматы для генерации или распознавания. Для КС-грамматики всегда найдется автомат с магазинной памятью, генерирующий или распознающий тот же язык, что и данная КС-грамматика. Магазин значит, что мы имеем доступ только к элементу на вершине магазина. Поэтому, так как для проверки того, объявлено или нет данное имя в программе, необходимо посмотреть по программе множество объявлений, т.е. вернуться назад, магазин использовать не получится. В случае КЗ-грамматик мы имеем устройство, в котором символы записываются на ленте, по которой, в случае необходимости, мы можем двигаться и в обратном направлении, не выталкивая символы, как это приходится делать в магазине. Вот, в данном случае, мы объяление имени проверить сможем.

Владимир.

Здравствуйте, Sergey J. A., Вы писали:

SJA>Является ли грамматика С++ контекстнозависимой ? Если да, то можно простенький пример ?
SJA>Мне кажется, что да, и пример — x(); неясно вызов это функции x или создание объекта типа x. Но я не уверен...

На самом деле, язык C++ не может быть задан даже контекстно-зависимой грамматикой. Дело в том, что есть такая штука, как метапрограммирование. Известно, что средства метапрограммирования вычислительно полны по Тьюрингу. Это значит, что любая распознающая машинка языка C++ должна быть вычислительно полна по Тьюрингу (мы сейчас отвлекаемся от того обстоятельства, что в реальных компиляторах есть ограничение на уровень вложенности инстантинации шаблонов). В соответсвтии с известными теоремами из теории формальных грамматик Хомского, для задания C++ недостаточно грамматики типа 1. Т.е. C++ не является даже КЗ языком.

Копай Нео, копай -- летать научишься. © Matrix. Парадоксы

Здравствуйте, davenger, Вы писали:

D>Предлагаю Вам самому убедиться в обратном:

D>

D>#include <iostream>

D>class X
D>{
D>    X()
D>    {
D>        std::cout << "X::X() called";
D>    }
D>};

D>int main(int argc, char* argv[])
D>{
D>    X x();
D>    return 0;
D>}
D>

И шо ? Может, в понятиях непонимание ? Декларация функции — она же Function Declaration — предложение, связывающее идентификатор с относящейся к нему информацией; в некоторых случаях может быть одновременно и описанием (Definition, конструкция, размещающая в памяти и инициализирующая переменную, функцию или класс).
Здесь же просто создание объекта класса X, это эквивалентно

int main(int argc, char* argv[])
{
    X x;
    return 0;
}

Но! Вот так не прокатит:

X x();

int main(int argc, char* argv[])
{
    // Тра-та-та
    
    return 0;
}

поскольку для компилятора это будет выглядеть как определение функции, а раз оно так выглядит — то так и будет откомпилировано.

Посыпаю голову пеплом...

WC>>Это утверждение согласуется с тем, что множество всех well-formed программ на языке С++ не одно и то же что и множество всех (синтаксических) предложений языка С++.
WH>Согласен. Я не много погорячился. Понятие well-formed program несколько шире чем я тут имел в виду и включает в себя также некоторые требования времени выполнения. Но в данной теме мы эти правила не рассамтриваем.
Я бы сказал, что не немного.

Забудь про well-formed programs! Они из другой оперы!

WH>Что касается ODR то кто сказал что предложение языка С++ состоит только из одной единицы трансляции?
А ты пробовал разбить одну функцию на несколько файлов?

ЗЫ. Хватит наездов и угроз. Английский я знаю получше тебя.

Вот относительно семантики языка я, кажется, в пылу спора немного палку перегнул. Под семантикой языка можно понимать две вещи: первая, это то, о чем мы говорили, в процессе описания языка некоторые его свойства, которые трудно или невозможно описать КС-грамматикой, описываются другими способами. Вторая — это понимание языковых структур людьми, т.е. как мы говорим, смысл языка, как мы его пониманием. Различие между этими двумя трактовками иногда очень небольшое и зависит только от точки зрения, с которорой мы данное свойство рассматриваем. Мы говорили о КЗ и КС языках и поэтому рассматривали языки в терминах теории Хомского, поэтому и трактовали семантику таким образом. Лингвисты часто спрашивают: изобретено ли колесо в лингвистике? Т.е. в природных способах передвижения колеса нет, его придумал человек и колесо неплохо выполняет свои функции, хотя не имеет никакого отношения к тому, как сам человек передвигается. В лингвистике роль колеса играет как раз порождающая грамматика Хомского. С помощью этой теории мы можем производить разбор (слушать и понимать речь собеседника) и генерировать предложения языка (разговаривать), но все таки это никакого отношения к тому, как сам человек это делает, не имеет. Не знаю относительно других, но мне, когда я впервые понял идею Хомского о гененрации языка посредством порождающей грамматики, стало как-то не по себе. Какое-то ощущение неживого, чуждого, копируещего поведение живого... Жутко как-то стало. Я задумался, почему я так себя ощущал и, кажется понял. Видимо, здесь дело в том, что человеческая мысль многомерна по своей сути, но, так как выражается посредством языка, как бы каждый раз ужимается в одномерную последовательность. Мы к этому явлению привыкли и воспринимаем его как должное, мы априори подразумевавем, что собеседник эту нашу выраженную последовательность знаков разложит в многомерную субстанцию, необходимую ему для понимания. Хотя предложения и одномерны, плоски, по факту они таковыми не являются, это как-бы проекции многих координат нашего мышления на линию предложений языка. А вот если этого не происходит, как в случае порождающей грамматики Хомского и мы пытаемся это явление в себе воспроизвезти, то наше сознание вынуждено ужиматься. От этого и возникает неприятное ощущение. Здесь как раз и проявляется различие между тек как мы понимаем себя и окружающую действительность (а этого мы сами не знаем) и как мы выражаем это понимание посредством языка. Это выражение плоско по своей сути и имеет мало отношения к нашему действительному пониманию. Вот, наверное, в этом и проявляется отличие живого от неживого.

Вообще, не каждый язык может быть выражен порождающей грамматикой. Это легко доказать: так как алфавит языка конечен, то всевозможных последовательностей, которые можно из этого алфавита составить, счетное множество, т.е. множество мощности алеф нуль или мощности множества натуральных чисел. Это множество есть язык и есть также максимальный по количеству строк язык. Каждый язык, как множество строк символов этого алфавита, есть некоторое подмножество максимального языка. Поэтому, множество всех языков, которые могут быть образованы от данного алфавита, можно рассматривать как совокупность всех подмножеств множества мощности алеф нуль. Т.е. множество всех языков над данным алфавитом имеет мощность два в степени алеф нуль, т.е. несчетно. А вот множество всех грамматик, которые могут генерировать язык от данного алфавита, очевидно, счетно. Получается, что грамматик меньше чем языков, и не каждый язык можно описать соответствующей грамматикой. Но си++ конечно можно описать порождающей грамматикой.

Грамматики подразделены на типы в ссответствии с их выразительной мощностью. Самые выразительные это грамматики типа 0, потом типа 1 и т.д. В великолепной книге двух голландских авторов (фамилий не помню, в их голландских именах сам черт ногу сломит), называется она Parsing Technics, есть четыре рисунка розы, в сооветствии с типами грамматик, использованных для рисования. Эти рисунки отличаются по выразительным возможностям. При использовании грамматики типа 3 имеется только грубый рисунок, где только угадывается силуэт розы. при использовании КС-грамматики та же роза изображена более точно, некорые линии прочерчены тоньше, силуэт выглядит изящнее. Но, точное изображение получается только при использовании грамматики типа 0. Относительно си++ эту мысль также можно выразить следующим образом: под корректными предложениями языка можно, с некоторым упрощением, понимать программу написанную на языке си++. Таким образом, если грамматика языка си++ и существует, то она должна уметь генерировать любую корректную программу на си++ и, кроме того, не должна генерировать ни одной некорректной программы. КС-грамматика, описывающая си++, генерирует множество корректных программ на си++, но также генерирует и некорректные. Например, как это было указано выше


void f()
А>{
А> i = 0; // Ни одного обьявления переменной
А>}

таким образом, нам необходимо наложить некоторые дополнительные ограничения, чтобы выразить в грамматике свойство обязательного объявления имени до его использования в программе, т.е. чтобы грамматика не генерировала программы описанного выше вида. Так вот, КС-грамматикой это сделать не удается. Здесь полная аналагия с рисунком розы, какие-то тонкие свойства языка не выразимы посредством КС-грамматики. Конечно, еще вопрос, можно ли эти свойства выразить с помощью Кз-грамматики, но оказывается можно. Чтобы уидеть это, лучше всего использовать более близкие человеческому мышлению автоматы для генерации или распознавания. Для КС-грамматики всегда найдется автомат с магазинной памятью, генерирующий или распознающий тот же язык, что и данная КС-грамматика. Магазин значит, что мы имеем доступ только к элементу на вершине магазина. Поэтому, так как для проверки того, объявлено или нет данное имя в программе, необходимо посмотреть по программе множество объявлений, т.е. вернуться назад, магазин использовать не получится. В случае КЗ-грамматик мы имеем устройство, в котором символы записываются на ленте, по которой, в случае необходимости, мы можем двигаться и в обратном направлении, не выталкивая символы, как это приходится делать в магазине. Вот, в данном случае, мы объяление имени проверить сможем.

Владимир.

Здравствуйте, Nick_, Вы писали:

LVV>>А он и не порождается! В том то и дело, что грамматика используется только для распознавания синтаксически правильных конструкций. А контекстные зависимости, о которых тут все время говорили (единственность объявления, "сначала объяви — потом используй), обрабатываются НЕФОРМАЛЬНЫМИ способами (таблица имен).

N_>У вас какая-то каша в голове.
N_>В приведенном мною выше примере на языке Си, как раз и есть синтаксическая контекстная зависимость!
N_>вы не можете написать:

N_>

N_>while(free(ptr));
N_>

N_>Если перед этим был typedef int free;

N_>Возникнет СИНТАКСИЧЕСКАЯ ошибка.

N_>А то что вы говорите про "сначала объяви — потом используй" — это уже семантическая ошибка, которая обнаруживается не во время синтаксического анализа, а уже после того как дерево разбора будет построено.

Подобные сорта деления на синтаксические (лучше было бы сказать -- грамматические, поскольку они возникают из-за несоответствия грамматике) и семантические ошибки имеют смысл только в контексте какого-то определённого способа компиляции языка. К самому языку это прямого отношения не имеет.

Копай Нео, копай -- летать научишься. © Matrix. Парадоксы

Здравствуйте, Sergey J. A., Вы писали:

SJA>Является ли грамматика С++ контекстнозависимой ? Если да, то можно простенький пример ?
SJA>Мне кажется, что да, и пример — x(); неясно вызов это функции x или создание объекта типа x. Но я не уверен...
Ни один из современных языков программирования на практике не описывается контекстно-зависимыми грамматиками, исключительно контестно-свободными (из соображений эффективности, кстати. Распознавание контекстно-зависимых языков требует экспоненциального времени, тогда как КС-языки распознаются в общем случае за полиномиальное время). Но помимо этого, конечно, в каждом компиляторе проверяются не контекстно-свободные характеристики, к которым относятся, например, требование единственности объявления или "сначала объяви, потом используй". Единственный язык, в котором использовалась не КС-грамматика — Алгол-68. Ван Вейнгартен изобрел для него специальные двухуровневые грамматики — видимо без этого невозможно было описать введение новых операций в процессе выполнения программы.

SJA>А можно примеры извесных контекстно свободных языков ?

Самый известный пример, наверное, это язык арифметических выражений без переменных (или можно с переменными, но без их предварительного объявления, скрипт короче).

Выражение --> Число
Выражение --> Число + Число
Выражение --> Число — Число
Выражение --> Число * Число
Выражение --> Число / Число

Число, +, -, * и / — терминалы грамматики, Выражение — ее единственный нетерминал, который также является стартовым (S в определении грамматики).

Конечно, эта грамматика не отражает приоритета операций, чтобы отражала, необходимо ввести еще один нетерминал, заставляющий сначала разбирать умножение и деление но, в принципе, является вполне фунгкциональной. Зависимость от контекста можно выразить как невозможность определить в языке, что данный нетерминал означает ВСЕГДА, где бы он в предложении не встретился, одно и тоже, причем заранее определенное одно и тоже. Выражение в языке выше не означает одно и тоже, а целых пять различных кончтрукций, но, встетив Выражение при разборе предложения языка мы не должны смотреть ни назад, ни заглядывать вперед, чтобы определить какую конструкцию использовать при разборе, т.е. не должны рассматирвать контекст, в котором встретился данный нетерминал.

SJA>Но непонятно, как из IDENTIFIER перейти к type или variable. Нужны доп. данные.
SJA>Как для данного выражения построить КС ?

Можно так показать контекстную зависимость языка с предварительными объявлениями. Для каждого типа грамматики существует свой тип рапознавателя — математической абстракции, моделирующеймашину для распознавания языка, который заддается этой грамматикой:

Тип 0 (грамматики без ограничений) — машина Тьюринга
Тип 1 (КЗ грамматики) — линейно ограниченный автомат
Тип 2 (КС грамматики) — автомат с магазинной памятью (стеком)
Тип 3 (регулярные грамматики) — конечный автомат

Вот отсюда можно увидеть, что при предварительном объявлении некоторого имени, далее, при разборе предложения языка, при встрече некоторого имени мы должны как бы откатиться назад и пройти по всем объявлениям имен, чтобы узнать, было ли объявлено данной имя или нет. Очевидно, что при организации памяти распознавателя в виде магазина это невозможно. А вот записывая объявления на ленте, по которой мы можем ходить также и в обратном направлении, это вполне возможно. Конечно, для этого придется расширить грамматику так, чтобы лексический анализатор не возвращал безликий ID, а сделать ID нетерминалом. Определить ID можно например так:

ID --> Буква Буквы_Цифры
Буквы_Цифры --> Буква Цифра | Цифра Буква | пустая_строка
Буква --> ....
Цифра --> ....

Тогда, в процессе разбора, у нас при объявлении, допустим, имени x где-то в программе будет исполнено правило ID --> x и при встрече переменной далее в предложении, мы попытаемся найти все такие правила, записанные на ленте, и таким образом, узнать было ли такое объявление. Аналогично, можно поступить с типизированными именами, а также именами типов. Вот это, с большой натяжкой конечно и неформально, можно считать доказательством контесктной зависимости языка с предварительными объявлениями имен.

Распознавание контекстно-зависимых языков требует экспоненциального времени, тогда как КС-языки распознаются в общем случае за полиномиальное время.

Алгоритм Эрли и алгоритм Кока-Янгера-Касами распознают КС языки за кубическое время, а однозначные языки вообще за квадратичное. Валиант в 1975 году придумал оптимизацию алгоритма Кока-Янгера-Касами посредством битового массива, поиск по которому дает логорифмическое время. Так что, теперь, по последним данным, анализ строки длиной N для я зыка, заданного КС-грамматикой, может быть произведен за время N * N * log N.

>>> А ничего и не надо убирать! Грамматика С++ — контекстно-свободная грамматика, и потому, этот
>>> язык сам и является контекстно-свободным.

АГ>>Хм. В таком случае, как разобрать выражение x * y не зная контекста (классика жанра)?

АТ> А в чем проблема? Если это относительно полное [под]выраждение, то очень просто:

АТ>

АТ>       *
АТ>     /  \
АТ>   /      \
АТ>  x        y
АТ>

Полное выражение:

x * y;

В случае

int x;
int y;

x * y;

очень просто, как показано у тебя выше, а вот в случае

typedef int x;

x * y;

я сомневаюсь, что будет построено именно это дерево.

А в случае x * y, z; все еще несколько усложняется.

--
aga

Грамматика С++ — контекстно-свободная! Все языки программирования описываются контекстно-свободными грамматиками! Даже те, в которых надо обьявлять переменную до использования, .

M>Мы же это уже обсуждали выше. То, о чем ты говоришь, конечно КС-грамматика, но она си++ не определяет, а только его подмножество, т.е. немного другой язык. Ведь в данной грамматике никак не выражена необходимость объявлять имя до его использования? Верно? Значит, грамматика язык не полностью определяет. Так часто делается, часть языка выражается грамматикой, другая — КЗ часть, парсится вручную и это называется семантикой языка. Мы же говорим о свойстве самого языка си++, какой он? Т.е. найдется ли КС грамматика, полностью описывающая весь язык полностью? Я утверждаю, что нет. Что в моем рассуждении неверно?
Все Ваши неверные выводы и рассуждения основаны на непонимании, что есть грамматика. Грамматика — это формальный способ описания синтаксиса языка! Утверждение же, что переменная должна быть обьявлена до использования — неформальное требование, которое грамматикой языка не описывается! К примеру, как Вы формально обьясните, что делает for (int i = 0; i < 5; ++i)? НИКАК! Такие [семантические] конструкции описываются неформально! Точно также неформально и описывается требование обьявлять переменную заранее!

Если Вы так уверены, что С++ контекстно-зависимый язык, то продукции, которые "требуют обьявления переменной до использования" — в студию!

Здравствуйте, mefrill, Вы писали:

M>анализ строки длиной N для я зыка, заданного КС-грамматикой, может быть произведен за время N * N * log N.

моя школьная учительница по физике, увидев бы ваше сообщение, непременно б возразила:
— это в "колбасках" все величины? существует ведь единая система измерения СИ, сколько то можно?

вот так с детства нам вбивали силу слова "СИ"

Ш>Да нет, это у вас непонимание элементарных вещей. Есть язык C++, есть множество well-formed программ на этом языке, которое представляет из себя некоторое множество конечных цепочек букв.
Может дадите определение ваших "well-formed программ на этом языке?"

Пришла зима. Нестерпимая жара установилась на дворе. Грамматика С++ — контекстно-свободная! В этом форуме куча тем. Кто из нас всех прав? Опять пришла зима и т.д.

Это пример из русского языка. Как видите, с точки зрения русской грамматики параграф и все предложения верны, но тем не менее смысла они не имеют. Точно также и с С++. Даже Лаптев, вон, выше заметил, что языки описываются КС грамматиками.

Ш>Так вот, это множество не может быть определено через КС грамматику.
Кто вам это сказал?

Ш>Это и означает, что C++ не контекстно свободный язык.
Ваш вывод (неверный, кстати) основан на вашем же и утверждении.

Ш>Будем спорить, что 2+2==4?
Не въехал...

Может все-таки откроете грамматику С++ и предоставите доказательства? (ака правила, которые требуют, чтобы переменная была обьявлена один и только один раз)

Ш>Читайте стандарт. По простому, well-formed программа -- это то, что компилятор C++, написанный в соответствии со стандартом, должен пропустить через себя и сгенерировать некоторый объектный код.
Слышал Шахтер звон да так и не понял где он!

Используя грамматику С++, можно вывести следующую функцию:

void foo()
{
       int i;
       return i;   // Все синтаксически здесь верно!!!
}

но нельзя вывести эту функцию:

void foo()
}
{  // Скобки перепутали местами...

Ш>Это доказано. Математически строго.
Ш>Читайте этот тред, а так же специальную литературу.
Это Вам надо посоветовать перечитать этот тред и запастись специальной литературой.

Ш>Вы пытаетесь оспорить, что 2+2==4. Таких людей обычно посылают в дет. сад.
Это Вы пытаетесь оспорить то, о чем совсем не имеете понятия!

ЗЫ. Хватит голословности! Может все-таки приведете мне какие-нибудь правила из грамматики С++, уличающие этот язык в контекстно-зависимости?!! Ы?

Ш>Вы пытаетесь оспорить, что 2+2==4. Таких людей обычно посылают в дет. сад.
Не говорите мне куда идти если не хотите быть посланным по одному всем известному адресу!

WH>Это не есть well-formed программа на языке С++. Грамматика языка должна описывать все well-formed программы и только well-formed программы. Если грамматика описывает все well-formed и еще множество не well-formed программ то это не грамматика данного языка. Исключить множество не well-formed программ языка С++ можно только при помощи КЗ грамматики.
WH>Но тк КЗ грамматика это очень сложно то используют компромисный вариант. Создают КС грамматику которая описывает язык являющеяси над множеством данного языка и создают допольнительные правила для отсечения не well-formed программ. И сделано это не по тому что грамматика языка КС, а по тому что построение КЗ грамматики во первых очень сложный процесс сам по себе во вторых парсер получается ну ооочееень медленный.
WolfHound, ну зачем говорить о чем не имеешь представления?

WH>Это не есть well-formed программа на языке С++.
А никто и не говорил, что это well-formed программа. Если взять грамматику С++, построить ее распознователь (а не компилятор!!!), то он скажет: "Да, эта функция была выведена грамматикой С++!"

WH>Грамматика языка должна описывать все well-formed программы и только well-formed программы.
Опять, кто это сказал? Грамматика должна описывать все синтаксически верные программы! Учите теорию. Чуете разницу между лексикой, синтаксисом и семантикой?

А вообще, откройте Страуструпа и убедитесь, что непонравившаяся Вам функция выводится грамматикой С++!

M>Так дискуссию вести невозможно, аргументы игнорируются, очевидные факты отвергаются.
Да-да-да... Аргументы игнорируются и очевидные факты отвергаются, но не мной а Вами!!!

M>Языком является множество строк, сформированных из символов данного алфавита. Порождающая грамматика Хомского — это устройство для порождения данных строк и только их. Язык может описываться не только порождающей грамматикой Хомского, а также и другими, каковых сущесвтует великое множество, как порождающих, так и не порождающих.
Ну не надо мне толкать все эти определения! Теорию формальных языков и трансляции я знаю и без Вас! Более того, из Ваших ответов видно, что Вы недопонимаете простые вещи, хотя теория Вам в целом ясна!

Примеры не порождающих грамматик — в студию!

M>кроме того, язык может быть описан без всякой грамматики. Например, предложение "множество сттрок, состоящих из нуля и более символов а" великолепно описывает язык, который задает грамматика:
M>S --> aS | пустая строка
Ну вот. Говорим о языке, который "может быть описан без всякой грамматики" и толкаем пример регулярной грамматики с использованием рекурсии (ака КС элемента)!!! Удивительная у Вас способность описывать простые грамматики более сложными!!! Неудивительно, что для языков программирования Вам нужна КЗ грамматика!


M>Здесь ГДЕ-НИБУДЬ о семантике хоть слово было произнесено?
Это Вы смешиваете чисто семантическая понятия с синтаксическими!

M>Семанитка языка (в ее настоящем смысле, т.е. интепретация строк языка человеком) не имеет никакого отношения к описанию структуры строк языка (его предложений). Этим занимает синтаксис. Например, мы могли бы интерпретировать описанный выше язык так: символ а значит произнесение звука а в течении одной секунды. Тогда строка ааа обозначала бы, что некий человек пропел а-а-а... три секунды подряд.
Долой абстрактные примеры и голословность! Все что от Вас требовалось — привести правила, которые требуют обьявления переменных один и только один раз! ВЫ ИХ НЕ ПРИВЕЛИ!

M>То же самое и в си++. Множество предложений данного языка это (с некоторым обобщением) множество правильных программ, написанных на языке си++.
Достает это уже. Повторюсь еще раз... Грамматика описывает только синтаксис языка, и ПРОГРАММА МОЖЕТ БЫТЬ СИНТАКСИЧЕСКИ ВЕРНОЙ, НО НЕВЕРНОЙ СЕМАНТИЧЕСКИ! Выше я уже привел два примера!

M>Вот и встает задача: описать это множество программ, используя ТОЛЬКО порождающую грамматику Хомского. Это сделать можно, как возможно описать любые структурные построения (например, множество музыкальных этюдов).

M>Но, КС-грамматика для этого не подойдет из-за свойства языка: каждое имя должно быть описано перед его использованием. Как я уже писал выше, данное свойство не может быть выражено КС-грамматикой.
Да кто Вам сказал, что требование, что имя должно быть описано до использования вообще должно быть выраженно через грамматику?!! ТРЕБОВАНИЕ, ЧТОБЫ ИМЯ БЫЛО ОБЬЯВЛЕНО ДО ИСПОЛЬЗОВАНИЯ — НЕФОРМАЛЬНО, И НЕ МОЖЕТ БЫТЬ ВЫРАЖЕННО ГРАММАТИКАМИ!!!

M>Так что все просто. Разумеется, язык можно описывать и не используя порождающие грамматики, а как-нибудь по другому. Например, как это делается в стандарте языка си++.

M>Чать описывается КС-грамматикой. Но такое описание позволяет породить и неверные программы на си++.
Повторюсь еще раз! Все программы, описанные грамматикой С++ будут синтаксически верны т.к. грамматика описывает только синтаксис (случай с КС грамматикой) и лексику (случай с регулярной грамматикой)! Это, однако, не значит, что программа будет верна семантически!!!

Как Вы опишите формально, что делает for loop? НИКАК! Точно также нельзя формально требовать, чтобы имена были обьявлены заранее. Это делается НЕФОРМАЛЬНО!

M>Поэтому, вводятся еще ограничения, причем в виде так называемых "семантических" правил. Это делать можно, но почему же при этом говорить, что КС-грамматика, описывающая часть языка, описывает весь язык!? С таким же успехом, я могу описать часть языка регулярной грамматикой, а остальную часть неформально на русском языке и сказать, что граматика языка си++ регулярна. Но это не так, конечно.
Ну да! Давайте вообще выбросим всю формализацию к черту и обьявим, что язык С++ вообще можно описать только словами (неформально)!

Именно эти и "семантические правила," которые неформальны, и требуют, чтобы имя было обьявлено. Все! Не путайте язык программирования с формальным языком!

M>Именно, понимание выразительной способности разных классов грамматик и составляет понимание идеи Хомского. Еще раз, в книге "Техники парсинга" есть такой рисунок:
Ну и зачем нам этот рисунок? Опять абстракция! Без него и так ясно, что существуют классы грамматик, которые описывают больше языков, чем другие, и сложность расспознавания которых выше. Вот и вся теория.

M>Владимир.
Учите теорию, Владимир, лучше!

Ну и аспиранты пошли... Грустно...

ЗЫ, Приведите правила из грамматики, подтверждающие, что язык С++ — КЗ язык! Хватит голословности и абстрактных размышлений!

WH>Ответьте на два вопроса
Мне следует задать эти вопросы т.к. Вы путаете разницу между формальным языком и грамматикой.

WH>1)Может ли порождающая грамматика языка порождать предложения не входящие в данный язык?
Глупый вопрос. Разумеется не может! Вопрос в том, что для Вас означают предложения языка С++. Ответьте сами на этот вопрос. Если Вы скажете, что это, что скомпилирует компилятор, то Вы ошибаетесь! Я уже привел пример функции с переставлеными скобками — это нелегальное предложение т.к. нет продукций, которые бы вывели эту строку. С другой стороны, та функция, что Вам не понравилась выводится грамматикой С++, и если взять книгу Страуструпа и написать по его грамматике распознаватель этого языка, то он подтвердит, что это легальное предложение. Тем не менее, компилятор его не скомпилирует т.к. компилятор это нечто большее чем простой расспознаватель.

WH>2)Что вы понимаете под предложением на языке С++?
Вопрос тоже не очень. Строка, которую можно вывести из грамматики С++, и, опять-таки, эта строка может не скомпилироваться компилятором. Не забывайте, грамматика просто порождает предложения языка, которые могут и не иметь смысла (и поэтому их компилятор и не скомпилирует). Для русского языка я привел уже параграф с простым набором предложений. Для С++ — функцию, return type которой void, но которая все равно возвращает int.

У нас замкнутый круг получается, т.к. для Вас легальные предложения С++ это то, что скомпилирует компилятор. Но, тем не менее, это не так! Предложение это то, что выводится грамматикой, а не то, что компилирует компилятор.

WH>Наезды поскипаны.
Это не наезды. Я вижу, что Вы совсем не знакомы с теорией формальных языков и трансляции.

Здравствуйте, <Аноним>, Вы писали:

WH>>1)Может ли порождающая грамматика языка порождать предложения не входящие в данный язык?
А>Разумеется не может!
Следовательно если при помощи данной грамматики нам удасться получить предложение не относящаяся к данному языку то данная грамматика не является грамматикой данного языка.
А>Вопрос в том, что для Вас означают предложения языка С++. Ответьте сами на этот вопрос.
well-formed программа. Не отдельная функция и тем болие не отдельный стейтмент, а все программа целиком.
Не well-formed программа не является предложением на языке С++. Грамматика которая порождает не well-formed программы не является грамматикой С++.
А>Если Вы скажете, что это, что скомпилирует компилятор, то Вы ошибаетесь!
Правда?!
А>Я уже привел пример функции с переставлеными скобками — это нелегальное предложение т.к. нет продукций, которые бы вывели эту строку. С другой стороны, та функция, что Вам не понравилась выводится грамматикой С++, и если взять книгу Страуструпа и написать по его грамматике распознаватель этого языка, то он подтвердит, что это легальное предложение.
Еще раз процитирую Страуструпа

Приведенное ниже описание синтаксиса С++ должно помочь пониманию языка. Оно не является точным определением языка С++. В частности, описаная здесь грамматика допускает надмножество допустимых конструкций С++.

Он сам говорит что это эта грамматика может порождать предложения не являющаюся предложениями языка С++ те это не грамматика С++.
Точно такие же оговорки есть в стандарте и красном драконе.
А>Тем не менее, компилятор его не скомпилирует т.к. компилятор это нечто большее чем простой расспознаватель.
Компилятор это ни что иное как распознователь языка.(про то что он еще и объектный код генерирует можно забыть это к делу не относится) И он должен распознать все предложения языка и только предложения языка.

WH>>2)Что вы понимаете под предложением на языке С++?
А>Вопрос тоже не очень. Строка, которую можно вывести из грамматики С++, и, опять-таки, эта строка может не скомпилироваться компилятором.
Вот именно что из грамматики С++ НО ни у Страуструпа ни в стандарте ни в краснтом драконе грамматики С++ нет. Там грамматики других языков подмножеством которых является С++.
А>Не забывайте, грамматика просто порождает предложения языка, которые могут и не иметь смысла (и поэтому их компилятор и не скомпилирует).
А>Для русского языка я привел уже параграф с простым набором предложений.
Для русского языка вы привели несколько предложений. Каждое из которых является предложением русского языка но вместе они ни как не связаны.
А>Для С++ — функцию, return type которой void, но которая все равно возвращает int.
Нет это предложение из другого языка. Для С++ вся программа это одно предложение. Если на С++ написать граффический редактор и архиватор то и то и другое будут отдельными предложениями на языке С++ и ни кого не удивляет почему у них нет ни чего общего.
Аналогом связанных предложений являются например N-tier системы где несколько предложений (возможно на разных языка) связанны друг с другом смыслом.

Что касается без смысленных предложений то вот два безсмысленных предложения одно на русском другое на С++.

Лом съел скалку.

int main()
{
    int a, b, c;
    a*b-c/a;
}

Еще раз повторю то что вы приводили в качестве безсмысленного С++ предложения не является предложением на С++.

WH>>>1)Может ли порождающая грамматика языка порождать предложения не входящие в данный язык?
А>>Разумеется не может!
WH>Следовательно если при помощи данной грамматики нам удасться получить предложение не относящаяся к данному языку то данная грамматика не является грамматикой данного языка.
Ну разумеется, сударь! Толькто кто Вам сказал, что не понравившаяся Вам функция не выводится грамматикой С++? Она очень даже выводится, хоть и не имеет смысла!

ВНИМАНИЕ! Попытаюсь теперь более доходчиво обьяснить, что же происходит на самом деле!

Допустим множество строк А порождается грамматикой С++. Среди всех этих строк есть строгое подмножество В, строки которого не имеют смысла! Точно также, есть строгое подмножество С, строки которого имеют смысл в языке С++. Имея грамматику С++, задача компилятора и состоит определить является ли данная функция элементом множества С, и если да, то скомпилировать ее код. Примерами функций подмножества В является та функция, которая Вам уже не понравилась или функция, в которой не описана локальная переменная до ее использования. В множестве С находятся функции, в которых тип возвращаемого значения соответсвует типу функции, в котором локальные переменные обьявлены и т.д.

А>>Вопрос в том, что для Вас означают предложения языка С++. Ответьте сами на этот вопрос.
WH>well-formed программа. Не отдельная функция и тем болие не отдельный стейтмент, а все программа целиком.
WH>Не well-formed программа не является предложением на языке С++. Грамматика которая порождает не well-formed программы не является грамматикой С++.
Ну-ну... Замените ту функцию, что я привел на main():

void main()
{
     return 8;
}

Как видите, это отдельная функция, которая является и целой программой. Синтаксически она верна. Семантически — нет. Ключевое слово здесь синтаксис т.к. грамматика описывает синтаксис языка.

А>>Если Вы скажете, что это, что скомпилирует компилятор, то Вы ошибаетесь!
WH>Правда?!
Правда!

А>>Я уже привел пример функции с переставлеными скобками — это нелегальное предложение т.к. нет продукций, которые бы вывели эту строку. С другой стороны, та функция, что Вам не понравилась выводится грамматикой С++, и если взять книгу Страуструпа и написать по его грамматике распознаватель этого языка, то он подтвердит, что это легальное предложение.
WH>Еще раз процитирую Страуструпа
WH>

WH>Приведенное ниже описание синтаксиса С++ должно помочь пониманию языка. Оно не является точным определением языка С++. В частности, описаная здесь грамматика допускает надмножество допустимых конструкций С++.

Упасть можно. Даже сам Страуструп толкует об этом! Грамматика С++ порождает множество А выше, и это он имеет в виду. Все предложения, порожденные его грамматикой, будут синтаксически верными, но часть из них не скомпилируется т.к. не будет иметь смысла.

WH>Он сам говорит что это эта грамматика может порождать предложения не являющаюся предложениями языка С++ те это не грамматика С++.
Вы хоть думаете, что говорите?!! Сам Страуструп в своей книге приводит грамматику С++, которая, однако не является грамматикой С++!!! Это как по-вашему?

WH>Точно такие же оговорки есть в стандарте и красном драконе.
Вот именно!!! Все грамматики порождают предложения множества А, в то время как компилятору нужно выявить элементы подмножества С. Поэтому Драконова книга и Стандарт и Страуструп так говорят! Поймите, что грамматика описывает синтаксис языка, но не каждая синтаксически верная программа имеет смысл и может быть скомпилирована!

А>>Тем не менее, компилятор его не скомпилирует т.к. компилятор это нечто большее чем простой расспознаватель.
WH>Компилятор это ни что иное как распознователь языка.(про то что он еще и объектный код генерирует можно забыть это к делу не относится) И он должен распознать все предложения языка и только предложения языка.
Опять-таки, компилятор это нечто большее и сложное чем простой распознаватель грамматики. Распознаватель приймет любою строку из множества А, в то время как компилятор должен определить принадлежит ли данная строка подмножеству С. Обычный расспознаватель не строит синтаксическое дерево программы; ему все равно, какими продукциями была выведена данная строка. Компилятор же должен построить синтаксическое дерево, выявив какие именно продукции были использованны при выводе.

WH>>>2)Что вы понимаете под предложением на языке С++?
А>>Вопрос тоже не очень. Строка, которую можно вывести из грамматики С++, и, опять-таки, эта строка может не скомпилироваться компилятором.

WH>Вот именно что из грамматики С++ НО ни у Страуструпа ни в стандарте ни в краснтом драконе грамматики С++ нет. Там грамматики других языков подмножеством которых является С++.
Угу. В стандарте по С++ дана грамматика какого-то друго языка, подмножеством, которого является С++. Я сейчас упаду. Подумайте над своими словами.

Опять Вы недопонимаете. Грамматика описывает синтаксис языка!!! Часть предложений, порожденной грамматикой из стандарта не будут иметь смысла (хотя, опять-таки, синтаксически они все будут верны), и поэтому будут отвергнуты компилятором! Та функция, что Вам не понравилась и есть пример!!!

А>>Не забывайте, грамматика просто порождает предложения языка, которые могут и не иметь смысла (и поэтому их компилятор и не скомпилирует).
А>>Для русского языка я привел уже параграф с простым набором предложений.
WH>Для русского языка вы привели несколько предложений. Каждое из которых является предложением русского языка но вместе они ни как не связаны.
Вот именно! Синтаксически, они вместе все верны, но вот семантически — нет. Грамматика определяет только синтаксис языка!

А>>Для С++ — функцию, return type которой void, но которая все равно возвращает int.
WH>Нет это предложение из другого языка. Для С++ вся программа это одно предложение. Если на С++ написать граффический редактор и архиватор то и то и другое будут отдельными предложениями на языке С++ и ни кого не удивляет почему у них нет ни чего общего.
См. пример с одной функцией main(). Кстати, где в грамматике С++ написано, что должна быть функция main()? Прошу не игнорировать этот вопрос.

WH>

WH>int main()
WH>{
WH>    int a, b, c;
WH>    a*b-c/a;
WH>}
WH>

Очень даже осмысленное предложение на С++ и будет скомпилировано компилятором (хоть результаты вычисления и отбрасываются)!

WH>Еще раз повторю то что вы приводили в качестве безсмысленного С++ предложения не является предложением на С++.
Как раз такие является! Оно является предложением С++, но которое, тем не менее, не имеет смысла. А вот Ваша функция выше — имеет смысл и является предложением С++.

Здесь грамматика Си. Взял ее так как с ней работать проще.

Вот продукции, которые выведут функцию main() выше (номера указаны с этого списка):

8) function-definition:
declaration-specifiers declarator compound-statement
17) declaration-specifiers:
type-specifier
25) type-specifier:
void
68) declarator:
direct-declarator
75) direct-declarator:
direct-declarator()
69) direct-declarator:
identifier
123) compound-statement:
{ statement-list }
125) statement-list:
statement: jump-statement
143) jump-statement:
return expression;

Продукции, которые расширяют expression не привожу т.к. их много (достало меня уже!), но вконце expression ведет к продукциям 213, 215, 219 и т.д. Так что не надо говорить, что "моя" функция не может быть выведена грамматикой!

Язык С++ — context free language!

Здравствуйте, <Аноним>, Вы писали:

А>Язык С++ — context free language!
Итого: Это утверждение строится на отрициании того что множество всех well-formed программ на языке С++ является множеством всех предложений языка С++.
Также вы отрицаете оговорки приведенные в стандарте, у Страуструпа и в красном драконе что их грамматики не являются точными грамматиками языка С++. И как следствие используя их нельзя породить все предложения языка С++ и только предложения языка С++.

Думаю разговор на этом можно считать оконченым.

Здравствуйте, <Аноним>, Вы писали:

А>Я тоже так думаю. Обратите внимание на кавычки в "грамматика."
Ага там во всем посте кавычки. В том числе и в той его части которая описывает грамматику в вашем понимании.
А>И вообще, хватит заниматься демагогией.
Поддерживаю. Рассуждения про кавычки это и есть демагогия.
Отрицание выделеного фрагмента

Приведенное ниже описание синтаксиса С++ должно помочь пониманию языка. Оно не является точным определением языка С++. В частности, описаная здесь грамматика допускает надмножество допустимых конструкций С++.

это тоже демагогия. Ибо тут четко написано что приведенная грамматика не является точной. И как следствие не является грамматикой С++.
А>Вы еще не ответили ни на одну просьбу о продукциях и не обьяснили почему мои примеры выводятся грамматикой С++.
Вы сначала найдите точную грамматику С++ (читыйте найдите грамматику С++) вот тогда и поговорим. А пока все ваши утверждения на основании не точных грамматик (читайте грамматик других языков) ни чего не стоят.
Тут вы опять начнете рассуждать о том что такое предложения языка С++ так вот: Множество всех предложений на языке С++ является множеством всех well-formed программ на С++. Не больше и не меньше.
Убедить меня в обратном вам не удасться и как следствие не удасться убедить меня в том что грамматика порождающая не well-formed программы является грамматикой С++.

А>Языки не описываются КЗ грамматиками т.к. КС грамматики достаточно для описания языка.
Еще раз читайте пост Лаптева. Там написано почему используют формальные КС грамматики и почему КЗ храктеристики проверяются не формально.

Распознавание контекстно-зависимых языков требует экспоненциального времени, тогда как КС-языки распознаются в общем случае за полиномиальное время

Это главная причина почему полную грамматику языка разбивают на формальное КС надмножество и не формальные КЗ правила которые вы называете сенематикой.
Вторая причина это то что построение точной формальной грамматики для современных языков (и С++ в особенности вы только вслушаейтесь в эти страшные слова ШАБЛОНЫ, SFINAE, ADL жуть мне уже страшно от того что придется сделать для того чтобы описать это формально ) является очень трудной задачей. И ни один вменяемый человек не станет тратить гигантское колличество ресурсов на то чтобы создать грамматику которая еще и распозноваться будет за экспоненциальное время. И так компиляторы еле ворочаются.
И если вы думаете что я все брошу и потрачу кучу времени на то чтобы создать точную грамматику С++ только ради того чтобы вам что-то доказать то вы ошибаетесь.

Народ, ну вы таки определитесь, какой язык вы собираетесь описывать, а потом будете спорить, он КС или КЗ.
Что является допустимым предложением языка?
В частности, приведённый пример с попутанным типом возвращаемого значения является допустимым предложением C++ или нет?

IMHO не является.
И аргумент, что является, т.к. удовлетворяет приведённой в стандарте грамматике не катит (http://rsdn.ru/Forum/Message.aspx?mid=753617&amp;only=1

Автор: WolfHound
Дата: 07.08.04

). Т.е. стандарт честно признаётся, что множество допустимых предложений языка C++ определяется совсем не приведённой в этом же стандарте грамматикой.
Тогда почему является? (если кто-то так думает)

Ш>По любой, какой сочтут подходящей.
Ну чего говорить? Ничего ведь умного не сказал в этом топике.

Здравствуйте, mefrill, Вы писали:

M>Вот теперь, действительно, в последний раз.
Раз уж решили ответить, теперь не торопитесь, пожалуйста. Тем более, что Вам захочется ответить мне, еще как минимум один раз.

M>А с чего Вы взяли, что я не могу построить грамматику для Вашего языка???
Тат я немного о другом... Знаете, когда жена в досаде мужу говорит "Ну почему ты даже мусор вынести не можешь?!!"

M>Почему я не привел грамматику для Вашего языка? Да просто потому, что здесь не курсы по (такой простой) теории формальных языков. Я Вам попытался это объяснить, но вместо ответа получил обвинения в некомпетентности.

Понимаете ли, вопрос Вашей компетентности или некомпетентности для меня важен только опосредованно. Мне сейчас (и всё больше) интересен вопрос возможности построения КЗ-грамматики для wellformed С++ языка (буду добавлять wellformed, чтобы не путать с синтаксическим языком С++). С недостаточностью КС — понятно.
Попутно к этому меня заинтересовала фраза анонима о неформализуемости требования "определение перед использованием". Причем, если он ошибается, то мне интересно не просто узнать это и точка, а понять в чем конкретно ошибка и откуда ноги растут у такого заявления.

Аноним, если сейчас читаете, проясните пожалуйста по ногам?

M>Ниже приведена (и объяснена!) грамматика для Вашего языка:
M>S --> A 0 S | A
M>A --> B A C | B 0 C
M>Эти правила позволяют генерировать последовательности вида BBB 0 CCC 0 BB 0 CC.

Вот какие уже на этом месте меня посетили мысли:

1.Какую из двух предложенных альтернатив языка выбрал мой оппонент?
По примеру (и другим примерам далее) выглядит, что условие "ровно два одинаковых", но с другой стороны те же правила генерируют и BBB 0 CCC 0 BBB 0 CCC. Значит выбрано "два и более одинаковых". Да, но тогда у нас выпадает строка BBB 0 CCC 0 ССС (или некий ее аналог), так что цепочки с нечетным колличеством одинаковых идентификаторов грамматика точно не распознает.

2.Дальше я пока, извините, недостаточно внимательно анилизировал (но конечно же обязательно это сделаю, как только смогу), потому что все мои мысли заняла вот какая гиппотеза:
А может быть ошибка утверждения анонима в том, что вместо правила "определение перед использованием" должно бы было указано правило "одного описания" (One Definition Rule). Может быть его нельзя выразить порождающей грамматикой? Если бы это было так, то тогда стало бы понятно почему в самом Стандарте это правило идет особняком (этот вопрос тоже у меня отложился и пока правильного ответа нет). В общем я твердо понял, что мне нужно эту гиппотезу проверить.

3.Я изменил язык своей грамматики на "идентификаторы без повторений" и попытался придумать схему (логику) грамматики. Можно было бы разбираться с языком "ровно два одинаковых", но лучше ведь упрощать, чтобы оставалась и была видна суть проблемы и решения, правильно? Попытки мои окончились безуспешно — мне не удалось построить такую грамматику. При попытке доказать или опровергнуть тезис существования такой грамматики я понял, что здесь моего уровня знаний без обращения к специальной литературе, которой у меня нет, точно недостаточно...

Если Вы строили грамматику для "два и более одинаковых":
По моим прикидкам, доработать первые два правила вполне возможно (укажите, если я ошибаюсь). Тогда, правда, вопрос об "One Definition Rule" пока останется для меня открытым, но я надеюсь в специальной литературе ссылки на которую Вы мне дадите, я смогу на него найти ответ.

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

M>Все ли здесь понятно мудрому белорусскому вьюноше?
И не надейтесь
Как видите вопросы начались уже с первых строк.
Без внимания не оставлю и все остальное, все непонятности буду формулировать.

Здравствуйте, <Аноним>, Вы писали:

А>Здравствуйте, LaptevVV, Вы писали:

LVV>>Здравствуйте, Nick_, Вы писали:

N_>>>Контекстно зависимой является даже грамматика простого Си!
LVV>>Еще раз повторяю: грамматика — контекстно-свободная, а язык — контекстно-зависимый! И не надо путать.

А>Я не знаю, что такое контекстно-зависимый язык в Вашем понимании. Но контекстно-зависимый язык в определении А.Ахо и Дж.Ульмана не может быть порожден контекстно-свободной грамматикой.

Контекстно-зависимый язык -- это язык, который может быть порожден контекстно-свободной грамматикой и не может быть порожден контекстно-свободной. И нет никакого другого понимания.

Копай Нео, копай -- летать научишься. © Matrix. Парадоксы

Является ли грамматика С++ контекстнозависимой ? Если да, то можно простенький пример ?
Мне кажется, что да, и пример — x(); неясно вызов это функции x или создание объекта типа x. Но я не уверен...

Здравствуйте, Sergey J. A., Вы писали:

SJA>Является ли грамматика С++ контекстнозависимой ? Если да, то можно простенький пример ?
SJA>Мне кажется, что да, и пример — x(); неясно вызов это функции x или создание объекта типа x. Но я не уверен...
правильно не уверены%) потому что это может быть экземпляр класса с перегруженным оператором ()

Здравствуйте, Sergey J. A., Вы писали:

SJA>Является ли грамматика С++ контекстнозависимой ? Если да, то можно простенький пример ?
SJA>Мне кажется, что да, и пример — x(); неясно вызов это функции x или создание объекта типа x. Но я не уверен...

Я думаю, что нет... вот сходу еще придумалось.

void f1()
{
   int a,b,c;

   a < b > c;
}

template <class> struct a {};

void f2()
{
  typedef int b;
  a< b > c;
}

struct X { X() {} };

int main()
{
  X x(); <- декларация фунции или переменная x ?
}

Здравствуйте, dimitry_dimitry, Вы писали:

_>Здравствуйте, Sergey J. A., Вы писали:

SJA>>Является ли грамматика С++ контекстнозависимой ? Если да, то можно простенький пример ?
SJA>>Мне кажется, что да, и пример — x(); неясно вызов это функции x или создание объекта типа x. Но я не уверен...
_>правильно не уверены%) потому что это может быть экземпляр класса с перегруженным оператором ()

Так что правильно-то ? Я не уверен, что грамматика С++ контекстнозависима. Она контекстно независима ?
Или мой пример не верен ?

Здравствуйте, _Winnie, Вы писали:

_W>Здравствуйте, Sergey J. A., Вы писали:

SJA>>Является ли грамматика С++ контекстнозависимой ? Если да, то можно простенький пример ?
SJA>>Мне кажется, что да, и пример — x(); неясно вызов это функции x или создание объекта типа x. Но я не уверен...

_W>Я думаю, что нет... вот сходу еще придумалось.
"Нет" — то есть граматика С++ контекстно не зависима ?

_W>int main()
_W>{
_W>  X x(); <- декларация фунции или переменная x ?
_W>}

Может я неправильно понимаю термин контекстнозависимый, но мне казалось, что данный пример как раз и говорит о контекстной зависимости:
в зависимости от контекста строка может быть декларацией фунции или переменной.

Здравствуйте, Sergey J. A., Вы писали:

SJA>Здравствуйте, _Winnie, Вы писали:

_W>>Здравствуйте, Sergey J. A., Вы писали:

SJA>>>Является ли грамматика С++ контекстнозависимой ? Если да, то можно простенький пример ?
SJA>>>Мне кажется, что да, и пример — x(); неясно вызов это функции x или создание объекта типа x. Но я не уверен...

_W>>Я думаю, что нет... вот сходу еще придумалось.
SJA>"Нет" — то есть граматика С++ контекстно не зависима ?

SJA>

_W>>int main()
_W>>{
_W>>  X x(); <- декларация фунции или переменная x ?
_W>>}
SJA>

SJA>Может я неправильно понимаю термин контекстнозависимый, но мне казалось, что данный пример как раз и говорит о контекстной зависимости:
SJA>в зависимости от контекста строка может быть декларацией фунции или переменной.

Нет, это всегда декларация функции.

Здравствуйте, Sergey J. A., Вы писали:

SJA>Здравствуйте, dimitry_dimitry, Вы писали:

_>>Здравствуйте, Sergey J. A., Вы писали:

SJA>>>Является ли грамматика С++ контекстнозависимой ? Если да, то можно простенький пример ?
SJA>>>Мне кажется, что да, и пример — x(); неясно вызов это функции x или создание объекта типа x. Но я не уверен...
_>>правильно не уверены%) потому что это может быть экземпляр класса с перегруженным оператором ()

SJA>Так что правильно-то ? Я не уверен, что грамматика С++ контекстнозависима. Она контекстно независима ?
нет. поэтому этот замечательный язык иногда является объектом нападок%)
SJA>Или мой пример не верен ?

Здравствуйте, Sergey J. A., Вы писали:

SJA>Так что правильно-то ? Я не уверен, что грамматика С++ контекстнозависима. Она контекстно независима ?
SJA>Или мой пример не верен ?
Определение понятия "контекстная зависимость" в студию.

А то я его в стандарте C++ не нашел

Здравствуйте, dimitry_dimitry, Вы писали:

SJA>>>>Является ли грамматика С++ контекстнозависимой ? Если да, то можно простенький пример ?
SJA>>>>Мне кажется, что да, и пример — x(); неясно вызов это функции x или создание объекта типа x. Но я не уверен...
_>>>правильно не уверены%) потому что это может быть экземпляр класса с перегруженным оператором ()

SJA>>Так что правильно-то ? Я не уверен, что грамматика С++ контекстнозависима. Она контекстно независима ?
_>нет. поэтому этот замечательный язык иногда является объектом нападок%)
То есть в таком случае я был "правильно уверен" ?

Здравствуйте, dimitry_dimitry, Вы писали:

SJA>>>>Является ли грамматика С++ контекстнозависимой ? Если да, то можно простенький пример ?
SJA>>>>Мне кажется, что да, и пример — x(); неясно вызов это функции x или создание объекта типа x. Но я не уверен...
_>>>правильно не уверены%) потому что это может быть экземпляр класса с перегруженным оператором ()

SJA>>Так что правильно-то ? Я не уверен, что грамматика С++ контекстнозависима. Она контекстно независима ?
_>нет. поэтому этот замечательный язык иногда является объектом нападок%)
SJA>>Или мой пример не верен ?

Тогда как это стыкуется с примером:
x();
Что тут x ? Тип или переменная (с переопределённым оператором () ) ? Вроде есть зависимость от контекста... ?

Здравствуйте, Sir Wiz, Вы писали:

SJA>>Так что правильно-то ? Я не уверен, что грамматика С++ контекстнозависима. Она контекстно независима ?
SJA>>Или мой пример не верен ?
SW>Определение понятия "контекстная зависимость" в студию.

SW>А то я его в стандарте C++ не нашел

Сам бы хотел услышать формальное определение контекстнозависимой грамматики.
Предполагаю, что это такая граматика в которой для разбора нужны некоторые дополнительные данные, собранные раньше в процессе разбора....
Яснее выразить не могу...

Здравствуйте, Sergey J. A., Вы писали:

SJA>Здравствуйте, dimitry_dimitry, Вы писали:

SJA>>>>>Является ли грамматика С++ контекстнозависимой ? Если да, то можно простенький пример ?
SJA>>>>>Мне кажется, что да, и пример — x(); неясно вызов это функции x или создание объекта типа x. Но я не уверен...
_>>>>правильно не уверены%) потому что это может быть экземпляр класса с перегруженным оператором ()

SJA>>>Так что правильно-то ? Я не уверен, что грамматика С++ контекстнозависима. Она контекстно независима ?
_>>нет. поэтому этот замечательный язык иногда является объектом нападок%)
SJA>То есть в таком случае я был "правильно уверен" ?
рискуя повториться в третий раз, скажу ДА.

SJA>>Является ли грамматика С++ контекстнозависимой ? Если да, то можно простенький пример ?
SJA>>Мне кажется, что да, и пример — x(); неясно вызов это функции x или создание объекта типа x.
SJA>>Но я не уверен...

W> Я думаю, что нет... вот сходу еще придумалось.

W>

W> void f1()
W> {
W>    int a,b,c;

W>    a < b > c;
W> }

W> template <class> struct a {};

W> void f2()
W> {
W>   typedef int b;
W>   a< b > c;
W> }
W>

Этот пример как раз иллюстрирует зависимость от контекста.

--
aga

Здравствуйте, Sergey J. A., Вы писали:

SJA>Сам бы хотел услышать формальное определение контекстнозависимой грамматики.
SJA>Предполагаю, что это такая граматика в которой для разбора нужны некоторые дополнительные данные, собранные раньше в процессе разбора....
SJA>Яснее выразить не могу...
Тогда да, конечно да. Я просто уверен, что да.

Простейшее: корректность выражения x = 1; зависит от того, был ли ранее и как продекларирован x.

Можно открыть стандарт и ввести поиск слова context. Найдется много замечаний насчет context-dependent и context-independent выражениях.

Здравствуйте, dimitry_dimitry, Вы писали:

SJA>>>>>>Является ли грамматика С++ контекстнозависимой ? Если да, то можно простенький пример ?
SJA>>>>>>Мне кажется, что да, и пример — x(); неясно вызов это функции x или создание объекта типа x. Но я не уверен...
_>>>>>правильно не уверены%) потому что это может быть экземпляр класса с перегруженным оператором ()

SJA>>>>Так что правильно-то ? Я не уверен, что грамматика С++ контекстнозависима. Она контекстно независима ?
_>>>нет. поэтому этот замечательный язык иногда является объектом нападок%)
SJA>>То есть в таком случае я был "правильно уверен" ?
_>рискуя повториться в третий раз, скажу ДА.

Первых два раза было больше похоже на "нет"

Здравствуйте, Sergey J. A., Вы писали:

SJA>Здравствуйте, dimitry_dimitry, Вы писали:

SJA>>>>>>>Является ли грамматика С++ контекстнозависимой ? Если да, то можно простенький пример ?
SJA>>>>>>>Мне кажется, что да, и пример — x(); неясно вызов это функции x или создание объекта типа x. Но я не уверен...
_>>>>>>правильно не уверены%) потому что это может быть экземпляр класса с перегруженным оператором ()

SJA>>>>>Так что правильно-то ? Я не уверен, что грамматика С++ контекстнозависима. Она контекстно независима ?
_>>>>нет. поэтому этот замечательный язык иногда является объектом нападок%)
SJA>>>То есть в таком случае я был "правильно уверен" ?
_>>рискуя повториться в третий раз, скажу ДА.

SJA>Первых два раза было больше похоже на "нет"
вы уж простите. я от Re[2]: char, потоки

Автор: Sir Wiz
Дата: 27.07.04

отойти не могу.

SW> Определение понятия "контекстная зависимость" в студию.

С++ (как и С) является контекстно-зависимым языком. Т.е. конструкцию языка не всегда можно распознать без знания ее более широкого контекста.


SW> А то я его в стандарте C++ не нашел

Дык этого в стандарте и не будет, я так думаю. Это в книге по теории компиляторов надо искать.

--
aga

Здравствуйте, Sir Wiz, Вы писали:

SJA>>Сам бы хотел услышать формальное определение контекстнозависимой грамматики.
SJA>>Предполагаю, что это такая граматика в которой для разбора нужны некоторые дополнительные данные, собранные раньше в процессе разбора....
SJA>>Яснее выразить не могу...
SW>Тогда да, конечно да. Я просто уверен, что да.

SW>Простейшее: корректность выражения x = 1; зависит от того, был ли ранее и как продекларирован x.

Вроде не совсем так. При разборе данного выражения нет неоднозначности — x должно быть переменной. А определена она или нет — это уже мне кажется ошибка другого рода... То есть если будет граматика типа :
expr: var operator const | var operator var | const operator const;
variable : IDENTIFIER;
const : NUMBER;
NUMBER : [0..9];
IDENTIFIER : [a..z_][a..z0-9_]*;
То можно однозначно построить дерево разбора.

А вот для x(); и граматики:
tmp_obj : type "(' ')';
par_operator : variable "(' ')';
type : IDENTIFIER; (1)
variable : IDENTIFIER; (2)
IDENTIFIER : [a..z_][a..z0-9_]*;
Нельзя точно сказать что такое x — type или variable. Поэтому при "подъёме" из IDENTIFIER в type или variable нужны контекстные данные для выбора. Вот.

Всё это только предположения... зря я не прочитал Ахо до конца...

SW>Можно открыть стандарт и ввести поиск слова context. Найдется много замечаний насчет context-dependent и context-independent выражениях.

Здравствуйте, dimitry_dimitry, Вы писали:

SJA>>Первых два раза было больше похоже на "нет"
_>вы уж простите. я от Re[2]: char, потоки

Автор: Sir Wiz
Дата: 27.07.04

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

Очень хорошее слово "ИМХО".
Вот и +1 за выдающуюся самокритику

Автор: dimitry_dimitry
Дата: 27.07.04

улетел

Здравствуйте, Андрей Галюзин, Вы писали:

SW>> Определение понятия "контекстная зависимость" в студию.

АГ>С++ (как и С) является контекстно-зависимым языком. Т.е. конструкцию языка не всегда можно распознать без знания ее более широкого контекста.

Меня вот ещё смущает такой вопрос... Ведь граматику можно построить упрощённую. Например:

statement : obj_or_type '(' ')';
obj_or_type : IDENTIFIER;
IDENTIFIER : [a-z_][a-z0-9_]*;

Теперь выражение x(); будет распознано однозначно. Нельзя ли написать для C/C++ такую простенькую контекстно свободную граматику ? А если можно, то как должен определяться порог "сложности" или "детальности" грамматики ?
Ведь я могу написать грамматику
program : TEXT;
TEXT : .*
?

Приветствуются также ссылки....

Здравствуйте, Sir Wiz, Вы писали:

SW>Здравствуйте, dimitry_dimitry, Вы писали:

SJA>>>Первых два раза было больше похоже на "нет"
_>>вы уж простите. я от Re[2]: char, потоки

Автор: Sir Wiz
Дата: 27.07.04

отойти не могу.
SW>Всё просто. Когда я вижу априоритивное, бездоказательное и нетерпящее возражений утверждение относительно весьма неоднозначных вещей, я становлюсь очень зол, у меня встаёт дыбом шерсть, из носа бьет пар, отрастают и немедленно начинают взбивать землю копыта, а шёлкаюшему хвосту позавидует кнут Барлога. Зверь дикий вобщем, наверное у меня детство тяжёлое было.

SW>Очень хорошее слово "ИМХО".
SW>Вот и +1 за выдающуюся самокритику

Автор: dimitry_dimitry
Дата: 27.07.04

улетел
да у меня тоже децтво не сахар было.
и не люблю я ссылки и С++ ИО-потоки, с ссылками я кстати объяснил почему.
а с потоками — из недавнего — человек сделал код с потоками — посмотрел по библиотекам — прицепилось еще 2 длл. ужос!!
и УБЛЮДОЧНО вы уж простите выглядит конструкция с потоками.
я ничего не имею против оператора << но в данном случае ...ну неудобно.
то ли дело printf. а?
а я себя не критиковал. я вас спросил.

Здравствуйте, Нахлобуч, Вы писали:


SJA>>>

_W>>>>int main()
_W>>>>{
_W>>>>  X x(); <- декларация фунции или переменная x ?
_W>>>>}
SJA>>>

D>>Нет, это всегда декларация функции.

Н>Эта строка является объявлением функции только тогда, когда она появляется в Global Scope, иначе это — вызов конструктора по умолчанию для объекта класса.

Предлагаю Вам самому убедиться в обратном:

#include <iostream>

class X
{
    X()
    {
        std::cout << "X::X() called";
    }
};

int main(int argc, char* argv[])
{
    X x();
    return 0;
}

Здравствуйте, Нахлобуч, Вы писали:

Вы пробовали запускать приведённый код? Что он вывел на экран?

Здравствуйте, mefrill, Вы писали:
M>Си++, как и большинство других языков программирования, контекстно зависим.
А можно примеры извесных контекстно свободных языков ?

Здравствуйте, Sergey J. A., Вы писали:

SJA>Здравствуйте, Андрей Галюзин, Вы писали:

SW>>> Определение понятия "контекстная зависимость" в студию.
АГ>>С++ (как и С) является контекстно-зависимым языком. Т.е. конструкцию языка не всегда можно распознать без знания ее более широкого контекста.
Насколько я помню курс Линвистики — Грамматика является контекстно независимой, если для проверки правильности программы (написанной по этой грамматике) достаточно выполнить синтаксический разбор. Т.е. грамматика калькулятора — контекстно независима, а грамматика языка С++ — контекстно зависима (требуется семантический разбор).

Н>Здесь же просто создание объекта класса X, это эквивалентно

Н>

Н>int main(int argc, char* argv[])
Н>{
Н>    X x;
Н>    return 0;
Н>}
Н>

Нет, это НЕ эквивалентно. Строчку в стандарте, где сказано обратное, можете привести?

Здравствуйте, davenger, Вы писали:

D>Здравствуйте, Нахлобуч, Вы писали:

D>Вы пробовали запускать приведённый код? Что он вывел на экран?

VC++ 2003 выдал свой Compiler Warning (level 1) C4930, а у Comeau все нормально. Но тогда почему

int x();

прокатывает?

SJA>А можно примеры извесных контекстно свободных языков ?
C, C++, Java, C#, you name it! Все языки программирования описываются контекстно-свободными грамматиками.

Н>VC++ 2003 выдал свой Compiler Warning (level 1) C4930, а у Comeau все нормально. Но тогда почему

Н>

Н>int x();
Н>

Н>прокатывает?
Да потому что это обьявление функции х, которая возвращает инт и не принимает аргументов!

G> Насколько я помню курс Линвистики — Грамматика является контекстно независимой, если для проверки правильности программы (написанной по этой грамматике) достаточно выполнить синтаксический разбор. Т.е. грамматика калькулятора — контекстно независима, а грамматика языка С++ — контекстно зависима (требуется семантический разбор).
Неправильно Вы помните, хотя бы потому, что существуют четыре вида грамматик по Хомскому, и для каждой грамматики существует свой распознаватель. Разница заключается только в том, что каждый распознаватель имеет свою вычислительную сложность.

Здравствуйте, <Аноним>, Вы писали:

А>

А>variable-declaration ::= type identifier ; |
А>                                type identifier ( argument-list ) ;
А>function-call        ::= identifier ( argument-list ) ;
А>

А>Курсивом выделены нетерминалы, темным — терминалы. Из этой, частичной граматики, неужели нельзя понять где обьявляется обьект а где вызывается функция? Для простоты, argument-list выводит как минимум один аргумент.

Но у меня в примере было немного по другому. x(); — x — тип (вызов функции или конструирование объекта) или x — переменная (вызов оператора () ). Как для такого варианта построить контекстно свободную граматику ?
Вот мой вариант КЗ:
(терминалы БОЛЬШИМИ БУКВАМИ и 'в кавычках')

statement : type '(' ')' | variable '(' ')' ;
type : IDENTIFIER;
variable : IDENTIFIER;
где
IDENTIFIER -> [a-z_][a-z0-9_]*

Но непонятно, как из IDENTIFIER перейти к type или variable. Нужны доп. данные.
Как для данного выражения построить КС ?

SJA>Но у меня в примере было немного по другому. x(); — x — тип (вызов функции или конструирование объекта) или x — переменная (вызов оператора () ). Как для такого варианта построить контекстно свободную граматику ?
Дайте лучше другой пример или в более полном контексте (не путать с контекстной грамматикой!) или загляните в Страуструпа. Непонятна эта фраза — x(); — x — тип (вызов функции или конструирование объекта) или x — переменная (вызов оператора () )

SJA>Вот мой вариант КЗ:
SJA>(терминалы БОЛЬШИМИ БУКВАМИ и 'в кавычках')

SJA>statement : type '(' ')' | variable '(' ')' ;
SJA>type : IDENTIFIER;
SJA>variable : IDENTIFIER;
SJA>где
SJA>IDENTIFIER -> [a-z_][a-z0-9_]*

SJA>Но непонятно, как из IDENTIFIER перейти к type или variable. Нужны доп. данные.
SJA>Как для данного выражения построить КС ?
Терминалы большими буквами да еще и продукция для IDENTIFIER? И вопрос последний тоже непонятен.

Здравствуйте, <Аноним>, Вы писали:

SJA>>Но у меня в примере было немного по другому. x(); — x — тип (вызов функции или конструирование объекта) или x — переменная (вызов оператора () ). Как для такого варианта построить контекстно свободную граматику ?
А>Дайте лучше другой пример или в более полном контексте (не путать с контекстной грамматикой!) или загляните в Страуструпа. Непонятна эта фраза — x(); — x — тип (вызов функции или конструирование объекта) или x — переменная (вызов оператора () )
А что тут непонятного ?
Вот полный пример:

class X {
public:
    int operator()() {
        return 666;
    };
};

int x() {
    return 999;
};

int main(int argc, char* argv[])
{
    {
        X x;
        int i = x();    //(1)
    }
    {
        int i = x();    //(2)
    }
    return 0;
}

Строки 1 и 2 одинаковые на вид, но в одном случае x это тип (функция), а в другом случае — переменная.
И без доп. данных это невозможно определить.

SJA>>Вот мой вариант КЗ:
SJA>>(терминалы БОЛЬШИМИ БУКВАМИ и 'в кавычках')

SJA>>statement : type '(' ')' | variable '(' ')' ;
SJA>>type : IDENTIFIER;
SJA>>variable : IDENTIFIER;
SJA>>где
SJA>>IDENTIFIER -> [a-z_][a-z0-9_]*

SJA>>Но непонятно, как из IDENTIFIER перейти к type или variable. Нужны доп. данные.
SJA>>Как для данного выражения построить КС ?
А>Терминалы большими буквами да еще и продукция для IDENTIFIER?
Я имел в виду, что терминалы обозначены большими буквами и символами в кавычках (так я в bison-е видел).
А продукция для IDENTIFIER: это я просто употребил неверный символ наверное "->"
Я имел в виду, что IDENTIFIER это последовательность букв, цифр и _ начинающаяся с _ или буквы.

А>И вопрос последний тоже непонятен.
Эт потому, что я и сам с трудом понимаю что говорю

Здравствуйте, mefrill, Вы писали:

M>На остальные аргументы я не считаю нужным отвечать просто потому, что это не аргументы. Мы сами с Вами говорим на разных языках . Относительно сложности реализации компилятора си++ через КС грамматику я могу отослать Вас к двум диссертациям Зуева и Кротова, посвященным как раз проблемам реализации языка. Но Вы, к сожалению, врядли их прочитаете.
Я! Я прочитаю! Пошлите меня, пожалуйста по указанному адресу!!!

Здравствуйте, mefrill, Вы писали:

LVV>>Я! Я прочитаю! Пошлите меня, пожалуйста по указанному адресу!!!

M>Зуевская диссертация лежит здесь: http://www.interstron.ru/publications.html. А насчет диссертации Александра Кротова надо наверное попростить его самого или кого-то из Интерстрона, чтобы выслали.
Большое спасибо, Владимир! Пока прочитаю Зуева. Это не его книжка по турбо паскалю в начале 90-х вышла?

LVV>Большое спасибо, Владимир! Пока прочитаю Зуева. Это не его книжка по турбо паскалю в начале 90-х вышла?

Честно говоря, не знаю, скорее всего. Он в МГУ преподавал, а потом уехал в Швейцарию, в Цюрих, не помню как у них университет называется, известный довольно.

Здравствуйте, mefrill, Вы писали:

M>Вот отсюда можно увидеть, что при предварительном объявлении некоторого имени, далее, при разборе предложения языка, при встрече некоторого имени мы должны как бы откатиться назад и пройти по всем объявлениям имен, чтобы узнать, было ли объявлено данной имя или нет.

А вот допустим я построю граматику, в которой не будет разницы между типом и переменной, а всё это будет identifier. Тогда граматика будет вроде как КС ? Вот мальенький пример:
Язык такой (показаны все допустимые конструкции). Идентификатор может быть function или variable. Затем его можно "активировать":
function f;
variable v;
f();
v();

Можно написать такую КС граматику:
program : /*empty*/ | statement_list
statement_list : statement | statement_list statement
statement : func_decl | var_decl | activate
func_decl : 'function' IDENTIFIER ';'
var_decl : 'variable' IDENTIFIER ';'
activate : IDENTIFIER '(' ')'

IDENTIFIER — набор букв.

Вроде граматика КС ? Разобрав ею программу и построив дерево можно приступить к определению что есть что в каждой конкретной "активизации".
Что тут не верно ?

Здравствуйте, Sergey J. A., Вы писали:

SJA>Здравствуйте, mefrill, Вы писали:

M>>Вот отсюда можно увидеть, что при предварительном объявлении некоторого имени, далее, при разборе предложения языка, при встрече некоторого имени мы должны как бы откатиться назад и пройти по всем объявлениям имен, чтобы узнать, было ли объявлено данной имя или нет.

SJA>А вот допустим я построю граматику, в которой не будет разницы между типом и переменной, а всё это будет identifier. Тогда граматика будет вроде как КС ? Вот мальенький пример:
SJA>Язык такой (показаны все допустимые конструкции). Идентификатор может быть function или variable. Затем его можно "активировать":
SJA>function f;
SJA>variable v;
SJA>f();
SJA>v();

SJA>Можно написать такую КС граматику:
SJA>program : /*empty*/ | statement_list
SJA>statement_list : statement | statement_list statement
SJA>statement : func_decl | var_decl | activate
SJA>func_decl : 'function' IDENTIFIER ';'
SJA>var_decl : 'variable' IDENTIFIER ';'
SJA>activate : IDENTIFIER '(' ')'

SJA>IDENTIFIER — набор букв.

SJA>Вроде граматика КС ? Разобрав ею программу и построив дерево можно приступить к определению что есть что в каждой конкретной "активизации".
SJA>Что тут не верно ?

Грамматика, конечно, контекстно свободная. Но, штука в том, что она не описывает тот язык, который Вы подразумеваете. Например, я пишу следущее:

b();

При разборе в соответствии только с вышеприведенной грамматикой, все будет хорошо, мы получим следующий вывод (дерево разбора):

program ==> statement_list ==> statement ==> activate ==> IDENTIFIER '(' ')'

Но это дерево не дает нам полной иинформации о программе и вообще, корректно допускает некорректное предложение языка. Здесь дело как раз в условии предварительного объявления. Нам надо это условие каким-то образом выразить в самой грамматике. Вот, если грамматика эта КС, то выразить не удается. Приходится КЗ грамматику определять, но методы разбора языков, задаваемых через КЗ-грамматики, очень сложные. Гораздо легче, определить КС-грамматику, котороя, строго говоря, не описывает язык, а какие-то Кз свойства языка сделать вручную и назвать "сеантикой" языка. В нашем случае, это свойство предварительного объявления имен, используемых в программе. Искать на ленте это объявление, как я показывал выше, долго, медленнее линейног времени и, если и нет, то константа очень большая. А вот реализуя это свойство вручную, мы поиск имен можем сделать логорифмическим, используя какою-нибудь хеш таблицу. Выгода налицо. Но сам язык от этой особенности реализации не стал контекстно свободным. Это ведь характеристика языка, а не метода разбора

[skipped]

> А ничего и не надо убирать! Грамматика С++ — контекстно-свободная грамматика, и потому, этот
> язык сам и является контекстно-свободным.

Хм. В таком случае, как разобрать выражение x * y не зная контекста (классика жанра)?

--
aga

Здравствуйте, mefrill, Вы писали:

M>Грамматика, конечно, контекстно свободная. Но, штука в том, что она не описывает тот язык, который Вы подразумеваете. Например, я пишу следущее:

M>b();

M>При разборе в соответствии только с вышеприведенной грамматикой, все будет хорошо, мы получим следующий вывод (дерево разбора):

M>program ==> statement_list ==> statement ==> activate ==> IDENTIFIER '(' ')'

M>Но это дерево не дает нам полной иинформации о программе и вообще, корректно допускает некорректное предложение языка. Здесь дело как раз в условии предварительного объявления. Нам надо это условие каким-то образом выразить в самой грамматике. Вот, если грамматика эта КС, то выразить не удается. Приходится КЗ грамматику определять, но методы разбора языков, задаваемых через КЗ-грамматики, очень сложные. Гораздо легче, определить КС-грамматику, котороя, строго говоря, не описывает язык, а какие-то Кз свойства языка сделать вручную и назвать "сеантикой" языка. В нашем случае, это свойство предварительного объявления имен, используемых в программе. Искать на ленте это объявление, как я показывал выше, долго, медленнее линейног времени и, если и нет, то константа очень большая. А вот реализуя это свойство вручную, мы поиск имен можем сделать логорифмическим, используя какою-нибудь хеш таблицу. Выгода налицо. Но сам язык от этой особенности реализации не стал контекстно свободным. Это ведь характеристика языка, а не метода разбора

Так. Кажется понял. То есть все предложения(тексты?), которые может породить граматика должно быть верной программой (в смысле компилироваться, а не работать) ? Тогда эта граматика является собственно граматикой языка ?
И если я правильно понял, то обычно компиляторы пользуются некоторой КС граматикой, которая более/менее описывают язык, а потом производят доп. обработку — семантический анализ ?

SJA>Так. Кажется понял. То есть все предложения(тексты?), которые может породить граматика должно быть верной программой (в смысле компилироваться, а не работать) ? Тогда эта граматика является собственно граматикой языка ?
SJA>И если я правильно понял, то обычно компиляторы пользуются некоторой КС граматикой, которая более/менее описывают язык, а потом производят доп. обработку — семантический анализ ?

В точности так. Потому, что свойство языка быть КС или КЗ — это свойство языка и, следовательно, всех, описывающих его, грамматик. А синитаксический анализатор сейчас обычно реализуется в виде двух компонентов: синтаксического анализатора, анализирующего КС подмножество языка и семантического анализатора, анализирующего оставшуюся, чаще всего КЗ, часть языка. Но все это вместе все равно есть синтаксический анализатор языка.

Здравствуйте, LaptevVV, Вы писали:

LVV>Здравствуйте, Sergey J. A., Вы писали:

SJA>>Является ли грамматика С++ контекстнозависимой ? Если да, то можно простенький пример ?
SJA>>Мне кажется, что да, и пример — x(); неясно вызов это функции x или создание объекта типа x. Но я не уверен...
LVV>Ни один из современных языков программирования на практике не описывается контекстно-зависимыми грамматиками, исключительно контестно-свободными (из соображений эффективности, кстати. Распознавание контекстно-зависимых языков требует экспоненциального времени, тогда как КС-языки распознаются в общем случае за полиномиальное время). Но помимо этого, конечно, в каждом компиляторе проверяются не контекстно-свободные характеристики, к которым относятся, например, требование единственности объявления или "сначала объяви, потом используй". Единственный язык, в котором использовалась не КС-грамматика — Алгол-68. Ван Вейнгартен изобрел для него специальные двухуровневые грамматики — видимо без этого невозможно было описать введение новых операций в процессе выполнения программы.

C++\CLI кстати содержит context-bound keywords.

Здравствуйте, Sergey J. A., Вы писали:

SJA>Является ли грамматика С++ контекстнозависимой ? Если да, то можно простенький пример ?
SJA>Мне кажется, что да, и пример — x(); неясно вызов это функции x или создание объекта типа x. Но я не уверен...

Грамматика языка описывает его синтаксис. А то, что ты иллюстрируешь своим примером с 'x()' — это уже семантика, которая, формально выражаясь, никакого отношения к грамматике не имеет. Разумеется, на практике грамматики языков стремятся формировать так, чтобы они адекватно отображали семантику эти языков. Это весьма разумно и упрощает написание трансляторов. Но, еще раз, к констекстной [не]зависимости грамматики это все равно никакого отношения не имеет.

Грамматика языка С++ не содержит правил с множественными лексемами в левой части — значит она контекстно независима по определению.

Здравствуйте, Sergey J. A., Вы писали:

SJA>Тогда как это стыкуется с примером:
SJA>x();
SJA>Что тут x ? Тип или переменная (с переопределённым оператором () ) ? Вроде есть зависимость от контекста... ?

Зависмость семантического смысла конструкции от контекста, размеется, есть. Но ни к грамматике, ни к ее контекстной независимости это никакого отношения не имеет.

Здравствуйте, Андрей Галюзин, Вы писали:

АГ>[skipped]

>> А ничего и не надо убирать! Грамматика С++ — контекстно-свободная грамматика, и потому, этот
>> язык сам и является контекстно-свободным.

АГ>Хм. В таком случае, как разобрать выражение x * y не зная контекста (классика жанра)?

А в чем проблема? Если это относительно полное [под]выраждение, то очень просто:

      *
    /  \
  /      \
 x        y

Здравствуйте, Андрей Тарасевич, Вы писали:

АТ>Здравствуйте, Sergey J. A., Вы писали:

SJA>>Является ли грамматика С++ контекстнозависимой ? Если да, то можно простенький пример ?
SJA>>Мне кажется, что да, и пример — x(); неясно вызов это функции x или создание объекта типа x. Но я не уверен...

АТ>Грамматика языка описывает его синтаксис. А то, что ты иллюстрируешь своим примером с 'x()' — это уже семантика, которая, формально выражаясь, никакого отношения к грамматике не имеет. Разумеется, на практике грамматики языков стремятся формировать так, чтобы они адекватно отображали семантику эти языков. Это весьма разумно и упрощает написание трансляторов. Но, еще раз, к констекстной [не]зависимости грамматики это все равно никакого отношения не имеет.

АТ>Грамматика языка С++ не содержит правил с множественными лексемами в левой части — значит она контекстно независима по определению.

Мы же это уже обсуждали выше. То, о чем ты говоришь, конечно КС-грамматика, но она си++ не определяет, а только его подмножество, т.е. немного другой язык. Ведь в данной грамматике никак не выражена необходимость объявлять имя до его использования? Верно? Значит, грамматика язык не полностью определяет. Так часто делается, часть языка выражается грамматикой, другая — КЗ часть, парсится вручную и это называется семантикой языка. Мы же говорим о свойстве самого языка си++, какой он? Т.е. найдется ли КС грамматика, полностью описывающая весь язык полностью? Я утверждаю, что нет. Что в моем рассуждении неверно?

M>Ведь в данной грамматике никак не выражена необходимость объявлять имя до его использования? Верно? Значит, грамматика язык не полностью определяет.
хм. интересно.
вот к примеру, как грамматикой русского языка определено то, что нельзя составить предложение из пяти прилагательных?

АТ>Все это хорошо, но тем не менне не имеет никакого отношения к исходному вопросу. Вопрос был о том, является ли грамматика языка С++ контекстно зависимой. Ответ однозначен — не является. Грамматика языка С++ является контекстно свободной по определению, т.к. в левой части каждого правила этой грамматики стоит ровно один нетерминал. Все.

АТ>Все остальные рассуждения и примеры, которые тут обильно привдятся, на самом деле не имеют никакого отношения к грамматике языка С++.
Во! My man! Поддерживаю на все сто!

Здравствуйте, dimitry_dimitry, Вы писали:

_>а с потоками — из недавнего — человек сделал код с потоками — посмотрел по библиотекам — прицепилось еще 2 длл. ужос!!
_>я ничего не имею против оператора << но в данном случае ...ну неудобно.
_>то ли дело printf. а?

Есть такая замечательная книга "Защищённый код" М. Лебланк, М. Ховард, в этой книге в 5-ой главе, посвящённой переполнению буфера, очень наглядно показано как с использованием printf-функций можно совершать неявные ошибки, открывающие дорогу к взлому вашего приложения. Допустить аналогичные ошибки с помощью потоков значительно труднее. Между количеством библиотек и надёжностью приложения лично я выбираю 2-ое.

M>На остальные аргументы я не считаю нужным отвечать просто потому, что это не аргументы. Мы сами с Вами говорим на разных языках .
Во-во! Мы действительно говорим на разных языках, и кто-то из нас не понимает теорию формальных языков и трансляции. Думаю, что это все-таки не я!

M>Относительно сложности реализации компилятора си++ через КС грамматику я могу отослать Вас к двум диссертациям Зуева и Кротова, посвященным как раз проблемам реализации языка.
Это что это за диссертации такие? Я всегда считал, что человек делает original research, затем пишет диссертацию и защищает ее. А тут они делают, что уже сделано другими и никаких оригинальных исследований?
M>Но Вы, к сожалению, врядли их прочитаете.
Говорите за себя! У меня есть хорошая литература, которую я могу почитать!

M>И могу Ва уверить также, что под неоднозначностью я понимал именно то, что имеется ввиду в теории формальных языков.
Сомневаюсь.

Здравствуйте, Mr. None, Вы писали:

MN>Здравствуйте, dimitry_dimitry, Вы писали:

_>>а с потоками — из недавнего — человек сделал код с потоками — посмотрел по библиотекам — прицепилось еще 2 длл. ужос!!
_>>я ничего не имею против оператора << но в данном случае ...ну неудобно.
_>>то ли дело printf. а?

MN>Есть такая замечательная книга "Защищённый код" М. Лебланк, М. Ховард, в этой книге в 5-ой главе, посвящённой переполнению буфера, очень наглядно показано как с использованием printf-функций можно совершать неявные ошибки, открывающие дорогу к взлому вашего приложения. Допустить аналогичные ошибки с помощью потоков значительно труднее. Между количеством библиотек и надёжностью приложения лично я выбираю 2-ое.
наверное фабула там в том, что можно подсовывать на выполнение свой код?
а дайте ссылку пжалста?

Здравствуйте, mefrill, Вы писали:

SJA>>>Является ли грамматика С++ контекстнозависимой ? Если да, то можно простенький пример ?
SJA>>>Мне кажется, что да, и пример — x(); неясно вызов это функции x или создание объекта типа x. Но я не уверен...

АТ>>Грамматика языка описывает его синтаксис. А то, что ты иллюстрируешь своим примером с 'x()' — это уже семантика, которая, формально выражаясь, никакого отношения к грамматике не имеет. Разумеется, на практике грамматики языков стремятся формировать так, чтобы они адекватно отображали семантику эти языков. Это весьма разумно и упрощает написание трансляторов. Но, еще раз, к констекстной [не]зависимости грамматики это все равно никакого отношения не имеет.

АТ>>Грамматика языка С++ не содержит правил с множественными лексемами в левой части — значит она контекстно независима по определению.

M>Мы же это уже обсуждали выше. То, о чем ты говоришь, конечно КС-грамматика, но она си++ не определяет, а только его подмножество, т.е. немного другой язык. Ведь в данной грамматике никак не выражена необходимость объявлять имя до его использования? Верно? Значит, грамматика язык не полностью определяет. Так часто делается, часть языка выражается грамматикой, другая — КЗ часть, парсится вручную и это называется семантикой языка. Мы же говорим о свойстве самого языка си++, какой он? Т.е. найдется ли КС грамматика, полностью описывающая весь язык полностью? Я утверждаю, что нет. Что в моем рассуждении неверно?

Ну это уже зависит от того, что же понимать под термином "грамматика" языка С++. Если то и только то, что приводится в соответствующем разделе стандарта ("грамматика" в узком толковании термина) — то эта грамматика очевидным образом КС.

Затем можно досыпать к этому еще набор очевидно чисто грамматических правил, которые в стандарте языка изложены "на словах", и получить "грамматику" в широком толковании термина. Например, правило, запрещающее пустые декларации. В принципе, я думаю, такие правила можно было внести в грамматику (в узком толковании) и при этом сохранить ее как КС, но это черезмерно бы ее усложнило. Поэтому эти дополнительные правила было решено изложить "на словах" (что, как известно, привело к тому, что многие компиляторы забывают эти правила проверять).

Ну и наконец ко всему этому можно еще обавить еще и такие правила, как требования объявления перед использованием и контроля типов, и получить "грамматику" в супершироком толковании термина (ни о каком КС при этом, разумеется, уже речи быть не может), но мне это кажется уже перебором.

Здравствуйте, <Аноним>, Вы писали:

А>Если Вы так уверены, что С++ контекстно-зависимый язык, то продукции, которые "требуют обьявления переменной до использования" — в студию!
Что такое

a<b>c;

Ы?
Если

template<class>
struct a{};
struct b{};

то это обьявление переменной c.
А если

int a, b, c;

то это хоть и безсмысленное но вполне корректное с точки зрения С++ выражение.
Вот и попробуй разрулить это КС грамматикой
И если внимательно посмотреть на ту грамматику С++ что в стандарте то не смотря на то что она выглядит как КС без анализа контекста ни чего не выдет.

Здравствуйте, dimitry_dimitry, Вы писали:

_>Здравствуйте, Mr. None, Вы писали:

MN>>Здравствуйте, dimitry_dimitry, Вы писали:

_>>>а с потоками — из недавнего — человек сделал код с потоками — посмотрел по библиотекам — прицепилось еще 2 длл. ужос!!
_>>>я ничего не имею против оператора << но в данном случае ...ну неудобно.
_>>>то ли дело printf. а?

MN>>Есть такая замечательная книга "Защищённый код" М. Лебланк, М. Ховард, в этой книге в 5-ой главе, посвящённой переполнению буфера, очень наглядно показано как с использованием printf-функций можно совершать неявные ошибки, открывающие дорогу к взлому вашего приложения. Допустить аналогичные ошибки с помощью потоков значительно труднее. Между количеством библиотек и надёжностью приложения лично я выбираю 2-ое.
_>наверное фабула там в том, что можно подсовывать на выполнение свой код?
_>а дайте ссылку пжалста?

Примерно. Ссылку уже дал: книга "Защищённый код" М. Лебланк, М. Ховард. Можно купить например здесь

WH>Что такое
WH>

WH>a<b>c;
WH>

WH>Ы?
WH>Если
WH>

WH>template<class>
WH>struct a{};
WH>struct b{};
WH>

WH>то это обьявление переменной c.
WH>А если
WH>

WH>int a, b, c;
WH>

WH>то это хоть и безсмысленное но вполне корректное с точки зрения С++ выражение.
WH>Вот и попробуй разрулить это КС грамматикой
Грамматика ничего не "разруляет!" Грамматика лишь используется для порождения правильных цепочек языка, и генератором в данном случае является программист!

Подумаешь привели выражение выше!!! Если просто проверить строку на принадлежность С++, то тебе не все равно какая продукция вывела эту строку? Ы?

WH>И если внимательно посмотреть на ту грамматику С++ что в стандарте то не смотря на то что она выглядит как КС без анализа контекста ни чего не выдет.
Она не выглядит! Она есть КС грамматика! За пример, что ты привел выше отвечает семантический анализатор!

Считываем "a". Просматриваем таблицу символов. Если "а" имя шаблонного класса, то находится одна продукция. Если же "а" имя переменной, то ищется другая продукция! Все.

ЗЫ. Еще раз повторю, грамматика описывает синтаксис языка, и строка a<b>c синтаксически верна чем бы не были a, b и с. Другое дело, что семантически эта конструкция не имела бы смысла!

А>Неправильно Вы помните, хотя бы потому, что существуют четыре вида грамматик по Хомскому, и для каждой грамматики существует свой распознаватель. Разница заключается только в том, что каждый распознаватель имеет свою вычислительную сложность.

Правильно, более того для С++ можно построить контекстно-независимую грамматику. Например в приложении к "Dragon Book"-у есть LALR(1) грамматика для Yacc-а.

> M>Ведь в данной грамматике никак не выражена необходимость объявлять имя до его использования? Верно? Значит, грамматика язык не полностью определяет.

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

Давайте не смешивать два разных значения слова "грамматика".

Здравствуйте, <Аноним>, Вы писали:

WH>>И если внимательно посмотреть на ту грамматику С++ что в стандарте то не смотря на то что она выглядит как КС без анализа контекста ни чего не выдет.
А>Она не выглядит! Она есть КС грамматика! За пример, что ты привел выше отвечает семантический анализатор!

А>Считываем "a". Просматриваем таблицу символов. Если "а" имя шаблонного класса, то находится одна продукция. Если же "а" имя переменной, то ищется другая продукция! Все.

А я то думал, что если в процессе поиска нужной продукции нужна доп. информация (здесь таблица символов), то это уже не КС ?

SJA>А я то думал, что если в процессе поиска нужной продукции нужна доп. информация (здесь таблица символов), то это уже не КС ?
Языки программирования описываются КС грамматиками. В Вашем предложении ключевые слова — "в процессе поиска нужной продукции." Таблица символов нужна для выявления смысловой нагрузки конструкций языка.

Здравствуйте, <Аноним>, Вы писали:

SJA>>А я то думал, что если в процессе поиска нужной продукции нужна доп. информация (здесь таблица символов), то это уже не КС ?
А>Языки программирования описываются КС грамматиками.
Да вроде выяснили уже, что КЗ...

А>В Вашем предложении ключевые слова — "в процессе поиска нужной продукции." Таблица символов нужна для выявления смысловой нагрузки конструкций языка.
А что, выбор нужной продукции, это уже не относится к граматике ?

SJA>Да вроде выяснили уже, что КЗ...
Не знаю, что вы там выяснили, но нутром чую, что выяснили неправильно.

SJA>А что, выбор нужной продукции, это уже не относится к граматике ?
Нет, не относится. На синтаксическом уровне одну и ту же строку можно вывести разными продукциями.

Здравствуйте, <Аноним>, Вы писали:

SJA>>А что, выбор нужной продукции, это уже не относится к граматике ?
А>Нет, не относится. На синтаксическом уровне одну и ту же строку можно вывести разными продукциями.
Что-то я совсем запутался....
Как говорил mefrill:

А в КС-грамматиках такого нет, нетерминал всегда значит одно и то же, поэтому там все правила имеют вид A --> alpha B beta, что можно обозначить просто как A --> alpha, т.к. alpha это строка нетерминальных и терминальных символов.

То есть вроде как A это всегда alpha, но alpha всегда ли это A ?
В нашем примере при одном и том же alpha есть 2 продукции:
A -> alpha
B -> alpha
Разве может быть такая граматика ? Не является ли она "противоречивой", или как оно там называется ?

SJA>То есть вроде как A это всегда alpha, но alpha всегда ли это A ?
SJA>В нашем примере при одном и том же alpha есть 2 продукции:
SJA>A -> alpha
SJA>B -> alpha
SJA>Разве может быть такая граматика ? Не является ли она "противоречивой", или как оно там называется ?

Такая грамматика вполне может быть, хотя, конечно, большого смысла это не имеет и ведет к неоднозначности. Как можно определить неоднозначность грамматики? Просто, если при разборе некоторого предложения x1x2...xn его можно разобрать хотя бы двумя разными способами, что значит вывести из стартового символа грамматики S строку x1x2...xn, то такая грамматика называется неоднозначной. В нашем случае, если из alpha выводится строка xixi+1...xk например, то мы имеем сразу два дерева разбора:

S
/ A \
/ alpha \
x1x2...xi-1 xi...xk xk+1xk+2...xn

S
/ B \
/ alpha \
x1x2...xi-1 xi...xk xk+1xk+2...xn

Таким образом, грамматика является неоднозначной, одно и тоже предложение выводится двумя различными способами. Вопрос, можно ли эту грамматику трансформировать так, чтобы она определяла тот же язык, но при этом грамматика была однозначной. Иногда можно, иногда нет. Язык, для которого не существует однозначной грамматики называется существенно неоднозначным. Можно ли по грамматике узнать, является ли она однозначной или нет? Нельзя, эта проблема алгоритмически неразрешима, т.е. не существует универсального алгоритма, котрый решает эту задачу. Проблема с парсингом си++ состоит не в том, что грамматика языка есть КЗ, как мы видели, это решается с помощью определения "семантических" свойств языка, а в том, что язык си++ существенно неоднозначен. Поэтому при разработке компиляторов начинаются проблемы когда используют инструменты типа бизона. Бизон, за исключением последних версий, реализует алгоритм анализа, называемый LALR(k), где число k обычно равно единице. Этот алгоритм есть небольшое улучшение алгоритма LR(k)-анализа. Теримнология была введена Кнутом в 1965 году: L значит, что предложение читается слева направо, R обозначает, что при выводе каждый раз заменяется крайний правый нетерминал, например:

S --> AB
A --> a
B --> b

При выводе строки ab получим: S ==> AB ==> Ab ==> ab

Кроме того, анализ ведется снизу-вверх, т.е. сначала подбирается правая часть правила и потом заменяется на нетерминал в левой части. Кнут придумал алгоритм, который для некоторых КС-граммматик производит такой разбор за линейное время относительно длины разбираемой строки. Линейное значит, что у нас нет правил вида:


A -> alpha
B -> alpha

так как при разборе получая строку alpha надо будет решить на какой нетерминал ее заменить. Обычно поступают так: сначала пробуют подставить первый нетерминал, если не получится вывода, то второй. При линейном времени, очевидно, это не получится. Можно попытаться посмотреть вперед на k символов чтобы решить какой нетерминал выбрать, в этом и состоит идея Кнута, но, к сожалению, существуют грамматики, для которых это узнать невозможно ни для какого, сколь угодно большого, числа k. Вот из-за таких вот неоднозначностей разбор си++ с бизоном проблематичен. Есть модификации бизона, позволяющие, при встрече альтернативных нетерминалов, пройти немного вперед при анализе и потом, когда будет известно, какой нетерминал выбрать, возвратиться назад. Понятно, что здесь о линейном времени говорить не приходиться. Алгоритм Томиты, введенный им в 1984 году при такой встрече производит параллельный анализ всех альтернатив (вот где простор для многопоточных анализаторов!) и, в результате, получает все деревья вывода, которые существуют. Есть еще несколько алгоритмов, позволяющих сделать такой анализ, например алгоритм Эрли. Анализатор на основе этого алгоритма был реализован мной при работе над диссертацией. В общем, парсер Си++ написать не сложно, но только не с LR(k)-анализатором.

Здравствуйте, ssm, Вы писали:

ssm>измерения

исчисления

Здравствуйте, Areg, Вы писали:

А>>Неправильно Вы помните, хотя бы потому, что существуют четыре вида грамматик по Хомскому, и для каждой грамматики существует свой распознаватель. Разница заключается только в том, что каждый распознаватель имеет свою вычислительную сложность.

A>Правильно, более того для С++ можно построить контекстно-независимую грамматику. Например в приложении к "Dragon Book"-у есть LALR(1) грамматика для Yacc-а.

Данная грамматика (как впрочем и практически все другие грамматики С++) базируется на предположении, что _сканнер_ (aka lexer) распознает (основываясь на информации собранной ранее парсером), является ли имя просто идентификатором, именем типа, именем шаблона или именем namespace'а.
Так что строго говоря, то что предлашается в этом приложении не есть классическая LALR(1) грамматика...

Здравствуйте, mefrill, Вы писали:

M>Здравствуйте, Андрей Тарасевич, Вы писали:

АТ>>Здравствуйте, Sergey J. A., Вы писали:

SJA>>>Является ли грамматика С++ контекстнозависимой ? Если да, то можно простенький пример ?
SJA>>>Мне кажется, что да, и пример — x(); неясно вызов это функции x или создание объекта типа x. Но я не уверен...

АТ>>Грамматика языка описывает его синтаксис. А то, что ты иллюстрируешь своим примером с 'x()' — это уже семантика, которая, формально выражаясь, никакого отношения к грамматике не имеет. Разумеется, на практике грамматики языков стремятся формировать так, чтобы они адекватно отображали семантику эти языков. Это весьма разумно и упрощает написание трансляторов. Но, еще раз, к констекстной [не]зависимости грамматики это все равно никакого отношения не имеет.

АТ>>Грамматика языка С++ не содержит правил с множественными лексемами в левой части — значит она контекстно независима по определению.

M>Мы же это уже обсуждали выше. То, о чем ты говоришь, конечно КС-грамматика, но она си++ не определяет, а только его подмножество, т.е. немного другой язык. Ведь в данной грамматике никак не выражена необходимость объявлять имя до его использования? Верно? Значит, грамматика язык не полностью определяет. Так часто делается, часть языка выражается грамматикой, другая — КЗ часть, парсится вручную и это называется семантикой языка. Мы же говорим о свойстве самого языка си++, какой он? Т.е. найдется ли КС грамматика, полностью описывающая весь язык полностью? Я утверждаю, что нет.

Скорее всего, это правда, но я, например, формального доказательства не видел.

А с другой стороны, я не видел доказательства другого факта -- что С++ может быть задан контекстно-зависимой грамматикой.

M>Что в моем рассуждении неверно?

Всё верно, только не хватает строгого доказательства невозможности построить КС грамматику, задающую язык. Или хотя бы ссылки.

Копай Нео, копай -- летать научишься. © Matrix. Парадоксы

Здравствуйте, <Аноним>, Вы писали:

А>Очень хорошо все изложено, но в конце последнего параграфа у Вас заблуждение.

Да нет, это у вас непонимание элементарных вещей. Есть язык C++, есть множество well-formed программ на этом языке, которое представляет из себя некоторое множество конечных цепочек букв. Так вот, это множество не может быть определено через КС грамматику. Это и означает, что C++ не контекстно свободный язык. Будем спорить, что 2+2==4?

Копай Нео, копай -- летать научишься. © Matrix. Парадоксы

Ш>Всё верно, только не хватает строгого доказательства невозможности построить КС грамматику, задающую язык. Или хотя бы ссылки.

Ну, для любого языка с предварительным объявлением имен: есть лемма о накачке для КС языков еще известная как лемма Огдена. Вот с помощью ентой леммы легко доказать, что язык, состоящий из двух подряд идущих строк неизвестной заранее длины и состоящих из алфавита мощностью более одного, не являетс КС. А это как раз подязык любого языка с предварительным объявлением имен.

Владимир.

Здравствуйте, <Аноним>, Вы писали:

Ш>>Да нет, это у вас непонимание элементарных вещей. Есть язык C++, есть множество well-formed программ на этом языке, которое представляет из себя некоторое множество конечных цепочек букв.
А>Может дадите определение ваших "well-formed программ на этом языке?"

Читайте стандарт. По простому, well-formed программа -- это то, что компилятор C++, написанный в соответствии со стандартом, должен пропустить через себя и сгенерировать некоторый объектный код.

Ш>>Так вот, это множество не может быть определено через КС грамматику.
А>Кто вам это сказал?

Это доказано. Математически строго.
Читайте этот тред, а так же специальную литературу.

Ш>>Будем спорить, что 2+2==4?
А>Не въехал...

Вы пытаетесь оспорить, что 2+2==4. Таких людей обычно посылают в дет. сад.

Копай Нео, копай -- летать научишься. © Matrix. Парадоксы

А>Пришла зима. Нестерпимая жара установилась на дворе. Грамматика С++ — контекстно-свободная! В этом форуме куча тем. Кто из нас всех прав? Опять пришла зима и т.д.
А>[/q]
А>Это пример из русского языка. Как видите, с точки зрения русской грамматики параграф и все предложения верны, но тем не менее смысла они не имеют. Точно также и с С++. Даже Лаптев, вон, выше заметил, что языки описываются КС грамматиками.

То, о чем Вы говорите как о грамматике русского языка и порождающая грамматика Хомского, это, как говорят в Одессе, две большие разницы.

Неужели так трудно внимательно проситать то, о чем здесь выше говорилось? Как об стенку горох, честное слово! Как в том анекдоте: папа, а ты с кем сейчас разговаривал? Мне кажется, тут дело либо в невнимательности (если не в чем похуже!), либо в элементарном неуважении к собеседнику.

M>То, о чем Вы говорите как о грамматике русского языка и порождающая грамматика Хомского, это, как говорят в Одессе, две большие разницы.
А Вы считаете, что предложения русского и английских языков, например, не могут быть описаны порождающей грамматикой Хомского? Если да, то Вы ОШИБАЕТЕСЬ!!! Как Вы сами и знаете, КЗ грамматики используются в переводчиках с одного естественного языка на другой, и пример с грамматикой русского языка и грамматикой С++ очень хорошо описывает сущность этих грамматик!

M>Неужели так трудно внимательно проситать то, о чем здесь выше говорилось? Как об стенку горох, честное слово!
Это я должен сказать "как об стенку горох, честное слово!"

M>Мне кажется, тут дело либо в невнимательности (если не в чем похуже!), либо в элементарном неуважении к собеседнику.
Мне тоже так кажется, но только дело здесь в том, что это ВЫ не желаете прислушаться к тому, что здесь говорят.

Здравствуйте, <Аноним>, Вы писали:

А>Используя грамматику С++, можно вывести следующую функцию:
А>

А>void foo()
А>{
А>       int i;
А>       return i;   // Все синтаксически здесь верно!!!
А>}
А>

Это не есть well-formed программа на языке С++. Грамматика языка должна описывать все well-formed программы и только well-formed программы. Если грамматика описывает все well-formed и еще множество не well-formed программ то это не грамматика данного языка. Исключить множество не well-formed программ языка С++ можно только при помощи КЗ грамматики.
Но тк КЗ грамматика это очень сложно то используют компромисный вариант. Создают КС грамматику которая описывает язык являющеяси над множеством данного языка и создают допольнительные правила для отсечения не well-formed программ. И сделано это не по тому что грамматика языка КС, а по тому что построение КЗ грамматики во первых очень сложный процесс сам по себе во вторых парсер получается ну ооочееень медленный.

Здравствуйте, Аноним, Вы писали:

M>>То, о чем Вы говорите как о грамматике русского языка и порождающая грамматика Хомского, это, как говорят в Одессе, две большие разницы.
А>А Вы считаете, что предложения русского и английских языков, например, не могут быть описаны порождающей грамматикой Хомского? Если да, то Вы ОШИБАЕТЕСЬ!!! Как Вы сами и знаете, КЗ грамматики используются в переводчиках с одного естественного языка на другой, и пример с грамматикой русского языка и грамматикой С++ очень хорошо описывает сущность этих грамматик!

Так дискуссию вести невозможно, аргументы игнорируются, очевидные факты отвергаются. Поэтому, пытаюсь объяснить в последний раз:

Языком является множество строк, сформированных из символов данного алфавита. Порождающая грамматика Хомского — это устройство для порождения данных строк и только их. Язык может описываться не только порождающей грамматикой Хомского, а также и другими, каковых сущесвтует великое множество, как порождающих, так и не порождающих. кроме того, язык может быть описан без всякой грамматики. Например, предложение "множество сттрок, состоящих из нуля и более символов а" великолепно описывает язык, который задает грамматика:
S --> aS | пустая строка

Здесь ГДЕ-НИБУДЬ о семантике хоть слово было произнесено? Семанитка языка (в ее настоящем смысле, т.е. интепретация строк языка человеком) не имеет никакого отношения к описанию структуры строк языка (его предложений). Этим занимает синтаксис. Например, мы могли бы интерпретировать описанный выше язык так: символ а значит произнесение звука а в течении одной секунды. Тогда строка ааа обозначала бы, что некий человек пропел а-а-а... три секунды подряд. То же самое и в си++. Множество предложений данного языка это (с некоторым обобщением) множество правильных программ, написанных на языке си++. Вот и встает задача: описать это множество программ, используя ТОЛЬКО порождающую грамматику Хомского. Это сделать можно, как возможно описать любые структурные построения (например, множество музыкальных этюдов). Но, КС-грамматика для этого не подойдет из-за свойства языка: каждое имя должно быть описано перед его использованием. Как я уже писал выше, данное свойство не может быть выражено КС-грамматикой. Так что все просто. Разумеется, язык можно описывать и не используя порождающие грамматики, а как-нибудь по другому. Например, как это делается в стандарте языка си++. Чать описывается КС-грамматикой. Но такое описание позволяет породить и неверные программы на си++. Поэтому, вводятся еще ограничения, причем в виде так называемых "семантических" правил. Это делать можно, но почему же при этом говорить, что КС-грамматика, описывающая часть языка, описывает весь язык!? С таким же успехом, я могу описать часть языка регулярной грамматикой, а остальную часть неформально на русском языке и сказать, что граматика языка си++ регулярна. Но это не так, конечно.

Именно, понимание выразительной способности разных классов грамматик и составляет понимание идеи Хомского. Еще раз, в книге "Техники парсинга" есть такой рисунок:


здесь

Владимир.

Здравствуйте, <Аноним>, Вы писали:

А>А вообще, откройте Страуструпа и убедитесь, что непонравившаяся Вам функция выводится грамматикой С++!
Ты сам то его читал?

Приведенное ниже описание синтаксиса С++ должно помочь пониманию языка. Оно не является точным определением языка С++...

(С) Язык программирования С++. Специальное издание. Б. Страуструп.

Да что там Страуструп читаем стандарт

This summary of C++ syntax is intended to be an aid to comprehension. It is not an exact statement of the language...

Здравствуйте, <Аноним>, Вы писали:

Ответьте на два вопроса
1)Может ли порождающая грамматика языка порождать предложения не входящие в данный язык?
2)Что вы понимаете под предложением на языке С++?

Наезды поскипаны.

А>Мне следует задать эти вопросы т.к. Вы путаете разницу между формальным языком и грамматикой.
Оговорился. Последнее следует читать: "между формальным языком и языком программирования."

Исправил и добавил пару номеров в продукции т.к. допустил там пару ошибок. Исправления здесь не выделены.

А>

А>8) function-definition:
А> declaration-specifiers declarator compound-statement
А>17) declaration-specifiers:
А> type-specifier
А>25) type-specifier:
А> void
А>68) declarator:
А> direct-declarator
А>75) direct-declarator:
А> direct-declarator()
А>69) direct-declarator:
А> identifier
А>123) compound-statement:
А> { statement-list }
А>125) statement-list: statement
А>115) statement: jump-statement
А>143) jump-statement:
А> return expression;

А>Продукции, которые расширяют expression не привожу т.к. их много (достало меня уже!), но вконце expression ведет к продукциям 213, 215, 219 и т.д. Так что не надо говорить, что "моя" функция не может быть выведена грамматикой!

А>Язык С++ — context free language!

Кстати, используя продукции 10, 17, 25, 46, 48, 68 и 69 (в этом порядке) можно обьявить переменную

void var;

Ы?

А>Примеры не порождающих грамматик — в студию!

Это уже оффтопик, писать здесь введение в теорию формальных языков не собираюсь. Но, уверяю Вас, сколько угодно, поищите на тему

трансформационных грамматик, категориальных и т. п...

M>>кроме того, язык может быть описан без всякой грамматики. Например, предложение "множество сттрок, состоящих из нуля и более символов а" великолепно описывает язык, который задает грамматика:

M>>S --> aS | пустая строка

А>Ну вот. Говорим о языке, который "может быть описан без всякой грамматики" и толкаем пример регулярной грамматики с использованием рекурсии (ака КС элемента)!!! Удивительная у Вас способность описывать простые грамматики более сложными!!! Неудивительно, что для языков программирования Вам нужна КЗ грамматика!

Вы это о чем??? Я привел пример языка и описал его двумя способами: предложением русского языка и порождающей грамматикой.

M>>Здесь ГДЕ-НИБУДЬ о семантике хоть слово было произнесено?
А>Это Вы смешиваете чисто семантическая понятия с синтаксическими!

И где я здесь СМЕШИВАЛ что-то??? Как можно здесь нечто смешивать, если есть только одна составляющая (синтаксис)?

M>>Семанитка языка (в ее настоящем смысле, т.е. интепретация строк языка человеком) не имеет никакого отношения к описанию структуры строк языка (его предложений). Этим занимается синтаксис. Например, мы могли бы интерпретировать описанный выше язык так: символ а значит произнесение звука а в течении одной секунды. Тогда строка ааа обозначала бы, что некий человек пропел а-а-а... три секунды подряд.

А>Долой абстрактные примеры и голословность! Все что от Вас требовалось — привести правила, которые требуют обьявления переменных один и только один раз! ВЫ ИХ НЕ ПРИВЕЛИ!

От меня этого и не требовалось. Вопрос был в том, что си++ не является КС-языком, с чем Вы, вроде-бы, согласились. Теперь, оказывается, я должен привести еще и доказательство того, что си++ описывается КЗ-грамматикой или, даже более того, что вообще порождающая грамматика Хомского может описывать такие свойства языка как предварительное объявление. Т.е. уважаемый Аноним выступает опровергателем теории Хомского. Чтобы не привлекать теорию машин Тьюринга, приведу просто пример КЗ-грамматики, описывающей подъязык языка си++. К сожалению, в данной теме можно быть либо голословным, либо многословным. Тетрум, как говорится, нон датур. Поэтому я приведу описание только совсем небольшого подязыка си++, состоящего из объявлений типа int ID и использования типа ++ID. Как мы уже доказывали, этот язык не является КС, а так как некоторое подмножество предложений языка не может быть описано КС-грамматикой, то и весь язык также не может быть описан КС-грамматикой. Это-то, надеюсь, понятно?

Итак, будем танцевать от следующего языка:

L = { xx : x есть {a1, a2, ... , an } + }. Т.е. данный язык есть множество пар одиннаковых строк, состоящих из символов a1, a2, ... , an. В си++, с некоторым обобщением, это идентификаторы. Этот язык определяется следующей КЗ-грамматикой:

(1)
1. ID --> A ID B
2. ID --> A B
3. ID --> ai ai
(2)
1. A --> Ci
2. Ci A --> Ci Ai
3. Ai A --> Ai Ai
4. Ai B --> Ai Di
5. Ai Fj --> Ai Fji
6. Fji Fk --> Fji Fki
7. Fji B --> Fji Di
(3)
1. Ci --> Ei
2. Ei Ai --> Ei A
3. A Ai --> A A
4. A Di --> A Fi
5. A Fji --> A Fj
6. Fj Fjk --> Fj Fk
7. Fj Di --> Fj Fi
(4)
1. Ei --> ai
2. Fi --> ai

Идея этой грамматики проста. Сначала группой правил (1) порождаем строки вида AAAAAA... BBBBBB... где вхождений A и B оиннаковое число. Потом, начиная с крайнего A, применяем правила группы (2) примерно так:
AAABBB ==> Ci AABBB ==> Ci Ai A BBB ==> Ci Ai Ai BBB ==> Ci Ai Ai Di BB.

После этого применяем правила группы (3), чтобы затереть ненужную информацию (символы Ai) примерно так:
Ci Ai Ai Di BB ==> Ei Ai Ai Di B B ==> Ei A Ai Di B B ==> Ei A A Di B B ==> Ei A A Fi B B

Теперь проделываем те же манипуляции для остальных A и B, в результате получим строку их Ei Ek.... Ep Fi Fk ... Fp и, используя правила группы (4), меняем полученную строку на соответствующие терминалы.

Легко доказать, что данная грамматика порождает только строки показанного вида и никакие больше. К тому же, ясно, что грамматика есть КЗ. Теперь можно данный язык расширить правилами вида:

(1)
1. Prog --> int ID
2. ID --> A ID B
2. ID --> A ++ B
3. ID --> ai ai
И, кроме того, изменить правила остальных групп так, чтобы они пропускали ++. Вот и получили язык, определяющий строку int ID ++ ID. Далее, можно вставить в правила группы (1) еще Prog в правые части так, чтобы порождать последовательности таких вот "int ID ++ ID" строк. Причем, построить грамматику так, чтобы генерировались строки вида "int ab int bc ++ bc ++ ab" также несложно. Затем расширить грамматику так, чтобы можно было менять int ab с каким-нибудь ++ bc. Вот и получится, что все строки нужного вида сгенерируются и только они.

Из приведенного выше видно, что порождающая грамматика является именно механизмом (устройством, машиной) который порождает строки определенной структуры. Есть теорема, что для любой КЗ-грамматики можно построить линейно-ограниченный автомат (ЛОА), генерирующий те же строки, что и данная грамматика. На самом деле, грамматика выше является не чем иным, как программой для такого автомата, причем нетерминалы — это состояния данного ЛОА. ЛОА — это машина Тьюринга, т.е. конечный алфавит, конечное число состояний и лента (память), в нашем случае, ограниченная в обе стороны. Теперь, надеюсь, идея стала ясна?

M>>То же самое и в си++. Множество предложений данного языка это (с некоторым обобщением) множество правильных программ, написанных на языке си++.

А>Достает это уже. Повторюсь еще раз... Грамматика описывает только синтаксис языка, и ПРОГРАММА МОЖЕТ БЫТЬ СИНТАКСИЧЕСКИ ВЕРНОЙ, НО НЕВЕРНОЙ СЕМАНТИЧЕСКИ! Выше я уже привел два примера!

Я просто в недоумении... Синтаксис описывает текст программы, а текст программы может быть либо верным либо неверным. Вот и все. Здесь даже не "иди в детский сад", а "мама, роди меня обратно" можно сказать!

M>>Вот и встает задача: описать это множество программ, используя ТОЛЬКО порождающую грамматику Хомского. Это сделать можно, как возможно описать любые структурные построения (например, множество музыкальных этюдов).

M>>Но, КС-грамматика для этого не подойдет из-за свойства языка: каждое имя должно быть описано перед его использованием. Как я уже писал выше, данное свойство не может быть выражено КС-грамматикой.

А>Да кто Вам сказал, что требование, что имя должно быть описано до использования вообще должно быть выраженно через грамматику?!!

ТРЕБОВАНИЕ, ЧТОБЫ ИМЯ БЫЛО ОБЬЯВЛЕНО ДО ИСПОЛЬЗОВАНИЯ — НЕФОРМАЛЬНО, И НЕ МОЖЕТ БЫТЬ ВЫРАЖЕННО ГРАММАТИКАМИ!!!

Смотри вверху.

M>>Так что все просто. Разумеется, язык можно описывать и не используя порождающие грамматики, а как-нибудь по другому. Например, как это делается в стандарте языка си++.

M>>Чать описывается КС-грамматикой. Но такое описание позволяет породить и неверные программы на си++.

А>Повторюсь еще раз! Все программы, описанные грамматикой С++ будут синтаксически верны т.к. грамматика описывает только синтаксис (случай с КС грамматикой) и лексику (случай с регулярной грамматикой)! Это, однако, не значит, что программа будет верна семантически!!!

А>Как Вы опишите формально, что делает for loop? НИКАК! Точно также нельзя формально требовать, чтобы имена были обьявлены заранее. Это делается НЕФОРМАЛЬНО!

В каком смысле ЧТО ДЕЛАЕТ??? Мы же говорим о тексте программы (т.е. о языке!!!) и более не о чем. А как этот текст использовать, это другой разговор. Кто-то в машину вводит для исполнения, можно еще пропеть в церкви в виде псалмов, а можно напечатать и в туалет с этой бумажкой сходить.

M>>Поэтому, вводятся еще ограничения, причем в виде так называемых "семантических" правил. Это делать можно, но почему же при этом говорить, что КС-грамматика, описывающая часть языка, описывает весь язык!? С таким же успехом, я могу описать часть языка регулярной грамматикой, а остальную часть неформально на русском языке и сказать, что граматика языка си++ регулярна. Но это не так, конечно.

А>Ну да! Давайте вообще выбросим всю формализацию к черту и обьявим, что язык С++ вообще можно описать только словами (неформально)!

Давайте, а что язык алгебры или мат анализа грамматикой в учебниках описывается? Нет, именно постредством русского языка, расширенного специальными символами. И чем неформальнее, тем понятнее.

А>Именно эти и "семантические правила," которые неформальны, и требуют, чтобы имя было обьявлено. Все! Не путайте язык программирования с формальным языком!

Конечно, они требуют. Но мы с Вами используем понятия КС-грамматик и КЗ-грамматик, т.е. оперируем в рамках языка порождающих грамматик Хомского. Поэтому, должны оставаться в рамках этой теории. А в этой теории нет ничего про семантику.

M>>Именно, понимание выразительной способности разных классов грамматик и составляет понимание идеи Хомского. Еще раз, в книге "Техники парсинга" есть такой рисунок:

А>Ну и зачем нам этот рисунок? Опять абстракция! Без него и так ясно, что существуют классы грамматик, которые описывают больше языков, чем другие, и сложность расспознавания которых выше. Вот и вся теория.

Ага, взять все и поделить! Чево нам переписка Энгельса с Каутским!

M>>Владимир.
А>Учите теорию, Владимир, лучше!

Теория, мой друг, суха. Но древо жизни зеленеет. не читали? Был там такой персонаж, Вагнер. В Вас я нахожу похожие черты. Но таки я ее учил и продолжаю с удовольствием. А вот Вам, Аноним, не советую, все-равно ничего путного не выйдет.

А>Ну и аспиранты пошли... Грустно...

Насчет аспирантов непонятно. А вот насчет недоучек-студентов можно и порассуждать. Или Вы кулибин из провинции? Сами изучали или курс кто-то читал? В Москве или Питере за такие знания зачеты не ставят... Или выгнали как раз на экзамене по курсу?

А>ЗЫ, Приведите правила из грамматики, подтверждающие, что язык С++ — КЗ язык! Хватит голословности и абстрактных размышлений!

Привел, см. выше. И, кстати, доказательство того, что си++ не КС язык тоже выше можно посмотреть.

Да, и отвечаю я Вам в последний раз. Действительно, хватит абстрактных размышлений и голословности, особенно, вкупе с многословностью. А то получается как в том анекдоте: папа, а ты с кем сейчас разговаривал?

M>>>кроме того, язык может быть описан без всякой грамматики. Например, предложение "множество сттрок, состоящих из нуля и более символов а" великолепно описывает язык, который задает грамматика:

M>>>S --> aS | пустая строка

А>>Ну вот. Говорим о языке, который "может быть описан без всякой грамматики" и толкаем пример регулярной грамматики с использованием рекурсии (ака КС элемента)!!! Удивительная у Вас способность описывать простые грамматики более сложными!!! Неудивительно, что для языков программирования Вам нужна КЗ грамматика!

M>Вы это о чем??? Я привел пример языка и описал его двумя способами: предложением русского языка и порождающей грамматикой.
Читайте внимательнее!

M>От меня этого и не требовалось. Вопрос был в том, что си++ не является КС-языком, с чем Вы, вроде-бы, согласились.
Когда это я согласился с неверным измышлением?!! Или Вы выдаете желаемое за действительное?

M>Теперь, оказывается, я должен привести еще и доказательство того, что си++ описывается КЗ-грамматикой или, даже более того, что вообще порождающая грамматика Хомского может описывать такие свойства языка как предварительное объявление. Т.е. уважаемый Аноним выступает опровергателем теории Хомского.
Бред. Я доказал почему С++ — КС язык. Вы же не можете доказать почему С++ — КЗ язык. Все ваши утверждения основаны на голословности и ни единой продукции из С++.

M>Чтобы не привлекать теорию машин Тьюринга, приведу просто пример КЗ-грамматики, описывающей подъязык языка си++. К сожалению, в данной теме можно быть либо голословным, либо многословным. Тетрум, как говорится, нон датур. Поэтому я приведу описание только совсем небольшого подязыка си++, состоящего из объявлений типа int ID и использования типа ++ID. Как мы уже доказывали, этот язык не является КС, а так как некоторое подмножество предложений языка не может быть описано КС-грамматикой, то и весь язык также не может быть описан КС-грамматикой. Это-то, надеюсь, понятно?
То что весь язык (а точнее требования об обьявлении имен) не может быть описан КС грамматикой еще НЕ значит, что он КЗ язык.

M>Итак, будем танцевать от следующего языка:

M>L = { xx : x есть {a1, a2, ... , an } + }. Т.е. данный язык есть множество пар одиннаковых строк, состоящих из символов a1, a2, ... , an. В си++, с некоторым обобщением, это идентификаторы. Этот язык определяется следующей КЗ-грамматикой:

M>(1)
M> 1. ID --> A ID B
M> 2. ID --> A B
M> 3. ID --> ai ai
M>(2)
M> 1. A --> Ci
M> 2. Ci A --> Ci Ai
M> 3. Ai A --> Ai Ai
M> 4. Ai B --> Ai Di
M> 5. Ai Fj --> Ai Fji
M> 6. Fji Fk --> Fji Fki
M> 7. Fji B --> Fji Di
M>(3)
M> 1. Ci --> Ei
M> 2. Ei Ai --> Ei A
M> 3. A Ai --> A A
M> 4. A Di --> A Fi
M> 5. A Fji --> A Fj
M> 6. Fj Fjk --> Fj Fk
M> 7. Fj Di --> Fj Fi
M>(4)
M> 1. Ei --> ai
M> 2. Fi --> ai
Опять голословность и не единой продукции из грамматики С++?

M>Идея этой грамматики проста. Сначала группой правил (1) порождаем строки вида AAAAAA... BBBBBB... где вхождений A и B оиннаковое число. Потом, начиная с крайнего A, применяем правила группы (2) примерно так:
M> AAABBB ==> Ci AABBB ==> Ci Ai A BBB ==> Ci Ai Ai BBB ==> Ci Ai Ai Di BB.
Да хватит мне обьяснять как выводить эти строчки! Ломает меня читать весь этот абстрактный бред.

M>После этого применяем правила группы (3), чтобы затереть ненужную информацию (символы Ai) примерно так:
M> Ci Ai Ai Di BB ==> Ei Ai Ai Di B B ==> Ei A Ai Di B B ==> Ei A A Di B B ==> Ei A A Fi B B

M>Теперь проделываем те же манипуляции для остальных A и B, в результате получим строку их Ei Ek.... Ep Fi Fk ... Fp и, используя правила группы (4), меняем полученную строку на соответствующие терминалы.

M>Легко доказать, что данная грамматика порождает только строки показанного вида и никакие больше. К тому же, ясно, что грамматика есть КЗ. Теперь можно данный язык расширить правилами вида:

M>(1)
M> 1. Prog --> int ID
M> 2. ID --> A ID B
M> 2. ID --> A ++ B
M> 3. ID --> ai ai
M>И, кроме того, изменить правила остальных групп так, чтобы они пропускали ++. Вот и получили язык, определяющий строку int ID ++ ID. Далее, можно вставить в правила группы (1) еще Prog в правые части так, чтобы порождать последовательности таких вот "int ID ++ ID" строк. Причем, построить грамматику так, чтобы генерировались строки вида "int ab int bc ++ bc ++ ab" также несложно.
Что это за строка такая в С++? Пока что я вижу, что ее можно описать регулярной грамматикой, а КЗ нах... не нужна.

M>Затем расширить грамматику так, чтобы можно было менять int ab с каким-нибудь ++ bc. Вот и получится, что все строки нужного вида сгенерируются и только они.
Расширяйте сколько угодно, но где РЕАЛЬНЫЕ продукции?

M>>>То же самое и в си++. Множество предложений данного языка это (с некоторым обобщением) множество правильных программ, написанных на языке си++.

А>>Достает это уже. Повторюсь еще раз... Грамматика описывает только синтаксис языка, и ПРОГРАММА МОЖЕТ БЫТЬ СИНТАКСИЧЕСКИ ВЕРНОЙ, НО НЕВЕРНОЙ СЕМАНТИЧЕСКИ! Выше я уже привел два примера!

M>Я просто в недоумении... Синтаксис описывает текст программы, а текст программы может быть либо верным либо неверным. Вот и все. Здесь даже не "иди в детский сад", а "мама, роди меня обратно" можно сказать!
Тут уже следует сказать "иди по такому-то адресу!" Грамматика описывает синтаксис, и синтаксическая структура программы, порожденная данной грамматикой, всегда будет верной! Единственное, она может быть неверной семантически, чего до Вас не доходит!

M>>>Вот и встает задача: описать это множество программ, используя ТОЛЬКО порождающую грамматику Хомского. Это сделать можно, как возможно описать любые структурные построения (например, множество музыкальных этюдов).

M>>>Но, КС-грамматика для этого не подойдет из-за свойства языка: каждое имя должно быть описано перед его использованием. Как я уже писал выше, данное свойство не может быть выражено КС-грамматикой.

А>>Да кто Вам сказал, что требование, что имя должно быть описано до использования вообще должно быть выраженно через грамматику?!!

M>ТРЕБОВАНИЕ, ЧТОБЫ ИМЯ БЫЛО ОБЬЯВЛЕНО ДО ИСПОЛЬЗОВАНИЯ — НЕФОРМАЛЬНО, И НЕ МОЖЕТ БЫТЬ ВЫРАЖЕННО ГРАММАТИКАМИ!!!

M>Смотри вверху.
Читай теорию.

M>>>Так что все просто. Разумеется, язык можно описывать и не используя порождающие грамматики, а как-нибудь по другому. Например, как это делается в стандарте языка си++.

M>>>Чать описывается КС-грамматикой. Но такое описание позволяет породить и неверные программы на си++.

А>>Повторюсь еще раз! Все программы, описанные грамматикой С++ будут синтаксически верны т.к. грамматика описывает только синтаксис (случай с КС грамматикой) и лексику (случай с регулярной грамматикой)! Это, однако, не значит, что программа будет верна семантически!!!

А>>Как Вы опишите формально, что делает for loop? НИКАК! Точно также нельзя формально требовать, чтобы имена были обьявлены заранее. Это делается НЕФОРМАЛЬНО!

M>В каком смысле ЧТО ДЕЛАЕТ??? Мы же говорим о тексте программы (т.е. о языке!!!) и более не о чем. А как этот текст использовать, это другой разговор. Кто-то в машину вводит для исполнения, можно еще пропеть в церкви в виде псалмов, а можно напечатать и в туалет с этой бумажкой сходить.
И после таких высказываний Вы считаете себя экспертом по трансляции? (раз уж взялись за эту ветвь)

M>>>Поэтому, вводятся еще ограничения, причем в виде так называемых "семантических" правил. Это делать можно, но почему же при этом говорить, что КС-грамматика, описывающая часть языка, описывает весь язык!? С таким же успехом, я могу описать часть языка регулярной грамматикой, а остальную часть неформально на русском языке и сказать, что граматика языка си++ регулярна. Но это не так, конечно.

А>>Ну да! Давайте вообще выбросим всю формализацию к черту и обьявим, что язык С++ вообще можно описать только словами (неформально)!

M>Давайте, а что язык алгебры или мат анализа грамматикой в учебниках описывается? Нет, именно постредством русского языка, расширенного специальными символами. И чем неформальнее, тем понятнее.

А>>Именно эти и "семантические правила," которые неформальны, и требуют, чтобы имя было обьявлено. Все! Не путайте язык программирования с формальным языком!

M>Конечно, они требуют. Но мы с Вами используем понятия КС-грамматик и КЗ-грамматик, т.е. оперируем в рамках языка порождающих грамматик Хомского. Поэтому, должны оставаться в рамках этой теории. А в этой теории нет ничего про семантику.
В теории Хомского семантики нет. В языках программирования, она есть, чего до вас не доходит. И требование, чтобы переменная была обьявлена заранее — семантическое. Вы же все еще застряли на синтаксисе.

M>>>Владимир.
А>>Учите теорию, Владимир, лучше!

M>Теория, мой друг, суха. Но древо жизни зеленеет. не читали? Был там такой персонаж, Вагнер. В Вас я нахожу похожие черты. Но таки я ее учил и продолжаю с удовольствием. А вот Вам, Аноним, не советую, все-равно ничего путного не выйдет.
Вы только можете ставить картинки, не понимая теорию. Я так и не догнал, что имелось в виду под "выразительной способностью разного класса грамматик."

А>>Ну и аспиранты пошли... Грустно...

M>Насчет аспирантов непонятно.
Где-то тут Вы уже зарекались про свою диссертацию. Вот я и решил, что Вы аспирант.

M>А вот насчет недоучек-студентов можно и порассуждать. Или Вы кулибин из провинции?
Я в своей "провинции" получил ВО получше чем Вы!

M>Сами изучали или курс кто-то читал?
Я вот и думаю, как Вам читали курс, который Вы так и не поняли, судя по вашим постам. Надеюсь вы НЕ будете читать этот курс?

M>В Москве или Питере за такие знания зачеты не ставят... Или выгнали как раз на экзамене по курсу?
Во-во. Я и удивляюсь как с такими знаниями вас допустили до диссертации.

А>>ЗЫ, Приведите правила из грамматики, подтверждающие, что язык С++ — КЗ язык! Хватит голословности и абстрактных размышлений!
M>Привел, см. выше. И, кстати, доказательство того, что си++ не КС язык тоже выше можно посмотреть.
Что-то я так и не увидел ни одного правила из грамматики С++. Одна голословность да регулярные языки!

M>Да, и отвечаю я Вам в последний раз. Действительно, хватит абстрактных размышлений и голословности, особенно, вкупе с многословностью. А то получается как в том анекдоте: папа, а ты с кем сейчас разговаривал?
Ну-ну... Еще интересно знать с чей стороны идут абстрактные размышления и голословность!