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 searc开发者_如何学Goh 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>

---

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

---

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...)

---

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)))