Сори, в сообщении была некорректная ссылка которая выводила из строя компилятор MS Html Help. Просьба дать ссылку еще раз, но без кракозябр (как в прошлый раз).
Есть логика намерений и логика обстоятельств, последняя всегда сильнее.
Здравствуйте, VladD2, Вы писали:
VD>Эта тема посвящена обдумыванию, описанию и возможно созданию некоего идеального парсера.
А зачем он этот самый "идеальный парсер"?
Вопрос не праздный и сугубо практический.
Какой класс задач он пытается накрыть?
Коментарии на полях:
Из всех известных мне компиляторов/парсеров ни один не использует yacc/bizon и иже с ними
по причинам производительности я думаю.
Я лично несколько раз делал попытки использовать yacc/bizon. Последний раз
была попытка использовать bizon для парсинга CSS т.к. спецификация содержит дефиницию грамматики.
Но во первых же строках там стоит такое:
The grammar below is LALR(1) (but note that most UA's should not use it directly, since it doesn't express the parsing conventions, only the CSS 2.1 syntax). The format of the productions is optimized for human consumption and some shorthand notation beyond Yacc (see [YACC]) is used
в общем как всегда...
И для справки: парсер tiscript это 2500 строк на C++ и туда же входит и bytecode generator.
Для скриптов вообще скорость парсинга это критичная вещь поэтому даже и попытки не делал использовать yacc.
c-smile wrote: > > Из всех известных мне компиляторов/парсеров ни один не использует > yacc/bizon и иже с ними > по причинам производительности я думаю.
gcc использовал. Только сейчас, вроде как, переписали ручками.
На yacc'е довольно сложно написать парсер с хорошей диагностикой
синтаксических ошибок, и с хорошим восстановлением после них. Кроме
того, современный C++ не очень хорошо ложится на yacc.
Что касается производительности, то она получается вполне разумной. В
принципе, у генераторов парсеров нет принципиальных причин, почему бы
сгенерированные парсеры должны были бы работать медленнее рукописных.
> И для справки: парсер tiscript это 2500 строк на C++ и туда же входит и > bytecode generator.
Написать парсер с нуля что на C, что на yacc'е, это примерно одинаковый
труд. Но yacc'овский парсер потом проще поддерживать, в том смысле, что
добавить туда еще что-нибудь уже похожее на то, что есть, это дело
минутное. И не обязательно самому делать — можно кого-нибудь из
подчиненных попросить. С другой стороны, гдеж их взять в наше время
таких подчиненных, которых не страшно в yacc'овскую граматику пускать?...
> Для скриптов вообще скорость парсинга это критичная вещь поэтому даже и > попытки не делал использовать yacc.
Здравствуйте, Pzz, Вы писали:
Pzz>Написать парсер с нуля что на C, что на yacc'е, это примерно одинаковый Pzz>труд. Но yacc'овский парсер потом проще поддерживать, в том смысле, что Pzz>добавить туда еще что-нибудь уже похожее на то, что есть, это дело Pzz>минутное. И не обязательно самому делать — можно кого-нибудь из Pzz>подчиненных попросить. С другой стороны, гдеж их взять в наше время Pzz>таких подчиненных, которых не страшно в yacc'овскую граматику пускать?...
If you want the best performance, and maintainability write your own
recursive descent parser.
It's generally complete bullshit that lex/yacc parsers are easier to
maintain. Try to find someone who understands the GCC C yacc parser, for
example The GCC C++ parser was a yacc parser, but was rewritten because
1. It wasn't easy to get good diagnostics out of it
2. It wasn't all that fast
3. It was a pain in the ass to maintain
А вот мнение Страуструпа:
"The Design and Evolution of C++", Bjarne Stroustrup comments (p. 68):
In 1982 when I first planned Cfront [the preprocessor from C++ to C],
I wanted to use a recursive descent parser because I had experience
writing and maintaining such a beast, because I liked such parsers'
ability to produce good error messages, and because I liked the idea
of having the full power of a general-purpose programming language
available when decisions had to be made in the parser. However, being
a conscientious young computer scientist I asked the experts. Al Aho
and Steve Johnson were in the Computer Science Research Center and
they, primarily Steve, convinced me that writing a parser by hand was
most old-fashioned, would be an inefficient use of my time, would
almost certainly result in a hard-to-understand and hard-to-maintain
parser, and would be prone to unsystematic and therefore unreliable
error recovery. The right way was to use an LALR(1) parser generator,
so I used Al and Steve's YACC.
For most projects, it would have been the right choice. For almost
every project writing an experimental language from scratch, it would
have been the right choice. For most people, it would have been the
right choice. In retrospect, for me and C++ it was a bad mistake.
А не пора ли кстати создать новый форум, посвященный парсерам, лексическим анализаторам и пр.? У меня вот например назрели кое-какие вопросы но при этом не совсем понятно куда их задавать..
Здравствуйте, Воронков Василий, Вы писали:
ВВ>А не пора ли кстати создать новый форум, посвященный парсерам, лексическим анализаторам и пр.? У меня вот например назрели кое-какие вопросы но при этом не совсем понятно куда их задавать..
В алгоритмы.
... << RSDN@Home 1.1.4 beta 6a rev. 436>>
Пусть это будет просто:
просто, как только можно,
но не проще.
(C) А. Эйнштейн
Здравствуйте, VladD2, Вы писали:
VD>Эта тема посвящена обдумыванию, описанию и возможно созданию некоего идеального парсера.
Ну и как прогресс? Есть ли уже наработанный материал? Проект стартовал?
... << RSDN@Home 1.2.0 alpha rev. 621>>
"Бог не терпит голой сингулярности" -- Роджер Пенроуз
Здравствуйте, CiViLiS, Вы писали:
VD>>Эта тема посвящена обдумыванию, описанию и возможно созданию некоего идеального парсера. CVL>Ну и как прогресс?
Как видишь.
CVL>Есть ли уже наработанный материал? Проект стартовал?
Дык видишь, народ не очень хорошо реагирует. У меня лично времени сейчас нет. Другие явно взять на себя ношу не способны. Ну, и на носу выход АНТЛР-3. К тому же к нему делается абалденная IDE — ANTLRWorks. Боюсь, что она в сочетании с улучшениями "трешки" может переплюнуть даже самый крутой алгоритм.
... << RSDN@Home 1.2.0 alpha rev. 620>>
Есть логика намерений и логика обстоятельств, последняя всегда сильнее.
Здравствуйте, c-smile, Вы писали:
CS>А зачем он этот самый "идеальный парсер"?
Чтобы можно было легко и быстро создать эффективный парсер для любого языка. Помоему, это очевидно.
CS>Из всех известных мне компиляторов/парсеров ни один не использует yacc/bizon и иже с ними CS>по причинам производительности я думаю.
Видимо тебе извесно очень мало компиляторов/парсеров. К примеру, даже GCC сделан на базе bizon-а, а Mono C# на клоне yacc-а. R# сделан на базе расширенного CocoR, а JetBrain IDEA и ReSharper на базе ANNTLR. Так что скорее рукопашная разработка парсеров — это удел контор вроде МС и фанатов.
CS>Я лично несколько раз делал попытки использовать yacc/bizon. Последний раз CS>была попытка использовать bizon для парсинга CSS т.к. спецификация содержит дефиницию грамматики.
Я не знаю кто такая "дефиницию", да и yacc/bizon построители парсеров явно хреновенькие. Но для твоих задач и их за глаза хватило бы. CSS, вроде бы, примитивнейшей граматикой обладает.
CS>Но во первых же строках там стоит такое:
CS>
CS>The grammar below is LALR(1) (but note that most UA's should not use it directly, since it doesn't express the parsing conventions, only the CSS 2.1 syntax). The format of the productions is optimized for human consumption and some shorthand notation beyond Yacc (see [YACC]) is used
CS>в общем как всегда...
Это ничего не значит. Скорее всего там пара конфликтов которые можно обойти вручную. Все равно это не сравнится с рукопашным написанием парсера. Тот же Бизон имеет нехилые средства разрешения конфликтов. Иначе бы на нем GCC вообще нельзя было бы сделать. Ведь С++ куда круче ЦСС-а в плане грамматики.
CS>И для справки: парсер tiscript это 2500 строк на C++ и туда же входит и bytecode generator.
Для той же справки. Парсер C# 2.0 (кстати, не законченный) занимает ~5000 строк. Причем без каких бы то нибыло лишних вещей вроде AST, разрешения имен и т.п. Это тольо код чистый парсер. Лексер к нему еще ~6000 строк. Так что твой tiscript — это довольно простенькая программка (в месте с bytecode generator). И писать все это вручную, лично мне кажется трудновато. По крайней мере за бесплатно.
CS>Для скриптов вообще скорость парсинга это критичная вещь поэтому даже и попытки не делал использовать yacc.
А с чего ты взял, что твой рукопашный вариант окажется быстрее генерируемого хорошим посторителем парсеров? Ты пойми, в ручную ты максимум что сможешь навоять — это LL(x)-парсер. Причем для разруливания конфликтов ты будешь вынужден постоянно заниматься заглядыванием вперед. А это тормоза. Любой посторитель парсеров строящий ДКА сделает намного более оптимальный код нежели ты вручную. А тем что они генерируют во многих случаях можно управлять. Так что даже LL(x)-парсер проще строить автоматизированно.
И почему ты так на yacc запал?
... << RSDN@Home 1.2.0 alpha rev. 620>>
Есть логика намерений и логика обстоятельств, последняя всегда сильнее.
Здравствуйте, VladD2, Вы писали:
VD>Чтобы можно было легко и быстро создать эффективный парсер для любого языка. Помоему, это очевидно.
Нет не очевидно.
Надо определится что важнее
1. Производительность для грамматик малого размера
2. Производительность для грамматик большого размера (типа естественных языков)
3. В каком порядке выполняются semantic actions. В случае неоднозначных грамматик можно ли вызвать пользовательское действие если в дальнейшем эта альтернатива будет отвергнута
4. Важно ли максимальное сжатие получаемых деревьев (когда деревья соответствующие разным альтернативам делят поддеревья между собой)
5. Насколько общая грамматика должна обрабатыватся.LL,LR,однозначная ,контекстно-свободная ....
Здравствуйте, little_alex, Вы писали:
_>Надо определится что важнее _>1. Производительность для грамматик малого размера _>2. Производительность для грамматик большого размера (типа естественных языков)
Невижу зависимости от размера грамматик. Ну, а естественные языки меня в принципе не интересуют. Так что речь о самых разных языках программирования.
_>3. В каком порядке выполняются semantic actions. В случае неоднозначных грамматик можно ли вызвать пользовательское действие если в дальнейшем эта альтернатива будет отвергнута
Это детали реализации. Но если спрашивать мое мнение, то я считаю, что в случае неоднозначностей сначала должно строиться дерево резбора, а затем уже по нему делаться все остальное (в том числе и семантика).
_>4. Важно ли максимальное сжатие получаемых деревьев (кода деревья соответствующие разным альтернативам делят поддеревья между собой)
Наверно не важно, но желательно.
_>5. Насколько общая грамматика должна обрабатыватся.LL,LR,однозначная ,контекстно-свободная ....
Дык на то она и "G" чобы небыло заморочек с конфликтами. Хотя для реальных задач достаточно LL(*), т.е. леворекурсивной с неограниченным заглядыванием вперед. Хотя, как я понимаю, GLR тут ничем не отлечается по возможностям. Так что тут скорее речь нужно вести об эффектинвности.
... << RSDN@Home 1.2.0 alpha rev. 620>>
Есть логика намерений и логика обстоятельств, последняя всегда сильнее.
