Здравствуйте, VladD2, Вы писали:
VD>Здравствуйте, Aleх, Вы писали:
A>>Кстати, чем плоха идея строить типа LL парсера (только обобщенного и с приоритетами) для разбора текста, заданного грамматикой в формате PEG?
A>>Под обобщенный LL я имею ввиду делить стек при возникновении неоднозначности. То есть если по первому символу не возможно раскрыть правило, то делим стек. Ну а когда, возникает такая ситуация, что некоторое множество стеков одинаково, оставлять из них только один, который был порожден раскрытием правила, стоящим в начале перечисления альтернатив PEG выражения.
VD>Описывать операторы одинакового неудобно в любых видах парсеров, если это не сделано специальным образом.
VD>Описать приоритеты операторов элементарная задача. А вот выразить тоже самое в виде грамматики — это задача уже посложнее (сильно).
Не понимаю, чем сильно сложнее.
VD>ЗЫ
VD>Я не представляю что такое "типа LL парсера (только обобщенного и с приоритетами)".
VD>Кроме того вообще не ясно что имеется в виду под стеком и как его можно делить.
VD>LL и есть нисходящий парсер. Для разбора ПЕГ-а используется его разновидность нисходящий парсер с откатами.
VD>В общем, идея описана настолько сумбурно, что можно только гадать, что же подразумевалось.
VD>Судя по идее что-то разделять осмелюсь предположить что под LL имелся в виду LL-автомат (т.е. ДКА), а под "стеком" имелись в виду таблица такого автомата.
Если быть точным, то LL анализатор это не ДКА, а автомат с магазинной памятью. А под стеком я имел ввиду магазин.
Если же стек не используется в явном виде, то это называется Recursive Descent Parser. И с откатами может быть скорее всего именно он, поскольку LL автомат с откатами сделать довольно проблематично и неудобно, да им просто нет смысла.
В общем и LL, и Recursive Descent Parser — нисходящие парсеры, но с тем отличием, что в LL стек задан в явном виде, а во втором нет. Причем, эта разница стирается, если используется функциональный язык программирования с оптимизацией хвостовой рекурсии. Точнее, на функциональных языках программирования никогда (я никогда не видел) не делают стек в явном виде, хотя, конечно, можно.
VD>Если мои предположения верны, то ответ будет следующим...
VD>В ANTLR 3 так и поступает. Он создает набор LL(1) ДКА.
VD>Но у этой идеи есть ряд существенных недостатков:
VD>1. Требуется отдельный лексер.
Не вижу веских причин делать лексер отдельно. Вообще говоря, такой парсер должен поддерживать всё то же что и парсеры для PEG.
VD>2. Трудно сделать модульную грамматику (в связи с п. 1).
VD>3. Практически невозможно сделать такой парсер расширяемым в рантайме.
Опять же не вижу особых проблем, за исключением того, что возможно нужно перестраивать множества выбора, что не должно сильно сказываться на производительности.
На самом деле, предложенный способ дает преимущества только тогда, если грамматика контекстно зависмая, например как в С++. А так, для контексто свободных грамматик этот способ разбора будет просто сложнее в реализации, чем используемый на данный момент в Nemerle.
Но опять же, как я считаю, Nemerle совсем бы не помешали контекстно зависимые грамматики, динамически расширямые грамматики, которые бы позволили описывать и использовать макросы в одном файле. Или же это можно реализовать и при существующем подходе?
VD>Учитывая, что например, наша реализация PEG-а на основе нисходящего парсера с откатами обеспечивает весьма высокую скорость парсинга и не обладает этими недостатками, идея генерации множества ДКА и возни с ними не кажется такой особо интересной.
PS Идея с использованием LL анализатора для разбора PEG, насколько я помню, была высказана на этом форуме ещё некоторое время назад вроде бы в теме
http://www.rsdn.ru/forum/philosophy/1588175.flat.aspxАвтор: mefrill
Дата: 12.01.06
