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

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

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

Д>Проблема в том, что здесь нужно иметь детальную информацию о каждом типе. Если это класс — нужно иметь полный список его конструкторов и операторов преобразования, иначе не получится различить случаи 2а, 2б и 3.
Д>Не нужно забывать и про операторы неявного преобразования типов, которые тихо и незаметно делают свое грязное дело

Гланое, что всю эту информацию можно выразить в некотором тексте. А раз так, то, значит, и в формальном языке. Отсюда, с большой долей вероятности (в случае Си++, стопроцентной), можно утверждать, что эту информацию можно закодировать в некоторой порождающей грамматике. Просто понятия типа, идентификатора, преобразования типа и всего остального, чем мы оперируем, не будет. Будет только множество текстов, которое генерируется согласно определенным правилам. Здесь ярко выявляется фундаментальное различие между человеком и машиной.

mefrill,

> VD>цитата из спецификации C# 2.0:
> VD>

> VD>9.2.3 Grammar ambiguities
> VD>The productions for simple-name (§14.5.2) and member-access (§14.5.4) can give rise to ambiguities in the
> VD>grammar for expressions. <...>

> <...>

Согласен с вводной частью относительно квалификации языков по Хомскому и прочими общими положениями.

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

Для описанных правил разрешения неоднозначностей в C# "смысл" идентификаторов никакого значения не имеет, они "работают" исключительно на основании синтаксиса рассматриваемой конструкции. В частности, например, вне зависимости от того, как были определены идентификаторы F, G, A и B ранее, выражение:

F(G<A, B>(7));

в соответствии с описанными правилами, будет всегда распознано как вызов F с одним аргументом, являющимся вызовом generic метода с двумя аргументами-типами (A и B), плюс одним "обычным" аргументом (7).

А раз знания о "смысле" идентификаторов не требуется, то и тезис о способе образования идентификаторов, процитированный чуть выше, насколько я вижу, к вопросу Влада не относится.

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

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


VD>Извини, но это уже самовнушение. Может от так же сложен для распознования (хотя естественные языки еще никто полностью распознать не сомог).

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

VD>Ну, да. ООП посредственно. ФП совсем посредственно. Логического вообще нет. АОП тоже. Какие еще парадигмы в нем реализованы?

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

Не буду отвечать на остальное, иначе мы наверняка зайдем в беспредметный флейм, в спор о вскусах. Мне интересно ответить вопрос относительно пардигм, которые реализует Си++. Вот я прочитал "Логического вообще нет" и задумался. действительно, логической парадигмы Си++ напрямую не поддерживает, но зато поддерживает декларативное программирование на этапе компиляции! Алгоритм нахождения нужного типа в процессе инстанциирования шаблона схож с прологовским. Ниже я набросал небольшую програмку, тем не менее, вполне позволяющую задавать вопросы и отвечать на них в стиле логического программирования. Кроме деларативного стиля, Си++ поддерживает еще и Generic Programming и относительно ООП в Си++, мне кажется, реализовано гораздо шире примитивной концепции ОО, где объекты представляются машинами состояний, которые закодированы в свойствах объекта и меняются посредством вызова методов.

#include <iostream>

enum { mersedes, volga, moskvich };
enum { Vasya, Slava, Petya };

// predicates

template < int, int > struct Predicate {};

template < int Name_  > struct Question{
   Question()
   { 
      Predicate < Name_, mersedes > q1;
      Predicate < Name_, volga > q2; 
      Predicate < Name_, moskvich > q3;
   }
};

// facts

template <> struct Predicate < Vasya, mersedes >{
   Predicate(){ std::cout << "Vasya - mersedes\n"; }
};

template <> struct Predicate < Vasya, volga >{
   Predicate(){ std::cout << "Vasya - volga\n"; }
   };

template <> struct Predicate < Slava, volga >{
   Predicate(){ std::cout << "Slava - volga\n";  }
};

template <> struct Predicate < Petya, volga >{
   Predicate(){ std::cout << "Petya - volga\n";  }
};

int main()
{
   // what auto Vasya has got?
   Question < Vasya > q;
   
   return 0;
}

Здравствуйте, Павел Кузнецов, Вы писали:

ПК>mefrill,

>> VD>цитата из спецификации C# 2.0:
>> VD>

>> VD>9.2.3 Grammar ambiguities
>> VD>The productions for simple-name (§14.5.2) and member-access (§14.5.4) can give rise to ambiguities in the
>> VD>grammar for expressions. <...>

>> <...>

ПК>Согласен с вводной частью относительно квалификации языков по Хомскому и прочими общими положениями.

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

ПК>Для описанных правил разрешения неоднозначностей в C# "смысл" идентификаторов никакого значения не имеет, они "работают" исключительно на основании синтаксиса рассматриваемой конструкции. В частности, например, вне зависимости от того, как были определены идентификаторы F, G, A и B ранее, выражение:
ПК>

ПК>F(G<A, B>(7));
ПК>

ПК>в соответствии с описанными правилами, будет всегда распознано как вызов F с одним аргументом, являющимся вызовом generic метода с двумя аргументами-типами (A и B), плюс одним "обычным" аргументом (7).

ПК>А раз знания о "смысле" идентификаторов не требуется, то и тезис о способе образования идентификаторов, процитированный чуть выше, насколько я вижу, к вопросу Влада не относится.

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

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

F(G<A, B>(7));

И главная трудность состоит в том, что без знания типа объекта, представленного в тексте программы именем G, мы не можем правильно провести интерпретацию данного фрагмента. Если тип G это имя некоторого объекта, то понятно, что G < A это операция меньше, примененная к двум объектам с именами G и A. Если же, G это имя параметрического типа, то к нему, очевидно, такую операцию применить нельзя. Поэтому, вводя в граматику нетерминалы Generic_Type и Identifier, а также и способы их объявления мы вполне можем эту неоднозначность в грамматике преодолеть. Что-то типа:

typename--> Generic_Type '<' Identifier, Identifier '>'
expr --> typename '(' Identifier ')' | Identifier '<' Identifier | expr, expr | ...


Ничего другого я и не имел ввиду. Но, вероятно, я неверно понял вопрос?

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

А еще ";" — это же монадный bind. Тач что, ФП реализовано круче, чем в Haskell.

mefrill,

> ПК> вне зависимости от того, как были определены идентификаторы F, G, A и B ранее, выражение:
> ПК>

> ПК>F(G<A, B>(7));
> ПК>

> ПК>в соответствии с описанными правилами, будет всегда распознано как вызов F с одним аргументом, являющимся вызовом generic метода с двумя аргументами-типами (A и B), плюс одним "обычным" аргументом (7).
>
> ПК>А раз знания о "смысле" идентификаторов не требуется, то и тезис о способе образования идентификаторов, процитированный чуть выше, насколько я вижу, к вопросу Влада не относится.
>
> ПК>В процитированном фрагменте стандарта C# я не увидел ничего, что не может быть описано с помощью КС-грамматики, хотя, конечно, получившаяся грамматика будет изрядно громоздкой.

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

> F(G<A, B>(7));
>

Да, собственно говоря, очень любопытный пример, т.к. и C#, и C++ в силу сходного синтаксиса неизбежно сталкиваются с одной и той же проблемой. Но решили эту неоднозначность авторы C# и авторы C++ по-разному.

> И главная трудность состоит в том, что без знания типа объекта, представленного в тексте программы именем G, мы не можем правильно провести интерпретацию данного фрагмента. Если тип G это имя некоторого объекта, то понятно, что G < A это операция меньше, примененная к двум объектам с именами G и A. Если же, G это имя параметрического типа, то к нему, очевидно, такую операцию применить нельзя.

Это подход, принятый в C++. Более сложный для анализа компилятором, и, действительно, не поддающийся описанию контекстно-свободной грамматикой, т.к. как минимум не проще задания грамматикой предварительного объявления переменных, что сводит задачу к классике.

> Поэтому, вводя в граматику нетерминалы Generic_Type и Identifier, а также и способы их объявления мы вполне можем эту неоднозначность в грамматике преодолеть. Что-то типа:
>
> typename--> Generic_Type '<' Identifier, Identifier '>'
> expr --> typename '(' Identifier ')' | Identifier '<' Identifier | expr, expr | ...
>
> Ничего другого я и не имел ввиду. Но, вероятно, я неверно понял вопрос?

Вопрос

Автор: VladD2
Дата: 22.12.04

Влада был в том, приводит ли другой способ разрешения данной неоднозначности, принятый в C# 2.0, к невозможности описать язык контекстно-свободной грамматикой.

"Смысл" данной конструкции в C# 2.0 определяется не "значением" идентификаторов, а только тем, какая лексема стоит за закрывающей угловой скобкой. Если это одно из следующего:

( ) ] : ; , . ? == !=

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

If a sequence of tokens can be parsed (in context) as a simple-name (§14.5.2), member-access (§14.5.4), or
pointer-member-access (§25.5.2) ending with a type-argument-list (§26.5.1), the token immediately following the closing > token is examined. If it is one of

( ) ] : ; , . ? == !=

then the type-argument-list is retained as part of the simple-name, member-access or pointer-member-access and any other possible parse of the sequence of tokens is discarded.

Чтобы совсем уж прояснить ситуацию, можно рассмотреть простой пример:

F(G<A, B>(7));

в C# 2.0 не будет разобрано как:

F( (G<A), (B>(7)) );

даже если G, A и B являются именами переменных типа int. В этом случае скобочки нужно будет расставить руками, т.к. без них компилятор C# 2.0 должен будет "жаловаться" на то, что G не является именем generic типа.

Вероятно смутившее '(in context)', в данной формулировке из спецификации C# означает то, что данные правила применяются только к тем случаям, где в процессе разбора мы натолкнулись на возможность в данном месте отпарсить, скажем, G<A, B>, по-разному. Если в данном месте альтернативных способов разбора данного выражения нет, то данные правила не применяются. В частности в конце цитаты приводятся два примера, это дело иллюстрирующих:

x = F<A> + y;

всегда будет разобрано как

x = (F < A) > (+y);

т.к. после '>' не следует одна из ранее перечисленных лексем. А в выражении:

x = y is C<T> + z;

это значения не имеет, т.к. после 'y is' никакие альтернативы, приводящие к тому, что <T> не будет аргументами С, идти не могут.

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

M>Здравствуйте, Шахтер, Вы писали:

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

Ш>>По поводу конкретно С++. В приложении к Красному дракону (русскому издание) есть грамматики С++ и С#, написанные Зуевым. Эти грамматики написаны на входном языке Yacc а, т.е. это LARL(1) грамматики (в них, правда, использована способность Yacc а генерировать парсер с учётом приоритета и ассоциативности, но насколько я смотрел, как раз эти неопределённости можно устранить за счет усложнения грамматики). Так что если там всё сделано правильно (на 100% я, конечно, не могу поручиться), то проблем с парсингом не должно быть.

M>Был флейм по поводу того, я вляется ли грамматика Си++ КЗ или КС. В конце-концов мы дошли до того, что грамматика, которая описана в Стандарте, на самом деле язык Си++ не описывает, а описывает некоторое его надмножество. Ограничения на конструкции этого надъязыка потом описываются не в терминах порождающий грамматик. Примерно тоже самое и в примере грамматики Си++ для Яка. Я, к сожалению, доступа прямо сейчас к этой книжке не имею, но я читал диссертацию Зуева. Там он как раз и описывает проблемы, возникающие при реализации синтаксического анализатора для Си++ с помощью Яка. Как он описывает, о линейном разборе не приходится говорить, приходится делать пробные разборы вперед, а затем возвращаться, т.е. как выше Иван Косарев говорил, делать откаты. И дело здесь не в конкретной грамматике, а в языке. Его свойства положить в прокрустово ложе LR(k) грамматики полностью не удается. как я уже написал выше, к книжке я доступа не имею, потому конкретные примеры не могу привести. Но, мне кажется, мы можем доверять мнению Зуева. все-таки это мнение в диссертации высказано.

Ну, собственно, если вернуться немного к теме. Вопрос ведь в том, насколько большую часть работы может выполнить LR(1) парсер, и сколько "хаков" в него нужно вставить, чтобы получить требуемое.

Ещё. По поводу GLR. Если я правильно понял, там генерируется дерево возможных разборов. Но тут возникает (в С++ по крайней мере), проблема экспоненциального роста числа ветвей. Разве нет?

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

Здравствуйте, Павел Кузнецов, Вы писали:

>> И главная трудность состоит в том, что без знания типа объекта, представленного в тексте программы именем G, мы не можем правильно провести интерпретацию данного фрагмента. Если тип G это имя некоторого объекта, то понятно, что G < A это операция меньше, примененная к двум объектам с именами G и A. Если же, G это имя параметрического типа, то к нему, очевидно, такую операцию применить нельзя.

ПК>Это подход, принятый в C++. Более сложный для анализа компилятором, и, действительно, не поддающийся описанию контекстно-свободной грамматикой, т.к. как минимум не проще задания грамматикой предварительного объявления переменных, что сводит задачу к классике.

Если я правильно понимаю ситуацию, то эта проблема решается встраиванием name lookup непосредственно в LR(1) парсер, т.е. парсер, вытащив очередной токен-идентификатор, должен запустить процедуру name lookup для нахождения определения идентификатора (отсюда растет корнями невозможность отказаться в С++ от принципа предварительного объявления как это сделано в С#) и определения его рода (т.е. это имя типа, переменной или шаблона). После чего происходит доквалификация идентификатора до идентификатора одного из этих типов, что позволяет разрешить неоднозначность.

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

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

M>Трудность синтаксического анализа действительно присутствует. Но просто потому, что Си++ не укладывается в LR(k) грамматику. А парсеры типа Bison как раз на такой грамматике и работают. Поэтому начинаются извращения, выраженные в бесконечных попытках упростить грамматику Си++ чтобы она работала на Bison. Сейчас есть хороший метод разбора, который работает для всех грамматик, без ограничений: алгоритм Томиты, еще называемый GLR. Если использовать этот алгоритм, то проблем не возникает.

Проблема возникает в скорости парсинга. GLR разрабатывался как алгоритм для разбора грамматик как раз естественных
языков и он быстр только по сравнению с другими алгоритмами для такого рода разбора. Кстати последние версии Bison поддерживают GLR. А если бы ты внимательно читал мое сообщение, то заметил бы упоминание о GLR(Generalised LR) и о генераторе парсеров Elkhound, который позволяет переключаться между GLR и LR, что значительно ускоряет процесс. Тем не менее даже используя этот замечательный беспроблемный алгоритм, полный парсер C++ написать пока никому не удалось. Упомянутый Шахтером EDG C++ frontend написан вручную как и другие парсеры компиляторов промышленного уровня, и на их разработку были затраченны многие десятки человеко-лет. Тогда как на полный, безглючный и юзабельный парсер того же C# уходит максимум два человеко-года.

M>Я понимаю, что в наш серенький век, когда в программировании присутствуют мириады ламеров, принцип "чем проще, тем лучше" превалирует надо всем остальным. Но, мне кажется, все-таки необходимо оставить людям отдушину, строем не все хотят ходить.
Можно я буду говорить за себя, а не за мириады других ламеров, коим я тоже отчасти являюсь...
Для меня такой отдушиной являются Prolog и Haskell, а строем в моем понимании ходят все те, кто программирует на ОО императивных языках, проще которых может быть только бревно. И я не хочу очередной клон Java, мне нужен универсальный язык, поддерживающий мета-программирование с человеческим лицом. C++ в этом отношении уже не устраивает.

P.S. В статье на которую я сослался в корневом сообщении темы как раз было многое сказано о особом отношении к себе и окружающим у C++ программистов.

Шахтер,

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

> ПК> Это подход, принятый в C++. Более сложный для анализа компилятором, и, действительно, не поддающийся описанию контекстно-свободной грамматикой, т.к. как минимум не проще задания грамматикой предварительного объявления переменных, что сводит задачу к классике.

> Если я правильно понимаю ситуацию, то эта проблема решается встраиванием name lookup непосредственно в LR(1) парсер, т.е. парсер, вытащив очередной токен-идентификатор, должен запустить процедуру name lookup для нахождения определения идентификатора

В общем да, но ему далеко не обязательно делать это для каждого встреченного идентификатора. Можно отложить поиск имени до момента, когда анализ непосредственно дойдет до неоднозначности. Правда, иногда это сделать нелегко, к тому же порой приходится делать возврат, т.к. неоднозначность распознается уже после того, как первые шаги разбора пошли в "неверном" направлении. Но это все равно может оказаться более эффективным, чем поиск имен для всех идентификаторов.

> (отсюда растет корнями невозможность отказаться в С++ от принципа предварительного объявления как это сделано в С#)

А вот как это следует из предыдущего, я пока не вижу. Имхо, в C++ вполне можно ввести модули, при импорте которых компилятор будет подгружать те же определения сущностей, которые он строит при анализе заголовков, включенных директивой препроцессора. Вопрос больше не в технических аспектах, а в том, чтобы удачно совместить концепцию модулей с огромным количеством уже существующего кода, использующего #include. Благо, хоть какие-то подвижки в этом направлении уже начались.

uw,

> Упомянутый Шахтером EDG C++ frontend написан вручную как и другие парсеры компиляторов промышленного уровня, и на их разработку были затраченны многие десятки человеко-лет.

Что вызвано по большей степени инкрементными изменениями языка по ходу написания парсеров. "Полный, безглючный и юзабельный" парсер для C++ в его текущем состоянии вполне можно написать за один-два человеко-года, если не меньше. За заметно меньшее время был написан полный компилятор (вместе с back-end'ом) C++-подобного языка. Правда, писал его человек, съевший не одну собаку на этом деле, писавший ранее в том числе и компилятор для Ады, которая тоже легкостью анализа не отличается.

Здравствуйте, Павел Кузнецов, Вы писали:

ПК>Шахтер,

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

>> ПК> Это подход, принятый в C++. Более сложный для анализа компилятором, и, действительно, не поддающийся описанию контекстно-свободной грамматикой, т.к. как минимум не проще задания грамматикой предварительного объявления переменных, что сводит задачу к классике.

>> Если я правильно понимаю ситуацию, то эта проблема решается встраиванием name lookup непосредственно в LR(1) парсер, т.е. парсер, вытащив очередной токен-идентификатор, должен запустить процедуру name lookup для нахождения определения идентификатора

ПК>В общем да, но ему далеко не обязательно делать это для каждого встреченного идентификатора. Можно отложить поиск имени до момента, когда анализ непосредственно дойдет до неоднозначности. Правда, иногда это сделать нелегко, к тому же порой приходится делать возврат, т.к. неоднозначность распознается уже после того, как первые шаги разбора пошли в "неверном" направлении. Но это все равно может оказаться более эффективным, чем поиск имен для всех идентификаторов.

Можно делать загрузку следующего токена, и, если в синтаксической таблице нашлась неоднозначность, запускать name lookup немедленно, в противном случае, отложенно. Смысл всего этого -- как можно меньше отойти от классического LR(1) парсера, чтобы упростить реализацию парсинга и большую часть её делать механически по механически же сгенерированным синтаксическим таблицам, а не вручную.

Я, правда, не совсем понимаю, какой бенефит от отложенного name lookup. Его же всё равно нужно делать, раньше или позже. Единственное, что приходит на ум -- упрощение архитектуры компилятора. В плане эффективности не должно быть разницы.

>> (отсюда растет корнями невозможность отказаться в С++ от принципа предварительного объявления как это сделано в С#)

ПК>А вот как это следует из предыдущего, я пока не вижу.

А где я буду делать name lookup? Только в отпарсеной части кода, т.е. перед идентификатором. Всё, что следует после -- terra incognita.

ПК>Имхо, в C++ вполне можно ввести модули, при импорте которых компилятор будет подгружать те же определения сущностей, которые он строит при анализе заголовков, включенных директивой препроцессора.

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

ПК>Вопрос больше не в технических аспектах, а в том, чтобы удачно совместить концепцию модулей с огромным количеством уже существующего кода, использующего #include. Благо, хоть какие-то подвижки в этом направлении уже начались.

Идея прекрасная, синтаксис только дурной. Почему бы не ввести ключевое слово module и не писать, например, using module std;? Не стоит перегружать namespace.

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

Шахтер,

> Я, правда, не совсем понимаю, какой бенефит от отложенного name lookup. Его же всё равно нужно делать, раньше или позже.

Смотря для чего пишется парсер. Например, если для средств автоматизации, то не обязательно. Для "полного" парсера, по идее, разницы не должно быть.

>>> (отсюда растет корнями невозможность отказаться в С++ от принципа предварительного объявления как это сделано в С#)

> ПК>А вот как это следует из предыдущего, я пока не вижу.

> А где я буду делать name lookup? Только в отпарсеной части кода, т.е. перед идентификатором. Всё, что следует после -- terra incognita.

Технически сделать возможность разрешать подобные неоднозначности без требования предварительного объявления можно. Вопрос в другом: хочется ли этого? Для C++ явным образом давно решили, что не хочется. Не по соображениям эффективности, а для того, чтобы уменьшить вероятность подхвата "чужих" имен. Правда, насколько это будет актуально, если введут модули, вопрос открытый.

> ПК> Имхо, в C++ вполне можно ввести модули, при импорте которых компилятор будет подгружать те же определения сущностей, которые он строит при анализе заголовков, включенных директивой препроцессора.

> Ну разумеется, только это не противоречит принципу предварительного объявления <...>

Ok. В первый раз я тебя неправильно понял.

> Идея прекрасная, синтаксис только дурной. Почему бы не ввести ключевое слово module и не писать, например, using module std;? Не стоит перегружать namespace.

Да, мне синтаксис тоже как-то не очень понравился.

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

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

M>>Здравствуйте, Шахтер, Вы писали:

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

Ш>>>По поводу конкретно С++. В приложении к Красному дракону (русскому издание) есть грамматики С++ и С#, написанные Зуевым. Эти грамматики написаны на входном языке Yacc а, т.е. это LARL(1) грамматики (в них, правда, использована способность Yacc а генерировать парсер с учётом приоритета и ассоциативности, но насколько я смотрел, как раз эти неопределённости можно устранить за счет усложнения грамматики). Так что если там всё сделано правильно (на 100% я, конечно, не могу поручиться), то проблем с парсингом не должно быть.

M>>Был флейм по поводу того, я вляется ли грамматика Си++ КЗ или КС. В конце-концов мы дошли до того, что грамматика, которая описана в Стандарте, на самом деле язык Си++ не описывает, а описывает некоторое его надмножество. Ограничения на конструкции этого надъязыка потом описываются не в терминах порождающий грамматик. Примерно тоже самое и в примере грамматики Си++ для Яка. Я, к сожалению, доступа прямо сейчас к этой книжке не имею, но я читал диссертацию Зуева. Там он как раз и описывает проблемы, возникающие при реализации синтаксического анализатора для Си++ с помощью Яка. Как он описывает, о линейном разборе не приходится говорить, приходится делать пробные разборы вперед, а затем возвращаться, т.е. как выше Иван Косарев говорил, делать откаты. И дело здесь не в конкретной грамматике, а в языке. Его свойства положить в прокрустово ложе LR(k) грамматики полностью не удается. как я уже написал выше, к книжке я доступа не имею, потому конкретные примеры не могу привести. Но, мне кажется, мы можем доверять мнению Зуева. все-таки это мнение в диссертации высказано.

Ш>Ну, собственно, если вернуться немного к теме. Вопрос ведь в том, насколько большую часть работы может выполнить LR(1) парсер, и сколько "хаков" в него нужно вставить, чтобы получить требуемое.

Ш>Ещё. По поводу GLR. Если я правильно понял, там генерируется дерево возможных разборов. Но тут возникает (в С++ по крайней мере), проблема экспоненциального роста числа ветвей. Разве нет?

Нет, не все возможные ветви дерева, а только те, которые могут быть выведены в данном контексте. Фактически, это тот же LR(k) разборщик, только, если в каком-то месте непонятно, какую альтернативу выбрать, разбор этих двух альтернатив идет параллельно и потом где-то обрывается, если, конечно, грамматика, однозначная. Скорость, понятно, от этого страдает, и память жрется, но такова плата за сложность языка.

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

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

VD>>Смешно. Я конечно понимаю, что на 100 странице может оказаться то, что нужно. Но до этого я и сам могу додуматься. Я просил прямую ссылкну на дельное изложение. И желательно по русски. Темболее, что веловек говорил о том, что у него какая-то большая статья по этому поводу есть.

M>Вечером из дому вышлю.

выслал

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

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

M>>Трудность синтаксического анализа действительно присутствует. Но просто потому, что Си++ не укладывается в LR(k) грамматику. А парсеры типа Bison как раз на такой грамматике и работают. Поэтому начинаются извращения, выраженные в бесконечных попытках упростить грамматику Си++ чтобы она работала на Bison. Сейчас есть хороший метод разбора, который работает для всех грамматик, без ограничений: алгоритм Томиты, еще называемый GLR. Если использовать этот алгоритм, то проблем не возникает.

uw>Проблема возникает в скорости парсинга. GLR разрабатывался как алгоритм для разбора грамматик как раз естественных
uw>языков и он быстр только по сравнению с другими алгоритмами для такого рода разбора.

Нет, это неверно. Для LR(k)-грамматик GLR разборщик будут работать также быстро как и LR(k)-анализатор. Фактически, алгоритм Томиты и есть алгоритм LR(k)-анализа. Отличия появляются только, когда входная грамматика не укладывается в LR(k)-условия.

uw>Кстати последние версии Bison поддерживают GLR. А если бы ты внимательно читал мое сообщение, то заметил бы упоминание о GLR(Generalised LR) и о генераторе парсеров Elkhound, который позволяет переключаться между GLR и LR, что значительно ускоряет процесс.

Тем не менее даже используя этот замечательный беспроблемный алгоритм, полный парсер C++ написать пока никому не удалось.

Ну почему же??? Куча парсеров в сети имеется. Например здесь. Для написания этого разборщика специально генератор на основе алгоритма Томиты был разработан.

uw>Упомянутый Шахтером EDG C++ frontend написан вручную как и другие парсеры компиляторов промышленного уровня, и на их разработку были затраченны многие десятки человеко-лет. Тогда как на полный, безглючный и юзабельный парсер того же C# уходит максимум два человеко-года.

Парсер это ведь не только синтаксический анализатор. При использовании хорошего метода анализа написание самомго синтаксического анализатора превращается в простейшую операцию. Трудности возникают при реализации семантики.

M>>Я понимаю, что в наш серенький век, когда в программировании присутствуют мириады ламеров, принцип "чем проще, тем лучше" превалирует надо всем остальным. Но, мне кажется, все-таки необходимо оставить людям отдушину, строем не все хотят ходить.
uw>Можно я буду говорить за себя, а не за мириады других ламеров, коим я тоже отчасти являюсь...
uw>Для меня такой отдушиной являются Prolog и Haskell, а строем в моем понимании ходят все те, кто программирует на ОО императивных языках, проще которых может быть только бревно. И я не хочу очередной клон Java, мне нужен универсальный язык, поддерживающий мета-программирование с человеческим лицом. C++ в этом отношении уже не устраивает.

Согласен про Пролог и Хаскел. Но ведь Вы в работе все же Си++, Java или C# используете? Значит тратите примерно треть жизни на написание программ именно на этих языках. Т.е. реальная альтернатива в современном промышленном программировании есть то, что я перечислил? Вот из этих языков я выбираю Си++. Относительно "ламеров" я имел ввиду только то, что дизайнеры как Java так и C#, ввиду ограничений, зашиты против дурака, введенных в эти языки, пошли на поводу у тех самых "ламеров". В этом отношении Си++, несомненно, демократичнее. Разве нет? А если мне нравится программировать на Си++, почему мне это запрещают делать? Ведь, как говорил Козьма Прутков: хочешь быть счастливым — будь им! Не нравится программировать на Си++, не программируй. Используй другой язык. Я просто не понимаю все эти разговоры про сложность языка.

uw>P.S. В статье на которую я сослался в корневом сообщении темы как раз было многое сказано о особом отношении к себе и окружающим у C++ программистов.

Ну а разве это плохо? Это нормальное отношение человека к своей профессии, гордость, если хотите, принадлежностью к гильдии.

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

M>Вечером из дому вышлю.

Буду очень признателен.

Здравствуйте, Павел Кузнецов, Вы писали:

ПК>mefrill,

>> ПК> вне зависимости от того, как были определены идентификаторы F, G, A и B ранее, выражение:
>> ПК>

>> ПК>F(G<A, B>(7));
>> ПК>

>> ПК>в соответствии с описанными правилами, будет всегда распознано как вызов F с одним аргументом, являющимся вызовом generic метода с двумя аргументами-типами (A и B), плюс одним "обычным" аргументом (7).
>>
>> ПК>А раз знания о "смысле" идентификаторов не требуется, то и тезис о способе образования идентификаторов, процитированный чуть выше, насколько я вижу, к вопросу Влада не относится.
>>
>> ПК>В процитированном фрагменте стандарта C# я не увидел ничего, что не может быть описано с помощью КС-грамматики, хотя, конечно, получившаяся грамматика будет изрядно громоздкой.

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

>> F(G<A, B>(7));
>>

ПК>Да, собственно говоря, очень любопытный пример, т.к. и C#, и C++ в силу сходного синтаксиса неизбежно сталкиваются с одной и той же проблемой. Но решили эту неоднозначность авторы C# и авторы C++ по-разному.

>> И главная трудность состоит в том, что без знания типа объекта, представленного в тексте программы именем G, мы не можем правильно провести интерпретацию данного фрагмента. Если тип G это имя некоторого объекта, то понятно, что G < A это операция меньше, примененная к двум объектам с именами G и A. Если же, G это имя параметрического типа, то к нему, очевидно, такую операцию применить нельзя.

ПК>Это подход, принятый в C++. Более сложный для анализа компилятором, и, действительно, не поддающийся описанию контекстно-свободной грамматикой, т.к. как минимум не проще задания грамматикой предварительного объявления переменных, что сводит задачу к классике.

>> Поэтому, вводя в граматику нетерминалы Generic_Type и Identifier, а также и способы их объявления мы вполне можем эту неоднозначность в грамматике преодолеть. Что-то типа:
>>
>> typename--> Generic_Type '<' Identifier, Identifier '>'
>> expr --> typename '(' Identifier ')' | Identifier '<' Identifier | expr, expr | ...
>>
>> Ничего другого я и не имел ввиду. Но, вероятно, я неверно понял вопрос?

ПК>Вопрос

Автор: VladD2
Дата: 22.12.04

Влада был в том, приводит ли другой способ разрешения данной неоднозначности, принятый в C# 2.0, к невозможности описать язык контекстно-свободной грамматикой.

ПК>"Смысл" данной конструкции в C# 2.0 определяется не "значением" идентификаторов, а только тем, какая лексема стоит за закрывающей угловой скобкой. Если это одно из следующего:
ПК>

ПК>( ) ] : ; , . ? == !=
ПК>

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

ПК>

If a sequence of tokens can be parsed (in context) as a simple-name (§14.5.2), member-access (§14.5.4), or
ПК>pointer-member-access (§25.5.2) ending with a type-argument-list (§26.5.1), the token immediately following the closing > token is examined. If it is one of
ПК>

ПК>( ) ] : ; , . ? == !=
ПК>

ПК>then the type-argument-list is retained as part of the simple-name, member-access or pointer-member-access and any other possible parse of the sequence of tokens is discarded.

ПК>Чтобы совсем уж прояснить ситуацию, можно рассмотреть простой пример:
ПК>

ПК>F(G<A, B>(7));
ПК>

ПК>в C# 2.0 не будет разобрано как:
ПК>

ПК>F( (G<A), (B>(7)) );
ПК>

ПК>даже если G, A и B являются именами переменных типа int. В этом случае скобочки нужно будет расставить руками, т.к. без них компилятор C# 2.0 должен будет "жаловаться" на то, что G не является именем generic типа.

ПК>Вероятно смутившее '(in context)', в данной формулировке из спецификации C# означает то, что данные правила применяются только к тем случаям, где в процессе разбора мы натолкнулись на возможность в данном месте отпарсить, скажем, G<A, B>, по-разному. Если в данном месте альтернативных способов разбора данного выражения нет, то данные правила не применяются. В частности в конце цитаты приводятся два примера, это дело иллюстрирующих:
ПК>

ПК>x = F<A> + y;
ПК>

ПК>всегда будет разобрано как
ПК>

ПК>x = (F < A) > (+y);
ПК>

ПК>т.к. после '>' не следует одна из ранее перечисленных лексем. А в выражении:
ПК>

ПК>x = y is C<T> + z;
ПК>

ПК>это значения не имеет, т.к. после 'y is' никакие альтернативы, приводящие к тому, что <T> не будет аргументами С, идти не могут.

Понял наконец . Трудности в понимании возникли еще и из-за того, что я правил "The productions for simple-name (§14.5.2) and member-access (§14.5.4)" не видел. Поэтому, могу только догадываться. Да, понятно, что здесь неоднозначности нет. Вот относительно контекстной зависимости надо еще посмотреть.

Можем ли мы свести проблему к "заглядыванию вперед" на 4 символа? Т.е. чтобы сделать выбор из помеченных правил

1. exr --> ID '<' ID * — свертка
2. generic_name --> ID '<' ID * ',' ID '>' — сдвиг символа ','

В некотором состоянии (видимо, это и есть тот "context" LR(k)-автомата), попытаться "разделить" эти состояния строкой предосмотра? Я думаю, вполне возможно. Но для этого нам необходимо строить LR(4)-автомат. В этом случае ,мы будем иметь дело с состояниями вида:


1. [exr --> ID '<' ID *, ',' ID '>' @] — где ',' ID '>' ( — это строка предосмотра и символ @ это один из символов ( ) ] : ; , . ? == !=

и состояниями

2. [generic_name --> ID '<' ID * ',' ID '>', ',' ID '>' @]

Все состояния группы один в данном контексте отбрасываются, так как, по условию, не существует вывода в грамматике, такого что за правилом 1 идет хотя бы один из символов ( ) ] : ; , . ? == !=. Т.е. в полученном состоянии LR(4)-автомата, которое есть ни что иное, как совокупность описанных выше двоек [помеченное правило, строка предосмотра] двойки вида 1 присутствовать не будут, значит и конфликта перенос\свертка также не будет.

Т.е. контекстной зависимости здесь тоже нет. проблема в построении LR(4) автомата. Число состояний там будем очень большим, что в принципе, при сегодняшнем наличии памяти, большого значения не играет.

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

Ш>Здравствуйте, Павел Кузнецов, Вы писали:

>>> И главная трудность состоит в том, что без знания типа объекта, представленного в тексте программы именем G, мы не можем правильно провести интерпретацию данного фрагмента. Если тип G это имя некоторого объекта, то понятно, что G < A это операция меньше, примененная к двум объектам с именами G и A. Если же, G это имя параметрического типа, то к нему, очевидно, такую операцию применить нельзя.

ПК>>Это подход, принятый в C++. Более сложный для анализа компилятором, и, действительно, не поддающийся описанию контекстно-свободной грамматикой, т.к. как минимум не проще задания грамматикой предварительного объявления переменных, что сводит задачу к классике.

Ш>Если я правильно понимаю ситуацию, то эта проблема решается встраиванием name lookup непосредственно в LR(1) парсер, т.е. парсер, вытащив очередной токен-идентификатор, должен запустить процедуру name lookup для нахождения определения идентификатора

Вряд ли возможно таким образом решить проблему. Дело здесь в том, что LR-анализатор использует LR-автомат, который строится на основе входной граматики. Что такое есть состояние LR-автомата? Это совокупность двоек [помеченное правило, строка предосмотра], где "помеченное правило" это просто правило грамматики с точкой в правой части. Точка показывает какая часть правила уже распознана в данном контексте анализа. А строка предосмотра это некоторая цепочка терминальных символов грамматики. Состояние LR-автомата строится как совокупность таких двоек до любого запуска алгоритма синтаксического анализа. Поэтому, name lookup здесь не может быть применен в принципе.

Ш>(отсюда растет корнями невозможность отказаться в С++ от принципа предварительного объявления как это сделано в С#) и определения его рода (т.е. это имя типа, переменной или шаблона). После чего происходит доквалификация идентификатора до идентификатора одного из этих типов, что позволяет разрешить неоднозначность.

Вот пример выше как раз и является хорошей иллюстрацией почему так нехорошо использовать LR(k)-анализаторы при анализе Си++. Как я уже говорил, мы получяем конфликт типа перенос\свертка и анализатор дальше работать не может. А при сипользовании GLR анализатор работает дальше, проводя анализ как для переноса, так и для свертки. Мы же, при построении дерева разбора, можем, на основе семантики идентификатора G, просто перестать строить дерево для свертки, таким образом разрешая неоднозначность.

Здравствуйте, Павел Кузнецов, Вы писали:

>> (отсюда растет корнями невозможность отказаться в С++ от принципа предварительного объявления как это сделано в С#)

ПК>А вот как это следует из предыдущего, я пока не вижу. Имхо, в C++ вполне можно ввести модули, при импорте которых компилятор будет подгружать те же определения сущностей, которые он строит при анализе заголовков, включенных директивой препроцессора. Вопрос больше не в технических аспектах, а в том, чтобы удачно совместить концепцию модулей с огромным количеством уже существующего кода, использующего #include. Благо, хоть какие-то подвижки в этом направлении уже начались.

Насколько я помню, примерно тоже было в Visual Age C++ версии 1998 года. Но там, по-моему даже язык не расширялся. Организация модулей производилась на уровне проекта.