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