Эта тема посвящена обдумыванию, описанию и возможно созданию некоего идеального парсера.
Основные требования предъявляемые к парсеру:
1. Проект с открытым кодом. Максимумам в виде донатвари.
2. Парсинг КСГ (контекстно-свободных грамматик) современных языков программирования без костылей и при минимуме ручной работы. В случае неоднозначностей должно появляться два пути разбора и верный должен выбираться семантическими методами. Другими словами для разных С++ и C# не должно начинаться танцев с бубнами.
3. Возможность парсить более сложные вещи вроде естественных языков (это лично для меня под вопросом, но все же).
Идеологическую и математическую базу, а так же поддержку в области разжевывания сложных алгоритмов на себя любезно согласился взять mefrill.
Если у вас есть опыт, идеи или желание поучаствовать в открытом проекте, то милости просим присоединяться.
Общий план действий таков. Сначала mefrill должен выложить материалы которые у него уже есть и объяснит нам основные идеи доработанных им алгоритмов. Далее мы обсудим эти идеи и попытаемся создать популярную статью разжевывающую смысл всего сказанного для простых смертных (т.е. для нас с вами). Далее откроем публичный проект, чтобы в нем реализовать все задуманное.
Сразу скажу, что мне этот проект интересен как подспорье для R# и Rsdn.Editor. Но приветствуются любое развитие идей.
... << RSDN@Home 1.2.0 alpha rev. 591>>
Есть логика намерений и логика обстоятельств, последняя всегда сильнее.
Здравствуйте, little_alex, Вы писали:
_>Здесь лежит GLR парсер генератор (напиcан на С++). _>И рабочий парсер C++ граматики. _>Документация
_>PS BSD лицензия.
Здорово, я о нем и не слышал. Но проблем с GLR две:
1. Трудно применить семантические ограничения на альтернативы.
2. Обработка и восстановление после обнаружения ошибок не очень хороша.
Быстрый алгоритм Эрли позволит эти ограничения устранить.
Здравствуйте, little_alex, Вы писали:
_>Здесь лежит GLR парсер генератор (напиcан на С++). _>И рабочий парсер C++ граматики. _>Документация
_>PS BSD лицензия.
И еще одно: он, вероятно, некорректен. Парень этот писал алгоритм по дисику 1992 года, а только в 2000 была придумана версия алгоритма Томиты, которая все без исключения грамматики корректно обрабатывает. Главное в этой версии — модификация LR-автомата. Код неохота смотреть, но вряд ли он это делает.
Здравствуйте, mefrill, Вы писали:
M>Здорово, я о нем и не слышал. Но проблем с GLR две: M>1. Трудно применить семантические ограничения на альтернативы. M>2. Обработка и восстановление после обнаружения ошибок не очень хороша.
M>Быстрый алгоритм Эрли позволит эти ограничения устранить.
А можно описание быстрой версии алгоритма Эрли.
Чем отличается от обычного?
И почему лучше востановление после ошибок?
И еще.Если строить синтаксическое дерево по гамматики напрямую, то в дереве будет много мусорных вершин типа скобок,запятых.
Конечно можно это отсечь на следующем этапе, но зачем делать лишнюю работу?
M>И еще одно: он, вероятно, некорректен. Парень этот писал алгоритм по дисику 1992 года, а только в 2000 была придумана версия алгоритма Томиты, которая все без исключения грамматики корректно обрабатывает. Главное в этой версии — модификация LR-автомата. Код неохота смотреть, но вряд ли он это делает.
Здравствуйте, little_alex, Вы писали:
_>А можно описание быстрой версии алгоритма Эрли. _>Чем отличается от обычного? _>И почему лучше востановление после ошибок?
Быстрый алгоритм Эрли использует LR-автомат, что позволяет увеличить скорость разбора. Каким образом рассказывать пока не буду, надо в алгоритме Эрли разбираться. Восстановление после ошибок в алгоритме очень хорошо и просто реализуется. Это, конечно, зависит от стратегии обработки ошибок. Но режим паники там тоже может применятся. Есть статьи по этой теме, могу прислать названия если интересно.
По быстрому алгоритму Эрли можно посмотреть здесь. Но это была только первая попытка, затем они усовершенствовали алгоритм здесь можно почитать как.
Есть еще статьи, но навскидку вспомнить сейчас не могу.
_>И еще.Если строить синтаксическое дерево по гамматики напрямую, то в дереве будет много мусорных вершин типа скобок,запятых. _>Конечно можно это отсечь на следующем этапе, но зачем делать лишнюю работу?
В алгоритме Эрли нет мусорных вершин, выводятся все возможные для данной строки деревья вывода и только они.
Здравствуйте, VladD2, Вы писали:
VD>Эта тема посвящена обдумыванию, описанию и возможно созданию некоего идеального парсера.
VD>Основные требования предъявляемые к парсеру: VD>2. Парсинг КСГ (контекстно-свободных грамматик) современных языков программирования без костылей и при минимуме ручной работы. В случае неоднозначностей должно появляться два пути разбора и верный должен выбираться семантическими методами.
Что-то я не понял. То есть, должны строиться все возможные результаты разбора?
А уже после этого "правильный" выбирается анализом семантики? Нет, наверное я мысль не понял
Где-то я видел инструмент, который утверждает, что любую КСГ на вход берет.
Работает, конечно, долго, но избавляет от ручного пропихивания грамматики в парсер.
VD>Если у вас есть опыт, идеи или желание поучаствовать в открытом проекте, то милости просим присоединяться.
С некоторых пор у меня есть стойкое убеждение, что при написании трансляторов/компиляторов
и прочих инструментов обработки формальных текстов, важнее не парсер, а то, что после него получается
— внутреннее представление входного текста, которое подлежит дальнейшему анализу и обработке.
Отсюда родилась идея явного описания структуры дерева внутреннего представления
и инструмента, транслирующего это описание в ЯП. Это, конечно, на первый взгляд парсера не касается,
но без средств построения дерева парсер остается простым распознавателем, непригодным для практических задач.
Так что могу внести в копилку идей нотацию и работающий инструмент: http://treedl.sf.net
Здравствуйте, all-x, Вы писали:
AX>Отсюда родилась идея явного описания структуры дерева внутреннего представления AX>и инструмента, транслирующего это описание в ЯП. Это, конечно, на первый взгляд парсера не касается, AX>но без средств построения дерева парсер остается простым распознавателем, непригодным для практических задач. AX>Так что могу внести в копилку идей нотацию и работающий инструмент: http://treedl.sf.net
Здравствуйте, mefrill, Вы писали:
_>>И еще.Если строить синтаксическое дерево по гамматики напрямую, то в дереве будет много мусорных вершин типа скобок,запятых. _>>Конечно можно это отсечь на следующем этапе, но зачем делать лишнюю работу?
M>В алгоритме Эрли нет мусорных вершин, выводятся все возможные для данной строки деревья вывода и только они.
Имеются ввиду символы которые неважны для последующего анализа. Например
List-> "(" A ")"
A-> digit "," A | digit -список (1,2,3)
Вершины относящиеся к скобкам и запятым в выходном дереве обычно уже ненужны.
Или так — есть parse trees, а есть AST.
Большинство LR и LL парсеров позволяют строить AST дерево через semantic actions, а не автоматически получать parse tree.
Здравствуйте, little_alex, Вы писали:
_>Здравствуйте, mefrill, Вы писали:
_>>>И еще.Если строить синтаксическое дерево по гамматики напрямую, то в дереве будет много мусорных вершин типа скобок,запятых. _>>>Конечно можно это отсечь на следующем этапе, но зачем делать лишнюю работу?
M>>В алгоритме Эрли нет мусорных вершин, выводятся все возможные для данной строки деревья вывода и только они.
_>Имеются ввиду символы которые неважны для последующего анализа. Например _>
List->> "(" A ")"
A->> digit "," A | digit -список (1,2,3)
_>
_>Вершины относящиеся к скобкам и запятым в выходном дереве обычно уже ненужны. _>Или так — есть parse trees, а есть AST.
_>Большинство LR и LL парсеров позволяют строить AST дерево через semantic actions, а не автоматически получать parse tree.
В общем, понял. Ты имеешь ввиду семантические действия, которые производятся при разборе с помощью LR или LL анализаторов, когда рапознается какое-то правило? Да, в данном виде адаптированный алгоритм Эрли возвращает множество деревьев вывода входной строки. Это удобно в том случае, когда появляются неоднозначности. Но возможно написать разборщик таким образом, что будет производиться вызов семантического действия каждый раз, когда распознается какое-то правило. У меня в реализации так и происходит.
Здравствуйте, all-x, Вы писали:
AX>Где-то я видел инструмент, который утверждает, что любую КСГ на вход берет. AX>Работает, конечно, долго, но избавляет от ручного пропихивания грамматики в парсер.
Я только слышал. GLR называется. Тут его упоминали.
AX>но без средств построения дерева парсер остается простым распознавателем, непригодным для практических задач.
Как раз построение дерева проблем не вызывает. Конечно хорошо если парсер эту задачу решает, но рельно это сэкономит лишнюю неделю работы из полугода убитого на парсер. А вот грамотный построитель парсеров способен сократить работу в разы.
Скорость получаемого в результате парсера и легкость наращивания его сложности тоже очень важны.
... << RSDN@Home 1.2.0 alpha rev. 591>>
Есть логика намерений и логика обстоятельств, последняя всегда сильнее.
Здравствуйте, AndrewVK, Вы писали:
AVK>Здравствуйте, all-x, Вы писали:
AX>>Отсюда родилась идея явного описания структуры дерева внутреннего представления AX>>и инструмента, транслирующего это описание в ЯП. Это, конечно, на первый взгляд парсера не касается, AX>>но без средств построения дерева парсер остается простым распознавателем, непригодным для практических задач. AX>>Так что могу внести в копилку идей нотацию и работающий инструмент: http://treedl.sf.net
AVK>А чем это лучше ANTLR?
TreeDL — это не замена ANTLR, а его дополнение (Вместо ANTLR может быть использован и любой другой генератор парсеров). В ANTLR тоже есть средства построения дерева, но они в первую очередь заточены
под обработку этих деревьев средствами самого ANTLR — это называется tree grammar, эдакий обходчик дерева, по совместительству и его парсер, потому как дерево гомогенное — все узлы представлены объектами одного типа, структура
задается не деревом, а обходчиком. Гомогенные деревья имеют свои недостатки, кроме того, нотация ANTLR довольно запутанна — почитайте список рассылки ANTLR, большая доля вопросов касается именно построения и обработки деревьев.
Есть и другой подход, который и использован в TreeDL — гетерогенные деревья, где узлы типизированны, тип узла задает его структуру — набор детей и атрибутов.
Используется эта парочка примерно так: на ANTLR пишется парсер, на TreeDL описывается структура дерева. В парсер добавляются действия, которые строят дерево. Остальные компоненты — проверка семантических требований, кодогенерация и т.п. используют только дерево, а от парсера не зависят. Реализуются обходчиками дерева, визитерами и т.п.
Описание структуры дерева — это контракт, спецификация внутреннего представления.
P.S. Я знаю, что в ANTLR 2.x есть кое-какая поддержка гетерогенных деревьев, но это не магистральная линия развития. Теренс любит tree grammars, в ANTLR 3 обещает вообще убрать поддержку гетерогенных деревьев. Впрочем, желающим описывать структуру дерева явно и строить дерево в парсере явно это не помешает — никакая поддержка парсера не требуется. Хотя и способна несколько сократить писанину.
Здравствуйте, VladD2, Вы писали:
VD>Здравствуйте, all-x, Вы писали:
AX>>Где-то я видел инструмент, который утверждает, что любую КСГ на вход берет. AX>>Работает, конечно, долго, но избавляет от ручного пропихивания грамматики в парсер.
VD>Я только слышал. GLR называется. Тут его упоминали.
Может быть, хотя мне помнится другое название. Может, это есть в TXL (http://www.txl.ca),
а может я и путаю, давно смотрел.
AX>>но без средств построения дерева парсер остается простым распознавателем, непригодным для практических задач.
VD>Как раз построение дерева проблем не вызывает. Конечно хорошо если парсер эту задачу решает, но рельно это сэкономит лишнюю неделю работы из полугода убитого на парсер. А вот грамотный построитель парсеров способен сократить работу в разы.
Совершенно верно, добавить в парсер действия для построения дерева легко.
Я же говорю об описании того дерева, которое получится.
Если описание этого дерева размазано по парсеру, то командной работы над таким транслятором не получится
— мало того, что всем разработчикам придется изучать нотацию генератора парсеров, так еще и готово описание дерева будет только вместе с парсером!
Описать же структуру дерева отдельно значительно проще, чем написать парсер (по трудоемкости примерно как написать bnf-грамматику разбираемого языка без ограничений, накладываемых парсером).
И другие разработчики после этого сразу же могут приступать к своим подсистемам.
VD>Скорость получаемого в результате парсера и легкость наращивания его сложности тоже очень важны.
По-моему, удобство написания парсера обратно пропорционально скорости его работы. LALR парсеры быстрее рекурсивных LL, но писать последние проще. Особенно, если язык сложный, а в генераторе парсера есть продвинутые средства борьбы с конфликтами.
Здравствуйте, all-x, Вы писали:
AX>По-моему, удобство написания парсера обратно пропорционально скорости его работы. LALR парсеры быстрее рекурсивных LL, но писать последние проще. Особенно, если язык сложный, а в генераторе парсера есть продвинутые средства борьбы с конфликтами.
Это не соотвествует действительности. И LL(1)-парсеры ни чуть не медленее чем LALR(k). И писать парсеры сложно для обоих подходов. Все зависит от граматики и реализации.
... << RSDN@Home 1.2.0 alpha rev. 591>>
Есть логика намерений и логика обстоятельств, последняя всегда сильнее.
Здравствуйте, VladD2, Вы писали:
VD>Здравствуйте, all-x, Вы писали:
AX>>По-моему, удобство написания парсера обратно пропорционально скорости его работы. LALR парсеры быстрее рекурсивных LL, но писать последние проще. Особенно, если язык сложный, а в генераторе парсера есть продвинутые средства борьбы с конфликтами.
VD>Это не соотвествует действительности. И LL(1)-парсеры ни чуть не медленее чем LALR(k). И писать парсеры сложно для обоих подходов. Все зависит от граматики и реализации.
Настаивать не буду. Может быть дело не в скорости, а в требованиях к памяти. Но вот отлаживать рекурсивные парсеры точно легче, чем табличные
