Здравствуйте, 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)-автомат. Известный алгоритм Де Ремера производит данное построение за линейное время. Идея алгоритма восходит к знаменитому алгоритму боба Таржана нахождения сильно связанных компонентов графа за линейное время. В той версии бизона, которую я впросматривал пару лет назад именно де Ремеровский алгоритм и используется.