tags:

views:

28

answers:

2

If you have grammar like this:

<assign> → <id> = <expr> 
<id> → A | B | C 
<expr> → <expr> + <term> 
         |  <term> 
<term> → <term> * <factor> 
         |  <factor> 
<factor> → ( <expr> ) 
          | <id>

And then the sentence A = B + C * A, you get this leftmost derivation:

<assign> => <id> = <expr> 
         => A = <expr> 
         => A = <expr> + <term> 
         => A = <term> + <term> 
         => A = <factor> + <term> 
         => A = <id> + <term> 
         => A = B + <term> 
         => A = B + <term> * <factor> 
         => A = B + <factor> * <factor> 
         => A = B + <id> * <factor> 
         => A = B + C * <factor> 
         => A = B + C * <id> 
         => A = B + C * A

But what about A = B + ( C * A )?

A: 

( C * A ) doesn't need a paren, because * has greater priority. One case where you'd see it is in A = B * ( C + B ).

You don't see it in the last two lines because <factor> is going to eval to be either a <term> + <term> or an <id>. In this case there's no + so it has to be an <id>.

Chuck Vose
I can't find a flaw in James' code so I must be wrong
Chuck Vose
+2  A: 

A = B + ( C * A )?

First five steps, same as above, then...

     => A = B + <term>  
     => A = B + <factor>    
     => A = B + ( <expr>) 
     => A = B + ( <term> )  
     => A = B + ( <term> * <factor> ) 
     => A = B + ( <factor> * <factor> ) 
     => A = B + ( <id> * <id> ) 
     => A = B + (  C   *   A  )
James Curran
Nominally you collapse two steps into one with the penultimate rule, but the result is clear enough.
Jonathan Leffler