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.