Pegged, From EBNF to PEG

[Philippe Sigaud]

On Sat, Mar 17, 2012 at 10:09, Dmitry Olshansky <dmitry.olsh at gmail.com> wrote:

> Ok, let's agree on fact that semantically
> a* is :
> As <- a As / a
>
> and a*? is this:
> As <- a / a As
>
> Now that's local ;)

It's local, yes. But the pb is with   Expr <- A* B C D, when D fails.
PEG sequences don't backtrack.


>> I remember trying compile-time backtracking in another similar library
>> in D 1-2 years ago and getting lots of pb. I might add that in Pegged,
>> but I don't know the consequences. How do you do that in std.regex?
>
>
>
> There are two fundamental ways to get around the problem
(snip)

Thanks for the explanations. Does std.regex implement this?


> Now if we put aside all crap talk about mathematical purity and monads, and
> you name it, a packrat is essentially this, a dynamic programming trick
> applied to recursive top-down parsing. The trick could be extended even more
> to avoid extra checks on input characters, but the essence is this
> "memoization".

I plan to store indices anyway. I might add this in the future. A read
something on using PEGs to parse Java and C and there was no need to
do a complete memoization: storing the last parse result as a
temporary seemed to be enough.

>> (nice article btw, I learnt some about regexes)
>
>
> Thanks, I hope it makes them more popular.
> Might as well keep me busy fixing bugs :)

As people said on Reddit, you should make more whooping sounds about
CT-regex. That was what wowed me and pushed me to tackle CT-parsing
again.