Здравствуйте, mefrill, Вы писали:
M>Можем ли мы свести проблему к "заглядыванию вперед" на 4 символа?
Нет, нельзя. Потому что число параметров дженерика может быть любым. В общем случае, тут надо заглядывать вперед, пока не найдется парная >, и на основе этого уже делать выводы. Т.е. грамматика не будет LR(k) ни для какого k.
M>Т.е. контекстной зависимости здесь тоже нет. проблема в построении LR(4) автомата. Число состояний там будем очень большим, что в принципе, при сегодняшнем наличии памяти, большого значения не играет.
В данном случае гораздо практичнее использовать LR(1) парсер, а для разрешения неоднозначности встроить в него "хак". Т.е. при появлении пары токенов <идентификатор> < < > возникает конфликт перенос-свертка, которую LR(1) парсер не может разрешить. В этой ситуации запускается просмотр вперед для выяснения ситуации: или это начало цепочки вида <идентификатор> < < >
<идентификатор> < , > <идентификатор> < , > ... < > > с последующим ( ) ] : ; , . ? == != , тогда перенос, в противном случае свертка.
Здравствуйте, uw, Вы писали:
uw>Тогда как на полный, безглючный и юзабельный парсер того же C# уходит максимум два человеко-года.
Думаю, что это даже преувеличение. Хотя человеки бывают разные.
Парсер R#-а парсит 98% конструкций C# 2.0 и 100% C# 1.2. Писался около года по остаточному принципу.
Думаю, что в сам парсер С++ намисать не намного сложнее. Сложно написать быстрый парсер. Ну, и сложно сделать разрешение имен и т.п.
uw>Для меня такой отдушиной являются Prolog и Haskell, а строем в моем понимании ходят все те, кто программирует на ОО императивных языках, проще которых может быть только бревно. И я не хочу очередной клон Java, мне нужен универсальный язык, поддерживающий мета-программирование с человеческим лицом. C++ в этом отношении уже не устраивает.
Так чем тебя тогда не устраивет Лисп или Окамл?
... << RSDN@Home 1.1.4 beta 3 rev. 267>>
Есть логика намерений и логика обстоятельств, последняя всегда сильнее.
Здравствуйте, Павел Кузнецов, Вы писали:
ПК>Правда, писал его человек, съевший не одну собаку на этом деле, писавший ранее в том числе и компилятор для Ады, которая тоже легкостью анализа не отличается.
Вот в этом и дело. Если ты уже прошел все грабли, то создание парсера/компилятора уже не так сложно. Основное время уходит не на код, а на то чтобы разобраться и предствить в голове (на бумаге) принципы заложенные в язык. Для С++ внятного описания семантики я не видел ни разу. По этому создание полноценного компилятора (ну, хотя бы парсера + резрешение имен) является очень сложной задачей.
Однако если не думать о скорость парсинга, то содать парсер С++ все же не так сложно. Было бы четкое его описание.
... << RSDN@Home 1.1.4 beta 3 rev. 267>>
Есть логика намерений и логика обстоятельств, последняя всегда сильнее.
Здравствуйте, Шахтер, Вы писали:
Ш>Здравствуйте, 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. А в алгоритме Томиты здесь все нормально работает. И еще гемморой с эпсилон правилами...
Да, вот еще в догонку относительно контекстной зависимости приведенных выше конструкций. Чтобы упростить рассуждение можно рассмотреть ту же самую проблему на более простой грамматике:
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 > (
И неоднозначности не получается. А вот конфликт перенос\свертка будет точно.
VladD2,
ПК> Парсер C++ без разрешения имен парсить C++ не сможет.
VD2> Для него нужен тольк список типов, который получается относительно не сложно. Полное разрешение несколько сложнее. Хотя учитывая все тайпдефы...
Учитывая все аспекты языка, "только списком типов, который получается относительно не сложно" тут не отобъешься. Придется реализовывать полноценный поиск имен, со всеми нюансами, включая ADL. Простой пример:
В результате "список типов" получить исключительно непросто, т.к. T< sizeof( F(a1) ) >::t — тип, а T< sizeof( F(a2) ) >::t — функция. И определить это можно только найдя "полным" поиском имен функции n1::F и n2::F.
Пример, как может проявляться эта неоднозначность в чуть более сложном случае:
Несмотря на полную идентичность объявлений 1 и 2 по форме, они являются различными синтаксическими конструкциями. В частности, 1 является объявлением функции b1 с аргументом — указателем на функцию типа int(*)(), в то время как 2 — определением переменой b2 типа int. Скажем, для примера выше, такое продолжение будет верным:
int f();
int main()
{
b1(f);
b2 = 10;
}
а такое — нет:
int f();
int main()
{
b1 = 10;
b2(f);
}
Posted via RSDN NNTP Server 1.9 delta
Легче одурачить людей, чем убедить их в том, что они одурачены. — Марк Твен
Здравствуйте, Павел Кузнецов, Вы писали:
ПК>В результате "список типов" получить исключительно непросто, т.к. T< sizeof( F(a1) ) >::t — тип, а T< sizeof( F(a2) ) >::t — функция. И определить это можно только найдя "полным" поиском имен функции n1::F и n2::F.
И тем не менее для целей парсинга это не так важно. До воплощения шаблона он один фиг может быть распарсен только в промежуточное предстваление, а при вопложении все становится известным. Причем если речь идет о парсере, то до воплощений они обычно не доходят.
ПК>Пример, как может проявляться эта неоднозначность в чуть более сложном случае: ПК>
Для парсера эти тонкасти неважны. Он рпспарсивает все дело в виде граматических конструкций где тип всего лишь ссылка. Ссылка может быть и не определенной или указывать на более общую конструкции допускающую двоякость. Это же все же не полноценный компилятор.
... << RSDN@Home 1.1.4 beta 3 rev. 267>>
Есть логика намерений и логика обстоятельств, последняя всегда сильнее.
пожалуйста, дочитай до конца, прежде чем отвечать
> ПК> В результате "список типов" получить исключительно непросто, т.к. T< sizeof( F(a1) ) >::t — тип, а T< sizeof( F(a2) ) >::t — функция. И определить это можно только найдя "полным" поиском имен функции n1::F и n2::F.
> И тем не менее для целей парсинга это не так важно. До воплощения шаблона он один фиг может быть распарсен только в промежуточное предстваление, а при вопложении все становится известным.
В данном примере шаблоны инстанцируются, и речь идет не о разборе конструкций в определениях шаблонов, а о разборе конструкций, использующих конкретные специализации. Проблема в том, что для разбора в ряде случаев все-таки придется выполнить полное разрешение имен.
> Причем если речь идет о парсере, то до воплощений они обычно не доходят.
Это смотря для каких целей парсер. Если речь по-прежнему идет о полном парсере, то придется. Либо проинстанцировать шаблоны, и разрешить имена до завершения синтаксического разбора, либо же отложить оставшуюся часть синтаксического разбора "на потом", пока не будет произведено инстанцирование шаблонов и не будут разрешены имена. Что, в принципе, как можно легко заметить, совершенно одно и то же
> ПК>Пример, как может проявляться эта неоднозначность в чуть более сложном случае: > ПК>
> > Для парсера эти тонкасти неважны. Он рпспарсивает все дело в виде граматических конструкций где тип всего лишь ссылка. Ссылка может быть и не определенной <...>
Дело в том, что без полного поиска имен не известно, является ли некоторая сущность типом, или нет, соответственно, неразрешенной ссылкой не обойдешься, т.к. неясно, какая же на самом деле перед нами синтаксическая конструкция.
Еще более простой пример (отличия от предыдущего выделены):
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.
И точно так же, как и раньше, не выйдет определить, с какой конструкцией мы имеем дело, пока не будут проинстанцированы шаблоны, и не будет произведено разрешение имен.
> [Ссылка может быть и не определенной] или указывать на более общую конструкции допускающую двоякость. Это же все же не полноценный компилятор.
Если мы откладываем часть разбора "на потом", это ничего не меняет. Так или иначе это часть синтаксического анализа.
Posted via RSDN NNTP Server 1.9 delta
Легче одурачить людей, чем убедить их в том, что они одурачены. — Марк Твен
Здравствуйте, mefrill, Вы писали:
M>Понял наконец . Трудности в понимании возникли еще и из-за того, что я правил "The productions for simple-name (§14.5.2) and member-access (§14.5.4)" не видел.
> Трудность синтаксического анализа действительно присутствует. Но просто потому, что Си++ не укладывается в LR(k) грамматику. А парсеры типа Bison как раз на такой грамматике и работают. Поэтому начинаются извращения, выраженные в бесконечных попытках упростить грамматику Си++ чтобы она работала на Bison. Сейчас есть хороший метод разбора, который работает для всех грамматик, без ограничений: алгоритм Томиты, еще называемый GLR. <...>
Простите за дилентантизм, а что, парсеры до сих пор ещё являются автоматами?
По этому создание полноценного компилятора (ну, хотя бы парсера + резрешение имен) является очень сложной задачей.
