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
