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
