Hi Chris, I'm having trouble understanding the following > pseudo-code line from Figure 4 on page 5 of your PDF: > > if lr.detected and ans =/= FAIL > > I'm missing where lr.detected ever gets set to TRUE. >
... > I do see an assignment in the else clause (when m was found in memo table) > > if m.ans is LR > then m.ans.detected <- TRUE > > but lr.detected is being tested in the not-yet-memoized case. > > Can anyone lead me into the light? > The first time you apply rule R at position P, there won't be a result in the memo table (m will be nil). The first thing we do in this case is memoize an LR with detected = false (note that this LR is also stored in the local variable lr); then we evaluate the body of the rule to get a result. (Here's what I think you missed.) If R is left-recursive, then evaluating its body will make the parser do another Apply-Rule(R, P) -- with the same R and P as before. This time around, m won't be nil; it will instead be a MemoEntry whose ans field holds the LR we memoized above. So we set that LR's detected = true, and return a Fail so that the seed parse can be computed. Now we're back to the original call to ApplyRule, where we'll look at lr's detected field to figure out whether to just return the non-left-recursive result, or grow the seed parse (the latter, in this example). I hope this helps. Cheers, Alex > > Thank you, > Chris Bratlien > > Alessandro Warth wrote: > > Hello, > > Our paper, "Packrat Parsers Can Support Left Recursion", is finally > ready > > for public consumption. :) Those of you who are interested can download > it > > from the VPRI writings page, http://www.vpri.org/html/writings.htm > > Cheers, > > Alex > > > > On Sep 20, 2007 8:31 AM, Claudio Campos <[EMAIL PROTECTED]> > > wrote: > > > >> VPRI Folks, > >> > >> Are there any version or update of OMeta (Meta for Squeak) that support > >> left > >> recursion (as describe in paper: "pakrat parser can support left > >> recursion" > >> with memoization table) > >> > >> Thanks, > >> > >> Claudio Campos > >> Santa Fe, Argentina > >> > >> > >> _______________________________________________ > >> fonc mailing list > >> [email protected] > >> http://vpri.org/mailman/listinfo/fonc > >> > > > > > > ------------------------------------------------------------------------ > > > > _______________________________________________ > > fonc mailing list > > [email protected] > > http://vpri.org/mailman/listinfo/fonc > > > > > > ------------------------------------------------------------------------ > > > > No virus found in this incoming message. > > Checked by AVG Free Edition. > > Version: 7.5.503 / Virus Database: 269.16.9/1155 - Release Date: > 11/27/2007 8:30 PM > > > _______________________________________________ > fonc mailing list > [email protected] > http://vpri.org/mailman/listinfo/fonc >
_______________________________________________ fonc mailing list [email protected] http://vpri.org/mailman/listinfo/fonc
