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

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

Да, пожалуйста. А если книги в электронном виде, то вообще здорово будет.
Можно в аську: 158153635.

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

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

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

WC>Да, пожалуйста. А если книги в электронном виде, то вообще здорово будет.
WC>Моюно в аську: 158153635.

Вечером из дома напишу.

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

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

Первые продукции позволяют генерировать последовательности пар идентификаторов, разделенных нулем:

S --> A 0 S | A

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

A --> B A C | B 0 C

Эти правила позволяют генерировать последовательности вида BBB 0 CCC 0 BB 0 CC. Теперь самое трудное, необходимы правила, чтобы менять последовательность нетерминалов C и стоящую справа строку из B или C местами. Т.е. если есть строка BBB 0 CCC 0 BB 0 CC, то получить из нее строку BBB 0 CCC 0 BB 0 CC. Добавим соответствующие правила:

1) C 0 --> 0 D
2) D B --> E F
3) D E --> E F
4) F B --> B F
5) 0 E --> B 0
6) 0 F --> 0 C
7) C F --> C C

Это группа правил, чтобы менять местами строки CCC... и BBB.... Попытаемся показать их применение:

Пусть, с помощью правил первой и второй групп, мы породили строку вида ... 0 CCC 0 BB 0 ... Здесь нам надо поменять местами эти строки, сначала с помощью 1) смещаем влево нуль, идущий после CCC и попутно заменяем все C на D.

0 CCC 0 BB 0 ==> 0 CC 0 D BB 0 ==> 0 C 0 DD BB 0 ==> 0 0 DDD BB 0

Теперь используем правила 2) — 4) чтобы поменять DDD и BB местами, попутно заменяя каждый D на F, а B на E.


0 0 DDD BB 0 ==> 0 0 DD E F B 0 ==> 0 0 D E FF B 0 ==> 0 0 E FFF B 0 ==> 0 0 E FF E F 0 ==> ... ==> 0 0 EE FFF 0

Сейчас применяем правило 5) чтобы перевести нуль обратно направо и попутно заменить все E на B.

0 0 EE FFF 0 ==> 0 B 0 E FFF 0 ==> 0 BB 0 FFF 0

Применяем правила 6) и 7) чтобы заменить F на C.

0 BB 0 FFF 0 ==> 0 BB 0 CFF 0 ==> 0 BB 0 CCF 0 ==> 0 BB 0 CCC 0


Аналогично, создаем группу правил чтобы менять строки из C на строки из C, например, CCC 0 CC на CC 0 CCC.

Последняя группа правил позволяет заменить B и C на единицу.

B --> 1
C --> 1

теперь, если нам необходимо вывести строку типа 111 0 11 0 1 0 1 0 111 0 11 просто генерируем строку

BBB 0 CCC 0 BB 0 CC 0 B 0 C

и приводим ее к следующему виду BBB 0 BB 0 B 0 C 0 CCC 0 CC После чего применяем правила последней группы.

Все ли здесь понятно мудрому белорусскому вьюноше?


M>>Я вообще предлагаю завершить весь этот разговор, так как это не приведет ни к чему. Тем более, что правы все 6-). Если хотите, то напишите ответ на это сообщение, я же отвечать уже не вижу необходимости.
WC>Не возражаю.

Вот теперь, действительно, в последний раз.

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

Ну, с Анонимом, я полагаю, все ясно?

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

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

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

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

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

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

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

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

Вы, наверное, уже увидели, что порождающая грамматика это, ни что иное, как недетерминированная машина Тьюринга, а попросту говоря, недетерминированный алгоритм генерации текста. При построении удобнее попрождающую грамматику именно в таком ракурсе. Я не буду приводить конкретные правила, а приведу пути как это можно сделать. Вас, как я понял, интересует язык, в котором было-бы только одно объявление идентификатора и множество использований, т.е. одно BBB... и много CCC... ? это сделать можно. Разделим нашу программу на две процедуры (точно также как в си). Первая процедура будет генерировать различные строки вида BBB... , проверяя при этом, нет ли уже такой строки в тексте. Это, опять-же, можно разбить на две процедуры, одна — генерации, другая — проверки. Первая генерирует множество символов-нетерминалов грамматики, обозначим эти символы-нетерминалы-состояния через M например. Все уже проверенные нетерминалы обозначим через K. После того, как строка MMM... порождена, переходим в состояние сравнения со строками, состоящими из символов K. Если есть уже такая строка, то терминальная строка не будет порождена. это, вообще, главный инструмент, не позволяющий строить не верные терминальные цепочки. Если еще такой строки нет, то переименовываем все M в K. после окончания фазы генераии переименовываем все K в B. Таким образом, после того как сгененрировано множество из различных BBB... строк, запускаем вторую процедуру, которая из каждой BBB... строки может построить неограниченное число копий вида CCC... Это несложно сделать, тем более что, в отличии от машины Тьюринга, мы можем как-бы раздвигать ленту путем применения правил вида AB --> ABC. На самом деле, достаточно группы правил, позволяющих создавать ОДНУ CCC... копию строки BBB... , а потом эти правило можно применять сколько угодно раз. После этого уже запускаем процедуру для продвижения по ленте вправо строк CCC... как это уже было описано. Так как двигаются только строки CCC... и только вправо, то правило объявления имени перед использованием будет соблюдено. Все.

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

Гладкий — 1973. Теория формальных языков, по-моему так называется. Эта книжка требует подготовки и поэтому, будет читаться очень трудно.

Ахо, Ульман — 1978. Теория ситаксического анализа, перевода и компиляции. Неплохая книжка, но по Кз-граммтаикам там написано очень мало. Издание жтой книги для нематематиков вышло в 1986 и называется книгой красного дракона.

Ульман, Хопкрофт, Мотвани — 2002 (2003)? Введение в теорию языков, автоматов и вычислений. Хорошая, написанаая ясным языком, но поэтому неглубокая книжка, первое издание было лучше, но на русском, к сожалению, не издано. В главе про ограничения КС-грамматик прямо написано почему язык из двух, идущих подряд, одиннаковых имен, неможет быть описан КС-грамматикой. Смотрите в сторону леммы о накачке для КС-языков. Другая формулировка — лемма Огдена. Она же есть и в Ахо, Ульман.



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

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

WC>Попутно к этому меня заинтересовала фраза анонима о неформализуемости требования "определение перед использованием". Причем, если он ошибается, то мне интересно не просто узнать это и точка, а понять в чем конкретно ошибка и откуда ноги растут у такого заявления.

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

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

WC>2.Дальше я пока, извините, недостаточно внимательно анилизировал (но конечно же обязательно это сделаю, как только смогу), потому что все мои мысли заняла вот какая гиппотеза:

WC>А может быть ошибка утверждения анонима в том, что вместо правила "определение перед использованием" должно бы было указано правило "одного описания" (One Definition Rule). Может быть его нельзя выразить порождающей грамматикой? Если бы это было так, то тогда стало бы понятно почему в самом Стандарте это правило идет особняком (этот вопрос тоже у меня отложился и пока правильного ответа нет). В общем я твердо понял, что мне нужно эту гиппотезу проверить.
Это правило идет особняком т.к. к синтаксису никакого отношения не имеет, да и КС грамматики явно недостаточно. На счет других грамматик не знаю, но интуитивно чувствую, что если и можно это как-то формализовать, то не при помощи грамматик. Вот как Вы, к примеру, выразите через грамматику, чтобы типы аргументов и параметров функции совпадали?


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

Может мефрилл тут выведет что-нибудь...

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

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

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

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

Вобщем, если кому-то ещё интересно.
В книге А.Ю. Молчанова "Системное программное обеспечение" говориться следующее:
Глава 5.

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

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

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

А>Это пример из русского языка. Как видите, с точки зрения русской грамматики параграф и все предложения верны, но тем не менее смысла они не имеют. Точно также и с С++. Даже Лаптев, вон, выше заметил, что языки описываются КС грамматиками.
Ш>>Это и означает, что C++ не контекстно свободный язык.
А>Ваш вывод (неверный, кстати) основан на вашем же и утверждении.
Грамматика — контекстно-свободная. а язык — контекстно-зависимый

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

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

Контекстно зависимой является даже грамматика простого Си!
например:

free(ptr);

может быть разобрано либо как statement — вызов функции free с аргументом ptr
либо как declaration — определение переменной ptr типа free.

Все зависит от контекста. Было ли выше написано

typedef int free;

или нет.

SJA>Вобщем, если кому-то ещё интересно.
SJA>В книге А.Ю. Молчанова "Системное программное обеспечение" говориться следующее:
SJA>Глава 5.
SJA>

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

SJA>(*)
SJA>Примером контекстной зависимости, часто встречающейся во многих языках программирования, может служить необхдимость предварительно описать идентификатор до его первого использования.

Автор абсолютно прав. Язык программирования С++ и формальный язык описанный грамматикой языка программирования С++ — две разные вещи. Термин контекстно-зависимый применяется только к формальным языкам.

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

А ты уже добрался до пятой главы или также как WolfHound выдираешь отдельные фразы не понимая всей сущности?

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

А>А ты уже добрался до пятой главы или также как WolfHound выдираешь отдельные фразы не понимая всей сущности?

Выдираю. Пока добрался только до середины 4-ой главы, но решил запостить, пока топик совершенно не забылся....

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

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

SJA>Выдираю. Пока добрался только до середины 4-ой главы, но решил запостить, пока топик совершенно не забылся....
Быстро, однако... А со всем разобрался хоть или просто решил примкнуть к лагерю любителей КЗ?

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

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

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

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

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

SJA>>Выдираю. Пока добрался только до середины 4-ой главы, но решил запостить, пока топик совершенно не забылся....
А>Быстро, однако... А со всем разобрался хоть или просто решил примкнуть к лагерю любителей КЗ?

Регулярные граматики пошли легко... А вот КС уже идёт сложнее....

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

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

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

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

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

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

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

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

Бред какой-то...

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

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

N_>Бред какой-то...

Это просто опечатка, следует читать так:

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

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

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

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

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

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

M>Это просто опечатка, следует читать так:

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

Правильно, я сам так и считаю.

Я не понимаю, что означают слова LaptevVV: "Еще раз повторяю: грамматика — контекстно-свободная, а язык — контекстно-зависимый! И не надо путать."