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

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

       
           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 
  

  Comments: there is a penalty if you change the language generated by your grammar.
• (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.

Exercise 12

       S ::= lambda | a | b | c | ... | z 
           | aSa | bSb | cSc | ... | zSz