On Tue, May 15, 2012 at 04:02:40PM -0400, Peter Goodman wrote: > 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,
A way how backtracking parser tries alternatives forms lexicographic ordering. For example for expression (a/b (e/f)) (c/d) a c 1 1 a d 1 2 b e c 2 1 1 b e d 2 1 2 b f c 2 2 1 b f d 2 2 2 > > Peter Goodman, > [1]http://www.petergoodman.me > 65 High Park Ave., > Toronto, Ontario > M6P 2R7 > > On Tue, May 15, 2012 at 3:40 PM, Peter Goodman > <[2]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, > [3]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 <[4]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: > [5]http://arxiv.org/abs/1205.1877 > -- > > temporary routing anomaly > > _______________________________________________ > PEG mailing list > [6]PEG@lists.csail.mit.edu > [7]https://lists.csail.mit.edu/mailman/listinfo/peg > > References > > Visible links > 1. http://www.petergoodman.me/ > 2. mailto:peter.good...@gmail.com > 3. http://www.petergoodman.me/ > 4. mailto:nel...@seznam.cz > 5. http://arxiv.org/abs/1205.1877 > 6. mailto:PEG@lists.csail.mit.edu > 7. https://lists.csail.mit.edu/mailman/listinfo/peg -- Your packets were eaten by the terminator _______________________________________________ PEG mailing list PEG@lists.csail.mit.edu https://lists.csail.mit.edu/mailman/listinfo/peg
