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 _______________________________________________ Haskell-Cafe mailing list Haskell-Cafe@haskell.org http://www.haskell.org/mailman/listinfo/haskell-cafe