Replies: 2 comments
-
Hi, I don't think it can work that way. You have to let the parser loop but it must know when to stop. There have been proposals in the past on how to extend PEG parsing to support left recursion. For example: @article{medeiros2014,
title = {Left recursion in parsing expression grammars},
author = {Medeiros, S{\'e}rgio and Mascarenhas, Fabio and Ierusalimschy, Roberto},
journal = {Science of Computer Programming},
volume = {96},
pages = {177--190},
year = {2014},
publisher = {Elsevier}
}
@report{tratt2010,
title = {{D}irect left-recursive parsing expression grammars},
author = {Tratt, Laurence},
year = {2010},
institution = {Tech. Rep. EIS-10-01, School of Engineering and Information Sciences, Middlesex University (October 2010)},
keywords = {parsing, peg, leftrecursion}
}
@conference{warth2008,
title = {{Packrat parsers can support left recursion}},
author = {Warth, A. and Douglass, J.R. and Millstein, T.},
year = {2008},
booktitle = {Proceedings of the 2008 ACM SIGPLAN symposium on Partial evaluation and semantics-based program manipulation},
organization = {ACM},
pages = {103–110},
keywords = {packrat, parsing, peg, fundinf2010, leftrecursion}
} In general, I think that the simple recursive-descent parsing approach of PEG is its great strength and implementing left recursion would lose great deal of that simplicity. Some parsing approaches handle left recursion naturally (e.g. parglare can handle it without problem). |
Beta Was this translation helpful? Give feedback.
-
Ah, I saw your edit after posting the reply. Yes, it is not that easy :) |
Beta Was this translation helpful? Give feedback.
-
Hi and thank you for this great project!
After using it for a while the only thing that I miss is the ability to use left recursive rules without having to transform them into right recursive ones.
The change I suggest is that instead of looping on a rule, if we are trying to match rule A and we have not consumed any input yet and we stumble on a match with A we backtrack immediately instead of looping. This should resolve the majority of ugly cases at a minimal cost, and it may be added only under a flag.
What do you think?
Edit: I actually realized that one has to consider the whole "rule stack" to detect the loop, so it may be more difficult than I initially realized.
Beta Was this translation helpful? Give feedback.
All reactions