CSE 428 : Solution of Assignment #1

Question 1

1.  
      S ::= lambda | aSa | bSb
      

2.  
      S ::= AB
      A ::= lambda | aAb
      B ::= lambda | bSa
      

3.  
      S ::= AAAAAB
      A ::= a | b
      B ::= lambda | aB | bB
      

Question 2

• a) This grammar is ambiguous. One example is int * name [number] ;

      
                Declaration   _                  Declaration  _ 
                  /    \        \                /       \      \  
               Type   Declarator ;            Type    Declarator ; 
               /       |   \                 /       /   |   |  \ 
            int        *  Declarator      int Declarator [ number ] 
                          /   |  |   \           /   \ 
                   Declarator [ number ]        *  Declarator 
                       |                               | 
                     name                             name 
  

• b)

      Declaration ::= Type Declarator ; 
             Type ::= int | char 
       Declarator ::= * Declarator | Decl  
             Decl ::= Decl '[' number ']' 
                    | Decl '(' Type ')' 
                    | '(' Declarator ')' 
                    | name 
  

• c) The former grammar introduces ambiguity due to lacking precedence of operators. However, when we change * to be a postfix operator, all operators in the grammar become postfix ones. In general, If we have only postfix operator, say op1 and op2, then the strings will be of the form name followed by a sequence of op1 and op2, and we can always infer the structure of the tree: the first operators (from left to right) must have been introduced later in the tree.

Question 3

1. There are various ambiguities, due to
   • lack of rules for associativity of "and" and ->
   • lack of a rule of precedence between -> and "and"
   • lack of a rule of precedence between -> and "not"
   • lack of a rule of precedence between "and" and "not"
   An example of the last kind of ambiguity is the following:

             BExp                  BExp
           /  |  \                /   |  
       BExp  and  BExp         not   BExp
       /  |        |               /  |  \ 
     not BExp    false         BExp  and  BExp
          |                      |         |
        false                  false     false    
   
   

2.    BExp  ::= BTerm -> BExp | BTerm
   
      BTerm ::= BTerm and Literal | Literal
   
      Literal ::= not Literal | Atom
    
      Atom  ::= true | false
   

Question 4

   Exp  ::= Exp + Term | Exp - Term | Term	

   Term ::= Term * Factor | Term / Factor | Factor

   Factor ::= Base ^ Factor | Base

   Base ::= (Exp) | Num

   Num ::= 0 | Non_Zero_Digit Seq

   Seq ::= lambda | Digit Seq 

   Non_Zero_Digit ::= 1 | 2 | ... | 9

   Digit ::= 0 | Non_Zero_Digit