Parsec port
От: VladD2 Российская Империя www.nemerle.org
Дата: 26.02.10 17:00
Оценка:
Кто-то из наших писал порт Хаскелевского Парсека на Немерле.
Вот тут товарищ интересуется исходниками.
http://groups.google.com/group/nemerle-en/browse_thread/thread/facdf356e20bdaad

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

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

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

ЗЫ

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

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

Пример (очень предварительный) можно поглядеть здесь.
http://nemerle.org/Banners/?g=dark
Есть логика намерений и логика обстоятельств, последняя всегда сильнее.
Re: Parsec port
От: Elifant  
Дата: 27.02.10 16:55
Оценка: 129 (1)
Здравствуйте, VladD2, Вы писали:

VD>Кто-то из наших писал порт Хаскелевского Парсека на Немерле.

VD>Вот тут товарищ интересуется исходниками.
VD>http://groups.google.com/group/nemerle-en/browse_thread/thread/facdf356e20bdaad

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


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


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


Выложил сорцы, отписался в той ветке. Я тоже не лыком шит — у меня тоже есть целый один макрос! Дай ссылку на более красивое решение, плз, интересно же.
Re[2]: Parsec port
От: VladD2 Российская Империя www.nemerle.org
Дата: 27.02.10 17:53
Оценка:
Здравствуйте, Elifant, Вы писали:

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


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

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


Дык я ее не прикопал в свое время. Если бы прикопал, то дал бы стразу.
http://nemerle.org/Banners/?g=dark
Есть логика намерений и логика обстоятельств, последняя всегда сильнее.
Re[2]: Parsec port
От: VladD2 Российская Империя www.nemerle.org
Дата: 27.02.10 18:03
Оценка:
Здравствуйте, Elifant, Вы писали:

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


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

ЗЫ

Кстати, не хочешь присоединиться к макросу построителю парсеров на базе PEG-нотации?
Все же парсек не самый эффективный вариант. Да и синтаксис при использовании комбинаторов не очень красивый.
У PEG-овского варианта должна и мощность быть выше, и грамматика будет полноценная, и скорость должна быть на уровне лучших генераторов парсеров.
http://nemerle.org/Banners/?g=dark
Есть логика намерений и логика обстоятельств, последняя всегда сильнее.
Re[3]: Parsec port
От: Elifant  
Дата: 01.03.10 05:47
Оценка: 43 (1)
Здравствуйте, VladD2, Вы писали:

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

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

http://kriomant.net/nparsec.zip
Re[3]: Parsec port
От: Elifant  
Дата: 01.03.10 06:14
Оценка:
Здравствуйте, VladD2, Вы писали:

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


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


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

VD>ЗЫ

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

Скорость, может быть и выше, но parsec погибче будет.
Но вообще интересно, много времени уделить не смогу, но чем могу — помогу. Давай вводную.
Re[4]: Parsec port
От: Мишень-сан  
Дата: 01.03.10 10:30
Оценка:
Здравствуйте, Elifant, Вы писали:

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


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


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


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


VD>>ЗЫ

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

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

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

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

Спасибо.
Re[5]: Parsec port
От: VladD2 Российская Империя www.nemerle.org
Дата: 01.03.10 16:25
Оценка:
Здравствуйте, Мишень-сан, Вы писали:

МС>Извиняюсь за возможно дурацкий вопрос.

МС>Но пока что у меня складывается мнение, что 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, ни его расширения нельзя. А расширения сделаны на базе той самой мемоизации.
http://nemerle.org/Banners/?g=dark
Есть логика намерений и логика обстоятельств, последняя всегда сильнее.
Re[4]: Parsec port
От: VladD2 Российская Империя www.nemerle.org
Дата: 01.03.10 20:12
Оценка:
Здравствуйте, Elifant, Вы писали:

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


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

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


Написал по этому поводу отдельное сообщение
Автор: VladD2
Дата: 01.03.10
.
http://nemerle.org/Banners/?g=dark
Есть логика намерений и логика обстоятельств, последняя всегда сильнее.
Re[5]: Parsec port
От: Elifant  
Дата: 03.03.10 02:21
Оценка:
Здравствуйте, VladD2, Вы писали:

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

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

Возможно. С помощью PEG можно выразить конструкцию "число, затем столько точек, каково значение этого числа"?
Re[6]: Parsec port
От: VladD2 Российская Империя www.nemerle.org
Дата: 03.03.10 12:29
Оценка:
Здравствуйте, 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);
  ...
}
http://nemerle.org/Banners/?g=dark
Есть логика намерений и логика обстоятельств, последняя всегда сильнее.
Re[7]: Parsec port
От: Мишень-сан  
Дата: 03.03.10 13:14
Оценка:
Здравствуйте, 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 расширяемым, то можно будет сделать такой мини-парсер врукопашную (это должно быть не так уж сложно) и потом примонтировать его к более крупному.
Re[8]: Parsec port
От: VladD2 Российская Империя www.nemerle.org
Дата: 03.03.10 13:26
Оценка:
Здравствуйте, Мишень-сан, Вы писали:

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


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

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


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

Скажем в грамматике C# есть всего 2-3 места когда нужны выкрутасы. В остальном ее можно легко описать с помощью PEG-а. А возможно даже и вообще всю можно.
http://nemerle.org/Banners/?g=dark
Есть логика намерений и логика обстоятельств, последняя всегда сильнее.
 
Подождите ...
Wait...
Пока на собственное сообщение не было ответов, его можно удалить.