Compile Time D Expression Parser?

Hisayuki Mima youxkei at gmail.com
Mon Feb 27 21:19:32 PST 2012


(2012/02/28 2:22), Dmitry Olshansky wrote:
> OK, does it check for Left recursive grammars?

No, it doesn't.
So currently left recursive grammar causes infinite loop.
I know the way to deal with the left recursive grammar well which is 
using memoization, but memoization causes very bad performance.

> Well I'm missing something about that BNF-grammar(right?) but undoubtedly:
> recursive -> A $ -> a A a $ -> a a A a a $ - > a a a a a $
> As for task of parsing only 2^n-1 sequences of "a" by CFG that's news
> for me.

If it is BNF, the expansion you said (recursive -> A $ -> a A a $ -> a a 
A a a $ - > a a a a a $) is right.
But the DSL which ctpg uses to generate parser is based on PEG.
Unlike BNF's choice operator "|", PEG's choice operator "/" is ordered.
For details, see: 
http://en.wikipedia.org/wiki/Parsing_expression_grammar#Definition .

Thanks,
Hisayuki Mima


More information about the Digitalmars-d mailing list