How to solve expressions using a parse tree?

Question

Hi I have been taking some basic tutorials of parsing, I have been able to understand the basics of CFG and parse tree.

Take following grammar for basic equations:

term
  : INTEGER
  | '(' expression ')'
  ;

mult
  : term ('*' term)*
  ;

add
  : mult ('+' mult)*
  ;

expression
  : add
  ;

What I would like to know is that how does it help us solve the equation? All of the tutorials end by making a parse tree or by writing a parser like a predictive parser, but all parser checkes is that if that expression is valid acc to grammar but it does not evaluate it.

Can anyone help me with that?

yes so How can we solve the equation with the help of parsing? — Max, Aug 13 '12 at 20:42
why a -1? it is a valid question I think, just because I dont know it does not mean that I am wasting your time... — Max, Aug 13 '12 at 20:44
A parser decides membership in the languages defined by the associated CFG. You can augment your parser routines (if it is recursive descent) to push/pop values on a stack; the result is on the top of the stack once the parsing (and execution) terminates. — mrk, Aug 13 '12 at 20:45
Well, a parser can provide an assertion that an equation is valid. Once validity is determined, you can execute the equation by sending it to some function that can evaluate it, possibly converting the equation to postfix first. — Chris Dargis, Aug 13 '12 at 20:45
Parsers won't help much with solving equations as that's more of a math than coding problem. Are you sure you aren't confusing expression evaluation with equation solving? Those are very different things and the former is more or less straightforward once you have the expression parsed into a tree. — Alexey Frunze, Aug 13 '12 at 20:47
lets say I want to solve 2*4+5*9 sort of equation, it will produce some parse tree and the in order of it will give the answer but is not there any direct way of getting the answer? just by defining the grammar and giving the input? — Max, Aug 13 '12 at 20:49
`2*4+5*9` is not an equation. There's nothing being equated to anything else in it. It's an expression. There's a nice [Lex & Yacc Tutorial by Tom Niemann](http://epaperpress.com/lexandyacc/) with sample code that implements a simple expression calculator (both, an interpreter and a compiler). You can find it useful. — Alexey Frunze, Aug 13 '12 at 20:55
A simple expression evaluator can be found here: http://stackoverflow.com/questions/1931307/antlr-is-there-a-simple-example — Bart Kiers, Aug 13 '12 at 21:00
You get an equation by adding variables as terminals, and an "=" operator (or any other constraint predicates you may like). This is a pretty easy extension. Such equations are not so easily "evaluated"; now you need algebra ("equivalence rules"), hence my answer to OP. — Ira Baxter, Aug 13 '12 at 21:08

How to solve expressions using a parse tree?

0 Answers0