Hello,
2009/5/19 leledumbo
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