Repository navigation
RFC: Automagical left recursion elimination #5
Description
Sometimes, it would be very convenient to implement a parser using left recursion, like in this example:
number = digit.at_least(1).map(''.join).map(int)
@generate
def expr():
lhs = yield expr
op = yield string('+') | string('-')
rhs = yield number
if op == '+':
return lhs + rhs
else:
return lhs - rhs
expr |= numberNote that this cannot be easily rewritten to use number +/- expr, because we need to parse 1 - 2 - 3 as (1 - 2) - 3 and not 1 - (2 - 3).
This currently doesn't work because calling expr inside of expr causes infinite recursion. The proper way to implement this is to unwrap the recursion manually, i.e. to use an explicit loop that consumes and adds/subtracts a sequence of numbers. However, this is much less convenient than implementing 'the mental model' directly.
This RFC proposes for parsy to be able to do such a transformation automatically.
A proof-of-concept (barely readable) implementation is here, and here's an explanation in pseudocode (that skips over many small details):
recursion_detected = False
parser_is_running = False
saved_result = None
def invoke_parser():
global parser_is_running, recursion_detected, saved_result
if not parser_is_running:
# we are the first invocation of this parser at this index
parser_is_running = True
res = normal_logic()
else:
# we are the second left-recursive invocation
recursion_detected = True
return saved_result or fail('recursion detected')
# we are the first invocation again
if not recursion_detected or res.is_fail():
parser_is_running = False # and other cleanup
return res
while True:
saved_result = res
res = normal_logic()
if res.is_fail():
parser_is_running = False # and other cleanup
return saved_resultThis works as if the recursion magically failed at just the right depth, giving the alternative sub-parsers (number in the example above) a chance to try their logic.
Unresolved questions:
- Should this be implemented for every parser, or should this be an explicit wrapper? If latter, do we call it
parsy.recursion_catcher(),Parser.left_recursive()or what? - Does this work for cases that are more complex than a simple left recursion in one of the parsers?
- How do we make it thread- (and multiple independent invocation-) safe?
Activity
spookylukey commentedon Sep 28, 2017
I currently don't understand either the problem or your solution well enough to be able to give feedback on this. The questions around the implementation, plus the use of mutability etc. make me think this is not a great idea, at least for a default. Also, it would be good to know what other similar projects do for this case.
spookylukey commentedon Oct 2, 2017
Thinking a little bit more:
I suspect the underlying issue here is that you are doing parsing and evaluating in one step. I think for these situations (i.e. where you have some precedence rules that you need to apply), then you should be using parsy to lex the string into tokens, and then run a separate parser and evaluator that consumes the tokens. Something like this might help. http://effbot.org/zone/simple-top-down-parsing.htm
It feels like parsy is the wrong place to be building the logic to cope with these kind of issues.
bugaevc commentedon Oct 2, 2017
Agreed. A proper implementation that I hope to write soon should be way more understandable, and I have an idea about how to mitigate the problem of mutability.
The problem is that it isn't convenient to parse left-recursive grammars using parsy. The most common case of left recursion (and the one shown in the example above) is parsing left-associative operator chains. Parsec implements a different, perhaps less magical, solution in the form of:
Now, I have a hard time parsing that, but IIUC it works like this, in parsy-like syntax:
This may be a bit more difficult to comprehend (higher-order functions and stuff) and it only works for that simple case; still I think it's a brilliant solution and we should implement that.
My "magical" solution is more generic and easier to use, but harder to reason about. Perhaps we can have both, the magical one being an explicit wrapper for "advanced" use-cases.
I don't think that's the problem. Right now, parsy is a great framework for creating lexers; it was possible to create parsers with it before, too. In fact, I was thinking we'd build a more robust and high-level infrastructure for these things, similar to
code from the article you've linked, and left recursion elimination (in one form or another) is the first step to that. Ideally, I'd imagine something like:
spookylukey commentedon Oct 3, 2017
@bugaevc Thanks for your explanation. I've done a bit more Googling and understand the issue with left-recursive grammars better now. I found the same solution as you did.
I also found, as I think you were implying, that there are some situations it doesn't work for e.g. for postfix left recursion, also with some solutions - https://www.reddit.com/r/haskelltil/comments/3ocukk/a_function_postfixchain_to_parse_a_left_recursive/ and http://www.joelwilliamson.ca/programming/parsing/haskell/2015/02/04/Parsec-Left-Recursion.html
I think the best approach at the moment is to implement something like
chainl1(with a better name!), possibly something for the postfix case, and have some cookbook style docs on left recursive grammars. If you wanted to contribute a version of your automagical implementation, we could add it as an explicit wrapper as you suggest, and mark it as experimental (I've haven't yet had the chance to get into the implementation, and I don't want to commit to maintaining something I don't understand!)A further step would be adding the higher level constructs you talk about, which I'm definitely open to, if they are generic enough.
douglas-raillard-arm commentedon May 13, 2022
Dropping it here in case someone encounters the same issue:
EDIT: removed custom
const()and replaced by parsy'ssuccess()