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

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

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;
}

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

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

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!

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

А>

А>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;

Ы?

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

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

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

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

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

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

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

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

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>>Владимир.
А>Учите теорию, Владимир, лучше!

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

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

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

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

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

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

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

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

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

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

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

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

А>Выше, Андрей Тарасевич кратко сказал почему грамматика С++ — КС грамматика.
Re[3]: Граматика С++

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

А>Лаптев, преподаватель в ВУЗе, подтвердил, что языки программирования описываются КС грамматиками.
Re: Граматика С++

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

А>После этого Вы будете продолжать спорить?
Я думаю вам стоит внимательно почитать что они пишут.

Еще раз напоминаю держите эмоции при себе. Ваши сообщения на грани фола. Переход на личности не допустим.
2mefrill вас это тоже касается.

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

А>>Выше, Андрей Тарасевич кратко сказал почему грамматика С++ — КС грамматика.
WH>Re[3]: Граматика С++
WH>

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

А>>Лаптев, преподаватель в ВУЗе, подтвердил, что языки программирования описываются КС грамматиками.
WH>Re: Граматика С++
WH>

WH>Ни один из современных языков программирования на практике не описывается контекстно-зависимыми грамматиками, исключительно контестно-свободными (из соображений эффективности,

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

Языки не описываются КЗ грамматиками т.к. КС грамматики достаточно для описания языка.

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

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

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

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

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

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

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

мне уже страшно от того что придется сделать для того чтобы описать это формально

) является очень трудной задачей. И ни один вменяемый человек не станет тратить гигантское колличество ресурсов на то чтобы создать грамматику которая еще и распозноваться будет за экспоненциальное время. И так компиляторы еле ворочаются.
И если вы думаете что я все брошу и потрачу кучу времени на то чтобы создать точную грамматику С++ только ради того чтобы вам что-то доказать то вы ошибаетесь.

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

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

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

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

Вот обьясните мне почему в Страуструпе и в самом стандарте по С++ приводится "какая-то другая грамматика," выражаясь Вашим языком? Что по-вашему должны делать писатели компиляторов — искать "некую целую грамматику С++" с описанием кучи страшных конструкций от которых у Вас шерсть дыбом встает?

Еще раз, КС грамматики используются т.к. их достаточно. Не имеет смысла использовать грамматику которая порождает большое количество языков и затрачивает больше ресурсов для расспознавания если это можно сделать с меньшими затратами. И потом, кто сказал, что объявление переменной должно быть выраженно грамматикой?

ЗЫ. Вы не поверите, но я даже видел описания темплейтов, а расспознаванием деклараций классов занимаются даже в рамках обычного ВУЗа.

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

А на счет лексики, синтаксиса и семантики — это второй класс средней школы...

Итак... Лексика — это множество правильных слов в языке (естественном и языке программирования). В С++ это ключевые слова, правильные переменные (foo, boo, var), знаки препинания (скобки, запятые, точки, стрелки). Описываются регулярной (и самой простой) грамматикой.

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

Для естественных языков приводить пример грамматики лучше на английском т.к. у него грамматика строже чем у русского. Шекспир, разве, что исключение — грамматика у него не к черту.

Например, можно определить английское предложение так.

sentence ::= noun verb noun.
noun     ::= child | girl | boy | ball
verb     ::= plays | likes | dislikes

Такая грамматика породит предложение "boy plays ball.", которое имеет смысл с точки зрения английского языка, но оно также породит предложение "ball plays boy.", которое не имеет смысла. Точно также и с языками программирования. Их грамматики могут могут порождать предложения которые синтаксически верны (как в этом примере), но не имеют смысла (семантики).

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

Итак, программа может не скомпилироваться по следущим трем причинам (в порядке возврастания "сложности"):
1) Лексической. В программе найдено неверное имя. Пример — 5abcv.
2) Синтаксический. Все слова в программе верны, но их порядок или порядок знаков препинания неверный. Например, statement не заканчивается точкой с запятой или перепутали скобки в функции.
3) Семантической. Программа не имеет смысла хоть и синтаксически верна. Пример:

void f() { return 5; }

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

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

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

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

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

А>ЗЫ. Вы не поверите, но я даже видел описания темплейтов, а расспознаванием деклараций классов занимаются даже в рамках обычного ВУЗа.
Полностью формальное? Сильно сомневаюсь.
Скорей всего вы видили тоже самое что представляет собой грамматика С++ из стандарта. Те не точную грамматику для которой необходимы дополнительные не формальные правила.

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

	От:	Аноним
	Дата:	07.08.04 17:57
	Оценка:	+1

	От:	Аноним
	Дата:	07.08.04 17:59
	Оценка:

	От:	WolfHound
	Дата:	07.08.04 19:30
	Оценка:	-1

	От:	Аноним
	Дата:	08.08.04 05:20
	Оценка:	+1

	От:	Аноним
	Дата:	08.08.04 05:28
	Оценка:

	От:	Sergey J. A.
	Дата:	09.08.04 11:07
	Оценка:

	От:	Sergey J. A.
	Дата:	09.08.04 12:39
	Оценка: