For another approach: http://norswap.com/pubs/sle2015.pdf
It's a bit hard to say if the semantics are different from the succint description, but I don't expect them to be. Nicolas LAURENT On 14 May 2017 at 06:57, Juancarlo Añez <apal...@gmail.com> wrote: > Hello Urik, > > I was wondering what the semantics of your PEG+leftrec implementation is, >> and whether it matches that of the paper by Medeiros, Mascarenhas & >> Ierusalimschy (https://arxiv.org/abs/1207.0443)? In that paper, they >> extend the operational semantics of PEG with left recursion by iteratively >> increasing bounds on the recursion depth of left recursive rules until a >> match is found. >> > > As I understood it, the depth is increased only up to the number of > options in the main recursive choice. > > >> I found it hard to wrap my head around that definition, and it didn't >> seem very natural to me, >> > > They went through the great effort of proving that the semantics resulting > from the changes were sound. It's a tough read. > > >> so I was wondering if you have a simpler, or at least different, approach? >> > > > > I sketched the algorithm implemented in TatSu a few messages back. This is > an explanation that is closer to the implementation. > > 1. Allow the input sequence to be marked with a non-terminal at any > position. > 2. Any mention of a left recursive non-terminal *R *on the right hand > side of a production matches only if the next input position is marked with > *R*. > 3. Parse the *RHS* of a rule as usual. > 4. If the parsed rule *R* is left-recursive and a parse succeeds, mark > the input position with symbol *R* and try to parse *R* again, > repeating until the parse fails. > > To recover the left-associative trees, mark the input positions with *(R, > T)* where *T* is the tree. > > -- > Juancarlo *Añez* > > _______________________________________________ > PEG mailing list > PEG@lists.csail.mit.edu > https://lists.csail.mit.edu/mailman/listinfo/peg > >
_______________________________________________ PEG mailing list PEG@lists.csail.mit.edu https://lists.csail.mit.edu/mailman/listinfo/peg
