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

SW>> Определение понятия "контекстная зависимость" в студию.

АГ>С++ (как и С) является контекстно-зависимым языком. Т.е. конструкцию языка не всегда можно распознать без знания ее более широкого контекста.

Меня вот ещё смущает такой вопрос... Ведь граматику можно построить упрощённую. Например:

statement : obj_or_type '(' ')';
obj_or_type : IDENTIFIER;
IDENTIFIER : [a-z_][a-z0-9_]*;

Теперь выражение x(); будет распознано однозначно. Нельзя ли написать для C/C++ такую простенькую контекстно свободную граматику ? А если можно, то как должен определяться порог "сложности" или "детальности" грамматики ?
Ведь я могу написать грамматику
program : TEXT;
TEXT : .*
?

Приветствуются также ссылки....

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

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

SJA>>>Первых два раза было больше похоже на "нет"
_>>вы уж простите. я от Re[2]: char, потоки

Автор: Sir Wiz
Дата: 27.07.04

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

SW>Очень хорошее слово "ИМХО".
SW>Вот и +1 за выдающуюся самокритику

Автор: dimitry_dimitry
Дата: 27.07.04

улетел
да у меня тоже децтво не сахар было.
и не люблю я ссылки и С++ ИО-потоки, с ссылками я кстати объяснил почему.
а с потоками — из недавнего — человек сделал код с потоками — посмотрел по библиотекам — прицепилось еще 2 длл. ужос!!
и УБЛЮДОЧНО вы уж простите выглядит конструкция с потоками.
я ничего не имею против оператора << но в данном случае ...ну неудобно.
то ли дело printf. а?
а я себя не критиковал. я вас спросил.

Здравствуйте, Нахлобуч, Вы писали:


SJA>>>

_W>>>>int main()
_W>>>>{
_W>>>>  X x(); <- декларация фунции или переменная x ?
_W>>>>}
SJA>>>

D>>Нет, это всегда декларация функции.

Н>Эта строка является объявлением функции только тогда, когда она появляется в Global Scope, иначе это — вызов конструктора по умолчанию для объекта класса.

Предлагаю Вам самому убедиться в обратном:

#include <iostream>

class X
{
    X()
    {
        std::cout << "X::X() called";
    }
};

int main(int argc, char* argv[])
{
    X x();
    return 0;
}

Хомский, человек, который ввел понятие генеративной грамматики, определил ее как множество G={N,T,P,S} из четырех элементов: N — нетерминальные символы? T — терминальные, P — правила и S — начальный символ грамматики. Терминальные смиволы это слова языка, в си++ это, различные лексемы, типа идентификатор, слово, которое начинается с буквы и потом может идти ряд цифр или букв, ри этом символ подчеркивания считается буквой, и т.д. В стандарте все эти лексемы определены. нетерминальные мимволы явно в языке не существуют, они как бы нызывают некие совокупности слов, т.е. терминалов языка. Например, описание функции можно назвать нетерминалом Function_Description. Правила, понятно, позволяют задать соответствие между нетерминальными символами и терминалами языка, например: Function_Description --> Type ID '(' list_of_parameters ')' ';' Здесб все — терминалы языка, за исключением нетерминала list_of_parameters. Хомский также ввел различные типы грамматик, нас здесь как раз интересуют грамматики типа 1 и 2, т.е. контекстно-зависимые (КЗ) и контекстно-независимые или контекстно-свободные (КС) типы. КН задается правилами вида: alpha A beta --> alpha B beta, где alpha и beta строки, состоящие как из терминалов, так и из нетерминалов языка. Они могут быть пустыми. Смысл здесь состоит в том, что нетерминал A может значить либо, например B, как в нашем правиле, либо какой-нибудь C, как в правиле alpha1 A beta1 --> alpha1 С beta1, в зависимости от строк alpha и beta, т.е. от контекста, в котором этот нетерминал встретился. А в КС-грамматиках такого нет, нетерминал всегда значит одно и то же, поэтому там все правила имеют вид A --> alpha B beta, что можно обозначить просто как A --> alpha, т.к. alpha это строка нетерминальных и терминальных символов.

Си++, как и большинство других языков программирования, контекстно зависим. Любая операция, где присутствует тип, является контестно зависимой. Действительно, если мы определяем функцию как void foo( int, char ) и потом вызываем foo( a, b ), то этот вызов будет законным только тогда, когда типы фактических параметров подходят под типы формальных. А это как раз контекстная зависимость. Просто, обычно все КЗ вещи убирают из грамматики языка, не давая работать с ними синтаксическому анализатору. КЗ конструкции языка тогда называют семантикой языка и разрешают эти проблемы вручную. Если язык достаточно сложный, как си++, то это сделать сложно, приходится извращаться изменяя грамматику, подгоняя ее под какй-либо алгоритм синтаксического анализа и, в результате, исходная грамматика, та, что в стандарте, изменяется очень сильно. Для конкретной конструкции x(); можно задать правила:

Fun_call --> ID '(' list_of_params ')' ';'
Constructor --> ID '(' list_of_params ')' ';'

Эта конструкция неоднозначна, надо как-то решить при вызове x(); что это есть. Можно идти от типа x, и разрешить все на семантическом уровне, задавая правила:

Fun_call --> Fun_name '(' list_of_params ')' ';'
Constructor --> Type_name '(' list_of_params ')' ';'

Type ID '(' list_of_params ')' ';' --> Type Fun_name '(' list_of_params ')' ';'

И для Type_name то же самое, только целую кучу правил, как для встроенных типов, так и для определяемых самыми различными способами, программистом. Вот это правило как раз и есть КЗ.


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

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

С уважением,
Владимир.

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

D>Предлагаю Вам самому убедиться в обратном:

D>

D>#include <iostream>

D>class X
D>{
D>    X()
D>    {
D>        std::cout << "X::X() called";
D>    }
D>};

D>int main(int argc, char* argv[])
D>{
D>    X x();
D>    return 0;
D>}
D>

И шо ? Может, в понятиях непонимание ? Декларация функции — она же Function Declaration — предложение, связывающее идентификатор с относящейся к нему информацией; в некоторых случаях может быть одновременно и описанием (Definition, конструкция, размещающая в памяти и инициализирующая переменную, функцию или класс).
Здесь же просто создание объекта класса X, это эквивалентно

int main(int argc, char* argv[])
{
    X x;
    return 0;
}

Но! Вот так не прокатит:

X x();

int main(int argc, char* argv[])
{
    // Тра-та-та
    
    return 0;
}

поскольку для компилятора это будет выглядеть как определение функции, а раз оно так выглядит — то так и будет откомпилировано.

Здравствуйте, Нахлобуч, Вы писали:

Вы пробовали запускать приведённый код? Что он вывел на экран?

Здравствуйте, mefrill, Вы писали:
M>Си++, как и большинство других языков программирования, контекстно зависим.
А можно примеры извесных контекстно свободных языков ?

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

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

SW>>> Определение понятия "контекстная зависимость" в студию.
АГ>>С++ (как и С) является контекстно-зависимым языком. Т.е. конструкцию языка не всегда можно распознать без знания ее более широкого контекста.
Насколько я помню курс Линвистики — Грамматика является контекстно независимой, если для проверки правильности программы (написанной по этой грамматике) достаточно выполнить синтаксический разбор. Т.е. грамматика калькулятора — контекстно независима, а грамматика языка С++ — контекстно зависима (требуется семантический разбор).

Н>Здесь же просто создание объекта класса X, это эквивалентно

Н>

Н>int main(int argc, char* argv[])
Н>{
Н>    X x;
Н>    return 0;
Н>}
Н>

Нет, это НЕ эквивалентно. Строчку в стандарте, где сказано обратное, можете привести?

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

D>Здравствуйте, Нахлобуч, Вы писали:

D>Вы пробовали запускать приведённый код? Что он вывел на экран?

VC++ 2003 выдал свой Compiler Warning (level 1) C4930, а у Comeau все нормально. Но тогда почему

int x();

прокатывает?

SJA>А можно примеры извесных контекстно свободных языков ?

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

Выражение --> Число
Выражение --> Число + Число
Выражение --> Число — Число
Выражение --> Число * Число
Выражение --> Число / Число

Число, +, -, * и / — терминалы грамматики, Выражение — ее единственный нетерминал, который также является стартовым (S в определении грамматики).

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

Ну и написано, однако! Я так и не осилил.
M>Си++, как и большинство других языков программирования, контекстно зависим. Любая операция, где присутствует тип, является контестно зависимой. Действительно, если мы определяем функцию как void foo( int, char ) и потом вызываем foo( a, b ), то этот вызов будет законным только тогда, когда типы фактических параметров подходят под типы формальных. А это как раз контекстная зависимость.
Не путайте контекстную зависимость в теории формальных языков, с требованием, чтобы типы данных аргументов и параметров совпадали. Это разные вещи. Грамматика всего лишь пораждает предложения языка и за их смысловую нагрузку не отвечает! Согласно грамматике, мы можем передать в функцию ноль, один, два, ..., тысячу аргументов, и синтаксический анализатор все равно найдет нужную продукцию, согласно которой было выведено это предложение. Другое дело семантические рутины, которые как раз и заявят о несоответствии типов, количиств аргументов и т.д.

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

M>Для конкретной конструкции x(); можно задать правила:
M>Fun_call --> ID '(' list_of_params ')' ';'
M>Constructor --> ID '(' list_of_params ')' ';'

M>Эта конструкция неоднозначна, надо как-то решить при вызове x(); что это есть. Можно идти от типа x, и разрешить все на семантическом уровне, задавая правила:

M>Fun_call --> Fun_name '(' list_of_params ')' ';'
M>Constructor --> Type_name '(' list_of_params ')' ';'

M>Type ID '(' list_of_params ')' ';' --> Type Fun_name '(' list_of_params ')' ';'

M>И для Type_name то же самое, только целую кучу правил, как для встроенных типов, так и для определяемых самыми различными способами, программистом. Вот это правило как раз и есть КЗ.
Это неверно и продукции какие-то кривые.

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

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

M>Вообще, интересно, на кокой стадии усложнения язык становится настолько сложным, что его нельзя описать КС-грамматикой? Известно, что естественные языки типа русского и английского — КЗ языки. Си++ получается тоже КЗ язык. Что надо убрать из языка, чтобы он стал КС языком?
А ничего и не надо убирать! Грамматика С++ — контекстно-свободная грамматика, и потому, этот язык сам и является контекстно-свободным.

variable-declaration ::= type identifier; |
                                type identifier(argument-list);
function-call        ::= identifier(argument-list);

Курсивом выделены нетерминалы, темным — терминалы. Из этой, частичной граматики, неужели нельзя понять где обьявляется обьект а где вызывается функция? Для простоты, argument-list выводит как минимум один аргумент.

SJA>А можно примеры извесных контекстно свободных языков ?
C, C++, Java, C#, you name it! Все языки программирования описываются контекстно-свободными грамматиками.

Н>VC++ 2003 выдал свой Compiler Warning (level 1) C4930, а у Comeau все нормально. Но тогда почему

Н>

Н>int x();
Н>

Н>прокатывает?
Да потому что это обьявление функции х, которая возвращает инт и не принимает аргументов!

G> Насколько я помню курс Линвистики — Грамматика является контекстно независимой, если для проверки правильности программы (написанной по этой грамматике) достаточно выполнить синтаксический разбор. Т.е. грамматика калькулятора — контекстно независима, а грамматика языка С++ — контекстно зависима (требуется семантический разбор).
Неправильно Вы помните, хотя бы потому, что существуют четыре вида грамматик по Хомскому, и для каждой грамматики существует свой распознаватель. Разница заключается только в том, что каждый распознаватель имеет свою вычислительную сложность.

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

А>

А>variable-declaration ::= type identifier ; |
А>                                type identifier ( argument-list ) ;
А>function-call        ::= identifier ( argument-list ) ;
А>

А>Курсивом выделены нетерминалы, темным — терминалы. Из этой, частичной граматики, неужели нельзя понять где обьявляется обьект а где вызывается функция? Для простоты, argument-list выводит как минимум один аргумент.

Но у меня в примере было немного по другому. x(); — x — тип (вызов функции или конструирование объекта) или x — переменная (вызов оператора () ). Как для такого варианта построить контекстно свободную граматику ?
Вот мой вариант КЗ:
(терминалы БОЛЬШИМИ БУКВАМИ и 'в кавычках')

statement : type '(' ')' | variable '(' ')' ;
type : IDENTIFIER;
variable : IDENTIFIER;
где
IDENTIFIER -> [a-z_][a-z0-9_]*

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

SJA>Но у меня в примере было немного по другому. x(); — x — тип (вызов функции или конструирование объекта) или x — переменная (вызов оператора () ). Как для такого варианта построить контекстно свободную граматику ?
Дайте лучше другой пример или в более полном контексте (не путать с контекстной грамматикой!) или загляните в Страуструпа. Непонятна эта фраза — x(); — x — тип (вызов функции или конструирование объекта) или x — переменная (вызов оператора () )

SJA>Вот мой вариант КЗ:
SJA>(терминалы БОЛЬШИМИ БУКВАМИ и 'в кавычках')

SJA>statement : type '(' ')' | variable '(' ')' ;
SJA>type : IDENTIFIER;
SJA>variable : IDENTIFIER;
SJA>где
SJA>IDENTIFIER -> [a-z_][a-z0-9_]*

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

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

А>

А>variable-declaration ::= type identifier; |
А>                                type identifier(argument-list);
А>function-call        ::= identifier(argument-list);
А>

А>Курсивом выделены нетерминалы, темным — терминалы. Из этой, частичной граматики, неужели нельзя понять где обьявляется обьект а где вызывается функция? Для простоты, argument-list выводит как минимум один аргумент.

Нет, конечно нельзя понять. Где здесь указано, что x является типом или именем функции или переменной? В самой грамматике этого нет. Я же постарался объяснить почему нет. А нет потому, что типизированные конструкции, вместе с их объявлениями и определениями, КЗ по своей природе. Именно поэтому эти конструкции синтаксически не описаны, а перенесены на "семантический" уровень. Если попытаться описать си++ грамматикой (не его КС подмножество, или даже LARL(1) подмножество, как это делается в Bison например), то придется как-то отличать друг от друга имена пременных, функций, их типы и т.д. А сейчас у нас есть один лексический ID и таблица имен (точнее их несколько), которая эту контекстную зависимость и обрабатывает. Говорить же о грамматике языка си++ что она КС на основании приведенной выше иерархии, это все равно, что говорить, что грамматика си++ регулярная, на основании следующей "грамматики":

Программа --> Текст_Программы точка_с_запятой

Где и Текст_Программы и точка_с_запятой явяляются терминальными символами языка, а весь разбор происходит на этапе лексичекого (читай семантического!) анализа.

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

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

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

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

SJA>>Но у меня в примере было немного по другому. x(); — x — тип (вызов функции или конструирование объекта) или x — переменная (вызов оператора () ). Как для такого варианта построить контекстно свободную граматику ?
А>Дайте лучше другой пример или в более полном контексте (не путать с контекстной грамматикой!) или загляните в Страуструпа. Непонятна эта фраза — x(); — x — тип (вызов функции или конструирование объекта) или x — переменная (вызов оператора () )
А что тут непонятного ?
Вот полный пример:

class X {
public:
    int operator()() {
        return 666;
    };
};

int x() {
    return 999;
};

int main(int argc, char* argv[])
{
    {
        X x;
        int i = x();    //(1)
    }
    {
        int i = x();    //(2)
    }
    return 0;
}

Строки 1 и 2 одинаковые на вид, но в одном случае x это тип (функция), а в другом случае — переменная.
И без доп. данных это невозможно определить.

SJA>>Вот мой вариант КЗ:
SJA>>(терминалы БОЛЬШИМИ БУКВАМИ и 'в кавычках')

SJA>>statement : type '(' ')' | variable '(' ')' ;
SJA>>type : IDENTIFIER;
SJA>>variable : IDENTIFIER;
SJA>>где
SJA>>IDENTIFIER -> [a-z_][a-z0-9_]*

SJA>>Но непонятно, как из IDENTIFIER перейти к type или variable. Нужны доп. данные.
SJA>>Как для данного выражения построить КС ?
А>Терминалы большими буквами да еще и продукция для IDENTIFIER?
Я имел в виду, что терминалы обозначены большими буквами и символами в кавычках (так я в bison-е видел).
А продукция для IDENTIFIER: это я просто употребил неверный символ наверное "->"
Я имел в виду, что IDENTIFIER это последовательность букв, цифр и _ начинающаяся с _ или буквы.

А>И вопрос последний тоже непонятен.
Эт потому, что я и сам с трудом понимаю что говорю