Can you go into more detail about left recursion in the REG^REG parser? What specifically is meant by the lexicographically smallest derivation? That is, on what do you base the ordering of derivations? Are you imposing an ordering on terminals, or are you inducing the ordering from PEG productions? Is there a case where the total ordering of a PEG removes ambiguity between two possible derivations (e.g. A -> a B / a b; B -> b), but where the lexicographic ordering as mentioned in the paper chooses "A -> a b" instead of "A -> a B"?
Best Regards, Peter Goodman, http://www.petergoodman.me 65 High Park Ave., Toronto, Ontario M6P 2R7 On Tue, May 15, 2012 at 3:40 PM, Peter Goodman <peter.good...@gmail.com>wrote: > Interesting, the approach reminds me of Mark Johnson's memoization in > top-down parsing, and I see that it was cited. > > On the subject of left recursion, the "desired" (assuming one desires left > associativity) might be achieved using multiple levels of seed growing. I > had some success with this, but ultimately my implementation was flawed in > one way or another (null pointer dereference in some old code). > > If one maintains a chain of seed points (places where at least one layer > of left recursion was successfully expanded), then left associativity can > be achieved by cascading along that chain. This is akin to a form of > backtracking. > > For example, consider a rule such as S -> S "+" S / F. For the purpose of > disambiguation, S -> S_1 "+" S_2 / F, where S_1 and S_2 are just different > names for the same thing. Then both S_1 and S_2 can be left recursive > seeds. > > For "F + F + F + F", S_1 can be identified as a left recursive seed, the > rule "S_1 + S_2" temporarily skipped, and then F matched. Then we "grow" > the seed, as with Tratt's method, match the first production, consume the > "+", and go to match S_2. On recognizing S_2 as left-recursive, I propose > that a chain be made between S_1's seed and S_2's seed. Before growing the > S_2 seed, we first attempt to re-grow S_1's seed. If we fail to grow S_1's > seed, then we go to the next link in the chain--S_2--and try to grow its > seed. If we succeed at growing any link in the chain, then we disconnect > all further links in the chain. E.g. if we succeed to re-grow S_1 in the > context of S_2, then disconnect S_2, only to re-discover it later. > > Best Regards, > > Peter Goodman, > http://www.petergoodman.me > 65 High Park Ave., > Toronto, Ontario > M6P 2R7 > > > > On Tue, May 15, 2012 at 12:56 PM, Ondřej Bílka <nel...@seznam.cz> wrote: > >> Hello >> >> I generalized packrat parsing algorithm to algoritm that runs in linear >> time and under natural conditions is equivalent to fully backtracking >> parser. >> >> I devise more flexible formalism REG^REG of relativized regular >> expressions. >> >> >> A preprint to submitted paper is available here: >> http://arxiv.org/abs/1205.1877 >> >> -- >> >> temporary routing anomaly >> >> _______________________________________________ >> 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
