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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

a<b>c;

Ы?
Если

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

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

int a, b, c;

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

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

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

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

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

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

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

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

WH>a<b>c;
WH>

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

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

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

WH>int a, b, c;
WH>

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

или так

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

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

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

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

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

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

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

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

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

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

АТ>

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

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

x * y;

В случае

int x;
int y;

x * y;

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

typedef int x;

x * y;

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

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

--
aga

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

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

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


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

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

Владимир.

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

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

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


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

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

Владимир.

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

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

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

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

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

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