www.digitalmars.com         C & C++   DMDScript  

digitalmars.D.announce - Pry v0.3.1 is out!

reply Dmitry Olshansky <dmitry.olsh gmail.com> writes:
Pry is a new pragmatic parser combinators library.

https://github.com/DmitryOlshansky/pry

(also available on Dub)

It's still in the early stages but I think it might be a good time to 
gauge some interest.

Two key areas of focus are (compared to say Pegged):
- performance, on par with hand-written code or die
- versatility, generating some goofy parse tree is not a goal, the goal 
is extraction of data the way the user specifies

For now it contains a modest example of a calculator app and a benchmark 
inspired by it. The interesting tidbit is that this version already 
includes an optimization that typically prevents recursive descent 
parser from falling into exponential behavior.

Future directions:
- actually add grammar layer on top of combinators, it is fancy but useful
- more built-in parsers to play with, including some stuff inspired by 
std.regex
- some goodies for usability, e.g. shortcuts to avoid constructing 
Stream out of string etc.

---
Dmitry Olshansky
Jan 14
next sibling parent reply Dicebot <public dicebot.lv> writes:
 protected-headers="v1"
From: Dicebot <public dicebot.lv>
Newsgroups: d,i,g,i,t,a,l,m,a,r,s,.,D,.,a,n,n,o,u,n,c,e
Subject: Re: Pry v0.3.1 is out!
References: <o5ej3g$27f2$1 digitalmars.com>
In-Reply-To: <o5ej3g$27f2$1 digitalmars.com>

--M290e2qNuu60taXBOLQ2DuElHvRp788KV
Content-Type: text/plain; charset=utf-8
Content-Transfer-Encoding: quoted-printable

Sounds intriguing!

On 01/15/2017 01:26 AM, Dmitry Olshansky wrote:
 - versatility, generating some goofy parse tree is not a goal, the goal=
 is extraction of data the way the user specifies
Can you show an example of what you have in mind for this? --M290e2qNuu60taXBOLQ2DuElHvRp788KV--
Jan 15
parent reply Dmitry Olshansky <dmitry.olsh gmail.com> writes:
On 1/15/17 12:43 PM, Dicebot wrote:
 Sounds intriguing!

 On 01/15/2017 01:26 AM, Dmitry Olshansky wrote:
 - versatility, generating some goofy parse tree is not a goal, the goal
 is extraction of data the way the user specifies
Can you show an example of what you have in mind for this?
Each parser has a value type that it extracts from the stream. It can be an AST node but doesn't have to. For instance, taking a page form the calculator example: auto expr = dynamic!int; auto primary = any( range!('0', '9').rep.map!(x => x.to!int), seq(tk!'(', expr, tk!')').map!(x => x[1]) ); Here 'expr' is a parser that produces an int that will be defined later. Then we see how digits are converted to string: 'range' has value of parsed digit, rep tells to apply it repeatedly and use the slice of input as the value. Finally map converts parser producing slice to parser producing int. Similarly the result of 'seq' is a tuple and map takes the middle one ('expr'), that produces an int. I could have wasted time by creating nodes and assigning values in the map functions but if you just want the result of calculation it's all moot. --- Dmitry Olshansky
Jan 15
parent Dicebot <public dicebot.lv> writes:
On Sunday, 15 January 2017 at 13:14:45 UTC, Dmitry Olshansky 
wrote:
 I could have wasted time by creating nodes and assigning values 
 in the map functions but if you just want the result of 
 calculation it's all moot.
Thanks for explanation! This is indeed very promising and much in spirit of D selling point of zero-overhead convenience abstractions.
Jan 15
prev sibling next sibling parent Dmitry Olshansky <dmitry.olsh gmail.com> writes:
On 1/15/17 2:26 AM, Dmitry Olshansky wrote:
 Pry is a new pragmatic parser combinators library.
[snip]
 Two key areas of focus are (compared to say Pegged):
 - performance, on par with hand-written code or die
Actually testing the latest version with LDC I found out that handwritten code is a bit *slower*. Beats me, as I spent quite some time laying out that handwritten stuff. All in all, this makes me confident that I soon will never have to write parsers by hand, the last nebulous reason is out. --- Dmitry Olshansky
Jan 15
prev sibling next sibling parent reply Bastiaan Veelo <Bastiaan Veelo.net> writes:
On Sunday, 15 January 2017 at 01:26:07 UTC, Dmitry Olshansky 
wrote:
 Pry is a new pragmatic parser combinators library.

 https://github.com/DmitryOlshansky/pry
Interesting. How about left-recursion? (I added support for left-recursive grammars to Pegged.)
Jan 15
parent reply Dmitry Olshansky <dmitry.olsh gmail.com> writes:
On 1/16/17 1:29 AM, Bastiaan Veelo wrote:
 On Sunday, 15 January 2017 at 01:26:07 UTC, Dmitry Olshansky wrote:
 Pry is a new pragmatic parser combinators library.

 https://github.com/DmitryOlshansky/pry
Interesting. How about left-recursion? (I added support for left-recursive grammars to Pegged.)
I think left-recursion is better handled at the grammar level. What I currently have is parser combinators level where adding this transformation is awkward and too much magic IMO. However I plan to add a grammar on top of combinators, and yes handling left-recursive grammars is going to be an interesting challenge. --- Dmitry Olshansky
Jan 16
parent reply Bastiaan Veelo <Bastiaan Veelo.net> writes:
On Monday, 16 January 2017 at 22:29:01 UTC, Dmitry Olshansky 
wrote:
 I think left-recursion is better handled at the grammar level.
 What I currently have is parser combinators level where adding
 this transformation is awkward and too much magic IMO.
Handling left-recursion by grammar transformation often has unwanted side-effects (operator precedence) and eliminating indirect left-recursion this way can be impossible in practice. Depending on the complexity of the grammar, even identifying the recursive loop can be a challenge. The trouble is that one can be happily implementing a parser or designing a grammar when suddenly for some input the parser hangs indefinitely. Users are likely quick to blame the parser lib, while in fact it is the grammar that has left-recursion. Hitting that roadblock is a real bummer. In some cases the grammar is a given (by a standard for example) and transforming it to combat left-recursion can obfuscate it beyond recognition. Hardening Pegged to deal with the various kinds of left-recursion was very challenging, but easier than transforming the grammar I was dealing with (ISO 10206).
Jan 17
parent reply Dmitry Olshansky <dmitry.olsh gmail.com> writes:
On 1/17/17 1:16 PM, Bastiaan Veelo wrote:
 On Monday, 16 January 2017 at 22:29:01 UTC, Dmitry Olshansky wrote:
 I think left-recursion is better handled at the grammar level.
 What I currently have is parser combinators level where adding
 this transformation is awkward and too much magic IMO.
Handling left-recursion by grammar transformation often has unwanted side-effects (operator precedence) and eliminating indirect left-recursion this way can be impossible in practice. Depending on the complexity of the grammar, even identifying the recursive loop can be a challenge.
I do not suggest to change the grammar itself, I think that processing of the grammar may perform hidden transformations internally.
 The trouble is that one can be happily implementing a parser or
 designing a grammar when suddenly for some input the parser hangs
 indefinitely. Users are likely quick to blame the parser lib, while in
 fact it is the grammar that has left-recursion. Hitting that roadblock
 is a real bummer.

 In some cases the grammar is a given (by a standard for example) and
 transforming it to combat left-recursion can obfuscate it beyond
 recognition. Hardening Pegged to deal with the various kinds of
 left-recursion was very challenging, but easier than transforming the
 grammar I was dealing with (ISO 10206).
Interesting, what kind of hardening? --- Dmitry Olshansky
Jan 17
parent Bastiaan Veelo <Bastiaan Veelo.net> writes:
On Tuesday, 17 January 2017 at 21:10:17 UTC, Dmitry Olshansky 
wrote:
 On 1/17/17 1:16 PM, Bastiaan Veelo wrote:
 On Monday, 16 January 2017 at 22:29:01 UTC, Dmitry Olshansky 
 wrote:
 I think left-recursion is better handled at the grammar level.
 What I currently have is parser combinators level where adding
 this transformation is awkward and too much magic IMO.
Handling left-recursion by grammar transformation often has unwanted side-effects (operator precedence) and eliminating indirect left-recursion this way can be impossible in practice. Depending on the complexity of the grammar, even identifying the recursive loop can be a challenge.
I do not suggest to change the grammar itself, I think that processing of the grammar may perform hidden transformations internally.
Interesting. Would that work with indirect left-recursion? That would be daunting, I fear. It'l still mess with order of operation / associativity, won't it?
 Hardening Pegged to deal with the various kinds of
 left-recursion was very challenging, but easier than 
 transforming the
 grammar I was dealing with (ISO 10206).
Interesting, what kind of hardening?
The trick is to recurse, but knowing when to stop. At a certain point, recursing once more will reduce the length of the matched string. So if you can break recursion when the match stops growing, you are good. This is implemented by memoizing previous recursions. There is an explanation along with literature references in my first PR on left-recursion [1]. However, the PR itself was flawed [2] and received several makeovers [3-5]. In the end, the solution was considerably more complex than the initial PR, involving introspection of the grammar to identify left-recursive loops and the appropriate rules to memoize. We now have complete support for direct, indirect and hidden left-recursion, including multiple intersecting loops and mixed left- and right-recursion. And it does not interfere with general memoization, which is important to speed up PEG parsers [6]. There are some illustrative unit tests in [7] and further. Bastiaan. [1] https://github.com/PhilippeSigaud/Pegged/pull/164 [2] https://github.com/PhilippeSigaud/Pegged/pull/165#issuecomment-158914006 [3] https://github.com/PhilippeSigaud/Pegged/pull/168 [4] https://github.com/PhilippeSigaud/Pegged/pull/186 [5] https://github.com/PhilippeSigaud/Pegged/pull/196 [6] Pegged does not memoize at CT though, at the moment. [7] https://github.com/PhilippeSigaud/Pegged/blob/master/pegged/grammar.d#L2965
Jan 17
prev sibling parent reply Bastiaan Veelo <Bastiaan Veelo.net> writes:
On Sunday, 15 January 2017 at 01:26:07 UTC, Dmitry Olshansky 
wrote:
 Two key areas of focus are (compared to say Pegged):
 - performance, on par with hand-written code or die
I didn't profile, but apart from the time-complexity that is inherent to straight forward recursive descent parsers like Pegged (improved by memoization), my impression is that Pegged's main performance problem is due to a very high constant: it is concatenating strings, all the time. A LOT of strings, and a LOT of concatenations. Almost all of them are discarded, of course. Finding a way to do the same without string concatenation would have a big impact. Bastiaan.
Jan 17
parent Dmitry Olshansky <dmitry.olsh gmail.com> writes:
On 1/17/17 11:52 PM, Bastiaan Veelo wrote:
 On Sunday, 15 January 2017 at 01:26:07 UTC, Dmitry Olshansky wrote:
 Two key areas of focus are (compared to say Pegged):
 - performance, on par with hand-written code or die
I didn't profile, but apart from the time-complexity that is inherent to straight forward recursive descent parsers like Pegged (improved by memoization), my impression is that Pegged's main performance problem is due to a very high constant: it is concatenating strings, all the time. A LOT of strings, and a LOT of concatenations. Almost all of them are discarded, of course. Finding a way to do the same without string concatenation would have a big impact.
I considered to work with Pegged but I decided against it, because my priorities are different: get it fast then get it full of features. IMHO performance is something to think of at design time not afterwards. --- Dmitry Olshansky
Jan 20