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
-
The program variable ``x'' is not declared
-
There is not enough space to represent the value of ``x''
-
An overflow at the parser table occurred
-
A shift/reduce conflict occurred
-
Regular expression contains too many symbols
-
A division by zero occurred at line $5$
-
The number of arguments of $p$ does not match its declaration
-
The context free grammar contains useless terminals
-
The program contains an infinite loop
-
Array indexing $a[i]$ is out of bound
Parsing(80%)
-
Consider the following grammar for Tiger type declarations
-
tydec -> type id = ty
-
ty -> id
-
ty -> { tyfields }
-
tyfields -> id : ty
-
tyfields -> tyfields , tyfields
A. Are there valid type declarations in Tiger which are not recognized
by this grammar?
B. Does this grammar allow declarations which are not valid in Tiger?
Here tokens appear in boldface and are underlined
-
Convert the grammar from exercise 1 into a non ambiguous grammar by assuring
that "tyfields" associate to the right.
-
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
-
Construct SLR(1) tables for resulting non ambiguous grammar from exercise
2
-
Apply the SLR parser to the declarations:
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?
-
Show that the following left-factored simplified if-then-else grammar is
not LL(1)
-
S -> if cond then S S'
-
S -> assignment
-
S' -> else S
-
S' -> empty-string
-
Investigate the two possibilities to patch the Select table in the above
grammar, and their consequences.
By "patching" the table, we mean removing tokens which cause conflicts
-
Show that the following grammar is LL(1) but not SLR(1)
-
S -> A a A b | B b B a
-
A -> empty-string
-
B -> empty-string
-
(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.