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
