Compile Time D Expression Parser?
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
>> Well I'm missing something about that BNF-grammar(right?) but
>> 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.
> Hisayuki Mima
More information about the Digitalmars-d