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

uw>Тем не менее трудность парсинга без сомнения один из основных минусов C++. Лично я не видел ни одного open-source парсера С++ (написанного на C++) и поддерживающего хотя бы парсинг на уровне сравнимом с наиболее адекватными компиляторами. До следующей фазы компиляции у их разработчиков руки просто не дошли. Основные усилия ушли на парсинг. В OpenC++ парсер рукописный recursive descent + backtracking, для Elsa был специально написан смешанный generalised lr / lr генератор парсеров, FOG парсит суперсет грамматики C++, а затем уже устраняет неоднозначности.
uw>Вся эта работа была проделана ими зря !?

Трудность синтаксического анализа действительно присутствует. Но просто потому, что Си++ не укладывается в LR(k) грамматику. А парсеры типа Bison как раз на такой грамматике и работают. Поэтому начинаются извращения, выраженные в бесконечных попытках упростить грамматику Си++ чтобы она работала на Bison. Сейчас есть хороший метод разбора, который работает для всех грамматик, без ограничений: алгоритм Томиты, еще называемый GLR. Если использовать этот алгоритм, то проблем не возникает. Просто, язык Си++, в отличии от C или C# с Java, это язык следующего поколения, очень похожий на естественные языки. Похожесть заключается в реализации в языке множества различных парадигм, что повышает на порядок сложность языка. Ввиду этой сложности, для упрощения синтаксических конструкций, многие из них имеют многозначную семантику. Это не обязательно выражается в неоднозначности грамматики, но на сложность влияет. Тоже самое присутствует и в человеческих языках, когда для обозначения объектов какой-то новой реальности люди используют старые слова и языковые конструкции по аналогии с какой-нибудь известной областью. Я понимаю, что в наш серенький век, когда в программировании присутствуют мириады ламеров, принцип "чем проще, тем лучше" превалирует надо всем остальным. Но, мне кажется, все-таки необходимо оставить людям отдушину, строем не все хотят ходить.

"mefrill" <31689@users.rsdn.ru> wrote in message news:956550@news.rsdn.ru...

> Трудность синтаксического анализа действительно присутствует. Но просто
> потому, что Си++ не укладывается в LR(k) грамматику.

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

> А парсеры типа Bison как раз на такой грамматике и работают.

Bison понимает LALR грамматики.

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


IAK>"mefrill" <31689@users.rsdn.ru> wrote in message news:956550@news.rsdn.ru...

>> Трудность синтаксического анализа действительно присутствует. Но просто
>> потому, что Си++ не укладывается в LR(k) грамматику.

IAK>Не просто поэтому. Грамматика Си++ сложна грамматическими неоднозначностями,
IAK>которые есть неоднозначности независимо от класса грамматики. И эти
IAK>неоднозначности могут быть разрешены только имея на руках в каждый момент
IAK>времени полную семантическую информацию о том, что мы уже разобрали. И даже
IAK>этого иногда недостаточно — приходится пробовать несколько вариантов, делая,
IAK>в случае неудачи, откат как в состоянии парсера, так и в семантических
IAK>структурах.

На самом деле, неоднозначностей в Си++ не так много. И трудности, о которых ты говоришь (приходится делать откат) как раз связаны с невозможностью линейного разбора. Линейный же разбор (без возвратов) снизу-вверх и производит так называемый LR(k) автомат, придуманый в свое время Кнутом. Но LR(k)-анализатор это не единственный метод разбора, существует множество других методов. У меня есть статья, в которой я описываю эволюцию LR(k)-разборщиков за последние 30 лет. Эволюция происходила в направлении увеличения класса грамматик, которые можно использовать для LR(k)-анализа. Первой ласточкой была статья Бернара Лэнга, выпущенная в 1974 году, в кторой он предложил способ при возникновении конфликтов при построении LR(k)-автомата все же производить анализ, создавая новую копию магазина для каждого конфликта. Получается разновидность параллельного анализатора. В 1984 году Томита пытался найти хороший алгоритм, позволяющий производить анализ неоднозначных языков. Он также попытался расширить алгоритм LR(k)-анализа путем параллельного разбора. Но, вместо копирования магазина при возникновении конфликтов при анализе (типа перенос\свертка, свертка\свертка) предложил копировать только ссылки на элементы. В результате он получил так называемый GSS — Graph Structured Stack. Кроме того, из-за особенностей алгоритма разбора снизу-вверх если грамматика имеет возможность вывода A ==>+ A для некоторого нетерминала A (например, правила A --> B и B --> A), исходный алгоритм LR(k)-анализа мог запросто зациклиться. Томита предложил для каждого символа анализируемой строки запоминать множество правил, применных при анализе в данной позиции. это позволило избежать зацикливания. Тем не менее, проблемы все-равно остались. И связаны они были с так называемыми эпсилон правилами, в которых правая часть это пустая строка. В этих случаях алгоритм все еще работал некорректно. В 2000 году эта проблема была устранена путем модификации исходного LR(k)-автомата. Так что теперь алгоритм Томиты использовть можно, а для анализа таких языков как Си++ и необходимо. Как я уже говорил, у меня есть статья по этому поводу, где я эту эволюцию описываю подробно. Другим алгоритмом, который можно было использовать для разбора неоднозначных КС языков, можно считать алгоритм Эрли. проблема с этим алгоритмом состоит в том, что он производит только распознование входной строки, но не ее разбор. Т.е. алгоритм отвечает на вопрос выодится или нет входная строка в данной грамматике, но не строит вывода входной строки. Попытки того же Томиты построить хороший разборщик на основе алгоритма Эрли не увенчались успехом, поэтому данный алгоритм не популярен в данное время. Другой причиной его непопулярности можно признать его невысокую, в сравнении с LR(k)-анализаторами, скорость. Последнюю проблему удалось решить двум канадским математикам Эйкоку и Хорспулу в 1994 году. Проблему построения деревьев разбора для неоднозначной грамматики не так давно удалось решить вашему покорному слуге. Правда, пока статья, в которой я доказываю корректность алгоритма, находится на рецензии, поэтому "удалось решить" надо поставить в кавычки. Вообще, очень интересно проследить как два, вроде бы совершенно разных алгоритма: алгоритм Эрли и алгоритм LR(k)-анализа, эволюционировали таким образом, что сейчас немногим отличаются по своим характеристикам ,как скоростным, так и по объему класса грамматик, с которыми они работают.

Еще раз хотелось бы подчеркнуть, что необходимость производить возвраты (откаты) в процессе работы синтаксического анализатора, вовсе не означает, что входная грамматика является неоднозначной. Это означает только, что грамматика не является LR(k)-грамматикой ни для какого k. Неоднозначность же означает, что для анализируемой строки можно построить, по крайней мере, два различных дерева разбора. И в обычных процедурных языках программирования такие неоднозначности присутствуют. Например, известная проблема с if else. Такие проблемы разрешаются обычно семантически, путем сужения множества деревьев разбора при параллельном анализе или путем произведения возвратов при анализе в глубину. Но в Си++ есть также и конструкции, в которых и семантическим ограничением устранить неоднозначность невозможно. Известный пример в книжке Майерса.


>> А парсеры типа Bison как раз на такой грамматике и работают.

IAK>Bison понимает LALR грамматики.

Ну так, а алгоритм то все равно LR(k)-анализа используется? Потом, что такое LALR (lookahead LR) грамматика? Это грамматика, для которой можно построить LALR(k)-автомат. Множество состояний этого автомата получается из состоянияний LR(k)-автомата путем слияния состояний с одинаковыми ядрами. Все это делается для того, чтобы уменьшить количество состояний, которое для LR(k)-автомата может быть очень большим (опять же, с нашей теперешней памятью это не имеет большого значений). Проблема раньше состояла в том, чтобы построить LALR(k)-автомат не строя соответствующий LR(k)-автомат. Известный алгоритм Де Ремера производит данное построение за линейное время. Идея алгоритма восходит к знаменитому алгоритму боба Таржана нахождения сильно связанных компонентов графа за линейное время. В той версии бизона, которую я впросматривал пару лет назад именно де Ремеровский алгоритм и используется.

You wrote on Tue, 21 Dec 2004 10:47:04 GMT:

>>> Трудность синтаксического анализа действительно присутствует. Но
>>> просто потому, что Си++ не укладывается в LR(k) грамматику.

IAK>>Не просто поэтому. Грамматика Си++ сложна грамматическими
IAK>>неоднозначностями, которые есть неоднозначности независимо от класса
IAK>>грамматики. И эти неоднозначности могут быть разрешены только имея
IAK>>на руках в каждый момент времени полную семантическую информацию о
IAK>>том, что мы уже разобрали. И даже этого иногда недостаточно -
IAK>>приходится пробовать несколько вариантов, делая, в случае неудачи,
IAK>>откат как в состоянии парсера, так и в семантических структурах.

m> На самом деле, неоднозначностей в Си++ не так много.

Это только подтверждает мои слова.

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

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

Проблема в том, что сами неопределенности в Си++ разрешать трудно. Не
в силу их грамматических свойств, а в силу сложности самой семантики
языка. Попробовать свернуть одну из грамматических единиц, которая
может следовать далее — это не очень большая техническая проблема.

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

Эти две проблемы говорят, по меньшей мере, о следующем. Во-первых,
парсер Си++ в любом случае будет чем-то очень нерегулярным. Во-вторых,
и тем более доколе первое справедливо, это, может быть, вообще не очень
удачная идея для парсера с коммерческим будущим — разбирать грамматику
Си++ как принадлежащую какому-то классу. На мой взгляд. Здесь опять
два пункта. Во-первых, любой генератор разборщиков — это утилита для
серийного производства. И если мы пишем компилятор с Си++, это не
актуально. Уж как-нибудь, только чтоб правильно работало. Во-вторых,
не видно серьезных гарантий того, что завтра в Си++ не появится чего-
нибудь эдакого, что не влезает в ограничения существующего генератора.
И это было бы если не катастрофой, то уж точно большой головной болью
для разработчика.

m> Так что теперь алгоритм Томиты использовть можно, а для анализа
m> таких языков как Си++ и необходимо.

Ну, это вряд ли — что необходимо.

m> Еще раз хотелось бы подчеркнуть, что необходимость производить
m> возвраты (откаты) в процессе работы синтаксического анализатора,
m> вовсе не означает, что входная грамматика является неоднозначной. Это
m> означает только, что грамматика не является LR(k)-грамматикой ни для
m> какого k. Неоднозначность же означает, что для анализируемой строки
m> можно построить, по крайней мере, два различных дерева разбора. И в
m> обычных процедурных языках программирования такие неоднозначности
m> присутствуют. Например, известная проблема с if else. Такие проблемы
m> разрешаются обычно семантически, путем сужения множества деревьев
m> разбора при параллельном анализе или путем произведения возвратов при
m> анализе в глубину. Но в Си++ есть также и конструкции, в которых и
m> семантическим ограничением устранить неоднозначность невозможно.
m> Известный пример в книжке Майерса.

Ты можешь привести два различных дерева для if else?

Мало того, я не могу припомнить ни одного случая, чтобы if else собиралась
с участием семантических структур. Тем более интересно.

Мне известна в Си только одна неоднозначность, но она связана с
использованием typedef-names.

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

IAK>You wrote on Tue, 21 Dec 2004 10:47:04 GMT:

>>>> Трудность синтаксического анализа действительно присутствует. Но
>>>> просто потому, что Си++ не укладывается в LR(k) грамматику.

IAK>>>Не просто поэтому. Грамматика Си++ сложна грамматическими
IAK>>>неоднозначностями, которые есть неоднозначности независимо от класса
IAK>>>грамматики. И эти неоднозначности могут быть разрешены только имея
IAK>>>на руках в каждый момент времени полную семантическую информацию о
IAK>>>том, что мы уже разобрали. И даже этого иногда недостаточно -
IAK>>>приходится пробовать несколько вариантов, делая, в случае неудачи,
IAK>>>откат как в состоянии парсера, так и в семантических структурах.

m>> На самом деле, неоднозначностей в Си++ не так много.

IAK>Это только подтверждает мои слова.

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

IAK>Да, но я говорю не только и главным образом не об этом. Невозможность
IAK>линейного разбора — это слишком общая формулировка, чтобы можно было
IAK>уловить, почему разбирать код на Си++ трудно. Так вот моя мысль
IAK>заключалась в том, что эта трудность — она вообще и главным образом
IAK>не связана с тем, что грамматика Си++ не принадлежит какому бы то ни
IAK>было классу.

IAK>Проблема в том, что сами неопределенности в Си++ разрешать трудно. Не
IAK>в силу их грамматических свойств, а в силу сложности самой семантики
IAK>языка. Попробовать свернуть одну из грамматических единиц, которая
IAK>может следовать далее — это не очень большая техническая проблема.

IAK>Черт, как обычно, в деталях. Есть две вещи, которые создают главные
IAK>проблемы. Это, во-первых, то, что в попытках свернуть нечто, идущее
IAK>далее мы вынуждены изменять семантический контекст, который далеко
IAK>не всегда понятно как вообще можно было бы откатить (и по проблемности
IAK>это дело не идет ни в какое сравнение с копированиями магазинов и
IAK>прочим в том же духе). Во-вторых, к моменту, когда нужно выбирать или
IAK>пробовать сворачивать иногда требуется информация, которая не может
IAK>быть получена, если мы всегда разбираем сверху вниз. И уж тем более не
IAK>может быть получена, если всегда разбираем снизу вверх. Другими словами,
IAK>важно уметь доставить всю необходимую семантическую информацию до того
IAK>момента, когда нужно будет решать, что делать. И эта проблема тоже не
IAK>имеет отношения классам грамматик, но имеет самое что ни на есть прямое
IAK>отношение к тому, как должен работать парсер и, следовательно, как его
IAK>следует писать.

IAK>Эти две проблемы говорят, по меньшей мере, о следующем. Во-первых,
IAK>парсер Си++ в любом случае будет чем-то очень нерегулярным. Во-вторых,
IAK>и тем более доколе первое справедливо, это, может быть, вообще не очень
IAK>удачная идея для парсера с коммерческим будущим — разбирать грамматику
IAK>Си++ как принадлежащую какому-то классу. На мой взгляд. Здесь опять
IAK>два пункта. Во-первых, любой генератор разборщиков — это утилита для
IAK>серийного производства. И если мы пишем компилятор с Си++, это не
IAK>актуально. Уж как-нибудь, только чтоб правильно работало. Во-вторых,
IAK>не видно серьезных гарантий того, что завтра в Си++ не появится чего-
IAK>нибудь эдакого, что не влезает в ограничения существующего генератора.
IAK>И это было бы если не катастрофой, то уж точно большой головной болью
IAK>для разработчика.

Иван, честно говоря, я здесь запутался. Мне все-таки кажется, что мы говорим о разных вещах. Во-первых, я не понял про регулярность языка. Не мог бы ты пояснить, что ты под этим подразумеваешь? Во-вторых, мне снова неясно насчет "откатов". Я еще раз поясню, что я имею ввиду. Как известно, процесс разбора некторой терминальной строки в соответствии с данной грамматикой есть процесс построения дерева разбора данной строки, корнем которого служит стартовый символ грамматики. Если таких деревьев несколько, то вывод неоднозначен, все грамматика является неоднозначной. Но это еще не значит, что для данного языка невозможно построить другую, однозначную грамматику. Я, конечно, полагаю, что здесь мы имеем ввиду только контекстно-свободные грамматики. Есть языки, для которых однозначную граматику не построишь в принципе. Такие языки называются существенно неоднозначными. Таким образом, есть вопрос: является ли Си++ существенно неоднозначным языком? Вероятно да, а может быть и нет. Я не знаю, может кто-то знает? Далее, дерево разбора входной строки мы принципиально можем строить:
1. Сверху вниз.
2. Снизу вверх.
3. Поиском в ширину.
4. Поиском в глубину.

Любой алгоритм разбора есть комбинация вышепреведенных методов. Например, LR(k)-анализатор использует методы 2 и 3. Понятно, что алгоритм построения дерева разбора можно сопоставить с алгоритмом его обхода. Тогда поиск в глубину соответствует обходу: сначала рекурсивно обходим левый (правый или еще какой-то) узел дерева, вместе со всеми его дочерними узлами, затем остальные. Необходимость отката при поискев глубину следует из того, что КС-грамматика не является алгоритмом, но, по выражению А. Маркова, является исчислением. Это, как-бы, недетерминированный алгоритм. Для каждого нетерминала A грамматики может существовать сколь угодно много правил вида A --> alpha с нетерминалом A в левой части. Поэтому, при поиске в глубину, мы, как-бы, "пробуем" построить нижнее дерево разбора для данного правила и узла, помеченного нетерминалом, стоящим в левой части правила, и если не получилось, пробуем для другого правила — это и есть пресловутый "откат". Может так случится, что пробы дадут результат для нескольких правил — это и есть неоднозначность. Бывает, что как-бы "заглядывая" вперед на несколько символов входной строки, мы можем, не строя дерево разбора, определить какое правило использовать при построении дерева. Это и есть линейный разбор, в частности LR(k) и LL(k) анализаторы так и поступают. Если нельзя определить нужное правило ни для какого числа k, то такая грамматика и не будет LR(k) или LL(k) грамматикой. Относительно поиска в ширину, мы строим сначала все узлы текущего уровня дерева и только потом переходим к нижним. Понятно, что здесь вообще речь об "откатах" идти не может. Такой способ разбора мы можем смело назвать "параллельным".

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

m>> Так что теперь алгоритм Томиты использовть можно, а для анализа
m>> таких языков как Си++ и необходимо.

IAK>Ну, это вряд ли — что необходимо.

Ну почему же? Конечно необходимо раз бизон не справляется.

m>> Еще раз хотелось бы подчеркнуть, что необходимость производить
m>> возвраты (откаты) в процессе работы синтаксического анализатора,
m>> вовсе не означает, что входная грамматика является неоднозначной. Это
m>> означает только, что грамматика не является LR(k)-грамматикой ни для
m>> какого k. Неоднозначность же означает, что для анализируемой строки
m>> можно построить, по крайней мере, два различных дерева разбора. И в
m>> обычных процедурных языках программирования такие неоднозначности
m>> присутствуют. Например, известная проблема с if else. Такие проблемы
m>> разрешаются обычно семантически, путем сужения множества деревьев
m>> разбора при параллельном анализе или путем произведения возвратов при
m>> анализе в глубину. Но в Си++ есть также и конструкции, в которых и
m>> семантическим ограничением устранить неоднозначность невозможно.
m>> Известный пример в книжке Майерса.

IAK>Ты можешь привести два различных дерева для if else?

Ну так! Это же известный пример. Опишем if-else следующей грамматикой:

IF --> if BOOL EXP | if BOOL EXP else EXP
EXP --> IF | exp | ...

Возмем строку if BOOL if BOOL exp else exp. В соответствии с грамматикой выше мы ее можем разобрать:
1. IF ==> if BOOL EXP ==> if BOOL IF ==> if BOOL if BOOL EXP else EXP ==> if BOOL if BOOL exp else exp
2. IF ==> if BOOL EXP else EXP ==> if BOOL if BOOL EXP else EXP ==> if BOOL if BOOL exp else exp

Получили два различных левых вывода — то бишь дерева разбора.

IAK>Мало того, я не могу припомнить ни одного случая, чтобы if else собиралась
IAK>с участием семантических структур. Тем более интересно.

Ну вот, из примера выше не ясно, какое дерево вывода использовать, для решения необходимо задействовать семантический анализатор, чтобы отбросить одно из деревьев, т.е. решить, к какому if относится else. обычно делается выбор в пользу варианта 1.

IAK>Мне известна в Си только одна неоднозначность, но она связана с
IAK>использованием typedef-names.

Кто здесь ?

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

KK>Кто здесь ?
Тень уходящео меня.

Спать иди еси в соотв. часовом поясе.

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

IAK>>Ты можешь привести два различных дерева для if else?

M>Ну так! Это же известный пример. Опишем if-else следующей грамматикой:

M>IF --> if BOOL EXP | if BOOL EXP else EXP
M>EXP --> IF | exp | ...

M>Возмем строку if BOOL if BOOL exp else exp. В соответствии с грамматикой выше мы ее можем разобрать:
M>1. IF ==> if BOOL EXP ==> if BOOL IF ==> if BOOL if BOOL EXP else EXP ==> if BOOL if BOOL exp else exp
M>2. IF ==> if BOOL EXP else EXP ==> if BOOL if BOOL EXP else EXP ==> if BOOL if BOOL exp else exp

M>Получили два различных левых вывода — то бишь дерева разбора. <...> Ну вот, из примера выше не ясно, какое дерево вывода использовать, для решения необходимо задействовать семантический анализатор, чтобы отбросить одно из деревьев, т.е. решить, к какому if относится else. обычно делается выбор в пользу варианта 1.

Ну почему же необходимо? Можно подправить

Автор: Павел Кузнецов
Дата: 26.11.04

грамматику.

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

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

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

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

M>Трудность синтаксического анализа действительно присутствует. Но просто потому, что Си++ не укладывается в LR(k) грамматику.

Не только. По-моему, основная проблема объем парсинга, инклюды, и отсуствие модулей. А проблемы неоднозначностей все же разрешимы.

M> алгоритм Томиты, еще называемый GLR. Если использовать этот алгоритм, то проблем не возникает.

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

M> Просто, язык Си++, в отличии от C или C# с Java, это язык следующего поколения,

Ну, это уже смешно. С++ вызывает проблему не толко у парсеров. Люди тоже клинят. При этом на русском они вроде объщаются неплохо.

M> очень похожий на естественные языки.

Ну, так и вижу программистов читающих/пщуших С++-ый код со скоростью чтения/ответа форумов/в форумы.

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

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

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

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

M> что повышает на порядок сложность языка.

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

M> Ввиду этой сложности, для упрощения синтаксических конструкций, многие из них имеют многозначную семантику.

Не думаю, что у Создателей языка стаяла задача внести неоднозначности. Неоднозначности скорее вызваны наследием С и тем что никто специально не устранял оные.

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

Это называется перегрузкой и есть в любых языках. Например, многие ключевые слова Шарпа применяются в разных конструциях (using, return, get/set и т.п.).

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

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

M> Я понимаю, что в наш серенький век, когда в программировании присутствуют мириады ламеров, принцип "чем проще, тем лучше" превалирует надо всем остальным. Но, мне кажется, все-таки необходимо оставить людям отдушину, строем не все хотят ходить.

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

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

M>Ну вот, из примера выше не ясно, какое дерево вывода использовать, для решения необходимо задействовать семантический анализатор, чтобы отбросить одно из деревьев, т.е. решить, к какому if относится else. обычно делается выбор в пользу варианта 1.

О! Похоже нашелся человек который может рассудить один наш спор.

С if/else все понятно. Это пример из учебников. Все парсеры и так по умолчанию парсят if/else так как требуют 99% язвеоа. А вот если взять немного боле сложный случай. Например, вот цитата из спецификации C# 2.0:

9.2.3 Grammar ambiguities
The productions for simple-name (§14.5.2) and member-access (§14.5.4) can give rise to ambiguities in the
grammar for expressions. [Example: The statement:

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

could be interpreted as a call to F with two arguments, G < A and B > (7). Alternatively, it could be
interpreted as a call to F with one argument, which is a call to a generic method G with two type arguments
and one regular argument. end example]
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. Otherwise, the type-argument-list is not
considered to be part of the simple-name, member-access or pointer-member-access, even if there is no other
possible parse of the sequence of tokens. [Note: These rules are not applied when parsing a type-argument-
list in a namespace-or-type-name (§10.8). end note] [Example: The statement:

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

will, according to this rule, be interpreted as a call to F with one argument, which is a call to a generic
method G with two type arguments and one regular argument. The statements

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

will each be interpreted as a call to F with two arguments. The statement
x = F<A> + y;
will be interpreted as a less-than operater, greater-than operator and unary-plus operator, as if the statement
had been written x = (F < A) > (+y), instead of as a simple-name with a type-argument-list followed
by a binary-plus operator. In the statement

x = y is C<T> + z;

the tokens C<T> are interpreted as a namespace-or-type-name with a type-argument-list. end example]

Являются ли данные вещи всего лишь проблемами LL(1)/LALR(1) парсеров. Или все же это зависимость от контекста. И формально такую граматику нельзя назвать контекстно свободной?

Если можно, дай максимально развернутый ответ.

VladD2,

> M>Трудность синтаксического анализа действительно присутствует. Но просто потому, что Си++ не укладывается в LR(k) грамматику.

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

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

Модули в данном случае вообще мимо кассы, т.к. при требовании знания об определениях сущностей для разрешения неоднозначностей, единицу трансляции анализировать легче, чем набор модулей. Хотя скорость обработки всей программы от отсутствия модулей, естественно, падает.

> M> алгоритм Томиты, еще называемый GLR. Если использовать этот алгоритм, то проблем не возникает.
>
> А где можно почитать о сути этого алгоритма? Если на русском, то вообще здорово.

По-английски — валом. Даже применительно к C++: A Generated Parser of C++.

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

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

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

Не так можно в С++ неоднозначностей чтобы серьезно затормозить процесс распознования. Для R# я пользуюсь LL(1) парсером и приходится постоянно сифонить вперед, чтобы устранить LL(1)-неоднозначности, но на скорости это отражается не очень серьезно. К тому же если GLR — это действительно то, что я думаю, то снимаются очень многие проблемы.


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

Модули тут в кассу. А мимо кассы неоднозначности. Модльность позволяет не парсить все каждый раз от пчки. В обработанном модуле просто не должно быть неоднозначностей. Там лежат принципиально правильные метаданные. Ин не нужно распозновать. Их нужно тупо читать.

ПК>По-английски — валом.

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

ПК> Даже применительно к C++: A Generated Parser of C++.

Поглядим.

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

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

IAK>>>Ты можешь привести два различных дерева для if else?

M>>Ну так! Это же известный пример. Опишем if-else следующей грамматикой:

M>>IF --> if BOOL EXP | if BOOL EXP else EXP
M>>EXP --> IF | exp | ...

M>>Возмем строку if BOOL if BOOL exp else exp. В соответствии с грамматикой выше мы ее можем разобрать:
M>>1. IF ==> if BOOL EXP ==> if BOOL IF ==> if BOOL if BOOL EXP else EXP ==> if BOOL if BOOL exp else exp
M>>2. IF ==> if BOOL EXP else EXP ==> if BOOL if BOOL EXP else EXP ==> if BOOL if BOOL exp else exp

M>>Получили два различных левых вывода — то бишь дерева разбора. <...> Ну вот, из примера выше не ясно, какое дерево вывода использовать, для решения необходимо задействовать семантический анализатор, чтобы отбросить одно из деревьев, т.е. решить, к какому if относится else. обычно делается выбор в пользу варианта 1.

ПК>Ну почему же необходимо? Можно подправить

Автор: Павел Кузнецов
Дата: 26.11.04

грамматику.

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

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

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

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

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

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

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

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

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

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

И неудивительно. Например, такая любопытная конструкция:

foo(bar);

Это может обозначать как минимум 4 (!!!) совершенно разные конструкции.
Если говорить точнее, это может быть:
1. Вызов функции foo
2. Создание анонимного объекта типа foo (конструктор с одним параметром, или конструктор копирования)
3. Вызов оператора преобразования к типу foo (эквивалент bar.operator foo() )
4. Оператор приведения типов (если foo — это примитивный тип)
Великолепная демонстрация всей мощи C++

Не вижу ни одного реального способа распарсить этот код, если использовать только грамматики

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

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

M>>Ну вот, из примера выше не ясно, какое дерево вывода использовать, для решения необходимо задействовать семантический анализатор, чтобы отбросить одно из деревьев, т.е. решить, к какому if относится else. обычно делается выбор в пользу варианта 1.

VD>О! Похоже нашелся человек который может рассудить один наш спор.

VD>С if/else все понятно. Это пример из учебников. Все парсеры и так по умолчанию парсят if/else так как требуют 99% язвеоа. А вот если взять немного боле сложный случай. Например, вот цитата из спецификации 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. [Example: The statement:
VD>

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

VD>could be interpreted as a call to F with two arguments, G < A and B > (7). Alternatively, it could be
VD>interpreted as a call to F with one argument, which is a call to a generic method G with two type arguments
VD>and one regular argument. end example]
VD>If a sequence of tokens can be parsed (in context) as a simple-name (§14.5.2), member-access (§14.5.4), or
VD>pointer-member-access (§25.5.2) ending with a type-argument-list (§26.5.1), the token immediately
VD>following the closing > token is examined. If it is one of
VD>

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

VD>then the type-argument-list is retained as part of the simple-name, member-access or pointer-member-access
VD>and any other possible parse of the sequence of tokens is discarded. Otherwise, the type-argument-list is not
VD>considered to be part of the simple-name, member-access or pointer-member-access, even if there is no other
VD>possible parse of the sequence of tokens. [Note: These rules are not applied when parsing a type-argument-
VD>list in a namespace-or-type-name (§10.8). end note] [Example: The statement:
VD>

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

VD>will, according to this rule, be interpreted as a call to F with one argument, which is a call to a generic
VD>method G with two type arguments and one regular argument. The statements
VD>

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

VD>will each be interpreted as a call to F with two arguments. The statement
VD>x = F<A> + y;
VD>will be interpreted as a less-than operater, greater-than operator and unary-plus operator, as if the statement
VD>had been written x = (F < A) > (+y), instead of as a simple-name with a type-argument-list followed
VD>by a binary-plus operator. In the statement
VD>

VD>x = y is C<T> + z;
VD>

VD>the tokens C<T> are interpreted as a namespace-or-type-name with a type-argument-list. end example]

VD>Являются ли данные вещи всего лишь проблемами LL(1)/LALR(1) парсеров. Или все же это зависимость от контекста. И формально такую граматику нельзя назвать контекстно свободной?

VD>Если можно, дай максимально развернутый ответ.

Определение языка и, в частности, языка программирования также, в совю очередь, очень зависит от контекста . Например, если мы понимаем язык как множество текстов и, таким образом, абстрагируемся от смыслового содержания слов данного языка, то мы рассматриваем данный язык через призму теории формальных языков. Обычно, так как мы применяем машину для разбора или генерации строк языка, применяются порождающие грамматики Хомского — они дают хороший путь для определения алгоритма, хотя сами алгоритмом не являются. В этом смысле, сложность конструкций языка измеряется в терминах их алгоритмического определения. Т.е. один язык можно определить с помощью КС грамматики, другой нельзя. Получается, что мерой синтаксической сложности формального языка служит тип грамматики, которая этот язык порождает. Для данного язык существует, вообще говоря, бесконечное, хотя и счетное, множество грамматик, которые его порождают. Из этого множества можно выбрать подкласс грамматик наибольшего, в смысле определения Хомского, типа. Например, грамматики типа 2 — КС грамматики. Тогда формальный язык называется контекстно-свободным. Кстати, существует бесконечное множество языков (мощности континиума) для которых невозможно найти грамматику, их порождающую. итак, для формального языка мерой его сложности служит наибольший тип из типов всех грамматик, которые его попрождают. Когда же мы говорим о разборе языка программирования с помощью компилятора или, что тоже самое, об описаниии данного языка в некоем стандарте, мы уже имеем ввиду нечто большее, чем просто набор текстов. Мы описываем язык не только с помощью некоторой порождающей грамматики, но также и с помощью другого текста на некотором метаязыке, обычно, на человеческом. Та порождающая КС-грамматика, которая в приводится в стандартах, обычно описывает не сам язык, некоторое его надмножество. После чего, на метаязыке описаный надъязык сужается до требуемого языка. Т.е. из множества предложений надъязыка исключаются те, которые не удовлетворяют описанию на метаязыке. Относительно контекстной зависимости языков программирования известно, что условие предварительного объявления имен до их использования не может быть выражено синтаксически посредством КС-грамматики. Именно поэтому, при построении анализаторов, в грамматике надъязыка мы имеем дело с ID, а не с конкретными строками и способами их построения. Синтаксическая конструкция

Definition --> Type ID
Using ID

позволяет появляться в языке таким строкам, как Type ttt using aaa так как в синтаксисе не выражена связь между объявлением и использованием идентификатора. Связь эта выражена на метаязыке и реализуется обычно таблицей идентификаторов. Также известно, что эту связь можно выразить с помощью КЗ грамматики, убрав абстрактное ID и поставив вместо него синтаксические конструкции образования идентификаторов. Поэтому, рассматривая язык программирования как формальный язык, мы говорим, что такой язык не является КС, но есть КЗ, оценивая, таким образом, синтаксическую сложность данного языка как множества текстов. И только в таком контексте мы можем применять выражения типа "контекстно-свободный" или "контекстно-зависимый".

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

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

Вроде бы все.

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

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

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

Д>И неудивительно. Например, такая любопытная конструкция:
Д>

Д>foo(bar);
Д>

Д>Это может обозначать как минимум 4 (!!!) совершенно разные конструкции.
Д>Если говорить точнее, это может быть:
Д>1. Вызов функции foo
Д>2. Создание анонимного объекта типа foo (конструктор с одним параметром, или конструктор копирования)
Д>3. Вызов оператора преобразования к типу foo (эквивалент bar.operator foo() )
Д>4. Оператор приведения типов (если foo — это примитивный тип)
Д>Великолепная демонстрация всей мощи C++

Д>Не вижу ни одного реального способа распарсить этот код, если использовать только грамматики

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

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

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

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

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

Д>Здравствуйте, 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 года. Но там, по-моему даже язык не расширялся. Организация модулей производилась на уровне проекта.

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

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

M>Можем ли мы свести проблему к "заглядыванию вперед" на 4 символа?

Нет, нельзя. Потому что число параметров дженерика может быть любым. В общем случае, тут надо заглядывать вперед, пока не найдется парная >, и на основе этого уже делать выводы. Т.е. грамматика не будет LR(k) ни для какого k.

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

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

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

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

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

Думаю, что это даже преувеличение. Хотя человеки бывают разные.
Парсер R#-а парсит 98% конструкций C# 2.0 и 100% C# 1.2. Писался около года по остаточному принципу.

Думаю, что в сам парсер С++ намисать не намного сложнее. Сложно написать быстрый парсер. Ну, и сложно сделать разрешение имен и т.п.

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

Так чем тебя тогда не устраивет Лисп или Окамл?

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

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

Вот в этом и дело. Если ты уже прошел все грабли, то создание парсера/компилятора уже не так сложно. Основное время уходит не на код, а на то чтобы разобраться и предствить в голове (на бумаге) принципы заложенные в язык. Для С++ внятного описания семантики я не видел ни разу. По этому создание полноценного компилятора (ну, хотя бы парсера + резрешение имен) является очень сложной задачей.

Однако если не думать о скорость парсинга, то содать парсер С++ все же не так сложно. Было бы четкое его описание.

VladD2,

> Думаю, что в сам парсер С++ намисать не намного сложнее. Сложно написать быстрый парсер. Ну, и сложно сделать разрешение имен и т.п.

Парсер C++ без разрешения имен парсить C++ не сможет.

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

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

M>>Можем ли мы свести проблему к "заглядыванию вперед" на 4 символа?

Ш>Нет, нельзя. Потому что число параметров дженерика может быть любым. В общем случае, тут надо заглядывать вперед, пока не найдется парная >, и на основе этого уже делать выводы. Т.е. грамматика не будет LR(k) ни для какого k.

Ага, точно! Ведь переменное число параметров, причем, что очень важно, как в функции, так и в списке типов дженерика. Но тогда непонятно зачем вообще разработчики стандарта это правило ввели? Для построения LR(k)-автомата оно, получается, совершенно бесполезно. А что там, все-таки, за правила такие, определяющие simple name и т.д.? Да, и еще, а в стандарте число параметров дженерика точно не ограничено?

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

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

Что-то подобное уже сделано. Я не помню названия, но как-то смотрел код модифицированного Berkeley YACC, в котором при таких конфликтах сначала производился псевдоразбор для каждой альтернативы, а потом, если какая-то из них подтверждалась, производился откат до места конфликта и начинался настоящий разбор. Псевдоразбор нужен был для того, чтобы не строить деревьев, а только подсказать анализатору какую альтернативу выбрать. В принципе, его можно вполне использовать. Но лучше, все-таки, использовать алгоритм Томиты. Тогда не нужно будет грамматику специально под LR(k) модифицировать. Ведь LR(k)-анализатор зацикливается, если в грамматике есть правила, например, вида A --> B и B --> A. А в алгоритме Томиты здесь все нормально работает. И еще гемморой с эпсилон правилами...

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

Да, вот еще в догонку относительно контекстной зависимости приведенных выше конструкций. Чтобы упростить рассуждение можно рассмотреть ту же самую проблему на более простой грамматике:

S --> Gen_Type Terminal | Expr Terminal
Gen_Type --> Name Type_List
Expr --> Name Expr_List
Terminal --> ( | ) |...

С Type_List и Expr_List понятно. Вот эта грамматика будет неоднозначной, строка G < A, B > ( будет выводится так

S ==> Gen_Type Terminal ==> Name Type_List Terminal ==> G < A, B > (

и так

S ==> Expr Terminal ==> Name Expr_List Terminal ==> G < A, B > (

Мы можем поменять грамматику так ,чтобы она стала однозначной:

S --> Gen_Type '(' | Expr Terminal
Gen_Type --> Name Type_List
Expr --> Name Expr_List
Terminal --> терминальные символы, не содержащие символа '('

Тогда, эта же строка G < A, B > ( может вывестись только так


S ==> Gen_Type ( ==> Name Type_List ( ==> G < A, B > (

И неоднозначности не получается. А вот конфликт перенос\свертка будет точно.

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

ПК>Парсер C++ без разрешения имен парсить C++ не сможет.

Для него нужен тольк список типов, который получается относительно не сложно. Полное разрешение несколько сложнее. Хотя учитывая все тайпдефы...

VladD2,

ПК> Парсер C++ без разрешения имен парсить C++ не сможет.

VD2> Для него нужен тольк список типов, который получается относительно не сложно. Полное разрешение несколько сложнее. Хотя учитывая все тайпдефы...

Учитывая все аспекты языка, "только списком типов, который получается относительно не сложно" тут не отобъешься. Придется реализовывать полноценный поиск имен, со всеми нюансами, включая ADL. Простой пример:

typedef char(&size1)[1];
typedef char(&size2)[2];

namespace n1 {
struct A { };
size1 F(A);
}

namespace n2 {
struct A { };
size2 F(A);
}

template< int > struct T;
template<> struct T< 1 > { typedef int t; };
template<> struct T< 2 > { static int t(); };

n1::A a1;
n2::A a2;

В результате "список типов" получить исключительно непросто, т.к. T< sizeof( F(a1) ) >::t — тип, а T< sizeof( F(a2) ) >::t — функция. И определить это можно только найдя "полным" поиском имен функции n1::F и n2::F.

Пример, как может проявляться эта неоднозначность в чуть более сложном случае:

int b1( T< sizeof( F(a1) ) >::t() ); // 1
int b2( T< sizeof( F(a2) ) >::t() ); // 2

Несмотря на полную идентичность объявлений 1 и 2 по форме, они являются различными синтаксическими конструкциями. В частности, 1 является объявлением функции b1 с аргументом — указателем на функцию типа int(*)(), в то время как 2 — определением переменой b2 типа int. Скажем, для примера выше, такое продолжение будет верным:

int f();

int main()
{
   b1(f);
   b2 = 10;
}

а такое — нет:

int f();

int main()
{
   b1 = 10;
   b2(f);
}

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

ПК>В результате "список типов" получить исключительно непросто, т.к. T< sizeof( F(a1) ) >::t — тип, а T< sizeof( F(a2) ) >::t — функция. И определить это можно только найдя "полным" поиском имен функции n1::F и n2::F.

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

ПК>Пример, как может проявляться эта неоднозначность в чуть более сложном случае:
ПК>

ПК>int b1( T< sizeof( F(a1) ) >::t() ); // 1
ПК>int b2( T< sizeof( F(a2) ) >::t() ); // 2
ПК>

Для парсера эти тонкасти неважны. Он рпспарсивает все дело в виде граматических конструкций где тип всего лишь ссылка. Ссылка может быть и не определенной или указывать на более общую конструкции допускающую двоякость. Это же все же не полноценный компилятор.

VladD2,

пожалуйста, дочитай до конца, прежде чем отвечать

> ПК> В результате "список типов" получить исключительно непросто, т.к. T< sizeof( F(a1) ) >::t — тип, а T< sizeof( F(a2) ) >::t — функция. И определить это можно только найдя "полным" поиском имен функции n1::F и n2::F.

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

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

> Причем если речь идет о парсере, то до воплощений они обычно не доходят.

Это смотря для каких целей парсер. Если речь по-прежнему идет о полном парсере, то придется. Либо проинстанцировать шаблоны, и разрешить имена до завершения синтаксического разбора, либо же отложить оставшуюся часть синтаксического разбора "на потом", пока не будет произведено инстанцирование шаблонов и не будут разрешены имена. Что, в принципе, как можно легко заметить, совершенно одно и то же

> ПК>Пример, как может проявляться эта неоднозначность в чуть более сложном случае:
> ПК>

> ПК>int b1( T< sizeof( F(a1) ) >::t() ); // 1
> ПК>int b2( T< sizeof( F(a2) ) >::t() ); // 2
> ПК>

>
> Для парсера эти тонкасти неважны. Он рпспарсивает все дело в виде граматических конструкций где тип всего лишь ссылка. Ссылка может быть и не определенной <...>

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

Еще более простой пример (отличия от предыдущего выделены):

typedef char(&size1)[1];
typedef char(&size2)[2];

namespace n1 {
struct A { };
size1 F(A);
}

namespace n2 {
struct A { };
size2 F(A);
}

template< int > struct T;
template<> struct T< 1 > { typedef int t; };
template<> struct T< 2 > { static const int t = 10; };

n1::A a1;
n2::A a2;

int x = 20;

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

int main()
{
    T< sizeof( F(a1) ) >::t * x;
}

Объявление переменной x типа "указатель на int".

То же самое с заменой одного идентификатора:

int main()
{
    T< sizeof( F(a2) ) >::t * x; // 2
}

В этом случае никакого объявления вообще нет, есть произведение двух целых чисел, 10 и 20.

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

> [Ссылка может быть и не определенной] или указывать на более общую конструкции допускающую двоякость. Это же все же не полноценный компилятор.

Если мы откладываем часть разбора "на потом", это ничего не меняет. Так или иначе это часть синтаксического анализа.

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

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

Спецификацию можно взять здесь.

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

Простите за дилентантизм, а что, парсеры до сих пор ещё являются автоматами?

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

G>Простите за дилентантизм, а что, парсеры до сих пор ещё являются автоматами?

Несомненно. Причем, как и все в этом мире, конечными.

> Несомненно. Причем, как и все в этом мире, конечными.

Значит есть ещё над чем подумать теоретикам, что усовершенствовать...