[Haskell-cafe] Parser left recursion

[Tillmann Rendel]

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.