[Haskell-cafe] Expression parsing problem

[Loup Vaillant]

Hello,

2009/5/19 leledumbo <leledumbo_cool at yahoo.co.id>:
>> expression ::= term | term "+" expression
>> term ::= factor | factor "*" term
>> factor ::= constant | variable | "(" expression ")"
>
> Oh, left recursion. Well, it should be easy to transform:
>
> expression ::= term | moreTerm
> term ::= factor | moreFactor
> moreTerm ::= term "+" expression
> factor ::= constant | variable | "(" expression ")"
> moreFactor := factor "*" term
>
> correct?

I think not. See for instance:

> expression ::= term | moreTerm
> moreTerm ::= term "+" expression

An expression begins by a term or a moreTerm… which itself begins by a
term. You still have the left recursion problem, I think.

What you mean was probably that:

expression ::= term moreTerm
term ::= factor moreFactor
factor ::= constant | variable | "(" expression ")"
moreTerm ::= "+" expression | nothing
moreFactor ::= "*" expression | nothing
nothing ::=

Unfortunately, if this work (I'm not entirely sure), it is right
associative. Example of parsing left associative operators can be
found on the net, however.

Finally, I strongly suggest you to take a look at the Parsec library
[1] (unless you can't?). It provide a "buildExpressionParser" function
which takes care of associativity and precedence for you.

[1] http://legacy.cs.uu.nl/daan/download/parsec/parsec.html