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.