Hi, That sounds like how I implemented left recursion for PEGs in Katahdin (http://www.chrisseaton.com/katahdin/, check page 35 of the thesis).
I described it as being bottom-up recursive calls to the rule parsing procedure. Chris Seaton On 9/2/07, Jeremy Bruestle <[EMAIL PROTECTED]> wrote: > I seem to have run across a very simple way to add support for left > recursion in PEGS. It looks like it works to me in all cases, but > perhaps I'm missing somthing. Without further ado... > > Presume we have your standard memorizing peg parser. In psudo-code it > might look like: > > // Lookup memorized result, or do actual parsing > // return -1 on failure, length of match on success > int check_parse(rule, position) > key = tuple(rule, postion); > if find(memory[key]) > return memory[key]; > else > memory[key] = do_pase(rule, position); > return memory[key]; > end > end > > // Do actual work, to parse sub-components, call check_parse > // Return result in same format as above > int do_parse(rule, position); // Actual code would be here > > Now if we have any left recursion in our rules, we go into an infinite > recursion. > > We can fix the infinite recursion, although not cause our left hand > rules to actually work by just setting the memory to failure when we > realize this is our first time trying a rule, but before we call > do_parse. that is: > ... > else > memory[key] = -1; > memory[key] = do_pase(rule, position); > return memory[key]; > end > ... > > Of course this just effectively makes the left recursive rules > worthless. However if change check_parse to be: > > int check_parse(rule, position) > key = tuple(rule, postion); > if find(memory[key]) > return memory[key]; > else > cur = -1; > do > memory[key] = cur; > prev = cur; > cur = do_pase(rule, position); > while(cur != -1 && cur != prev) > end > end > > We now cause the first parse to pick out only non-recursive rules, > then we try again with out current 'match' for the recursive > nonterminal at the position in question. So long as it keeps working > we keep expanding at the same location. Once we have expanded as much > as we can, we stop and return. If we ever try to parse that same > location for the same terminal type, we just return the memorized > version as usual. This of course presumes that our recursive rules > come before our non-recursive one for a given type. > > Anyway, it seems to work, just curious on people's thoughts. > > -Jeremy > > _______________________________________________ > 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
