Re: Граматика С++ - C/C++

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

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

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

... << RSDN@Home 1.1.0 stable >>

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

Так собственно вопрос в том, синтаксическая это ошибка или семантическая ?

Я — свихнувшееся сознание Джо.

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

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

SJA>Так собственно вопрос в том, синтаксическая это ошибка или семантическая ?

А это зависит от того, что вы понимаете под синтаксисом и семантикой.

... << RSDN@Home 1.1.0 stable >>

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

Прошу позволения ссылаться на стандарт С (ISO 9899-1999). — Имхо сути спора это не меняет ни на грамм, но зато в этом документе намного более четко разделены правила относящиеся к синтаксису и к семантике (он как бы несколько позже вышел чем стандарт C++).

M>А что такое the syntax rules и diagnosable semantic rules в данном предложении?

diagnosable rules — все правила за исключением тех о которых стандарт говорит "диагностики не требуется" (со стороны компилятора имхо), а также тех для которых имеет место быть "неопределенное поведение".

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

syntax rules — правила определяющие синтаксис языка, в стандарте C в синтаксис секции присутствуют
исключительно правила порождающей грамматики, кроме того присутствиет далее секция constraint.
Сам стандарт определяет constraint, как restriction, either syntactic or semantic, by which the exposition of language elements is to be interpreted.

имхо под syntax rules — подразумеваются или правила порождающей грамматики в явном виде или правила заданные неформально, но которые возможно выразить в правилами грамматики

semantic rules — правила поведения абстрактной машины (интерпретации и выполнения программы)

semantic constraints — ограничения на предложения языка, для которых соответственно будут определены (иметь смысл) semantic rules

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

SJA>>Так собственно вопрос в том, синтаксическая это ошибка или семантическая ?

Ш>А это зависит от того, что вы понимаете под синтаксисом и семантикой.

Прикольно....

Я думал есть некоторое формальное определение ситаксиса и семантики...
Так может мне пояснят, как эту границу провести ?

А то я могу сказать, что С++ задаётся регулярной (если я правильно употребляю слово) граматикой вида
program ::= .* [в смысле сколько угодно каких угодно символов]

А всё остальное — семантика...

Я — свихнувшееся сознание Джо.

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

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

WC>>>Раз ты так любишь букву то:
WC>>>1.3.14. well-formed program
WC>>>a C++ program constructed according to the syntax rules, diagnosable semantic rules, and the One Definition Rule

M>>А что такое the syntax rules и diagnosable semantic rules в данном предложении?

Ш>Это все те правила, из которых, собственно, и состоит стандарт.

Ш>The set of diagnosable rules consists of all syntactic and semantic rules in this International Standard

Ш>except for those rules containing an explicit notation that “no diagnostic is required” or which are described as resulting in “undefined behavior.”

Замечательно, но таки не дает полной ясности, что считать синтаксическими, а что семантическими правилами. поэтому я и спросил. Очевидно, что требовать таких определений от стандарта нельзя, он описывает язык си++, а не теорию формальных языков и различия между семантикой и синтаксисом. Поэтому, для большей ясности, ниже я просто приведу примеры определений языков, порождаемых грамматикой Хомского, из различных (широко известных) книжек.

Гладкий А. В. "Формальные грамматики и языки". стр. 28 Множество предложений, состоящих из терминальных символов грамматики и выводимых из ее стартового символа, называется языком, порожденным грамматикой G и обозначается L(G)

Ахо А., Ульман Дж. "Теория синтаксического анализа, перевода и компиляции", стр. 106. Язык, порождаемый грамматикой G, это множество терминальных цепочек (предложений языка), порождаемых грамматикой G.

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

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

(1) Итак, применительно к си++, что есть язык си++? ответ: это множество текстов программ, являющихся корректными по стандарту языка.

(2) Если есть порождающая грамматика языка си++, то что есть язык, порождаемый данной грамматикой? Ответ: согласно (1), множество текстов программ, корректных по стандарту языка си++.

(3) Приведенная в стандарте грамматика порождает множество корректных программ на языке си++? Ответ: да, но порождает также некорректные по стандарту тексты программ (примеры обильно были приведены выше).

(4) Какой язык определяет грамматика из стандарта? Ответ: язык, во множество терминальных цепочек которого входят корректные по стандарту тексты программ, но входят также и некорректные. Следовательно, грамматика определяет не язык си++, а некий язык, включающий корректные тексты программ языка си++.

Вот, в принципе, и все. Мне кажется, все предельно ясно. А разговоры про стандарт и выдержки из него затеян, мне кажется, напрасно.

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

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

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

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

Очень интересно, а нельзя ли ссылочку на доказательсво? Мне просто интересно, как это доказать можно.

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

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

А>>Да ну! Это уж в стандарте и не точная?!!
WH>Вы читать умеете? А быть может вы просто английский не знаете? Так и быть поработаю переводчиком
WH>[q]
WH>...
WH>This summary of C++ syntax is intended to be an aid to comprehension.
WH>Это краткое описание синтаксиса С++ предназначено для помощи в понимании.
WH>It is not an exact statement of the language.
WH>Это не точное определение языка
WH>In particular, the grammar described here accepts a superset of valid C++ constructs.
WH>В частности представленная здесь грамматика допускает надмножество допустимых конструкций С++.
WH>...

Нда... А почему не хватило сил на точки? Ведь получили же цитату выдраную из контекста

Продолжаем:
Disambiquation rules (6.8, 7.1, 10.2) must be applied to distinguish expressions from declarations.
Правила разрешения неоднозначностей должны быть применены для различения выражений и деклараций.
//Так может только в этом и только в этом то все и дело, а?
Futher, access control, ambiquity, and type rules must be used to weed out sintactically valid but meaningless constructs.
Далее, правила контроля доступа, неоднозначностей и типов должны быть применены для искоренения синтаксически корректных, но бессмысленных конструкцй.

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

access control:

class A {int i;} a;
...
a.i=5;

ambiquity:

void f(unsigned short){}
void f(long){}
...
f('a');

type rules:

void f()
{
  return 10;
}
void* g()
{
  return 10;
}

Очевидно, эти синтаксически верные примеры ни один компилятор, соответствующий стандарту, не пропустит.

Кстати, насчет того что стандарт описывает грамматику ненормативной. Так принято делать, чтобы было формально только одно место имеющее доказательную силу, хотя бы чтобы избавиться от случайных проблем в несоответствии (описка) двух описаний. В стандарте С, кстати, никакой оговорки о том что грамматика описывает надмножество языка нет. Раздел с грамматикой все равно ненормативный, хотя слово в слово (и со ссылками даже) повторяет те же правила которые встречаются в тексте стандарта и которые являются формальным определением синтаксиса языка.

Надеюсь, сказал достаточно.

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

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

SJA>>>Так собственно вопрос в том, синтаксическая это ошибка или семантическая ?

Ш>>А это зависит от того, что вы понимаете под синтаксисом и семантикой.

SJA>Прикольно....

Я думал есть некоторое формальное определение ситаксиса и семантики...
SJA>Так может мне пояснят, как эту границу провести ?

SJA>А то я могу сказать, что С++ задаётся регулярной (если я правильно употребляю слово) граматикой вида
SJA>program ::= .* [в смысле сколько угодно каких угодно символов]

SJA>А всё остальное — семантика...

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

Но напомню, исходный вопрос звучал так: определяется ли язык си++ КС-грамматикой? Ответ однозначный — нет, не определяется. Язык си++ определяется КС-грамматикой + описанной в стандарте семанттикой.

Мне кажется, что мы вроже бы наконец прояснили ситуацию.

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

WC>>Имхо негоже модератору так часто обвинять других в демагогии, попутно занимаясь ей же (касаемо вопроса wellformed программы) ...
WH>1)Где тут демагогия? Тут только ссылка на стандарт.
ДЕМАГОГИЯ, и, ж.
2. Рассуждения или требования, основанные на грубо одностороннем истолковании чегон.

Неполное цитирование меняющее контекст и следовательно точный смысл цитаты подпадает под это определение, так что ...

Обсуждение действий модератора удалено. Все вопросы на moderator@rsdn.ru
WolfHound

WC>Надеюсь, сказал достаточно.

Исходный вопрос был: существует ли КС-грамматика, определяющая язык си++? Не КС-грамматика + семантические правила, а ТОЛЬКО КС-грамматика.

Ответ: нет, не существует. И стандарт, к сожалению здесь не поможет ответить. Ведь в нем синтаксис + семантика приведен. А вот проблема: есть ли КС-грамматика, без всяких семантических правил определяющая язык си++, решаема, что и было доказано выше.

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

M>Но напомню, исходный вопрос звучал так: определяется ли язык си++ КС-грамматикой? Ответ однозначный — нет, не определяется. Язык си++ определяется КС-грамматикой + описанной в стандарте семанттикой.

Вопрос:

Является ли грамматика С++ контекстнозависимой ? Если да, то можно простенький пример ?

И ответ:
Нет, грамматка языка С++, как это принято в теории трансляции, является контекстно свободной. При этом следует отметить, что грамматика — это еще не полное определение языка. Язык определяется КС-грамматикой + описанной в стандарте семанттикой + описанными в стандарте синтаксическими ограничениями, которые формально в грамматике не присутствуют.

M>Мне кажется, что мы вроже бы наконец прояснили ситуацию.
Различия имхо тольк в церквях

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

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

M>>Но напомню, исходный вопрос звучал так: определяется ли язык си++ КС-грамматикой? Ответ однозначный — нет, не определяется. Язык си++ определяется КС-грамматикой + описанной в стандарте семанттикой.

WC>Вопрос:
WC>

WC>Является ли грамматика С++ контекстнозависимой ? Если да, то можно простенький пример ?

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

Кроме того, вопрос был: является ли грамматика си++ КС? Почему же я должен отвечать на другой вопрос о том, является ли она КЗ? Какое это к первому вопросу имеет отношение? Если такое отношение есть, то приведите его, только четко и ясно.

WC>И ответ:
WC>Нет, грамматка языка С++, как это принято в теории трансляции,

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

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

Еще раз, вопрос звучал так: Существует ли КС-грамматика определяющая язык си++. Что такое "определяющая" я показал выше дав поределения из двух классических книг по теории формальных языков и теории компиляции. В вопросе нет ничего про семантику и еще что-то. Только КС-грамматика. Пожалуйста, дайте ответ на этот вопрос.

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

M>>Мне кажется, что мы вроже бы наконец прояснили ситуацию.
WC>Различия имхо тольк в церквях

Вот это я совсем не понял. В каких церквях и какие различия?

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

M>Очень интересно, а нельзя ли ссылочку на доказательсво? Мне просто интересно, как это доказать можно.
Шаблоны C++ и полнота по Тьюрингу.
В принципе шаблоны это функциональный язык. На пример разложение числа на простые множители во время компиляции

... << RSDN@Home 1.1.3 beta 1 >>

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

WC>Неполное цитирование меняющее контекст и следовательно точный смысл цитаты подпадает под это определение, так что ...

Аноним делал выводы на основе не точной грамматики о чем собственно и сказано в цитате.

... << RSDN@Home 1.1.3 beta 1 >>

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

WC>>Вопрос:
WC>>

WC>>Является ли грамматика С++ контекстнозависимой ? Если да, то можно простенький пример ?

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

M>Кроме того, вопрос был: является ли грамматика си++ КС? Почему же я должен отвечать на другой вопрос о том, является ли она КЗ? Какое это к первому вопросу имеет отношение? Если такое отношение есть, то приведите его, только четко и ясно.

Или я совсем уже туплю (но ведь из первого, самого первого сообщения этой темы цитату взял

M>Вот это я совсем не понял. В каких церквях и какие различия?
Один — теоретик, другой — практик. И ортогонально: Один — ортодокс, другой — сектант.

Надеюсь без обид

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

WC>>Неполное цитирование меняющее контекст и следовательно точный смысл цитаты подпадает под это определение, так что ...

WH>Аноним делал выводы на основе не точной грамматики о чем собственно и сказано в цитате.

Твоя фраза свидетельствует о непонимани цитаты и недостаточного знакомства с формальными грамматиками и теорией трансляции/компиляции/перевода.

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

WC>Твоя фраза свидетельствует о непонимани цитаты и недостаточного знакомства с формальными грамматиками и теорией трансляции/компиляции/перевода.

...недостаточном знакомстве ... ну и плюс к этому о моём незнании правил согласования падежей в русском языке ...

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

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

WC>>>Вопрос:
WC>>>

WC>>>Является ли грамматика С++ контекстнозависимой ? Если да, то можно простенький пример ?

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

M>>Кроме того, вопрос был: является ли грамматика си++ КС? Почему же я должен отвечать на другой вопрос о том, является ли она КЗ? Какое это к первому вопросу имеет отношение? Если такое отношение есть, то приведите его, только четко и ясно.

WC>Или я совсем уже туплю (но ведь из первого, самого первого сообщения этой темы цитату взял

) или Вы вопрос сами себе придумали, а теперь почему то возмущаетесь. Вы решили подвести итог. Указали, какой был вопрос обсуждаемой темы и дали на него свой ответ. Я Вас поправил с вопросом и соответственно ответом, причем не вступив в противоречие с ответом Вашим...

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

WC>>>И ответ:
WC>>>Нет, грамматка языка С++, как это принято в теории трансляции,

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

WC>А вот это уже хуже ...
WC>STFW

Ну, как всегда, искажение великого и могучего... Из той-же оперы, что и диллеры и лизинги. В классическом переводе Агафонова книги Ахо и Ульмана, в первом томе, есть такое понятие как теория ПЕРЕВОДА, другой термин применять нехорошо, как неустоявшийся.

M>>является контекстно свободной. При этом следует отметить, что грамматика — это еще не полное определение языка.

M>>Еще раз, вопрос звучал так: Существует ли КС-грамматика определяющая язык си++.
WC>Хорошо давайте возмем этот вопрос, если Вы так настаиваете.

M>>Пожалуйста, дайте ответ на этот вопрос.
WC>Синтаксис языка программирования С++ определяется контекстно-свободной грамматикой. Никакой другой грамматики якобы определяющей данный язык — нет. Поэтому на Ваш вопрос ответ также — нет. Ответ на ваш вопрос также — нет и если принять то понятие "определяющий", которым Вы оперируете. Но этот ответ имеет не более, чем академическую ценность.

Т.е. нет — не существует? Полностью с этим согласен. Если Вы имели ввиду нечто другое, то пожалуйста напишите. И давайте определимся с терминов грамматика, ОПРЕДЕЛЯЮЩАЯ язык. Что это значит? Я привел определение из известных учебников, это значит, что данный язык есть множество всех предложений, выводимых данной грамматикой, не большеи не меньше. С этим будете спорить?

КС-грамматика, определенная в стандарте, позволяет вывести множество программ, не являющихся корректными. Потом на них налагают дополнительные ограничения. но это к нашему разговору не относится. Мы ведь говорим ТОЛЬКО о грамматике?

M>>>>Мне кажется, что мы вроже бы наконец прояснили ситуацию.
WC>>>Различия имхо только в церквях

M>>Вот это я совсем не понял. В каких церквях и какие различия?
WC>Один — теоретик, другой — практик. И ортогонально: Один — ортодокс, другой — сектант.

Надеюсь без обид

Ну зачем так? Я как раз и есть тот практик и профессионал (

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

	От:	Шахтер
	Дата:	09.08.04 16:41
	Оценка:

	От:	Шахтер
	Дата:	09.08.04 16:41
	Оценка:	5 (1) +1

	От:	Sergey J. A.
	Дата:	09.08.04 16:46
	Оценка:

	От:	Шахтер
	Дата:	09.08.04 16:52
	Оценка:

	От:	WeCom
	Дата:	09.08.04 16:55
	Оценка:

	От:	mefrill
	Дата:	10.08.04 05:27
	Оценка: