CSE 428 : Assignment #1 Solution

Question 1

a.
 S ::= A | SA
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

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