Здравствуйте, 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.