CSE 428 : Solution of Assignment #1

Question 1

1.  (x+2)*y
   
   
           expression
               |
               |
              term
             /   |   \
          term   * factor
            |         |
          factor   identifier
        /    |   \     |
       (expression)    y
         /    |    \
   expression +   term
       |            |
      term        factor
       |            |
     factor       literal
       |            |
    identifier      2
       |
       x
   
   
   

2.  2*x+3/y-4
   
                            expression
                            /     |   \
                       expression -   term
                        /   |   \         | 
               expression   +   term     factor
              /                /  |  \      |
           term              term / factor identifier
        /    |   \             |       |         |                
     term    *  factor      factor  identifier   4
       |           |           |       |
    factor     identifier   literal    y
       |            |          | 
    literal         x          3
       |            
       2   
                  
   

3.  1
          expression
               |
              term
               |  
             factor
               |       
            literal
               |
               1
   
   

Question 2

1.   S::=S1S2
     S1::=lambda|aS1b
     S2::=lambda|bS2a
   

2.   
     S::=S1S1S1S1S1S2
     S1::=a|b
     S2::=lambda|aS2|bS2
   

Question 3

1. For the string false and true and false there are two different derivation tree:

   
   
                             expression
                            /     |   \
                           exp   and  exp  
                         /  |  \       | 
                      exp  and exp   false
                       |         |
                     false      true
   
                            
   
                             expression
                            /     |   \
                           exp   and  exp  
                            |        /  |  \        
                          false    exp and exp   
                                   |         |
                                  true     false
   
   

2.      A::=B imp A| B
        B::=B and C| C
        C::=not C| D
        D::=true|false
   

Question 4

1. For word int * name[Number], there are two different derivation tree:

   
                            Declaration
                            /        \
                           Type     Declarator 
                            |      /       /  |  \        
                           int Declarator [ Number] 
                               /       \      
                              *    Declarator
                                        | 
                                      name  
   
   
                            Declaration
                            /      /     \
                           Type   *   Declarator 
                            |         /       /  |  \        
                           int    Declarator [ Number] 
                                     | 
                                    name  
   
   
   
   

2.      Declaration::= Type Declarator
        Type       ::= int|char
        Declarator ::= * Declarator|Dec
        Dec        ::= Dec '['number']'| Dec '('Type')' | '('Declarator')' | name
   
   

3. The grammar would be unambiguous because all the operators would, in the case of Declarator *, are all postfix. So in the start of the string there is name, and then, depending on the sequence of the operators, the left most operator is introduced last in the tree.

   For instance:

              int name *'['number']' '('int')' * '('char')'
   
   
                              Declaration
                               /       \
                             Type       Declarator
                               |       /      / |\
                              int Declarator (Type)
                                  /      \         
                            Declarator    *    
                           /  /   |   \
                  Declarator (  Type   )
                 /  /   | \       |
        Declarator [ number]     int 
         /       \
      Declarator  *
          |
         name
   
    

   All declarators are to the left of the tree except the first one. This is the only derivation tree of the expression.