[Haskell-cafe] Expression parsing problem
Loup Vaillant
loup.vaillant at gmail.com
Tue May 19 08:23:11 EDT 2009
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
More information about the Haskell-Cafe
mailing list