On Mon, May 8, 2017 at 1:16 PM, Ger Hobbelt <g...@hobbelt.com> wrote:
> Just wondering: isn't this the same approach as that described in > https://arxiv.org/abs/1207.0443, if you leave out their associativity > handling? (AFAIR) > It's not the same. The approach in medeiros is to bind left recursion by adding book-keeping to the options in a choice operator. From the paper: 3. Bounded Left Recursion Intuitively, bounded left recursion is a use of a non-terminal where we limit the number of left-recursive uses it may have. I haven't seen the approach implemented in TatSu mentioned anywhere in relation to PEG, but I think it is similar to some of the ones used with pushdown automata (sorry; I know that pushing non-terminals onto the front of the input stream is an old idea, but I can't remember the source). This is the TatSu algorithm, explained briefly: 1. Expand the set of terminals to include the set of non-terminals (E'= E U N). 2. Any mention of a left recursive non-terminal *R *on the right hand side of a production matches only if *R* is the next input symbol. 3. Parse the *RHS* of a rule as usual. 4. If the parsed rule *R* is left-recursive and a parse succeeds, push the symbol *R* onto the front of the input stream (so it's the first/next symbol) and try to parse *R* again, repeating until the parse fails. When there's a fail pop an *R* symbol from the front of the input, and proceed. In TatSu, the non-terminals are augmented to include the pairs of non-terminals and trees (E'= E U NxTree) so the correct parse trees can be returned. Met vriendelijke groeten -- Juancarlo *Añez*
_______________________________________________ PEG mailing list PEG@lists.csail.mit.edu https://lists.csail.mit.edu/mailman/listinfo/peg
