Давичи мне указали на то что в мире имеется еще один интересный алгоритм распознавания текстов — Pratt. Это так называемый "Top Down Operator Precedence".
По сути это ни что иное как обычный Top Down парсер, т.е. без откатов (бэктрекинка) как в PEG (и прочих блэкджеков).
Интересен он тем, что алгоритм рекурсивного спуска дополнен отдельной стадией обработки приоритетов и ассоциативности (или правых и левых приоритетов) операторов. Учитывая что многое при парсинге можно описать в виде операторов (в том числе точку в С-подобных языках и даже скобки) — этот подход может существенно упростить описание грамматик современных языков программирования.
На мой взгляд это весьма разумный подход который может быть легко интегрирован с PEG-ом (разбираемым с помощью парсеров рекурсивного спуска с откатами). Простой пример... Недавно hardcase реализовал парсер C# 4.0 на базе макроса Nemerle PegGrammar
. При реализации он столкнулся с тем, что в парсере не врено обрабатывался приоритет оператора "as". Попытки решить проблему в лоб не не привили к положительному результату. Оказалось, что на грамматике такого объема с операторами очень легко запутаться. Посовещавшись мы решили вместо описания приоритетов операторов в виде иерархии правил использовать алгоритм с двумя стеками. В результате вместо нагромождения правил (в которых черт ногу сломит) получились три простых правила (Parser.n):
Собственно мораль сей басни в том, что к генераторам парсеров и комбинаторным парсерам использующим алгоритм рекурсивного спуска очень полезно было бы добавить данную возможность (приоритетной обработки операторов).
ЗЫ
Надеюсь, что данные ссылки будут кому-то интересны.
Забавно, что идея стара (почти) как мир (алгоритм разработан на Лиспе еще в 70-ых). Но почему-то до недавнего момента я о нем ни разу не слышал. Все же хорошие идеи обязаны популяризироваться. Что я и делаю .
Кстати, чем плоха идея строить типа LL парсера (только обобщенного и с приоритетами) для разбора текста, заданного грамматикой в формате PEG?
Под обобщенный LL я имею ввиду делить стек при возникновении неоднозначности. То есть если по первому символу не возможно раскрыть правило, то делим стек. Ну а когда, возникает такая ситуация, что некоторое множество стеков одинаково, оставлять из них только один, который был порожден раскрытием правила, стоящим в начале перечисления альтернатив PEG выражения.
Здравствуйте, Aleх, Вы писали:
A>Кстати, чем плоха идея строить типа LL парсера (только обобщенного и с приоритетами) для разбора текста, заданного грамматикой в формате PEG?
A>Под обобщенный LL я имею ввиду делить стек при возникновении неоднозначности. То есть если по первому символу не возможно раскрыть правило, то делим стек. Ну а когда, возникает такая ситуация, что некоторое множество стеков одинаково, оставлять из них только один, который был порожден раскрытием правила, стоящим в начале перечисления альтернатив PEG выражения.
Описывать операторы одинакового неудобно в любых видах парсеров, если это не сделано специальным образом.
Описать приоритеты операторов элементарная задача. А вот выразить тоже самое в виде грамматики — это задача уже посложнее (сильно).
ЗЫ
Я не представляю что такое "типа LL парсера (только обобщенного и с приоритетами)".
Кроме того вообще не ясно что имеется в виду под стеком и как его можно делить.
LL и есть нисходящий парсер. Для разбора ПЕГ-а используется его разновидность нисходящий парсер с откатами.
В общем, идея описана настолько сумбурно, что можно только гадать, что же подразумевалось.
Судя по идее что-то разделять осмелюсь предположить что под LL имелся в виду LL-автомат (т.е. ДКА), а под "стеком" имелись в виду таблица такого автомата.
Если мои предположения верны, то ответ будет следующим...
В ANTLR 3 так и поступает. Он создает набор LL(1) ДКА.
Но у этой идеи есть ряд существенных недостатков:
1. Требуется отдельный лексер.
2. Трудно сделать модульную грамматику (в связи с п. 1).
3. Практически невозможно сделать такой парсер расширяемым в рантайме.
Учитывая, что например, наша реализация PEG-а на основе нисходящего парсера с откатами обеспечивает весьма высокую скорость парсинга и не обладает этими недостатками, идея генерации множества ДКА и возни с ними не кажется такой особо интересной.
Есть логика намерений и логика обстоятельств, последняя всегда сильнее.
Здравствуйте, 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-а на основе нисходящего парсера с откатами обеспечивает весьма высокую скорость парсинга и не обладает этими недостатками, идея генерации множества ДКА и возни с ними не кажется такой особо интересной.
Здравствуйте, Aleх, Вы писали:
A>PS Идея с использованием LL анализатора для разбора PEG, насколько я помню, была высказана на этом форуме ещё некоторое время назад вроде бы в теме http://www.rsdn.ru/forum/philosophy/1588175.flat.aspx
Здравствуйте, Wolverrum, Вы писали:
NB>>ты LL анализатором леворекурсивную грамматику разобрать смогешь? W>Так вроде ж не проблема леворекурсию убрать.
не всегда.
к тому же, усложнение правил увеличивает вероятность ошибки.
Здравствуйте, Aleх, Вы писали:
VD>>Описать приоритеты операторов элементарная задача. А вот выразить тоже самое в виде грамматики — это задача уже посложнее (сильно).
A>Не понимаю, чем сильно сложнее.
В одном случае это плоский список операторов с их приоритетами, в другом нагромождения правил зависимости между которыми нужно еще разглядеть. А ведь, приоритеты они еще бывают правые и левые (ассоциативность) в грамматике это совершенно не очевидно.
В общем, попробуй сделать парсер более-менее серьезного языка обоими методами, тогда поймешь.
A>Если быть точным, то LL анализатор это не ДКА,
Синтаксический LL-анализатор (LL parser) — нисходящий синтаксический анализатор для подмножества контекстно-свободных грамматик. Он анализирует входной поток слева направо, и строит левый вывод грамматики. Класс грамматик, для которых можно построить LL-анализатор, известен как LL-грамматики.
Автоматная реализация — одна из возможных.
A>а автомат с магазинной памятью.
Вообще заблуждение. Автоматы с магазинной памятью используются для LALR(1).
LL(1) парсится или без автомата или по простому табличному автомату.
A>А под стеком я имел ввиду магазин.
Понятно, но это вообще не из той оперы.
A>Если же стек не используется в явном виде, то это называется Recursive Descent Parser.
Спасибо за разъяснение. Если под стеком понимать магазинную память, то конечно. Вот только если под стеком понимать стек...
A>И с откатами может быть скорее всего именно он, поскольку LL автомат с откатами сделать довольно проблематично и неудобно, да им просто нет смысла.
Сделать можно. И даже некоторый смысл есть. Но автомат по любому создает свои проблемы (о которых я уже говорил).
A>В общем и LL, и Recursive Descent Parser — нисходящие парсеры, но с тем отличием, что в LL стек задан в явном виде, а во втором нет.
Вообще не стоит влезать в обсуждение если в теме плохо разбираться. Лучше экономить свое и чужое время.
Почитай хотя бы википедию о том, что такое LL. LL == парсер рекурсивного спуска производящий разбор слива (первая L) на правло и строит левый (вторая L) вывод грамматики. Точка! И никакие автоматы тут не причем. То что автомат можно использовать для предсказания разбора LL(1) грамматик ничего ровным счетом не меняет.
A>Причем, эта разница стирается, если используется функциональный язык программирования с оптимизацией хвостовой рекурсии.
О, как? Языки у нас уже способны стирать различия между алгоритмами?
К сведению, хвостовая рекурсия всегда может быть заменена на цикл. Так что все что можно написать на функциональном языке всегда можно написать на императивном. Обратно не верно.
A> Точнее, на функциональных языках программирования никогда (я никогда не видел) не делают стек в явном виде, хотя, конечно, можно.
Еще одна чушь. Если алгоритм требует двух стектов, то тут как не крути, но без отдельной структуры данных не обойтись. Да и вообще смешно говорить об отличиях алгоритмов на ФЯ и ИЯ. В ФЯ могут выбираться другие средства, но алгоритм есть алгоритм. Он не может меняться от использования языка. Да и деление на ФЯ и ИЯ весьма уловы. Нет такого ФЯ на котором нельзя было бы залудить императивный код. Даже на Хаскеле можно (хотя и раком).
VD>>Если мои предположения верны, то ответ будет следующим...
VD>>В ANTLR 3 так и поступает. Он создает набор LL(1) ДКА. VD>>Но у этой идеи есть ряд существенных недостатков: VD>>1. Требуется отдельный лексер. A>Не вижу веских причин делать лексер отдельно.
Веская причина 1 — LL(1) с ДКА плохо умеют работать в жадном режиме, а лексические зачастую выбирают самую длинную ветвь (например, разбор идентификатора).
Веская причина 2 — LL(1) с ДКА значительно менее эффективен нежели ДКА для регулярных выражений.
В общем, я не видел ни одного LL-парсера (да и LALR) использующего ДКА который бы при этом не использовал выделенный лексер. CocoR, ANTLR... и Yacc все используют отдельный лексер.
Собственно PEG тем и хорош, что он позволяет описывать парсер и лексер в одном флаконе.
A>Вообще говоря, такой парсер должен поддерживать всё то же что и парсеры для PEG.
Вообще, говоря если кто-то крякает как утка, плавает как утка, и летает как утка, то может это и есть утка?
Другими словами, если что-то удовлетворяет описанию PEG-а, то это скорее всего он и есть. Или некий гибрид.
VD>>2. Трудно сделать модульную грамматику (в связи с п. 1). VD>>3. Практически невозможно сделать такой парсер расширяемым в рантайме. A>Опять же не вижу особых проблем,
Обожаю тех кто ходит по форумам и не видит ни в чем проблем.
Что тут можно сказать?
Разберись в вопросе по глубже и увидишь все проблемы.
A>за исключением того, что возможно нужно перестраивать множества выбора, что не должно сильно сказываться на производительности.
Еще одна многозначительная, загадочная фраз... Что такое "перестраивать множества выбора"?
Если у нас есть ДКА, то он создан для конкретной грамматики. Если грамматика меняется в рантайме, то нужно пересоздавать автомат (а у нас он еще и не один будет). Это резко усложняет задачу и может привести к тому, что конечный парсер или будет не эффективным, или будет тратить много времени на самоконфигурацию.
A>На самом деле, предложенный способ дает преимущества только тогда, если грамматика контекстно зависмая, например как в С++. А так, для контексто свободных грамматик этот способ разбора будет просто сложнее в реализации, чем используемый на данный момент в Nemerle.
Не вижу никаких проблем с контекстной-зависимостью а-ля С++. Грамматика С/С++ всего лишь требует ведения таблицы символов. Это не полноценная контекстная зависимость. Ее можно реализовать как на парсере с откатами, так и на парсере основанном на автоматах. Лично мы для этого реализовали фичу которую мы назвали Scope. Это некая именованная область область. Ею можно окружить часть подправил. На ее входе будет вызван один метод-обработчик, а на выходе другой. Причем второй обработчик будет вызван независимо от того производится ли откат данного правила, или оно успешно сопоставилось. Таким образом во втором обработчике можно восстанавливать таблицу символов в том виде в каком она была при вызове первого обработчика.
A>Но опять же, как я считаю, Nemerle совсем бы не помешали контекстно зависимые грамматики, динамически расширямые грамматики, которые бы позволили описывать и использовать макросы в одном файле. Или же это можно реализовать и при существующем подходе?
Не просто можно, а уже реализовано (см. выше). Динамическое расширение еще не реализовано, но будет реализовано в ближайшее время. Можно будет пометить правило (состоящие из оператора приоритетного выбора) как расширяемое. Это позволит добавлять в него другие правила в рантайме.
Таким образом в грамматике можно будет пометить ряд правил как динамически расширяемые, а потом подгружать библиотеки экспортирующие правила-расширения.
Такие правила будут хранить список подправил в динамическом массиве. Скажем если язык позволяет вводить правила путем открытия пространств имен (как сам Немерле), то в обработчике using-а нам надо будет считать правила-расширения отрываемые этим using-ом и пополнить ими соответствующие расширяемые правила. Это приведет к тому, то при разборе этих правил парсер будет разбирать уже другую — расширенную — грамматику.
При этом правило "пространство имен" нужно будет обернуть в Scope, чтобы в конце разбора пространства имен можно было удалить динамически-загруженные правила из точек расширения.
A>PS Идея с использованием LL анализатора для разбора PEG, насколько я помню, была высказана на этом форуме ещё некоторое время назад вроде бы в теме http://www.rsdn.ru/forum/philosophy/1588175.flat.aspx
Здесь много чего высказывалось. Но практика — критерий истины. Пока что все неплохо получается без ДКА на верхнем уровне. К тому же давать ссылку на целую тему — это перебор. Мне неохота читать всю тему, чтобы вспомнить о чем там была речь.
Мы генерируем ДКА для виртуальных терминалов. Виртуальных, потому как в ПЕГ реальным терминалом всегда является отдельный символ. Виртуальным терминалом я называю листовую ветвь грамматики разбирающую не рекурсивное правило и не имеющее внутри обработчика (т.е. просто распознающая текст). Такое правило может быть преобразовано в ДКА (или регулярные выражения).
Кроме того делается ряд оптимизаций. Это приводит к тому, что скомпилированный в релиз (с оптимизациями) парсер работает на процессорах класса Core 2 и частотой 2+ Ггц со скоростью порядка 3 мегабайт в секунду (тестировалось на парсере C# 4.0). (И это при том, что парсер написан на типобезопасном языке.) Этого хватает для реального применения.
Учитывая что ПЕГ — это очень мощный формализм — это позволяет парсить практически любой язык программирования без танцев с бубнами.
Простой пример. Грамматика C# 4.0 была создана не профессионалом в области создания парсеров за 2 недели.
Это практически смертный приговор платным генераторам парсеров .
Есть логика намерений и логика обстоятельств, последняя всегда сильнее.
Здравствуйте, night beast, Вы писали:
NB>Здравствуйте, Aleх, Вы писали:
A>>PS Идея с использованием LL анализатора для разбора PEG, насколько я помню, была высказана на этом форуме ещё некоторое время назад вроде бы в теме http://www.rsdn.ru/forum/philosophy/1588175.flat.aspx
Здравствуйте, VladD2, Вы писали:
VD>Здравствуйте, Aleх, Вы писали:
VD>>>Описать приоритеты операторов элементарная задача. А вот выразить тоже самое в виде грамматики — это задача уже посложнее (сильно).
A>>Не понимаю, чем сильно сложнее.
VD>В одном случае это плоский список операторов с их приоритетами, в другом нагромождения правил зависимости между которыми нужно еще разглядеть. А ведь, приоритеты они еще бывают правые и левые (ассоциативность) в грамматике это совершенно не очевидно.
VD>В общем, попробуй сделать парсер более-менее серьезного языка обоими методами, тогда поймешь.
A>>Если быть точным, то LL анализатор это не ДКА,
VD>http://ru.wikipedia.org/wiki/LL VD>
VD>Синтаксический LL-анализатор (LL parser) — нисходящий синтаксический анализатор для подмножества контекстно-свободных грамматик. Он анализирует входной поток слева направо, и строит левый вывод грамматики. Класс грамматик, для которых можно построить LL-анализатор, известен как LL-грамматики.
VD>Автоматная реализация — одна из возможных.
A>>а автомат с магазинной памятью.
VD>Вообще заблуждение. Автоматы с магазинной памятью используются для LALR(1). VD>LL(1) парсится или без автомата или по простому табличному автомату.
Во первых, почитай всё таки Википедию, если конечно доверяешь тому что там написано. Я имею ввиду статью полностью.
Я понимаю, что ты практик. Но всё-таки нужно ингода и не пренебрегать теорией. C помощью ДКА можно разбирать только регулярные языки. Контекстно-свободный в принципе не может быть разобран с помощью ДКА.
Теорема Клини гласит, что класс языков, представимых конечными автоматами, совпадает с классом регулярных языков. Кроме того, этот класс совпадает с классом языков, задаваемых регулярными грамматиками.
Это формально так.
Но, я понимаю, что часто бывает, если программист-практик говорит, что не использует ДКА, на самом деле не используется ДКА просто в явном виде (когда есть таблица переходов).
A>>А под стеком я имел ввиду магазин.
VD>Понятно, но это вообще не из той оперы.
A>>Если же стек не используется в явном виде, то это называется Recursive Descent Parser.
VD>Спасибо за разъяснение. Если под стеком понимать магазинную память, то конечно. Вот только если под стеком понимать стек...
A>>И с откатами может быть скорее всего именно он, поскольку LL автомат с откатами сделать довольно проблематично и неудобно, да им просто нет смысла.
VD>Сделать можно. И даже некоторый смысл есть. Но автомат по любому создает свои проблемы (о которых я уже говорил).
A>>В общем и LL, и Recursive Descent Parser — нисходящие парсеры, но с тем отличием, что в LL стек задан в явном виде, а во втором нет.
VD>Вообще не стоит влезать в обсуждение если в теме плохо разбираться. Лучше экономить свое и чужое время. VD>Почитай хотя бы википедию о том, что такое LL. LL == парсер рекурсивного спуска производящий разбор слива (первая L) на правло и строит левый (вторая L) вывод грамматики. Точка! И никакие автоматы тут не причем. То что автомат можно использовать для предсказания разбора LL(1) грамматик ничего ровным счетом не меняет.
Я то нормально разбираюсь. С помощью ДКА невозможно разбирать контекстно свободные языки, как бы там алгоритм не назывался и как бы его реализация на конкретном языке программирования не выглядела.
A>>Причем, эта разница стирается, если используется функциональный язык программирования с оптимизацией хвостовой рекурсии.
VD>О, как? Языки у нас уже способны стирать различия между алгоритмами? VD>К сведению, хвостовая рекурсия всегда может быть заменена на цикл.
Я говорил обратное? VD>Так что все что можно написать на функциональном языке всегда можно написать на императивном. Обратно не верно.
Угу, только в имепративных языках хвостовая рекурсия обычно не заменяется циклом.
A>> Точнее, на функциональных языках программирования никогда (я никогда не видел) не делают стек в явном виде, хотя, конечно, можно.
VD>Еще одна чушь. Если алгоритм требует двух стектов, то тут как не крути, но без отдельной структуры данных не обойтись. Да и вообще смешно говорить об отличиях алгоритмов на ФЯ и ИЯ. В ФЯ могут выбираться другие средства, но алгоритм есть алгоритм. Он не может меняться от использования языка. Да и деление на ФЯ и ИЯ весьма уловы. Нет такого ФЯ на котором нельзя было бы залудить императивный код. Даже на Хаскеле можно (хотя и раком).
Ну если требует двух стеков... А при парсинге обычно требует?
A>>Не вижу веских причин делать лексер отдельно.
VD>Веская причина 1 — LL(1) с ДКА плохо умеют работать в жадном режиме, а лексические зачастую выбирают самую длинную ветвь (например, разбор идентификатора). VD>Веская причина 2 — LL(1) с ДКА значительно менее эффективен нежели ДКА для регулярных выражений.
VD>В общем, я не видел ни одного LL-парсера (да и LALR) использующего ДКА который бы при этом не использовал выделенный лексер. CocoR, ANTLR... и Yacc все используют отдельный лексер.
VD>Собственно PEG тем и хорош, что он позволяет описывать парсер и лексер в одном флаконе.
A>>Вообще говоря, такой парсер должен поддерживать всё то же что и парсеры для PEG.
VD>Вообще, говоря если кто-то крякает как утка, плавает как утка, и летает как утка, то может это и есть утка? VD>Другими словами, если что-то удовлетворяет описанию PEG-а, то это скорее всего он и есть. Или некий гибрид.
PEG — способ задания грамматики. Способ задания грамматики != анализатор.
VD>>>2. Трудно сделать модульную грамматику (в связи с п. 1). VD>>>3. Практически невозможно сделать такой парсер расширяемым в рантайме. A>>Опять же не вижу особых проблем,
VD>Обожаю тех кто ходит по форумам и не видит ни в чем проблем. VD>Что тут можно сказать? VD>Разберись в вопросе по глубже и увидишь все проблемы.
A>>за исключением того, что возможно нужно перестраивать множества выбора, что не должно сильно сказываться на производительности.
VD>Еще одна многозначительная, загадочная фраз... Что такое "перестраивать множества выбора"?
Термин множество выбора не я придумал. Я его где то встреал в литературе.
Вот что это
У правила E -> TE' множеством выбора будет {id, ( } . То есть множество, по которому выбирается правило.
VD>Если у нас есть ДКА, то он создан для конкретной грамматики. Если грамматика меняется в рантайме, то нужно пересоздавать автомат (а у нас он еще и не один будет). Это резко усложняет задачу и может привести к тому, что конечный парсер или будет не эффективным, или будет тратить много времени на самоконфигурацию.
A>>На самом деле, предложенный способ дает преимущества только тогда, если грамматика контекстно зависмая, например как в С++. А так, для контексто свободных грамматик этот способ разбора будет просто сложнее в реализации, чем используемый на данный момент в Nemerle.
VD>Не вижу никаких проблем с контекстной-зависимостью а-ля С++. Грамматика С/С++ всего лишь требует ведения таблицы символов. Это не полноценная контекстная зависимость. Ее можно реализовать как на парсере с откатами, так и на парсере основанном на автоматах. Лично мы для этого реализовали фичу которую мы назвали Scope. Это некая именованная область область. Ею можно окружить часть подправил. На ее входе будет вызван один метод-обработчик, а на выходе другой. Причем второй обработчик будет вызван независимо от того производится ли откат данного правила, или оно успешно сопоставилось. Таким образом во втором обработчике можно восстанавливать таблицу символов в том виде в каком она была при вызове первого обработчика.
A>>Но опять же, как я считаю, Nemerle совсем бы не помешали контекстно зависимые грамматики, динамически расширямые грамматики, которые бы позволили описывать и использовать макросы в одном файле. Или же это можно реализовать и при существующем подходе?
VD>Не просто можно, а уже реализовано (см. выше). Динамическое расширение еще не реализовано, но будет реализовано в ближайшее время. Можно будет пометить правило (состоящие из оператора приоритетного выбора) как расширяемое. Это позволит добавлять в него другие правила в рантайме.
VD>Таким образом в грамматике можно будет пометить ряд правил как динамически расширяемые, а потом подгружать библиотеки экспортирующие правила-расширения.
VD>Такие правила будут хранить список подправил в динамическом массиве. Скажем если язык позволяет вводить правила путем открытия пространств имен (как сам Немерле), то в обработчике using-а нам надо будет считать правила-расширения отрываемые этим using-ом и пополнить ими соответствующие расширяемые правила. Это приведет к тому, то при разборе этих правил парсер будет разбирать уже другую — расширенную — грамматику. VD>При этом правило "пространство имен" нужно будет обернуть в Scope, чтобы в конце разбора пространства имен можно было удалить динамически-загруженные правила из точек расширения.
A>>PS Идея с использованием LL анализатора для разбора PEG, насколько я помню, была высказана на этом форуме ещё некоторое время назад вроде бы в теме http://www.rsdn.ru/forum/philosophy/1588175.flat.aspx
VD>Здесь много чего высказывалось. Но практика — критерий истины. Пока что все неплохо получается без ДКА на верхнем уровне. К тому же давать ссылку на целую тему — это перебор. Мне неохота читать всю тему, чтобы вспомнить о чем там была речь.
VD>Мы генерируем ДКА для виртуальных терминалов. Виртуальных, потому как в ПЕГ реальным терминалом всегда является отдельный символ. Виртуальным терминалом я называю листовую ветвь грамматики разбирающую не рекурсивное правило и не имеющее внутри обработчика (т.е. просто распознающая текст). Такое правило может быть преобразовано в ДКА (или регулярные выражения).
VD>Кроме того делается ряд оптимизаций. Это приводит к тому, что скомпилированный в релиз (с оптимизациями) парсер работает на процессорах класса Core 2 и частотой 2+ Ггц со скоростью порядка 3 мегабайт в секунду (тестировалось на парсере C# 4.0). (И это при том, что парсер написан на типобезопасном языке.) Этого хватает для реального применения.
VD>Учитывая что ПЕГ — это очень мощный формализм — это позволяет парсить практически любой язык программирования без танцев с бубнами.
VD>Простой пример. Грамматика C# 4.0 была создана не профессионалом в области создания парсеров за 2 недели. VD>Это практически смертный приговор платным генераторам парсеров .
Здравствуйте, Aleх, Вы писали:
A>>>PS Идея с использованием LL анализатора для разбора PEG, насколько я помню, была высказана на этом форуме ещё некоторое время назад вроде бы в теме http://www.rsdn.ru/forum/philosophy/1588175.flat.aspx
Здравствуйте, night beast, Вы писали:
NB>Здравствуйте, Aleх, Вы писали:
A>>>>PS Идея с использованием LL анализатора для разбора PEG, насколько я помню, была высказана на этом форуме ещё некоторое время назад вроде бы в теме http://www.rsdn.ru/forum/philosophy/1588175.flat.aspx
NB>>>ты LL анализатором леворекурсивную грамматику разобрать смогешь?
A>>Дык и PEG парсеры часто не поддерживают левую рекурсию.
NB>и? из того что некоторые этого не делают не следует то что это не делают все.
A>>Тем более левую рекурсию можно убирать.
NB>
NB>\S -> \A b | \A c
NB>\A -> \A \B | a
NB>\B -> a
NB>
<S> -> <A> <D>
<D> -> b | c
<A> -> <B> <A> | <epsilon>
<B> -> a
A>>Ну а сама по себе она не представляет большой ценности.
NB>это высказывание оставлю на твоей совести
Здравствуйте, Aleх, Вы писали:
NB>>и? из того что некоторые этого не делают не следует то что это не делают все.
A>>>Тем более левую рекурсию можно убирать.
NB>>
NB>>\S -> \A b | \A c
NB>>\A -> \A \B | a
NB>>\B -> a
NB>>
A>
A><S> -> <A> <D>
A><D> -> b | c
A><A> -> <B> <A> | <epsilon>
A><B> -> a
A>
Здравствуйте, night beast, Вы писали:
NB>Здравствуйте, Aleх, Вы писали:
NB>>>и? из того что некоторые этого не делают не следует то что это не делают все.
A>>>>Тем более левую рекурсию можно убирать.
NB>>>
NB>>>\S -> \A b | \A c
NB>>>\A -> \A \B | a
NB>>>\B -> a
NB>>>
A>>
A>><S> -> <A> <D>
A>><D> -> b | c
A>><A> -> <B> <A> | <epsilon>
A>><B> -> a
A>>
NB>грамматики не эквивалентны.
да. вот теперь эквивалентны?
<S> -> <B> <A> <D>
<D> -> b | c
<A> -> <B> <A> | <epsilon>
<B> -> a
NB>>>>\S -> \A b | \A c
NB>>>>\A -> \A \B | a
NB>>>>\B -> a
NB>>>>
A>да. вот теперь эквивалентны?
теперь вроде да. только надо бы пустые продукции убрать, тогда еще правил добавится.
на самом деле, пример не очень удачный выбрал (скопипастил не думая)
в исходном достаточно было поменять \A и \B местами
.
