Большое Вам спасибо, товарищ, за поддержку! Очень приятно видеть здесь лицо, которое не просто заучило синтаксис а понимает, что происходит на самом деле!

Жаль, что не имею возможности дать Вам плюсы за ответ.

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

WC>Если мы теперь посмотрим на указанные правила, то легко увидим, какие такие конструкции программы будут синтаксически верными, но бессмысленными и убедимся, что то что аноним нас не обманывал.
Благодарю! Я уж было хотел обратиться к Александреску по поводу этого топика, так он меня достал.

WC>access control:
WC>

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

WC>ambiquity:
WC>

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

WC>type rules:
WC>

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

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

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

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

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

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

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

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

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

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

Автор: achp
Дата: 10.03.04

WH>В принципе шаблоны это функциональный язык. На пример разложение числа на простые множители во время компиляции

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

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

Тогда я так понимаю, взяв граматику С++ из стандарта, я могу запихнуть её с небольшими преобразованиями в Bison, и получу парсер синтаксических конструкций, который свернёт любую синтаксически верную программу в translation-unit ?
Или Bison тут почему-либо не прокатит ?

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

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

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

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

SJA>>>Ок. Такая строка будет синтаксически верна ?
SJA>>>

SJA>>>int rez = (A < B > C);
SJA>>>

А>>Yeah.
WH>Без знания того что такое A, B, C ни чего сказать нельзя.
Нет. Ответ неправильный т.к. мы можем построить дерево вывода. Есть продукция для инициализации при декларации, есть продукция для relational expression в которой используются идентификаторы и есть продукции, которые описывают эти самые идентификаторы.

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

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

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

WC>Вопрос:
WC>

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

Я ответа на этот вопрос пытался добиться в куче постов. И от М. и от ВХ. Молчат как партизаны.

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

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

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

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

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

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

Кстати, я тоже не представляю, что имеется в виду под "выразительной мощностью."

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

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

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

Ну давайте попробуем найти в каком конкретно месте Вы нас "обманываете".

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

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

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

M>(1) Итак, применительно к си++, что есть язык си++? ответ: это множество текстов программ, являющихся корректными по стандарту языка.
Нет, это неверно.
Есть язык программирования C++. Язык программирования C++ определяется:
-правилами представления программ;
-синтаксисом и ограничениями;
-семантическими правилами для интерпретации программ;
-правилами представления входных/выходных данных программ;
...

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

M>(3) Приведенная в стандарте грамматика порождает множество корректных программ на языке си++? Ответ: да, но порождает также некорректные по стандарту тексты программ (примеры обильно были приведены выше).
А вот здесь Вы правы частично. Грамматика С++ действительно порождает некоторые синтаксически некорректные программы. Но не по той причине, что Вы указываете и примеры Вы приводили не верные.

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

M>Вот, в принципе, и все. Мне кажется, все предельно ясно. А разговоры про стандарт и выдержки из него затеян, мне кажется, напрасно.
5 баллов!
А что мы здесь обсуждаем? Теорию формальных языков или язык программирования С++? Если стандарт говорит, что грамматика языка определяет его СИНТАКСИС, но синтаксис — это не весь язык, то почему мы должны этому "не верить"??? Вот поэтому я, кстати, и говорю, что Вы занимаетесь здесь теоретизированием и можете быть признаны правыми, НО только с академической точки зрения, потому что рассуждаете не о языке программирования С++, определенном в соответсвующем стандарте со всем его синтаксисом, ограничениями и семантикой, а о формальном языке совпадающем с множеством всех wellformed программ языка С++.

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

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

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

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

Извините, но это ВЫ определили, что термин неустоявшийся или Ваша научная секта? Вот у меня сложилось обратное впечатление, что термин "теория перевода" оказался неудачным и недостаточно точным, поэтому, кстати, был еще "теория машинного перевода", а вот "теория трансляции" очень удачная калька с английского и очень широко распространена (см программы ВУЗов). Но вопросы канонизации одних писаний и анафемы других — это имхо вопросы не столь принципиальны, чтобы доказывать у кого что более устоявшееся.

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

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

M>Ну зачем так? Я как раз и есть тот практик и профессионал ( ) о котором говорил аноним. Кроме фронт-енд компиляторов я разрабатывал еще и генератор синтаксических анализаторов и парсер регулярных выражений. Поэтому, обвинять меня в теоретизировании несправедливо.
Не умаляя Ваших заслуг, здесь Вы выступаете исключительно теоретиком. Это не плохо и не хорошо — это просто другой ракурс. Имхо, на формуме "Формальные языки" Вы были бы более правыми

WC>5 баллов!
WC>А что мы здесь обсуждаем? Теорию формальных языков или язык программирования С++? Если стандарт говорит, что грамматика языка определяет его СИНТАКСИС, но синтаксис — это не весь язык, то почему мы должны этому "не верить"??? Вот поэтому я, кстати, и говорю, что Вы занимаетесь здесь теоретизированием и можете быть признаны правыми, НО только с академической точки зрения, потому что рассуждаете не о языке программирования С++, определенном в соответсвующем стандарте со всем его синтаксисом, ограничениями и семантикой, а о формальном языке совпадающем с множеством всех wellformed программ языка С++.

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

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

В связи с этим, если мы говорим о си++ НЕ как о формальном языке, то вопрос: "является ли си++ КЗ-языком" совершенно некорректен, ибо есть попытка применить к концепции одной теории (языков программирования, определяемых синтаксисом и семантикой) понятия из совсем другой теории (теории формальных языков).

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

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

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

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

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

WC>Извините, но это ВЫ определили, что термин неустоявшийся или Ваша научная секта? Вот у меня сложилось обратное впечатление, что термин "теория перевода" оказался неудачным и недостаточно точным, поэтому, кстати, был еще "теория машинного перевода", а вот "теория трансляции" очень удачная калька с английского и очень широко распространена (см программы ВУЗов). Но вопросы канонизации одних писаний и анафемы других — это имхо вопросы не столь принципиальны, чтобы доказывать у кого что более устоявшееся.

Нет. это вопрос вовсе не канонизации, а терминологии. Теория перевода, называйте ее теорией трансляции если хотите, это не совсем то, что Вы под этим подразумеваете. В Вашем понимании (как я это уразумел из написанного выше) теория трансляции — это раздел программирования, изучающий построение компиляторов для языков программирования. Но это не так, теория перевода это только ЧАСТЬ этого раздела. Фундаментальный труд Ахо и Ульмана называется: Теория Синтаксического анализа, перевода и компиляции. Т.е. есть три совсем разных раздела и теория перевода, в том объеме, в котором она используется в написании компиляторов, совсем небольшая тема, к которой синтаксический анализ имеет опосредованное отношение. Часто, даже совсем не имеет. например, перевод регулярных языков осуществляется постредством конечных преобразователей — трансдьюсеров по английски и в их теории нет ничего про синтаксический анализ. Есть, конечно синтаксически управляемый перевод, такой как атрибутные грамматики Кнута, но и здесь с методами синтаксического анализа мало пересечений.

Поэтому я и настаиваю на четком определении терминов. Это даст нам возможность не смешивать понятия.

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

M>>Я привел определение из известных учебников, это значит, что данный язык есть множество всех предложений, выводимых данной грамматикой, не большеи не меньше. С этим будете спорить?
WC>Буду. Ваши верные определения применены не к тому месту.

M>>Ну зачем так? Я как раз и есть тот практик и профессионал ( ) о котором говорил аноним. Кроме фронт-енд компиляторов я разрабатывал еще и генератор синтаксических анализаторов и парсер регулярных выражений. Поэтому, обвинять меня в теоретизировании несправедливо.
WC>Не умаляя Ваших заслуг, здесь Вы выступаете исключительно теоретиком. Это не плохо и не хорошо — это просто другой ракурс. Имхо, на формуме "Формальные языки" Вы были бы более правыми

Ну, значит, вся эта ветка оффтопик. Как только заговорили о КЗ и КС языках.

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

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

WC>>Извините, но это ВЫ определили, что термин неустоявшийся или Ваша научная секта? Вот у меня сложилось обратное впечатление, что термин "теория перевода" оказался неудачным и недостаточно точным, поэтому, кстати, был еще "теория машинного перевода", а вот "теория трансляции" очень удачная калька с английского и очень широко распространена (см программы ВУЗов). Но вопросы канонизации одних писаний и анафемы других — это имхо вопросы не столь принципиальны, чтобы доказывать у кого что более устоявшееся.

M>Нет. это вопрос вовсе не канонизации, а терминологии. Теория перевода, называйте ее теорией трансляции если хотите, это не совсем то, что Вы под этим подразумеваете. В Вашем понимании (как я это уразумел из написанного выше) теория трансляции — это раздел программирования, изучающий построение компиляторов для языков программирования. Но это не так, теория перевода это только ЧАСТЬ этого раздела. Фундаментальный труд Ахо и Ульмана называется: Теория Синтаксического анализа, перевода и компиляции. Т.е. есть три совсем разных раздела и теория перевода, в том объеме, в котором она используется в написании компиляторов, совсем небольшая тема, к которой синтаксический анализ имеет опосредованное отношение. Часто, даже совсем не имеет. например, перевод регулярных языков осуществляется постредством конечных преобразователей — трансдьюсеров по английски и в их теории нет ничего про синтаксический анализ. Есть, конечно синтаксически управляемый перевод, такой как атрибутные грамматики Кнута, но и здесь с методами синтаксического анализа мало пересечений.

Ну вот сначала заставлял меня называть теорию трансляции теорией перевода, а теперь обвиняет в том, что теория перевода на самом деле является частью теории трансляции В моем понимании, теория трансляции это раздел computer science, изучающий построение трансляторов (компиляторов в частности), в том числе включающая в себя теорию синтаксического анализа, перевода и компиляции (а может и совпадающая с этой теорией). Кстати, уверены ли Вы, что правомочно выделили из ахоульмана теорию перевода, ведь труд же не называется теорИИ, а теорИЯ?

WC>>Не умаляя Ваших заслуг, здесь Вы выступаете исключительно теоретиком. Это не плохо и не хорошо — это просто другой ракурс. Имхо, на формуме "Формальные языки" Вы были бы более правыми
M>Ну, значит, вся эта ветка оффтопик. Как только заговорили о КЗ и КС языках.

Нет, Вы в контексте форума теорию применяете не к тому языку.

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

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

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

WC>>>Извините, но это ВЫ определили, что термин неустоявшийся или Ваша научная секта? Вот у меня сложилось обратное впечатление, что термин "теория перевода" оказался неудачным и недостаточно точным, поэтому, кстати, был еще "теория машинного перевода", а вот "теория трансляции" очень удачная калька с английского и очень широко распространена (см программы ВУЗов). Но вопросы канонизации одних писаний и анафемы других — это имхо вопросы не столь принципиальны, чтобы доказывать у кого что более устоявшееся.

M>>Нет. это вопрос вовсе не канонизации, а терминологии. Теория перевода, называйте ее теорией трансляции если хотите, это не совсем то, что Вы под этим подразумеваете. В Вашем понимании (как я это уразумел из написанного выше) теория трансляции — это раздел программирования, изучающий построение компиляторов для языков программирования. Но это не так, теория перевода это только ЧАСТЬ этого раздела. Фундаментальный труд Ахо и Ульмана называется: Теория Синтаксического анализа, перевода и компиляции. Т.е. есть три совсем разных раздела и теория перевода, в том объеме, в котором она используется в написании компиляторов, совсем небольшая тема, к которой синтаксический анализ имеет опосредованное отношение. Часто, даже совсем не имеет. например, перевод регулярных языков осуществляется постредством конечных преобразователей — трансдьюсеров по английски и в их теории нет ничего про синтаксический анализ. Есть, конечно синтаксически управляемый перевод, такой как атрибутные грамматики Кнута, но и здесь с методами синтаксического анализа мало пересечений.

WC>В моем понимании, теория трансляции это раздел computer science, изучающий построение трансляторов (компиляторов в частности), в том числе включающая в себя теорию синтаксического анализа, перевода и компиляции (а может и совпадающая с этой теорией).

Ну это неверное понимание. Поэтому я и предлагал определиться в терминах. Было бы нехорошо наверное если бы Вы на русском языке для обозначения понятия "стол" использовали слово "стул"? В этом случае, когда Вы говорите стул, а подразумеваете стол, вряд ли Вас кто-то правильно поймет, кроме может-быть, еще кого, кто столы стульями называет. Точно так и во всем остальном. Термин теория перевода, также как и термин порождающая грамматика, придумали не Вы и не я, и де факто и де юре, впрочем, этот термин стал обозначать совершенно точно определенные понятия в определенной теории. Здесь же Вы пытаетесь произвести подмену понятий, используя для этого неоднозначность русского языка. Я Вам на это аргументировано указал. В ответ же получил только утверждения типа: я так называю. Называть вещи так как Вам хочется — это Ваше право. Но в дисскусии необходимо использовать утвердившуюся терминологию, хотя бы из уважения к собеседникам.

WC>Кстати, уверены ли Вы, что правомочно выделили из ахоульмана теорию перевода, ведь труд же не называется теорИИ, а теорИЯ?

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

WC>>>Не умаляя Ваших заслуг, здесь Вы выступаете исключительно теоретиком. Это не плохо и не хорошо — это просто другой ракурс. Имхо, на формуме "Формальные языки" Вы были бы более правыми
M>>Ну, значит, вся эта ветка оффтопик. Как только заговорили о КЗ и КС языках.

WC>Нет, Вы в контексте форума теорию применяете не к тому языку.

Не могли бы НОРМАЛЬНО объяснить, КАКУЮ теорию я некорректно применяю к КАКОМУ языку. Я думаю, что я применяю понятия теории формальных языков, а следовательно, и саму теорию к языку си++, который понимается мною как формальный язык. Ведь было бы некорректно применять теорию формальных языков к неформальному языку?

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

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

Но! Я готов принять на время Ваше предложение и посмотреть, какой содержательный результат Вы нам предложите.
Итак, я согласен на то, чтобы Вы ответили на вопрос "является ли си++ КЗ-языком?". Единственное, уточним немного эту формулировку "является ли язык, представляющий из себя множество wellformed по стандарту С++ цепочек символов КЗ-языком?"

M>мы должны решить две проблемы
Да верно, и сейчас я попрошу Вас убедить меня в том, что 1)Вы можете обе проблемы решить 2)решение имеет практическую ценность. Из Ваших постов я понял, что у Вас положительный ответ по обоим пунктам. Так?

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

M>доказать, что существует КЗ-грамматика, определяющая язык си++ (вы понимаете вероятно, что доказать, что КЗ-грамматика для си++ существует это не значит обязательно ее показать).
Да, показывать не надо. Хотя кроме доказательства существования у нас еще остается вопрос практической ценности, но пока о ней забудем.
Итак, о чем я сейчас Вас хочу попросить.
Есть в С++ правило "определение перед использованием", знаете, о нем аноним упоминал. Очевидно, что это правило существенным образом влияет на язык и поэтому грамматика должна его выполнение обеспечивать. Чтобы сильно Вас не напрягать, я ослаблю это требование до самого минимума и попрошу Вас дополнить грамматику:

---
Терминалы: 0,1

<Идентификатор> ::= 1
<Идентификатор> ::= 1 <Идентификатор>
<Разделитель> ::= 0

S ::= ??? // дополните здесь пожалуйста, грамматика у нас КЗ

Словестное описание языка: множество цепочек идентификаторов, разделенных одним разделителем, так что
(можете выбрать любое из)
1. каждый идентификатор встречается в последовательности дважды
или
2. каждый идентификатор встречается в последовательности не менее чем дважды

Два идентификатора тождественны, если колличество единичек их образующих одинаково.
---

Я думаю, что у Вас не возникнет возражение на то, что если существует КЗ-грамматика обеспечивающая выполнение правила "определение перед использованием" для С++, то мной предложенная грамматика будет 1)точно существовать 2)несоизмеримо проще, чем КЗ-грамматика С++ о которой Вы говорили.

M>В связи с этим, если мы говорим о си++ НЕ как о формальном языке, то вопрос: "является ли си++ КЗ-языком" совершенно некорректен, ибо есть попытка применить к концепции одной теории (языков программирования, определяемых синтаксисом и семантикой) понятия из совсем другой теории (теории формальных языков).
Да! да! да! Вопрос действительно не корректен! И некорректен именно из-за того, что теория формальных языков приманяется НЕ К ТОМУ МЕСТУ. Об этом Вам твердил аноним, об этом же Вам твержу я. Корректным является вопрос "Является ли множество синтаксически верных С++ программ (даже не программ, а единиц трансляции) КЗ-языком".

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

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

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

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

WC>Но! Я готов принять на время Ваше предложение и посмотреть, какой содержательный результат Вы нам предложите.
WC>Итак, я согласен на то, чтобы Вы ответили на вопрос "является ли си++ КЗ-языком?". Единственное, уточним немного эту формулировку "является ли язык, представляющий из себя множество wellformed по стандарту С++ цепочек символов КЗ-языком?"

M>>мы должны решить две проблемы
WC>Да верно, и сейчас я попрошу Вас убедить меня в том, что 1)Вы можете обе проблемы решить 2)решение имеет практическую ценность. Из Ваших постов я понял, что у Вас положительный ответ по обоим пунктам. Так?

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

M>>доказать, что существует КЗ-грамматика, определяющая язык си++ (вы понимаете вероятно, что доказать, что КЗ-грамматика для си++ существует это не значит обязательно ее показать).
WC>Да, показывать не надо. Хотя кроме доказательства существования у нас еще остается вопрос практической ценности, но пока о ней забудем.

WC>Итак, о чем я сейчас Вас хочу попросить.
WC>Есть в С++ правило "определение перед использованием", знаете, о нем аноним упоминал. Очевидно, что это правило существенным образом влияет на язык и поэтому грамматика должна его выполнение обеспечивать. Чтобы сильно Вас не напрягать, я ослаблю это требование до самого минимума и попрошу Вас дополнить грамматику:

WC>---
WC>Терминалы: 0,1

WC><Идентификатор> ::= 1
WC><Идентификатор> ::= 1 <Идентификатор>
WC><Разделитель> ::= 0

WC>S ::= ??? // дополните здесь пожалуйста, грамматика у нас КЗ

WC>Словестное описание языка: множество цепочек идентификаторов, разделенных одним разделителем, так что
WC>(можете выбрать любое из)
WC>1. каждый идентификатор встречается в последовательности дважды
WC>или
WC>2. каждый идентификатор встречается в последовательности не менее чем дважды

WC>Два идентификатора тождественны, если колличество единичек их образующих одинаково.
WC>---

WC>Я думаю, что у Вас не возникнет возражение на то, что если существует КЗ-грамматика обеспечивающая выполнение правила "определение перед использованием" для С++, то мной предложенная грамматика будет 1)точно существовать 2)несоизмеримо проще, чем КЗ-грамматика С++ о которой Вы говорили.

Понимаете, Вашу грамматику невозможно ДОПОЛНИТЬ, ибо в ней явно определен идентификатор как нетерминал. контекстная зависимость как раз и предполагает, что <Идентификатор> не будет определен явно, а как-бы растворится в контескте. Выше я приводил КЗ-грамматику для языка, состоящего из двух, идущих друг за другом одиннаковых строк. Алфавит языка при этом должен состоять хотя бы из двух символов. С помощью леммы огдена доказывается, что этот язык не является КС. КЗ-грамматика этого языка приведена здесь

Автор: mefrill
Дата: 08.08.04

. Как видите, эта грамматика очень сложна, но корректна, я взял ее из книги Гладкого, там же доказывается, что язык, порождаемый данной грамматикой есть в точности описанный выше. Фактически, это программа для машины Тьюринга, где нетерминалы соответствуют состояниям МТ.

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

Таким образом, полагаю, что вопрос выяснен?.

M>>В связи с этим, если мы говорим о си++ НЕ как о формальном языке, то вопрос: "является ли си++ КЗ-языком" совершенно некорректен, ибо есть попытка применить к концепции одной теории (языков программирования, определяемых синтаксисом и семантикой) понятия из совсем другой теории (теории формальных языков).
WC>Да! да! да! Вопрос действительно не корректен! И некорректен именно из-за того, что теория формальных языков приманяется НЕ К ТОМУ МЕСТУ. Об этом Вам твердил аноним, об этом же Вам твержу я. Корректным является вопрос "Является ли множество синтаксически верных С++ программ (даже не программ, а единиц трансляции) КЗ-языком".

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

WC>>В моем понимании, теория трансляции это раздел computer science, изучающий построение трансляторов (компиляторов в частности), в том числе включающая в себя теорию синтаксического анализа, перевода и компиляции (а может и совпадающая с этой теорией).

M>Ну это неверное понимание.
Хорошо, пусть будет так. Радует только одно — большое число ВУЗов ошибается вместе со мной (не верите? — просто внимательно изучите программы курсов "теория трансляции" или "теория формальных языков и трансляций" которых в инете полным полно).
Далее постараюсь не смущать Вас и буду пользоваться "теория синтаксического анализа, перевода и компиляции".

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


WC>>Нет, Вы в контексте форума теорию применяете не к тому языку.

M>Не могли бы НОРМАЛЬНО объяснить, КАКУЮ теорию я некорректно применяю к КАКОМУ языку.
КАКУЮ — теорию формальных языков (грамматик).
КАКОМУ — языку состоящему из всех wellformed программ (единиц трансляции) на языке программирования С++

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

M>Ведь было бы некорректно применять теорию формальных языков к неформальному языку?
Так о чем и разговор...