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.