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

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

SJA>Но непонятно, как из IDENTIFIER перейти к type или variable. Нужны доп. данные.
SJA>Как для данного выражения построить КС ?

Можно так показать контекстную зависимость языка с предварительными объявлениями. Для каждого типа грамматики существует свой тип рапознавателя — математической абстракции, моделирующеймашину для распознавания языка, который заддается этой грамматикой:

Тип 0 (грамматики без ограничений) — машина Тьюринга
Тип 1 (КЗ грамматики) — линейно ограниченный автомат
Тип 2 (КС грамматики) — автомат с магазинной памятью (стеком)
Тип 3 (регулярные грамматики) — конечный автомат

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

ID --> Буква Буквы_Цифры
Буквы_Цифры --> Буква Цифра | Цифра Буква | пустая_строка
Буква --> ....
Цифра --> ....

Тогда, в процессе разбора, у нас при объявлении, допустим, имени x где-то в программе будет исполнено правило ID --> x и при встрече переменной далее в предложении, мы попытаемся найти все такие правила, записанные на ленте, и таким образом, узнать было ли такое объявление. Аналогично, можно поступить с типизированными именами, а также именами типов. Вот это, с большой натяжкой конечно и неформально, можно считать доказательством контесктной зависимости языка с предварительными объявлениями имен.

LVV>Я! Я прочитаю! Пошлите меня, пожалуйста по указанному адресу!!!

Зуевская диссертация лежит здесь: http://www.interstron.ru/publications.html. А насчет диссертации Александра Кротова надо наверное попростить его самого или кого-то из Интерстрона, чтобы выслали.

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

LVV>>Я! Я прочитаю! Пошлите меня, пожалуйста по указанному адресу!!!

M>Зуевская диссертация лежит здесь: http://www.interstron.ru/publications.html. А насчет диссертации Александра Кротова надо наверное попростить его самого или кого-то из Интерстрона, чтобы выслали.
Большое спасибо, Владимир! Пока прочитаю Зуева. Это не его книжка по турбо паскалю в начале 90-х вышла?

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

Алгоритм Эрли и алгоритм Кока-Янгера-Касами распознают КС языки за кубическое время, а однозначные языки вообще за квадратичное. Валиант в 1975 году придумал оптимизацию алгоритма Кока-Янгера-Касами посредством битового массива, поиск по которому дает логорифмическое время. Так что, теперь, по последним данным, анализ строки длиной N для я зыка, заданного КС-грамматикой, может быть произведен за время N * N * log N.

LVV>Большое спасибо, Владимир! Пока прочитаю Зуева. Это не его книжка по турбо паскалю в начале 90-х вышла?

Честно говоря, не знаю, скорее всего. Он в МГУ преподавал, а потом уехал в Швейцарию, в Цюрих, не помню как у них университет называется, известный довольно.

Посыпаю голову пеплом...

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

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

А вот допустим я построю граматику, в которой не будет разницы между типом и переменной, а всё это будет identifier. Тогда граматика будет вроде как КС ? Вот мальенький пример:
Язык такой (показаны все допустимые конструкции). Идентификатор может быть function или variable. Затем его можно "активировать":
function f;
variable v;
f();
v();

Можно написать такую КС граматику:
program : /*empty*/ | statement_list
statement_list : statement | statement_list statement
statement : func_decl | var_decl | activate
func_decl : 'function' IDENTIFIER ';'
var_decl : 'variable' IDENTIFIER ';'
activate : IDENTIFIER '(' ')'

IDENTIFIER — набор букв.

Вроде граматика КС ? Разобрав ею программу и построив дерево можно приступить к определению что есть что в каждой конкретной "активизации".
Что тут не верно ?

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

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

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

SJA>А вот допустим я построю граматику, в которой не будет разницы между типом и переменной, а всё это будет identifier. Тогда граматика будет вроде как КС ? Вот мальенький пример:
SJA>Язык такой (показаны все допустимые конструкции). Идентификатор может быть function или variable. Затем его можно "активировать":
SJA>function f;
SJA>variable v;
SJA>f();
SJA>v();

SJA>Можно написать такую КС граматику:
SJA>program : /*empty*/ | statement_list
SJA>statement_list : statement | statement_list statement
SJA>statement : func_decl | var_decl | activate
SJA>func_decl : 'function' IDENTIFIER ';'
SJA>var_decl : 'variable' IDENTIFIER ';'
SJA>activate : IDENTIFIER '(' ')'

SJA>IDENTIFIER — набор букв.

SJA>Вроде граматика КС ? Разобрав ею программу и построив дерево можно приступить к определению что есть что в каждой конкретной "активизации".
SJA>Что тут не верно ?

Грамматика, конечно, контекстно свободная. Но, штука в том, что она не описывает тот язык, который Вы подразумеваете. Например, я пишу следущее:

b();

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

program ==> statement_list ==> statement ==> activate ==> IDENTIFIER '(' ')'

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

[skipped]

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

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

--
aga

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

M>Грамматика, конечно, контекстно свободная. Но, штука в том, что она не описывает тот язык, который Вы подразумеваете. Например, я пишу следущее:

M>b();

M>При разборе в соответствии только с вышеприведенной грамматикой, все будет хорошо, мы получим следующий вывод (дерево разбора):

M>program ==> statement_list ==> statement ==> activate ==> IDENTIFIER '(' ')'

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

Так. Кажется понял. То есть все предложения(тексты?), которые может породить граматика должно быть верной программой (в смысле компилироваться, а не работать) ? Тогда эта граматика является собственно граматикой языка ?
И если я правильно понял, то обычно компиляторы пользуются некоторой КС граматикой, которая более/менее описывают язык, а потом производят доп. обработку — семантический анализ ?

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

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

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

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

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

C++\CLI кстати содержит context-bound keywords.

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

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

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

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

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

SJA>Тогда как это стыкуется с примером:
SJA>x();
SJA>Что тут x ? Тип или переменная (с переопределённым оператором () ) ? Вроде есть зависимость от контекста... ?

Зависмость семантического смысла конструкции от контекста, размеется, есть. Но ни к грамматике, ни к ее контекстной независимости это никакого отношения не имеет.

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

M>Си++, как и большинство других языков программирования, контекстно зависим. Любая операция, где присутствует тип, является контестно зависимой.

M>...

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

Все это хорошо, но тем не менне не имеет никакого отношения к исходному вопросу. Вопрос был о том, является ли грамматика языка С++ контекстно зависимой. Ответ однозначен — не является. Грамматика языка С++ является контекстно свободной по определению, т.к. в левой части каждого правила этой грамматики стоит ровно один нетерминал. Все.

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

Здравствуйте, Андрей Галюзин, Вы писали:

АГ>[skipped]

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

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

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

      *
    /  \
  /      \
 x        y

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

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

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

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

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

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

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

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

АТ>Все остальные рассуждения и примеры, которые тут обильно привдятся, на самом деле не имеют никакого отношения к грамматике языка С++.
Во! My man! Поддерживаю на все сто!