Hello, 2009/5/19 leledumbo <leledumbo_c...@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 _______________________________________________ Haskell-Cafe mailing list Haskell-Cafe@haskell.org http://www.haskell.org/mailman/listinfo/haskell-cafe