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

Такая грамматика вполне может быть, хотя, конечно, большого смысла это не имеет и ведет к неоднозначности. Как можно определить неоднозначность грамматики? Просто, если при разборе некоторого предложения x1x2...xn его можно разобрать хотя бы двумя разными способами, что значит вывести из стартового символа грамматики S строку x1x2...xn, то такая грамматика называется неоднозначной. В нашем случае, если из alpha выводится строка xixi+1...xk например, то мы имеем сразу два дерева разбора:

S
/ A \
/ alpha \
x1x2...xi-1 xi...xk xk+1xk+2...xn

S
/ B \
/ alpha \
x1x2...xi-1 xi...xk xk+1xk+2...xn

Таким образом, грамматика является неоднозначной, одно и тоже предложение выводится двумя различными способами. Вопрос, можно ли эту грамматику трансформировать так, чтобы она определяла тот же язык, но при этом грамматика была однозначной. Иногда можно, иногда нет. Язык, для которого не существует однозначной грамматики называется существенно неоднозначным. Можно ли по грамматике узнать, является ли она однозначной или нет? Нельзя, эта проблема алгоритмически неразрешима, т.е. не существует универсального алгоритма, котрый решает эту задачу. Проблема с парсингом си++ состоит не в том, что грамматика языка есть КЗ, как мы видели, это решается с помощью определения "семантических" свойств языка, а в том, что язык си++ существенно неоднозначен. Поэтому при разработке компиляторов начинаются проблемы когда используют инструменты типа бизона. Бизон, за исключением последних версий, реализует алгоритм анализа, называемый LALR(k), где число k обычно равно единице. Этот алгоритм есть небольшое улучшение алгоритма LR(k)-анализа. Теримнология была введена Кнутом в 1965 году: L значит, что предложение читается слева направо, R обозначает, что при выводе каждый раз заменяется крайний правый нетерминал, например:

S --> AB
A --> a
B --> b

При выводе строки ab получим: S ==> AB ==> Ab ==> ab

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


A -> alpha
B -> alpha

так как при разборе получая строку alpha надо будет решить на какой нетерминал ее заменить. Обычно поступают так: сначала пробуют подставить первый нетерминал, если не получится вывода, то второй. При линейном времени, очевидно, это не получится. Можно попытаться посмотреть вперед на k символов чтобы решить какой нетерминал выбрать, в этом и состоит идея Кнута, но, к сожалению, существуют грамматики, для которых это узнать невозможно ни для какого, сколь угодно большого, числа k. Вот из-за таких вот неоднозначностей разбор си++ с бизоном проблематичен. Есть модификации бизона, позволяющие, при встрече альтернативных нетерминалов, пройти немного вперед при анализе и потом, когда будет известно, какой нетерминал выбрать, возвратиться назад. Понятно, что здесь о линейном времени говорить не приходиться. Алгоритм Томиты, введенный им в 1984 году при такой встрече производит параллельный анализ всех альтернатив (вот где простор для многопоточных анализаторов!) и, в результате, получает все деревья вывода, которые существуют. Есть еще несколько алгоритмов, позволяющих сделать такой анализ, например алгоритм Эрли. Анализатор на основе этого алгоритма был реализован мной при работе над диссертацией. В общем, парсер Си++ написать не сложно, но только не с LR(k)-анализатором.

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

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

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

вот так с детства нам вбивали силу слова "СИ"

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

ssm>измерения

исчисления

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

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

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

Данная грамматика (как впрочем и практически все другие грамматики С++) базируется на предположении, что _сканнер_ (aka lexer) распознает (основываясь на информации собранной ранее парсером), является ли имя просто идентификатором, именем типа, именем шаблона или именем namespace'а.
Так что строго говоря, то что предлашается в этом приложении не есть классическая LALR(1) грамматика...

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

M>Здравствуйте, Андрей Тарасевич, Вы писали:

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

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

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

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

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

Скорее всего, это правда, но я, например, формального доказательства не видел.

А с другой стороны, я не видел доказательства другого факта -- что С++ может быть задан контекстно-зависимой грамматикой.

M>Что в моем рассуждении неверно?

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

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

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

А>Очень хорошо все изложено, но в конце последнего параграфа у Вас заблуждение.

Да нет, это у вас непонимание элементарных вещей. Есть язык C++, есть множество well-formed программ на этом языке, которое представляет из себя некоторое множество конечных цепочек букв. Так вот, это множество не может быть определено через КС грамматику. Это и означает, что C++ не контекстно свободный язык. Будем спорить, что 2+2==4?

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

Ш>Всё верно, только не хватает строгого доказательства невозможности построить КС грамматику, задающую язык. Или хотя бы ссылки.

Ну, для любого языка с предварительным объявлением имен: есть лемма о накачке для КС языков еще известная как лемма Огдена. Вот с помощью ентой леммы легко доказать, что язык, состоящий из двух подряд идущих строк неизвестной заранее длины и состоящих из алфавита мощностью более одного, не являетс КС. А это как раз подязык любого языка с предварительным объявлением имен.

Владимир.

Ш>Да нет, это у вас непонимание элементарных вещей. Есть язык C++, есть множество well-formed программ на этом языке, которое представляет из себя некоторое множество конечных цепочек букв.
Может дадите определение ваших "well-formed программ на этом языке?"

Пришла зима. Нестерпимая жара установилась на дворе. Грамматика С++ — контекстно-свободная! В этом форуме куча тем. Кто из нас всех прав? Опять пришла зима и т.д.

Это пример из русского языка. Как видите, с точки зрения русской грамматики параграф и все предложения верны, но тем не менее смысла они не имеют. Точно также и с С++. Даже Лаптев, вон, выше заметил, что языки описываются КС грамматиками.

Ш>Так вот, это множество не может быть определено через КС грамматику.
Кто вам это сказал?

Ш>Это и означает, что C++ не контекстно свободный язык.
Ваш вывод (неверный, кстати) основан на вашем же и утверждении.

Ш>Будем спорить, что 2+2==4?
Не въехал...

Может все-таки откроете грамматику С++ и предоставите доказательства? (ака правила, которые требуют, чтобы переменная была обьявлена один и только один раз)

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

Ш>>Да нет, это у вас непонимание элементарных вещей. Есть язык C++, есть множество well-formed программ на этом языке, которое представляет из себя некоторое множество конечных цепочек букв.
А>Может дадите определение ваших "well-formed программ на этом языке?"

Читайте стандарт. По простому, well-formed программа -- это то, что компилятор C++, написанный в соответствии со стандартом, должен пропустить через себя и сгенерировать некоторый объектный код.

Ш>>Так вот, это множество не может быть определено через КС грамматику.
А>Кто вам это сказал?

Это доказано. Математически строго.
Читайте этот тред, а так же специальную литературу.

Ш>>Будем спорить, что 2+2==4?
А>Не въехал...

Вы пытаетесь оспорить, что 2+2==4. Таких людей обычно посылают в дет. сад.

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

А>Пришла зима. Нестерпимая жара установилась на дворе. Грамматика С++ — контекстно-свободная! В этом форуме куча тем. Кто из нас всех прав? Опять пришла зима и т.д.
А>[/q]
А>Это пример из русского языка. Как видите, с точки зрения русской грамматики параграф и все предложения верны, но тем не менее смысла они не имеют. Точно также и с С++. Даже Лаптев, вон, выше заметил, что языки описываются КС грамматиками.

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

Неужели так трудно внимательно проситать то, о чем здесь выше говорилось? Как об стенку горох, честное слово! Как в том анекдоте: папа, а ты с кем сейчас разговаривал? Мне кажется, тут дело либо в невнимательности (если не в чем похуже!), либо в элементарном неуважении к собеседнику.

M>То, о чем Вы говорите как о грамматике русского языка и порождающая грамматика Хомского, это, как говорят в Одессе, две большие разницы.
А Вы считаете, что предложения русского и английских языков, например, не могут быть описаны порождающей грамматикой Хомского? Если да, то Вы ОШИБАЕТЕСЬ!!! Как Вы сами и знаете, КЗ грамматики используются в переводчиках с одного естественного языка на другой, и пример с грамматикой русского языка и грамматикой С++ очень хорошо описывает сущность этих грамматик!

M>Неужели так трудно внимательно проситать то, о чем здесь выше говорилось? Как об стенку горох, честное слово!
Это я должен сказать "как об стенку горох, честное слово!"

M>Мне кажется, тут дело либо в невнимательности (если не в чем похуже!), либо в элементарном неуважении к собеседнику.
Мне тоже так кажется, но только дело здесь в том, что это ВЫ не желаете прислушаться к тому, что здесь говорят.

Ш>Читайте стандарт. По простому, well-formed программа -- это то, что компилятор C++, написанный в соответствии со стандартом, должен пропустить через себя и сгенерировать некоторый объектный код.
Слышал Шахтер звон да так и не понял где он!

Используя грамматику С++, можно вывести следующую функцию:

void foo()
{
       int i;
       return i;   // Все синтаксически здесь верно!!!
}

но нельзя вывести эту функцию:

void foo()
}
{  // Скобки перепутали местами...

Ш>Это доказано. Математически строго.
Ш>Читайте этот тред, а так же специальную литературу.
Это Вам надо посоветовать перечитать этот тред и запастись специальной литературой.

Ш>Вы пытаетесь оспорить, что 2+2==4. Таких людей обычно посылают в дет. сад.
Это Вы пытаетесь оспорить то, о чем совсем не имеете понятия!

ЗЫ. Хватит голословности! Может все-таки приведете мне какие-нибудь правила из грамматики С++, уличающие этот язык в контекстно-зависимости?!! Ы?

Ш>Вы пытаетесь оспорить, что 2+2==4. Таких людей обычно посылают в дет. сад.
Не говорите мне куда идти если не хотите быть посланным по одному всем известному адресу!

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

А>Используя грамматику С++, можно вывести следующую функцию:
А>

А>void foo()
А>{
А>       int i;
А>       return i;   // Все синтаксически здесь верно!!!
А>}
А>

Это не есть well-formed программа на языке С++. Грамматика языка должна описывать все well-formed программы и только well-formed программы. Если грамматика описывает все well-formed и еще множество не well-formed программ то это не грамматика данного языка. Исключить множество не well-formed программ языка С++ можно только при помощи КЗ грамматики.
Но тк КЗ грамматика это очень сложно то используют компромисный вариант. Создают КС грамматику которая описывает язык являющеяси над множеством данного языка и создают допольнительные правила для отсечения не well-formed программ. И сделано это не по тому что грамматика языка КС, а по тому что построение КЗ грамматики во первых очень сложный процесс сам по себе во вторых парсер получается ну ооочееень медленный.

WH>Это не есть well-formed программа на языке С++. Грамматика языка должна описывать все well-formed программы и только well-formed программы. Если грамматика описывает все well-formed и еще множество не well-formed программ то это не грамматика данного языка. Исключить множество не well-formed программ языка С++ можно только при помощи КЗ грамматики.
WH>Но тк КЗ грамматика это очень сложно то используют компромисный вариант. Создают КС грамматику которая описывает язык являющеяси над множеством данного языка и создают допольнительные правила для отсечения не well-formed программ. И сделано это не по тому что грамматика языка КС, а по тому что построение КЗ грамматики во первых очень сложный процесс сам по себе во вторых парсер получается ну ооочееень медленный.
WolfHound, ну зачем говорить о чем не имеешь представления?

WH>Это не есть well-formed программа на языке С++.
А никто и не говорил, что это well-formed программа. Если взять грамматику С++, построить ее распознователь (а не компилятор!!!), то он скажет: "Да, эта функция была выведена грамматикой С++!"

WH>Грамматика языка должна описывать все well-formed программы и только well-formed программы.
Опять, кто это сказал? Грамматика должна описывать все синтаксически верные программы! Учите теорию. Чуете разницу между лексикой, синтаксисом и семантикой?

А вообще, откройте Страуструпа и убедитесь, что непонравившаяся Вам функция выводится грамматикой С++!

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

M>>То, о чем Вы говорите как о грамматике русского языка и порождающая грамматика Хомского, это, как говорят в Одессе, две большие разницы.
А>А Вы считаете, что предложения русского и английских языков, например, не могут быть описаны порождающей грамматикой Хомского? Если да, то Вы ОШИБАЕТЕСЬ!!! Как Вы сами и знаете, КЗ грамматики используются в переводчиках с одного естественного языка на другой, и пример с грамматикой русского языка и грамматикой С++ очень хорошо описывает сущность этих грамматик!

Так дискуссию вести невозможно, аргументы игнорируются, очевидные факты отвергаются. Поэтому, пытаюсь объяснить в последний раз:

Языком является множество строк, сформированных из символов данного алфавита. Порождающая грамматика Хомского — это устройство для порождения данных строк и только их. Язык может описываться не только порождающей грамматикой Хомского, а также и другими, каковых сущесвтует великое множество, как порождающих, так и не порождающих. кроме того, язык может быть описан без всякой грамматики. Например, предложение "множество сттрок, состоящих из нуля и более символов а" великолепно описывает язык, который задает грамматика:
S --> aS | пустая строка

Здесь ГДЕ-НИБУДЬ о семантике хоть слово было произнесено? Семанитка языка (в ее настоящем смысле, т.е. интепретация строк языка человеком) не имеет никакого отношения к описанию структуры строк языка (его предложений). Этим занимает синтаксис. Например, мы могли бы интерпретировать описанный выше язык так: символ а значит произнесение звука а в течении одной секунды. Тогда строка ааа обозначала бы, что некий человек пропел а-а-а... три секунды подряд. То же самое и в си++. Множество предложений данного языка это (с некоторым обобщением) множество правильных программ, написанных на языке си++. Вот и встает задача: описать это множество программ, используя ТОЛЬКО порождающую грамматику Хомского. Это сделать можно, как возможно описать любые структурные построения (например, множество музыкальных этюдов). Но, КС-грамматика для этого не подойдет из-за свойства языка: каждое имя должно быть описано перед его использованием. Как я уже писал выше, данное свойство не может быть выражено КС-грамматикой. Так что все просто. Разумеется, язык можно описывать и не используя порождающие грамматики, а как-нибудь по другому. Например, как это делается в стандарте языка си++. Чать описывается КС-грамматикой. Но такое описание позволяет породить и неверные программы на си++. Поэтому, вводятся еще ограничения, причем в виде так называемых "семантических" правил. Это делать можно, но почему же при этом говорить, что КС-грамматика, описывающая часть языка, описывает весь язык!? С таким же успехом, я могу описать часть языка регулярной грамматикой, а остальную часть неформально на русском языке и сказать, что граматика языка си++ регулярна. Но это не так, конечно.

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


здесь

Владимир.

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

А>А вообще, откройте Страуструпа и убедитесь, что непонравившаяся Вам функция выводится грамматикой С++!
Ты сам то его читал?

Приведенное ниже описание синтаксиса С++ должно помочь пониманию языка. Оно не является точным определением языка С++...

(С) Язык программирования С++. Специальное издание. Б. Страуструп.

Да что там Страуструп читаем стандарт

This summary of C++ syntax is intended to be an aid to comprehension. It is not an exact statement of the language...

M>Так дискуссию вести невозможно, аргументы игнорируются, очевидные факты отвергаются.
Да-да-да... Аргументы игнорируются и очевидные факты отвергаются, но не мной а Вами!!!

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

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

M>кроме того, язык может быть описан без всякой грамматики. Например, предложение "множество сттрок, состоящих из нуля и более символов а" великолепно описывает язык, который задает грамматика:
M>S --> aS | пустая строка
Ну вот. Говорим о языке, который "может быть описан без всякой грамматики" и толкаем пример регулярной грамматики с использованием рекурсии (ака КС элемента)!!! Удивительная у Вас способность описывать простые грамматики более сложными!!! Неудивительно, что для языков программирования Вам нужна КЗ грамматика!


M>Здесь ГДЕ-НИБУДЬ о семантике хоть слово было произнесено?
Это Вы смешиваете чисто семантическая понятия с синтаксическими!

M>Семанитка языка (в ее настоящем смысле, т.е. интепретация строк языка человеком) не имеет никакого отношения к описанию структуры строк языка (его предложений). Этим занимает синтаксис. Например, мы могли бы интерпретировать описанный выше язык так: символ а значит произнесение звука а в течении одной секунды. Тогда строка ааа обозначала бы, что некий человек пропел а-а-а... три секунды подряд.
Долой абстрактные примеры и голословность! Все что от Вас требовалось — привести правила, которые требуют обьявления переменных один и только один раз! ВЫ ИХ НЕ ПРИВЕЛИ!

M>То же самое и в си++. Множество предложений данного языка это (с некоторым обобщением) множество правильных программ, написанных на языке си++.
Достает это уже. Повторюсь еще раз... Грамматика описывает только синтаксис языка, и ПРОГРАММА МОЖЕТ БЫТЬ СИНТАКСИЧЕСКИ ВЕРНОЙ, НО НЕВЕРНОЙ СЕМАНТИЧЕСКИ! Выше я уже привел два примера!

M>Вот и встает задача: описать это множество программ, используя ТОЛЬКО порождающую грамматику Хомского. Это сделать можно, как возможно описать любые структурные построения (например, множество музыкальных этюдов).

M>Но, КС-грамматика для этого не подойдет из-за свойства языка: каждое имя должно быть описано перед его использованием. Как я уже писал выше, данное свойство не может быть выражено КС-грамматикой.
Да кто Вам сказал, что требование, что имя должно быть описано до использования вообще должно быть выраженно через грамматику?!! ТРЕБОВАНИЕ, ЧТОБЫ ИМЯ БЫЛО ОБЬЯВЛЕНО ДО ИСПОЛЬЗОВАНИЯ — НЕФОРМАЛЬНО, И НЕ МОЖЕТ БЫТЬ ВЫРАЖЕННО ГРАММАТИКАМИ!!!

M>Так что все просто. Разумеется, язык можно описывать и не используя порождающие грамматики, а как-нибудь по другому. Например, как это делается в стандарте языка си++.

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

Как Вы опишите формально, что делает for loop? НИКАК! Точно также нельзя формально требовать, чтобы имена были обьявлены заранее. Это делается НЕФОРМАЛЬНО!

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

Именно эти и "семантические правила," которые неформальны, и требуют, чтобы имя было обьявлено. Все! Не путайте язык программирования с формальным языком!

M>Именно, понимание выразительной способности разных классов грамматик и составляет понимание идеи Хомского. Еще раз, в книге "Техники парсинга" есть такой рисунок:
Ну и зачем нам этот рисунок? Опять абстракция! Без него и так ясно, что существуют классы грамматик, которые описывают больше языков, чем другие, и сложность расспознавания которых выше. Вот и вся теория.

M>Владимир.
Учите теорию, Владимир, лучше!

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

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

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

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

А>>А вообще, откройте Страуструпа и убедитесь, что непонравившаяся Вам функция выводится грамматикой С++!
WH>Ты сам то его читал?
Читал, и только в оригинале приведенное тобой издание!

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

Это тебе не классы на С++ штамповать. Это именно те знания, которые делают программиста программистом!

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

Ответьте на два вопроса
1)Может ли порождающая грамматика языка порождать предложения не входящие в данный язык?
2)Что вы понимаете под предложением на языке С++?

Наезды поскипаны.