Compile Time D Expression Parser?

Dmitry Olshansky dmitry.olsh at gmail.com
Tue Feb 28 00:52:19 PST 2012


On 28.02.2012 9:19, Hisayuki Mima wrote:
> (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.
>

I haven't thought that was PEG, as these grammars are harder to rewrite 
automatically.

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

Ordered is fine, but it still means that once first alternative fails 
(in this case when we finally hit the end of input) engine has to 
backtrack(!) then try second, then 3rd etc. More then that, if all of 
this fails it has to "backtrack" through all choices made on the way and 
pick other alternatives.

This backtracking is what packrat parser optimizes via memoization. By 
the way this is what makes doing semantic actions problematic in packrat 
parsing as they have to be 'reverted' once it backtracks.


> Thanks,
> Hisayuki Mima


-- 
Dmitry Olshansky


More information about the Digitalmars-d mailing list