[My thanks to David Hazell for pointing me at this thread] Dominic Cooney wrote:
> I think I've found a problem with the algorithm for left-recursive rules in > Warth, Douglass and Millstein's PEPM 2008 paper. If this is old news, > sorry. I don't know if this is a fundamental problem with a Warth-like solution, or just the fact that it uses memoisation. I came up with a 'pure PEG' version of Warth's left-recursive algorithm which doesn't use memoisation and it parses your inputs correctly. That said, in my opinion, some other left-recursive PEGs do give surprising results using Warth's left-recursive algorithm. I note here that the "in my opinion" really is just that - Alex, for example, doesn't agree with my analysis (and I respect his reasons for doing so), though he did kindly answer some questions I had a while back. The basic problem I noted is that rules which are both left-recursive and right-recursive give parses which I wouldn't have expected. I tried to narrow down both the problem and also possible solutions (both in restricting the set of input grammars; and in providing an alternative algorithm). This proved rather trickier than I had first expected, and therefore I wouldn't put money on my solutions being perfect. Since publishing papers takes an age, and there is interest on the list, I'll throw caution to the wind and point you at a draft of the relevant paper which you may, or may not, find interesting: http://tratt.net/laurie/research/publications/papers/tratt__direct_left_recursive_parsing_expression_grammars.pdf There is also a link in the paper to code against which you can test left-recursive PEGs, if you wish. If anyone has any comments, suggestions, or questions, please feel free to ask further on the list or to my personal e-mail address. Laurie -- http://tratt.net/laurie/ -- Personal http://fetegeo.org/ -- Free text geocoding http://convergepl.org/ -- The Converge programming language http://www.model-transformation.org/ICMT2010/ -- ICMT 2010 _______________________________________________ PEG mailing list PEG@lists.csail.mit.edu https://lists.csail.mit.edu/mailman/listinfo/peg
