CSE 428: Solutions of the exercises on grammars

This page contains the solution of a selection of the exercises on grammars.

Exercise 1 All the grammar presented below are possible solutions, other grammars might be good solutions as well.

  1.     <Identifier> ::= <Letter> <String> 
            <String> ::= <empty> | <Letter> <String> | <Digit> <String> 
             <Digit> ::= 0 | <NonZeroDigit> 
      <NonZeroDigit> ::= 1 | 2 | ... | 8 | 9 
            <Letter> ::= a | b | ... | y | z 
    
    Comment: if you have considered capital letters instead, or both, is fine as well.
  2.      <NaturalNum> ::= <NonZeroDigit> <DigitString> 
        <DigitString> ::= <empty> | <Digit> <DigitString> 
              <Digit> ::= 0 | <NonZeroDigit> 
       <NonZeroDigit> ::= 1 | 2 | ... | 8 | 9 
    
  3.          <RealNum> ::= .<Fraction> | <Integer>. | <Integer>.<Fraction> 
             <Integer> ::= <Digit> | <NonZeroDigit> <DigitString> 
            <Fraction> ::= <Digit> | <Digit> <DigitString> 
         <DigitString> ::= <empty> | <Digit> DigitString> 
               <Digit> ::= 0 | <NonZeroDigit> 
        <NonZeroDigit> ::= 1 | 2 | ... | 8 | 9 
    
    Comment: This grammar does not generate numbers like 01.12. However it geneartes numbers like 1.00. There was no precise specification in the text about the 0's, hence difefrent solutions on this regard are possible.

Exercise 2

   <Formula> ::= exitsts <Ide>. <Formula> | forall <Ide>. <Formula> | <F1> 
        <F1> ::= <F2> implies <F1> | <F2> 
        <F2> ::= <F2> or <F3> | <F3> 
        <F3> ::= <F3> and <F4> | <F4> 
        <F4> ::= not <F4> | <Atom> 

Exercise 3 There are 2 kind of ambiguities due to the definition of this grammar.

  1. Associativity of ";"
                     Cmd                               Cmd           
                   /  |  \                          /   |   \ 
                Cmd   ;   Cmd                    Cmd    ;     Cmd 
             / /  |       |                       |           |  \ \ 
          Cmd ;  Cmd      print(3)           print(1)        Cmd ; Cmd 
           |     |                                            |     | 
        print(1) print(2)                                print(2)  print(3) 
    
    
    This kind of ambiguity is not relevant semantically because ";" is associative.
  2. Precedence between ";" and "if-then-else"
    
               Cmd                                          Cmd 
      __________|___________                             /   |   \ 
      |  |   |   |    |    |                           Cmd   ;   Cmd 
     if Exp then Cmd else Cmd           ________________|___       | 
                  /      / | \          | |    |   |   |   |   print(3) 
           print(1)     Cmd; Cmd      if Exp then Cmd else Cmd             
                        |     |                     |       | 
                   print(2)  print(3)           print(1)  print(2) 
    
    
    This ambiguity is relevant at semantical level becuase if the statement print(3) is inside the else then will be executed only if the condition is true, otherwise will always be executed (after the conditional statement).

Exercise 4

         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 
            e.                                   | 
                                               2             
            E 
          / | \ 
         E  +  T 
         |     | 
         T     F |
         |   / | \ 
         F  (  E  ) 
         |     | 
        num    T 
         |   / | \ 
         2  T  *  F 
            |     | 
            F    num 
            |     | 
           num    5 
            | 
            3 


Exercise 8

    Type ::= CType -> Type | CType
   CType ::= CType * TVar | TVar

Exercise 10

Exercise 12

       S ::= lambda | a | b | c | ... | z 
           | aSa | bSb | cSc | ... | zSz 
where lambda stands for the empty string.