CSE 428 : Assignment #1 Solution


Question 1

      a.    S ::= A | S A 
            A ::= blank | tab | newline
     
      b.    S ::= L Seq 
            Seq ::= L Seq | D Seq | <empty> 
            L ::= a | b | c | ... | z 
            D ::= 0 | 1 | 2 | ... | 9
      
      c.    S ::= I. | .F | I.F 
            I ::= <non_zero_digit><seq_digits> 
            F ::= <digit><seq_digits> 
            <non_zero_digit> ::= 1 | 2 | 3 | ... | 9 
            <seq_digits> ::= <digit><seq_digits> | <empty> 
            <digit> ::= 0 | <non_zero_digit> 

            Note: The grammar here does not generate numbers like 01., 001., etc. 
                  (No initial zeroes)

Question 2

        a.                                          b. 

        E                                           E 
     /  |  \                                        | 
    E   +   T                                       T 
    |       |                                       | 
    T       F                                       F 
    |       |                                     / | \ 
    F      num                                   (  E  ) 
    |       |                                     / | \ 
   num      3                                    E  +  T 
                                                 |     | 
                                                 T     F 
                                                 |     | 
                                                 F    num 
                                                 |     | 
                                                num    3 
                                                 | 
                                                 2 
        

          c.                                         d. 

          E                                          E 
       /  |  \                                       | 
      E   +   T                                      T 
      |     / | \                                  / | \ 
      T    T  *  F                                T  *  F 
      |    |     |                                |     | 
      F    F    num                               F    num 
      |    |     |                              / | \   | 
     num  num    5                             (  E  )  5 
      |          |                              / | \ 
      2          3                             E  +  T 
                                               |     | 
                                               T     F 
                                               |     | 
                                               F    num 
                                               |     | 
                                              num    3 
                                               | 
                                               2 
        
            e. 

            E 
          / | \ 
         E  +  T 
         |     | 
         T     F 
         |   / | \ 
         F  (  E  ) 
         |     | 
        num    T 
         |   / | \ 
         2  T  *  F 
            |     | 
            F    num 
            |     | 
           num    5 
            | 
            3 
       

             

Question 3

     a. There are several ambiguities. 
        One example due to precedence between "and" and "not" is as follows: 
        
              not true and false     can be grouped as: 
        
              (not true) and false       or      not (true and false) 
        
                   BExp                                   BExp 
                  /  |  \                                /    \ 
                 /   |   \                              /      \ 
               BExp and BExp                          not      BExp 
              /  \        |                                   /  |  \ 
             /    \       |                                  /   |   \ 
           not    BExp  false                              BExp and BExp 
                   |                                        |         | 
                   |                                        |         | 
                  true                                    true       false 
      b. 
        
             BExp ::= F -> BExp | F 
               F  ::= F and L | L 
               L  ::= A | not L 
               A  ::= true | false 
       

Question 4

       S ::= <empty> | a | b | c | ... | z 
            | aSa | bSb | cSc | ... | zSz