CODEWITHSUNDEEP
parsingmathtree
sid
sid

Reputation: 1

Deriving an arithmetic expression?

How would you derive this expression? I need to draw a parse tree for this, but having real trouble deriving this. A google search didn't give any useful links either, any help would be much appreciated, but please do give a brief explanation of how you did it as I have few others to do myself. Does the "|" stand for an "or" operator just like in programming?

< exp> ---> < exp> * < factor> | < factor>
< factor> ---> < factor> - < term> | < term>
< term> ---> x | y | z

This is the best I could come up with and I am fully lost ..

< exp> ---> < exp> * < factor>
---> x * < factor>
---> x * < factor> * < factor>

Upvotes: 0

Views: 300

Answers (3)

btilly
btilly

Reputation: 46408

Yes, the | is or, just like in regular programming. A line like:

< exp> ---> < exp> * < factor> | < factor>

means that something can be an < exp> if it is a of the form < exp> * < factor> or if it is a < factor>.

Looking at your full grammar:

< exp>    ---> < exp> * < factor> | < factor>
< factor> ---> < factor> - < term> | < term>
< term>   ---> x | y | z

an expression like x - y * x - y - y * z could be built up in passes as follows:

x        y        x          y        y        z
<term> - <term> * <term>   - <term> - <term> * <term>
<factor>        * <factor> - <term> - <term> * <factor>
<factor>        * <factor>          - <term> * <factor>
<expr>          * <factor>                   * <factor>
<expr>                                       * <factor>
<expr>

Reverse the order to get the parse:

          e
         /|\
        / | \
       e  *  f
      /|\     \
     / | \     t
    /  |  \     \
   /   |   \     z
  e    *    f
  |        /|\
  f       / | \
 /|\     f  -  t
f - t   /|\    |
|   |  f - t   y
t   y  |   |
|      t   y
x      |
       x

(That diagram took more work to draw than I was expecting...)

Upvotes: 1

Samsdram
Samsdram

Reputation: 1635

To answer your question the | is used to denote an or like in programming. The grammar you posted though looks like its precedence is off. Usually multiplication has a higher precedence than addition, but the grammar you have posted has the reverse, that might be part of your problem.

The usual way to right an expression grammar (for the limited set of operations in your example) is 

expression = expression+ term 
           | term
term       = term * factor
           | factor
factor     = x 
           | y 
           | z

This way you do the multiplications before the additions. For x+y*z you would have the following. I don't do ASCII art so you'll have to settle for S-expressions with operators instead of commas as delimiters.

(Expression (Expression(Term (Factor x)))'+' (Term (Factor y) '*' (Factor z)))

Upvotes: 0

Xodarap
Xodarap

Reputation: 11849

It's a context-free grammar. The section on "Algebraic expressions" contains a sample parse tree similar to what you want.

Upvotes: 1

Related Questions