date:20120317

Re: Pegged, From EBNF to PEG

2012-03-17 Thread Philippe Sigaud

On Wed, Mar 14, 2012 at 10:48, Dmitry Olshansky dmitry.o...@gmail.com wrote:

 That's one of the caveats on PEG. That and greedy operators.

 'a*a' never succeeds because 'a*' consumes all the available a's.


 Hey, wait, I thought there has to be backtrack here, i.e. when second 'a'
 finally fails?

PEG only do local backtracking in 'or' choices, not in sequences. I
think that's because the original author was dealing with packrat
parsing and its O(input-size) guarantee.

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?

(nice article btw, I learnt some about regexes)

Re: Pegged: Syntax Highlighting

2012-03-17 Thread Philippe Sigaud

On Wed, Mar 14, 2012 at 21:03, Andrej Mitrovic
andrej.mitrov...@gmail.com wrote:

 how would one use a parser like Pegged for syntax
 highlighting?

 Ok, typically one would use a lexer and not a parser. But using a
 parser might be more interesting for creating more complex syntax
 highlighting. :)


 Actually I think I can use the new ddmd-clean port for just this
 purpose. Sorry for the noise.

Sorry for the late reply, I was away for a few days, in a Net-forsaken place ;)

If ddmd-clean is OK for you, that's cool. Keep us informed how that went.
If you want to use Pegged, you'd need to enter the entire D grammar to
get a correct parse tree.
I just finished writing it, but I'm afraid to try and compile it :)
It's one huge monster.

Re: Pegged, From EBNF to PEG

2012-03-17 Thread Dmitry Olshansky


On 17.03.2012 10:59, Philippe Sigaud wrote:

On Wed, Mar 14, 2012 at 10:48, Dmitry Olshanskydmitry.o...@gmail.com  wrote:


That's one of the caveats on PEG. That and greedy operators.

'a*a' never succeeds because 'a*' consumes all the available a's.



Hey, wait, I thought there has to be backtrack here, i.e. when second 'a'
finally fails?


PEG only do local backtracking in 'or' choices, not in sequences. I
think that's because the original author was dealing with packrat
parsing and its O(input-size) guarantee.



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 ;)



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, the easiest
to implement is to use a stack to record a position in input + number of 
alternative/production (I call it a PC - program counter) every time 
there is a fork like that. Then when the current path ultimately fails 
pop stack, reset input and go over again until you either match or empty 
the stack. That's how to avoid dp recursion that happens here.


The problematic thing now is combinatorial explosion of
a* a* a*  //simplified, but you get the idea

The trick to avoid this sort of crap is to
1) agree that whatever matches first has higher priority (left-most 
match) that's a simple disambiguation rule.
2) record what positions + pc you place on stack e.g. use a set, or in 
fact, a bitmap to push every unique combination  (pc,index) only once.


Voila! Now you have a linear worst-case algorithm with (M*N) complexity 
where M is number of all possible PCs, and N is number of all possible 
indexes in input.


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.




(nice article btw, I learnt some about regexes)


Thanks, I hope it makes them more popular.
Might as well keep me busy fixing bugs :)

--
Dmitry Olshansky

Re: DUnit - class MyTest { mixin TestMixin; void testMethod1() {} void testMethod2() {}}

2012-03-17 Thread Marc P. Michel

On Monday, 20 February 2012 at 01:49:04 UTC, Juan Manuel Cabo 
wrote:
I thought I could do a better effort to describe why DUnit is 
so extraordinary,
for a native language, especially for those unfamiliar with 
xUnit frameworks


This is great stuff, thanks !

Anyway, I'm not fond of your examples; so here is a silly one 
from me :


http://lanael.free.fr/summertest.d.html

Re: Pegged: Syntax Highlighting

2012-03-17 Thread Extrawurst


On 17.03.2012 08:01, Philippe Sigaud wrote:

On Wed, Mar 14, 2012 at 21:03, Andrej Mitrovic
andrej.mitrov...@gmail.com  wrote:


how would one use a parser like Pegged for syntax
highlighting?


Ok, typically one would use a lexer and not a parser. But using a
parser might be more interesting for creating more complex syntax
highlighting. :)



Actually I think I can use the new ddmd-clean port for just this
purpose. Sorry for the noise.


Sorry for the late reply, I was away for a few days, in a Net-forsaken place ;)

If ddmd-clean is OK for you, that's cool. Keep us informed how that went.
If you want to use Pegged, you'd need to enter the entire D grammar to
get a correct parse tree.
I just finished writing it, but I'm afraid to try and compile it :)
It's one huge monster.


I want to use Pegged for that purpose. So go ahead an commit the D 
grammar ;)

Would be so awesome if Pegged would be able to parse D.

~Extrawurst

Re: Pegged, From EBNF to PEG

2012-03-17 Thread Philippe Sigaud

On Sat, Mar 17, 2012 at 10:09, Dmitry Olshansky dmitry.o...@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.

Re: Pegged: Syntax Highlighting

2012-03-17 Thread Extrawurst


On 17.03.2012 15:13, Philippe Sigaud wrote:

The D grammar is a 1000-line / hundreds of rules monster. I finished
writing it and am now crushing bugs.


Any ETA when u gonna commit it for the public ? Wouldn't mind getting my 
hands dirty on it and looking for bugs too ;)

Re: Pegged, From EBNF to PEG

2012-03-17 Thread Dmitry Olshansky

On 17.03.2012 18:11, Philippe Sigaud wrote:

On Sat, Mar 17, 2012 at 10:09, Dmitry Olshanskydmitry.o...@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'd argue they do. As I see it as:
Expr - As B C D / B C D
As - A / A As
(or use an epsilon production for As, is it allowed in pegged ?)

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?

It does the second way that I haven't told about, and had hard time to
implement in C-T :)
And the simple version of what I presented (i.e. stack stuff) is used
in CT-regex and as fallback in R-T. The problem with doing a bitmap
memoization is that regex often used to _search_ things in large inputs.
Some compromise and/or thresholds have to be estimated and found.
Parsing on the contrary guaranties that the whole input is used or in
error, hence bitmap is not wasted.

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.

Well even straight no-memorization is somehow enough, it's just a way to
ensure no extra work is done. C Java are not much of backtracky grammars.

(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.

It's just I'm also well aware of how much luck it (still) takes to fly ;)
The asserts that compare C-T vs R-T go off too often for my taste, other
then this the memory usage during compile is too high.
I recall once dmd had GC re-enabled for brief period, dmd used no more
then ~64Mb doing real crazy ct-regex stuff.

OK, back to C-T parsing, I have one crazy idea that I can't get away
from - add operator precedence grammar into the mix. From what I observe
it should integrate into PEG smoothly. Then it would make
military-grade hybrid that uses operator precedence parsing of
expressions and the like. Few more tricks and it may beat some

existing parser generators.

See this post, where I tried to describe that idea early on:
http://www.digitalmars.com/webnews/newsgroups.php?art_group=digitalmars.Darticle_id=159562

I might catch spare time to go about adding it myself, the only tricky
thing is to embed plain semantic actions, as AST generation would be
more or less the same.

1 2 >

1 - 100 of 149 matches

Mail list logo