Эта тема посвящена обдумыванию, описанию и возможно созданию некоего идеального парсера.
Основные требования предъявляемые к парсеру:
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). И писать парсеры сложно для обоих подходов. Все зависит от граматики и реализации.
Настаивать не буду. Может быть дело не в скорости, а в требованиях к памяти. Но вот отлаживать рекурсивные парсеры точно легче, чем табличные
Здравствуйте, Курилка, Вы писали:
К>Вопрос несколько в сторону — на чём будет парсер написан? У Володи на плюсах вариант вроде бы как...
Риторический вопрос
new RSDN@Home(1.1.4, 303) << new Message(); std::head::ear << "Mohicans — A New Day";
Здравствуйте, ansi, Вы писали:
A>Здравствуйте, Курилка, Вы писали:
К>>Вопрос несколько в сторону — на чём будет парсер написан? У Володи на плюсах вариант вроде бы как... A>Риторический вопрос
А мне казалось, что риторический вопрос: "Будет написан?"
... << RSDN@Home 1.1.4 stable rev. 510>>
SObjectizer: <микро>Агентно-ориентированное программирование на C++.
Здравствуйте, eao197, Вы писали:
К>>>Вопрос несколько в сторону — на чём будет парсер написан? У Володи на плюсах вариант вроде бы как... A>>Риторический вопрос
E>А мне казалось, что риторический вопрос: "Будет написан?" E>
Ну тогда они оба риторические. Итого, имеем:
Парсер будет не написан на C#
new RSDN@Home(1.1.4, 303) << new Message(); std::head::ear << "Celtic Awakening — The Wind Dances";
Здравствуйте, mefrill, Вы писали:
M>Здравствуйте, little_alex, Вы писали:
_>>Здесь лежит GLR парсер генератор (напиcан на С++). _>>И рабочий парсер C++ граматики. _>>Документация
M>И еще одно: он, вероятно, некорректен. Парень этот писал алгоритм по дисику 1992 года, а только в 2000 была придумана версия алгоритма Томиты, которая все без исключения грамматики корректно обрабатывает. Главное в этой версии — модификация LR-автомата. Код неохота смотреть, но вряд ли он это делает.
Вот что ответил автор:
> How elkhound does handle epsilon rule?
> Documentation is silent about this.
Elkhound can handle any context-free grammar, including those with
epsilon rules.
> Does elkhound suffer from problems described is this paper
>
http://www.cs.rhul.ac.uk/research/languages/publications/tomita_style_1.ps?
The Elkhound implementation was originally based on the description in
Rekers' PhD thesis, which uses Farshi's solution to the hidden left
recursion problem. As such, like Farshi's algorithm, for highly ambiguous
grammars, it can perform poorly (polynomial of degree as high as the
longest rule) due to the link search.
Johnstone's modification to Farshi (5.3 of the above link) isn't suitable
because the constant-factor costs of maintaining GSS precessor links is
prohibitve; one of Elkhound's goals is to be competitive with Bison for
LALR (fragments of) grammars, so the constant factors have to be kept to a
minimum. Unfortunately, that means the asymptotic costs for some (very
non-LALR) grammars are higher than they otherwise could be.
I have studied Johnstone's right-nulled parser approach (section 6, and
later publications) somewhat, but still have concerns about the ability to
properly execute user-defined actions in that scheme. I would have to
implement it myself to really explore it, and have not done so.
-Scott
Здравствуйте, little_alex, Вы писали:
M>>И еще одно: он, вероятно, некорректен. Парень этот писал алгоритм по дисику 1992 года, а только в 2000 была придумана версия алгоритма Томиты, которая все без исключения грамматики корректно обрабатывает. Главное в этой версии — модификация LR-автомата. Код неохота смотреть, но вряд ли он это делает.
_>Вот что ответил автор: _>[code] >> How elkhound does handle epsilon rule? >> Documentation is silent about this. _>Elkhound can handle any context-free grammar, including those with _>epsilon rules. >> Does elkhound suffer from problems described is this paper >> _>http://www.cs.rhul.ac.uk/research/languages/publications/tomita_style_1.ps?
_>The Elkhound implementation was originally based on the description in _>Rekers' PhD thesis, which uses Farshi's solution to the hidden left _>recursion problem. As such, like Farshi's algorithm, for highly ambiguous _>grammars, it can perform poorly (polynomial of degree as high as the _>longest rule) due to the link search.
Ага, ясно, автор использовал алгоритм Фарши. Я описывал его в моей статье
Некорректная ссылка удалена
. алгоритм работает корректно, но к сожалению, очень медленный.
_>Johnstone's modification to Farshi (5.3 of the above link) isn't suitable _>because the constant-factor costs of maintaining GSS precessor links is _>prohibitve; one of Elkhound's goals is to be competitive with Bison for _>LALR (fragments of) grammars, so the constant factors have to be kept to a _>minimum. Unfortunately, that means the asymptotic costs for some (very _>non-LALR) grammars are higher than they otherwise could be.
_>I have studied Johnstone's right-nulled parser approach (section 6, and _>later publications) somewhat, but still have concerns about the ability to _>properly execute user-defined actions in that scheme. I would have to _>implement it myself to really explore it, and have not done so.
Честно говоря, не совсем понятно, что автор имеет ввиду. Главная идея Джонстона состоит в том, чтобы модифицировать LR-атвомат так, чтобы там, где существуют эпсилон-правила, были переходы по этим символам в это же состояние. Тогда исчезают, как показал Джонстон, проблемы с цепными с некорректным разбором. Алгоритм, который приводил Джонстон, ничего особенного и отличного от алгоритма Томиты в себе не содержит, поэтому его можно просто не брать в расчет. Автор пишет, что одной из целей было "to be competitive with Bison for LALR (fragments of) grammars", видимо поэтому он не стал это реализовывать. Но и это тоже непонятно, такая модификация LR-автомата может быть проведена только для грамматик с эпсилон правилами, которые, как известно, не могут быть обработаны бизоном. Последний абзац наводит на мысль, что автор просто пока еще не вчитался в статью и не понял идеи Джонстона.
Здравствуйте, mefrill, Вы писали:
> Но и это тоже непонятно, такая модификация LR-автомата может быть проведена только для грамматик с эпсилон правилами, которые, как известно, не могут быть обработаны бизоном.
Разве гамматики с эпсилон правилами не являются LALR ?
Здравствуйте, little_alex, Вы писали:
_>Разве гамматики с эпсилон правилами не являются LALR ?
Ну да, там же неоднозначность. Если в каком-нибудь состоянии LR-автомата есть правило с точкой перед эпсилон-символом, то значит должна быть свертка по этому символу в это же состояние. Если есть переход по какому-нибудь другому символу, то имеем конфликт вида переход\свертка. Иначе, должна быть свертка по какому-то другому правилу, не эпсилон, т.е. имеем конфликт свертка\свертка.
Здравствуйте, mefrill, Вы писали:
M>Здравствуйте, little_alex, Вы писали:
_>>Разве гамматики с эпсилон правилами не являются LALR ?
M>Ну да, там же неоднозначность. Если в каком-нибудь состоянии LR-автомата есть правило с точкой перед эпсилон-символом, то значит должна быть свертка по этому символу в это же состояние. Если есть переход по какому-нибудь другому символу, то имеем конфликт вида переход\свертка. Иначе, должна быть свертка по какому-то другому правилу, не эпсилон, т.е. имеем конфликт свертка\свертка.
%token id
%start S
%%
S: A;
A: B '+' A
| B;
B: '(' A ')'
| id
| ;
что-то вроде (a+b+c+())+(v+w+z)
Bison.Никаких конфликтов нет.
?
M>Ну как же нет? в состоянии
M>A --> * B '+' A M>A --> * B
M>у тебя будет переход по символу B в состояние
M>A --> B * '+' A M>A --> B *
M>Теперь, здесь у тебя конфликт свертка по правилу A --> B\сдвиг по символу '+'.
свертка по A выполняется если только следующей символ $ или ')'
сдвиг выполняется если только следующей символ '+'
Здравствуйте, little_alex, Вы писали:
_>Здравствуйте, mefrill, Вы писали:
M>>Ну как же нет? в состоянии
M>>A --> * B '+' A M>>A --> * B
M>>у тебя будет переход по символу B в состояние
M>>A --> B * '+' A M>>A --> B *
M>>Теперь, здесь у тебя конфликт свертка по правилу A --> B\сдвиг по символу '+'.
_>свертка по A выполняется если только следующей символ $ или ')' _>сдвиг выполняется если только следующей символ '+'
А по B?
_>bison конфликтов не нашел
Я не помню уже, код бизона смотрел достаточно давно. Но, по-моему, он просто эпсилон-правила игнорирует. Проверить неоднозначности можно вручную построив LR-автомат. Советую тебе это проделать для данной грамматики и увидишь в чем проблема.
Здравствуйте, mefrill, Вы писали:
M>Здравствуйте, little_alex, Вы писали:
_>>Здравствуйте, mefrill, Вы писали:
M>>>A --> B * '+' A (5) M>>>A --> B *
M>А по B?
Терминальные символы, следующие за нетерминалом A, это ) $
Другие в корректном входном потоке быть не могут.
Соответственно в состояние 5 если lookahead равен '+' выполняем перенос,а если ) $ делаем свертку A-->B
Грамматика
0 $accept: S $end
1 S: A
2 A: B '+' A
3 | B
4 B: '(' A ')'
5 | id
6 | /* пусто */
Терминальные символы с правилами, в которых они появляются
$end (0) 0
'(' (40) 4
')' (41) 4
'+' (43) 2
error (256)
id (258) 5
Нетерминальные символы с правилами, в которых они появляются
$accept (7)
налево: 0
S (8)
налево: 1, направо: 0
A (9)
налево: 2 3, направо: 1 2 4
B (10)
налево: 4 5 6, направо: 2 3
состояние 0
0 $accept: . S $end
id shift, and go to state 1
'(' shift, and go to state 2
$default reduce using rule 6 (B)
S go to state 3
A go to state 4
B go to state 5
состояние 1
5 B: id .
$default reduce using rule 5 (B)
состояние 2
4 B: '(' . A ')'
id shift, and go to state 1
'(' shift, and go to state 2
$default reduce using rule 6 (B)
A go to state 6
B go to state 5
состояние 3
0 $accept: S . $end
$end shift, and go to state 7
состояние 4
1 S: A .
$default reduce using rule 1 (S)
состояние 5
2 A: B . '+' A
3 | B .
'+' shift, and go to state 8
$default reduce using rule 3 (A)
состояние 6
4 B: '(' A . ')'
')' shift, and go to state 9
состояние 7
0 $accept: S $end .
$default accept
состояние 8
2 A: B '+' . A
id shift, and go to state 1
'(' shift, and go to state 2
$default reduce using rule 6 (B)
A go to state 10
B go to state 5
состояние 9
4 B: '(' A ')' .
$default reduce using rule 4 (B)
состояние 10
2 A: B '+' A .
$default reduce using rule 2 (A)
Неохота разбираться. Во-первых, Для строки "+a" будет вывод в этой грамматике
S ==> A ==> B + A ==> + A ==> + B ==> + id
Так что, грамматика у тебя немного не то определяет.
Во-вторых, обрати внимание на состояния
состояние 0
0 $accept: . S $end
id shift, and go to state 1
'(' shift, and go to state 2
$default reduce using rule 6 (B)
S go to state 3
A go to state 4
B go to state 5
состояние 1
5 B: id .
$default reduce using rule 5 (B)
состояние 2
4 B: '(' . A ')'
id shift, and go to state 1
'(' shift, and go to state 2
$default reduce using rule 6 (B)
A go to state 6
B go to state 5
С какой стати здесь свертка делается только по символу $? Почему по символу "(" ее не делать? Что это за "$default" такое? Откуда взялось?
M>Так что, грамматика у тебя немного не то определяет.
А я и не писал что она определяет.Прсто это пример гмамматики с eps правилами успешно разбараемой LALR(1).
Совсем простой пример
S-->B c;
B--> a|eps;
M> Что это за "$default" такое? Откуда взялось?
Это оптимизация таблиц — в красном драконе это вроде есть.
$default — все остальные терминалы ( все оставшиеся возможности )
Пусть терминалы -id + ( ) $
Тогда
( — shift ...
$default -reduce ...
под $default имеют ввиду id + ) $
Зачастую $default содержит больше терминалов, чем необходимо, то есть парсер делает reduce даже
в том случае если до оптимизации в таблице действия не было (то есть было действие-ошибка)
Здравствуйте, little_alex, Вы писали:
M>> Что это за "$default" такое? Откуда взялось?
_>Это оптимизация таблиц — в красном драконе это вроде есть. _>$default — все остальные терминалы ( все оставшиеся возможности ) _>Пусть терминалы -id + ( ) $ _>Тогда _>( — shift ... _>$default -reduce ... _>под $default имеют ввиду id + ) $ _>Зачастую $default содержит больше терминалов, чем необходимо, то есть парсер делает reduce даже _>в том случае если до оптимизации в таблице действия не было (то есть было действие-ошибка)
состояние 2
4 B: '(' . A ')'
id shift, and go to state 1
'(' shift, and go to state 2
$default reduce using rule 6 (B)
A go to state 6
B go to state 5
А почему свертка на "(" и "id" не делается? Откуда парсер вывел, что на этот символ свертку нельзя делать? Вообще,в LR-анализе свертка делается безусловно, не на какой-то символ. Вот, здесь, очевидно, бизон хитрит и делает всевозможные сдвиги, а затем "для остальных" терминалов оставляет свертку. Это жульничество и грамматика, которая была введена в генератор, и грамматика, для которой был построен разборщик, разные. Конфликт существет, но бизон его маскирует, выбирая сдвиг в качестве приоритета. Т.е. конфликт налицо и парсер работате некорректно.
Здравствуйте, mefrill, Вы писали:
M>состояние 2 M>4 B: '(' . A ')' M>id shift, and go to state 1 M>'(' shift, and go to state 2 M>$default reduce using rule 6 (B) M>A go to state 6 M>B go to state 5
M>А почему свертка на "(" и "id" не делается? Откуда парсер вывел, что на этот символ свертку нельзя делать? Вообще,в LR-анализе свертка делается безусловно, не на какой-то символ.
Это не верно. LR(0) действительно не использует предпросмотр вообще. Но LR(1) и LALR(1) используют предпросмотр прежде чем сделать
свертку равно как и перенос.
В данном примере за B может быть только + ) $ — соответственно делать свертку по B если во входном потоке другой символ бессмысленно.
Здравствуйте, little_alex, Вы писали:
_>Здравствуйте, mefrill, Вы писали:
M>>состояние 2 M>>4 B: '(' . A ')' M>>id shift, and go to state 1 M>>'(' shift, and go to state 2 M>>$default reduce using rule 6 (B) M>>A go to state 6 M>>B go to state 5
M>>А почему свертка на "(" и "id" не делается? Откуда парсер вывел, что на этот символ свертку нельзя делать? Вообще,в LR-анализе свертка делается безусловно, не на какой-то символ.
_>Это не верно. LR(0) действительно не использует предпросмотр вообще. Но LR(1) и LALR(1) используют предпросмотр прежде чем сделать _>свертку равно как и перенос.
Ты попутал предостмотр и переход по символу. За символом B в данном случае может идти как '+', так и '(' и 'id'. Еще раз говорю, построй LR-автомат и увидешь проблему. Иначе, разговор беспредметный — ты говоришь о том, чего не знаешь. Ты ведь не строил LR-автоматов?
_>В данном примере за B может быть только + ) $ — соответственно делать свертку по B если во входном потоке другой символ бессмысленно.
А что LR-анализатор уже мыслить начал??? Ты представление об алгоритме построения LR(k)-автомата имеешь? Ну зачем спорить до уср-ки о том, в чем не разбираешься?
Здравствуйте, mefrill, Вы писали:
Спорить действительно больше не стоит.
Но всетаки открой книжку Parsing Techniques A Practical Guide и посмотри 210 стр. —
LR(1) with eps-rules . Fortunately LR(1) parses are strong enough to handle them without problems.
Сори, в сообщении была некорректная ссылка которая выводила из строя компилятор 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>>
Есть логика намерений и логика обстоятельств, последняя всегда сильнее.
