Compiler Construction
Theoretical Assignment 1: Due December 10

General Questions (20%)

Identify for every activity when does it occur, i.e., at compile time, run-time, or different time (specify). Justify your answer
  1. The program variable ``x'' is not declared
  2. There is not enough space to represent the value of ``x''
  3. An overflow at the parser table occurred
  4. A shift/reduce conflict occurred
  5. Regular expression contains too many symbols
  6. A division by zero occurred at line $5$
  7. The number of arguments of $p$ does not match its declaration
  8. The context free grammar contains useless terminals
  9. The program contains an infinite loop
  10. Array indexing $a[i]$ is out of bound

Parsing(80%)

  1. Consider the following grammar for Tiger type declarations
  2. Convert the grammar from exercise 1 into a non ambiguous grammar by assuring that "tyfields" associate to the right.
  3. Compute Nullable, FIRST, FOLLOW, and SELECT for the resulting non ambiguous grammar from exercise 2. Is the grammar LL(1)? If not convert it into an LL(1) grammar and justify your answer
  4. Construct SLR(1) tables for resulting non ambiguous grammar from exercise 2
  5. Apply the SLR parser  to the declarations:

  6.                      type rec = {
                                          f1 : rec,
                                          f2 : rec,
                                          f3 : rec
                                          }

    What can you conclude from this example on the usage of right associative grammar in LR parsing?

  7. Show that the following left-factored simplified if-then-else grammar is not LL(1) 
  8. Investigate the two possibilities to patch the Select table in the above grammar, and their consequences.

  9. By "patching" the table, we mean removing tokens which cause conflicts
  10. Show that the following grammar is LL(1) but not SLR(1) 
  11. (Bonus) Give a non ambiguous grammar that Bison and yacc will not be able to parse due to a shift/reduce conflict. Show a particular valid input in the grammar that will not be recognized.