Кто-то из наших писал порт Хаскелевского Парсека на Немерле.
Вот тут товарищ интересуется исходниками.
http://groups.google.com/group/nemerle-en/browse_thread/thread/facdf356e20bdaad

Если не жалко киньте ему исходники.

Или, если тут есть кто-то с хабра, то опросите сделать это в этой ветке.

В прочем, решение которое я видел раньше было более красивым (с макросами).

ЗЫ

Ну, и небольшой анонс. Надеюсь IT на меня не обидится...

IT обещал довести до ума макрос-генератор парсеров. Если кто-то хочет помочь в этом полезном деле, то подключайтесь.

Пример (очень предварительный) можно поглядеть здесь.

Здравствуйте, VladD2, Вы писали:

VD>Кто-то из наших писал порт Хаскелевского Парсека на Немерле.
VD>Вот тут товарищ интересуется исходниками.
VD>http://groups.google.com/group/nemerle-en/browse_thread/thread/facdf356e20bdaad

VD>Если не жалко киньте ему исходники.

VD>Или, если тут есть кто-то с хабра, то опросите сделать это в этой ветке.

VD>В прочем, решение которое я видел раньше было более красивым (с макросами).

Выложил сорцы, отписался в той ветке. Я тоже не лыком шит — у меня тоже есть целый один макрос! Дай ссылку на более красивое решение, плз, интересно же.

Здравствуйте, Elifant, Вы писали:

E>Выложил сорцы, отписался в той ветке.

Дал бы сюда прямую ссылку.

E>Дай ссылку на более красивое решение, плз, интересно же.

Дык я ее не прикопал в свое время. Если бы прикопал, то дал бы стразу.

Здравствуйте, Elifant, Вы писали:

E>Я тоже не лыком шит — у меня тоже есть целый один макрос! Дай ссылку на более красивое решение, плз, интересно же.

На счет более красивого я возможно погорячился. Давно дело было... В твоей реализации я не заметил макроса, а той что видел до этого была эмуляция do-нотации хаскеля. Вот и сказал, что та была боле красивая. Если макрос для do-нотации есть, то наверно они похожи.

ЗЫ

Кстати, не хочешь присоединиться к макросу построителю парсеров на базе PEG-нотации?
Все же парсек не самый эффективный вариант. Да и синтаксис при использовании комбинаторов не очень красивый.
У PEG-овского варианта должна и мощность быть выше, и грамматика будет полноценная, и скорость должна быть на уровне лучших генераторов парсеров.

Здравствуйте, VladD2, Вы писали:

E>>Выложил сорцы, отписался в той ветке.
VD>Дал бы сюда прямую ссылку.

http://kriomant.net/nparsec.zip

Здравствуйте, VladD2, Вы писали:

E>>Я тоже не лыком шит — у меня тоже есть целый один макрос! Дай ссылку на более красивое решение, плз, интересно же.

VD>На счет более красивого я возможно погорячился. Давно дело было... В твоей реализации я не заметил макроса, а той что видел до этого была эмуляция do-нотации хаскеля. Вот и сказал, что та была боле красивая. Если макрос для do-нотации есть, то наверно они похожи.

Тот мой единственный макрос — как раз для do-нотации.

VD>ЗЫ
VD>Кстати, не хочешь присоединиться к макросу построителю парсеров на базе PEG-нотации?
VD>Все же парсек не самый эффективный вариант. Да и синтаксис при использовании комбинаторов не очень красивый.
VD>У PEG-овского варианта должна и мощность быть выше, и грамматика будет полноценная, и скорость должна быть на уровне лучших генераторов парсеров.

Скорость, может быть и выше, но parsec погибче будет.
Но вообще интересно, много времени уделить не смогу, но чем могу — помогу. Давай вводную.

Здравствуйте, Elifant, Вы писали:

E>Здравствуйте, VladD2, Вы писали:

E>>>Я тоже не лыком шит — у меня тоже есть целый один макрос! Дай ссылку на более красивое решение, плз, интересно же.

VD>>На счет более красивого я возможно погорячился. Давно дело было... В твоей реализации я не заметил макроса, а той что видел до этого была эмуляция do-нотации хаскеля. Вот и сказал, что та была боле красивая. Если макрос для do-нотации есть, то наверно они похожи.

E>Тот мой единственный макрос — как раз для do-нотации.

VD>>ЗЫ
VD>>Кстати, не хочешь присоединиться к макросу построителю парсеров на базе PEG-нотации?
VD>>Все же парсек не самый эффективный вариант. Да и синтаксис при использовании комбинаторов не очень красивый.
VD>>У PEG-овского варианта должна и мощность быть выше, и грамматика будет полноценная, и скорость должна быть на уровне лучших генераторов парсеров.

E>Скорость, может быть и выше, но parsec погибче будет.
E>Но вообще интересно, много времени уделить не смогу, но чем могу — помогу. Давай вводную.

Извиняюсь за возможно дурацкий вопрос.
Но пока что у меня складывается мнение, что PEG и комбинаторные парсеры — по сути одна и та же концепция, но только с немножко разным подходом к реализации.
В чём же разница?
P.S: А как Вы предполагаете решать проблему левой рекурсии? Переписыванием правил? Или есть более изящный способ? ЕМНИП, все top-down парсеры с ней не дружат. Если возможно, поделитесь ссылочкой на разъяснения по этому поводу.

Спасибо.

Здравствуйте, Мишень-сан, Вы писали:

МС>Извиняюсь за возможно дурацкий вопрос.
МС>Но пока что у меня складывается мнение, что PEG и комбинаторные парсеры — по сути одна и та же концепция,

Я не знаток комбинаторных парсеров. Возможно это и так. Собственно — это даже хорошо.

МС>но только с немножко разным подходом к реализации.

Вот это сто процентов — да. Парсек по сути интерпретатор плюс в Nemerle, в отличии от Haskell, не делается агрессивных оптимизаций функциональных вычислений, что значительно снижает производительность парсера. В прочем, уверен, что и Haskell сильно отстанет от рукописного рекурсивного парсера или от парсера построенного с помощью генераторов парсеров использующих КА.

МС>В чём же разница?

Для меня основные различия следующие:
1. Оптимальная производительность (а значит возможность использования парсеров в любых задачах без каких-либо компромиссов).
2. Наличие полноценного синтаксиса.
3. Генерация и проверка парсеров во время компиляции.

МС>P.S: А как Вы предполагаете решать проблему левой рекурсии? Переписыванием правил? Или есть более изящный способ?

На первых порах — никак. Максимум сделать выявление левой рекурсии и выдачу соответствующего сообщения об ошибке.

МС>ЕМНИП, все top-down парсеры с ней не дружат. Если возможно, поделитесь ссылочной на разъяснения по этому поводу.

Для алгоритма "Packrat" есть расширения позволяющие парсить леворекурсивные правила. Ссылки можно найти здесь:
http://en.wikipedia.org/wiki/Parsing_expression_grammar#Indirect_Left_Recursion

Но к сожалению Packrat сам по себе дикий тормоз. Идея мемоизировать результаты вычисления всех правил приводит к диким, хотя и линейным, тормозам. Так что напрямую использовать ни Packrat, ни его расширения нельзя. А расширения сделаны на базе той самой мемоизации.

Здравствуйте, Elifant, Вы писали:

E>Скорость, может быть и выше, но parsec погибче будет.

Не факт. PEG — это только нотация. А гибкость зависит от реализации. Собственно PEG-парсер можно реализовать на основе комбинаторов.

E>Но вообще интересно, много времени уделить не смогу, но чем могу — помогу. Давай вводную.

Написал по этому поводу отдельное сообщение

Автор: VladD2
Дата: 01.03.10

.

Здравствуйте, VladD2, Вы писали:

E>>Скорость, может быть и выше, но parsec погибче будет.
VD>Не факт. PEG — это только нотация. А гибкость зависит от реализации. Собственно PEG-парсер можно реализовать на основе комбинаторов.

Возможно. С помощью PEG можно выразить конструкцию "число, затем столько точек, каково значение этого числа"?

Здравствуйте, Elifant, Вы писали:

E>Возможно. С помощью PEG можно выразить конструкцию "число, затем столько точек, каково значение этого числа"?

Ну, если число конкретное, по почему бы и нет. Будет что-то вроде:

Rule = "1." / "2.." / "3..." / ...

Если же речь идет о переменном числе, то это можно отработать только во время анализа распознанного, т.е. грамматика будет:

Rule = [0..9]+ "."*

а далее уже в обработчике:

Rule(num : Token, dots : Token) : ?
{
  def x = int.Parrse(num.GetString());
  assert(dots.Length == x);
  ...
}

Здравствуйте, VladD2, Вы писали:

VD>Здравствуйте, Elifant, Вы писали:

E>>Возможно. С помощью PEG можно выразить конструкцию "число, затем столько точек, каково значение этого числа"?

VD>Ну, если число конкретное, по почему бы и нет. Будет что-то вроде:
VD>

VD>Rule = "1." / "2.." / "3..." / ...
VD>

VD>Если же речь идет о переменном числе, то это можно отработать только во время анализа распознанного, т.е. грамматика будет:
VD>

VD>Rule = [0..9]+ "."*
VD>

VD>а далее уже в обработчике:

VD>

VD>Rule(num : Token, dots : Token) : ?
VD>{
VD>  def x = int.Parrse(num.GetString());
VD>  assert(dots.Length == x);
VD>  ...
VD>}
VD>

По-моему, имелось ввиду не проверить, сколько точек, а конструкция int(N) "."{N,N} — это уже контекстно-зависимая грамматика. Чистый PEG такие не умеет по определению.
Грубо говоря, PEG-грамматики можно рассматривать как подмножество комбинаторных парсеров с фиксированным набором примитивных парсеров и их комбинаторов. Впрочем, если сделать PEG расширяемым, то можно будет сделать такой мини-парсер врукопашную (это должно быть не так уж сложно) и потом примонтировать его к более крупному.

Здравствуйте, Мишень-сан, Вы писали:

МС>Грубо говоря, PEG-грамматики можно рассматривать как подмножество комбинаторных парсеров с фиксированным набором примитивных парсеров и их комбинаторов.

Комбинаторные они или нет — это детали реализации. А рассматривать грамматику как подмножество некоторых деталей реализации мягко говоря некорректно.

МС>Впрочем, если сделать PEG расширяемым, то можно будет сделать такой мини-парсер врукопашную (это должно быть не так уж сложно) и потом примонтировать его к более крупному.

Можно конечно. Но особого смысла не имеет. Для реальных задач достаточно чистого (но мощного и быстрого) парсера, а разные там финтифлюшки можно уже и на схематических действиях обработать, если что.

Скажем в грамматике C# есть всего 2-3 места когда нужны выкрутасы. В остальном ее можно легко описать с помощью PEG-а. А возможно даже и вообще всю можно.