Здравствуйте, 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 как раз на такой грамматике и работают.
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.
Здравствуйте, 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.
По поводу конкретно С++. В приложении к Красному дракону (русскому издание) есть грамматики С++ и С#, написанные Зуевым. Эти грамматики написаны на входном языке Yacc а, т.е. это LARL(1) грамматики (в них, правда, использована способность Yacc а генерировать парсер с учётом приоритета и ассоциативности, но насколько я смотрел, как раз эти неопределённости можно устранить за счет усложнения грамматики). Так что если там всё сделано правильно (на 100% я, конечно, не могу поручиться), то проблем с парсингом не должно быть.
Здравствуйте, mefrill, Вы писали:
M>Трудность синтаксического анализа действительно присутствует. Но просто потому, что Си++ не укладывается в LR(k) грамматику.
Не только. По-моему, основная проблема объем парсинга, инклюды, и отсуствие модулей. А проблемы неоднозначностей все же разрешимы.
M> алгоритм Томиты, еще называемый GLR. Если использовать этот алгоритм, то проблем не возникает.
А где можно почитать о сути этого алгоритма? Если на русском, то вообще здорово.
M> Просто, язык Си++, в отличии от C или C# с Java, это язык следующего поколения,
Ну, это уже смешно. С++ вызывает проблему не толко у парсеров. Люди тоже клинят. При этом на русском они вроде объщаются неплохо.
M> очень похожий на естественные языки.
Ну, так и вижу программистов читающих/пщуших С++-ый код со скоростью чтения/ответа форумов/в форумы.
Извини, но это уже самовнушение. Может от так же сложен для распознования (хотя естественные языки еще никто полностью распознать не сомог).
M> Похожесть заключается в реализации в языке множества различных парадигм,
Ну, да. ООП посредственно. ФП совсем посредственно. Логического вообще нет. АОП тоже. Какие еще парадигмы в нем реализованы?
А уж сколько парадигм в естественных языках...
M> что повышает на порядок сложность языка.
Сложность языка в общем-то не такая высокая. Сложность создается морем никому не нужных нюансов растут которые из довольно посредственного проектирования языка, попыток во что бы то не стало оставить совместимость с С и стремлениея к ускорению создаваемого кода любой ценой. Плюс сюда прибавляется нежелание его менять.
M> Ввиду этой сложности, для упрощения синтаксических конструкций, многие из них имеют многозначную семантику.
Не думаю, что у Создателей языка стаяла задача внести неоднозначности. Неоднозначности скорее вызваны наследием С и тем что никто специально не устранял оные.
M> Это не обязательно выражается в неоднозначности грамматики, но на сложность влияет. Тоже самое присутствует и в человеческих языках, когда для обозначения объектов какой-то новой реальности люди используют старые слова и языковые конструкции по аналогии с какой-нибудь известной областью.
Это называется перегрузкой и есть в любых языках. Например, многие ключевые слова Шарпа применяются в разных конструциях (using, return, get/set и т.п.).
Перегрузка не всегда является неоднозначностью. Перегрузки в разговорных языках обычно разрешаются контксом. И порой перегрзуки вызывают огромные проблемы. Например, разные инстанциирования коверкают язык только с целью устранения неоднозначностей.
В общем, разговорые языки тут совсем непричем. Аналогия неуместна, да и нельзя ничего доказывать аналогиями.
M> Я понимаю, что в наш серенький век, когда в программировании присутствуют мириады ламеров, принцип "чем проще, тем лучше" превалирует надо всем остальным. Но, мне кажется, все-таки необходимо оставить людям отдушину, строем не все хотят ходить.
Я думаю, что самые серьезные баги в программх сажают слишком уверенные в себе программисты, а не какие-то ламеры. В 21 веке, в языке программирования и рантайме обызяны быть средства обеспечения надежности программ. Ну, а отдушины можно делать давая более мощьные инструменты.
... << RSDN@Home 1.1.4 beta 3 rev. 267>>
Есть логика намерений и логика обстоятельств, последняя всегда сильнее.
Здравствуйте, 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) парсеров. Или все же это зависимость от контекста. И формально такую граматику нельзя назвать контекстно свободной?
Если можно, дай максимально развернутый ответ.
... << RSDN@Home 1.1.4 beta 3 rev. 267>>
Есть логика намерений и логика обстоятельств, последняя всегда сильнее.
VladD2,
> M>Трудность синтаксического анализа действительно присутствует. Но просто потому, что Си++ не укладывается в LR(k) грамматику.
> Не только. По-моему, основная проблема объем парсинга, инклюды, и отсуствие модулей. А проблемы неоднозначностей все же разрешимы.
В контексте разговора об инструментальных средствах объем исходного кода уж точно менее важен, чем неоднозначности грамматики: объем влияет только на скорость обработки, что для многих средств автоматизации роли не играет, а вот неоднозначности в грамматике, требующие возвратов и/или информации о результатах предыдущего разбора, действительно, осложняют дело.
Модули в данном случае вообще мимо кассы, т.к. при требовании знания об определениях сущностей для разрешения неоднозначностей, единицу трансляции анализировать легче, чем набор модулей. Хотя скорость обработки всей программы от отсутствия модулей, естественно, падает.
> M> алгоритм Томиты, еще называемый GLR. Если использовать этот алгоритм, то проблем не возникает. > > А где можно почитать о сути этого алгоритма? Если на русском, то вообще здорово.
Здравствуйте, Павел Кузнецов, Вы писали:
ПК>В контексте разговора об инструментальных средствах объем исходного кода уж точно менее важен, чем неоднозначности грамматики: объем влияет только на скорость обработки, что для многих средств автоматизации роли не играет, а вот неоднозначности в грамматике, требующие возвратов и/или информации о результатах предыдущего разбора, действительно, осложняют дело.
Не могу согласиться. Интерактивных средств не зависящих от скорости практически не существует. Тот же рефакторинг, комплит ворд, навигация и т.п. все это требует не просто парсера, а быстрого парсера. Причем в следствии того, что любое изменение требует обновления внутренних структур парсинг должен быть еще и инкрементальным.
Не так можно в С++ неоднозначностей чтобы серьезно затормозить процесс распознования. Для R# я пользуюсь LL(1) парсером и приходится постоянно сифонить вперед, чтобы устранить LL(1)-неоднозначности, но на скорости это отражается не очень серьезно. К тому же если GLR — это действительно то, что я думаю, то снимаются очень многие проблемы.
ПК>Модули в данном случае вообще мимо кассы, т.к. при требовании знания об определениях сущностей для разрешения неоднозначностей, единицу трансляции анализировать легче, чем набор модулей. Хотя скорость обработки всей программы от отсутствия модулей, естественно, падает.
Модули тут в кассу. А мимо кассы неоднозначности. Модльность позволяет не парсить все каждый раз от пчки. В обработанном модуле просто не должно быть неоднозначностей. Там лежат принципиально правильные метаданные. Ин не нужно распозновать. Их нужно тупо читать.
ПК>По-английски — валом.
Смешно. Я конечно понимаю, что на 100 странице может оказаться то, что нужно. Но до этого я и сам могу додуматься. Я просил прямую ссылкну на дельное изложение. И желательно по русски. Темболее, что веловек говорил о том, что у него какая-то большая статья по этому поводу есть.
ПК> Даже применительно к C++: A Generated Parser of C++.
Поглядим.
... << RSDN@Home 1.1.4 beta 3 rev. 267>>
Есть логика намерений и логика обстоятельств, последняя всегда сильнее.
Здравствуйте, Павел Кузнецов, Вы писали:
ПК>Здравствуйте, 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.
ПК>Ну почему же необходимо? Можно подправить
Согласен, что граматику можно поправить. Но, от своих слов не отказываюсь, чтобы в примере выше выбрать дерево разбора, необходимо использовать семантический анализатор .
Здравствуйте, Шахтер, Вы писали:
Ш>Здравствуйте, 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.
Не нужно забывать и про операторы неявного преобразования типов, которые тихо и незаметно делают свое грязное дело
