Thank you very much. To clarify: I am not in need of a parser, I just wanted to understand why left recursion is an issue (that was easy) and what techniques help to circumvent the problem. So your answer was spot-on (though I haven't implemented it yet) On Wednesday, 20. February 2013 09:59:47 Tillmann Rendel wrote:
Hi,
Martin Drautzburg wrote:
As an exercise I am writing a parser roughly following the expamples in Graham Hutton's book. The language contains things like:
data Exp = Lit Int -- literal integer
| Plus Exp Exp
So the grammar is:
Exp ::= Int
| Exp "+" Exp
My naive parser enters an infinite recursion, when I try to parse "1+2". I do understand why:
"hmm, this expression could be a plus, but then it must start with an expression, lets check".
and it tries to parse expression again and again considers Plus.
Indeed.
Twan van Laarhoven told me that:
Left-recursion is always a problem for recursive-descend parsers.
Note that the left recursion is already visible in the grammar above, no need to convert to parser combinators. The problem is that the nonterminal Exp occurs at the left of a rule for itself.
One way to fix this problem is to refactor the grammar in order to avoid left recursion. So let's distinguish "expressions that can start with expressions" and "expressions that cannot start with expressions":
Exp-norec ::= Int Exp-rec ::= Exp-norec
| Exp-norec "+" Exp-rec
Note that Exp-rec describes a list of Exp-norec with "+" in-between, so you can implement it with the combinator many.
Now if you want to add a rule like
Exp ::= "(" Exp ")"
you need to figure out whether to add it to Exp-norec or Exp-rec. Since the new rule is not left recursive, you can add it to Exp-norec:
Exp-norec ::= Int
| "(" Exp-rec ")"
Exp-rec ::= Exp-norec
| Exp-norec "+" Exp-rec
If you implement this grammar with parser combinators, you should be able to parse "(1+2)+3" just fine.
Tillmann
PS. Try adding multiplication to your grammar. You will need a similar trick to get the priorities right.
-- Martin