CS451 Exam 1 Compilers
Instructions
1. The is a closed-book exam, but you are allowed to use a single page (both sides) of notes.
2. There are 3 problems in this exam and you have 75 minutes to answer them.
Copyright By PowCoder代写 加微信 powcoder
3. To receive full credit, your solution must not only be correct but also show all the steps.
4. Discussing the exam contents with anyone who has not taken the exam is a violation of the academic honesty code.
Problem 1. (32 points) Consider the language L of binary strings (ie, strings over the alphabet {0, 1}) of length at least 1.
a. (4 points) Provide a regular expression for L.
b. (4 points) List all the strings in L that are of length 3.
c. (8 points) Use the Thompson¡¯s construction method to derive a non-deterministic finite automaton (NFA) that recognizes L. It is enough to show the final NFA.
d. (8 points) Use the powerset construction method to derive an equivalent deterministic finite automa- ton (DFA). You must show the computation of ¦Å-closures and draw the DFA.
e. (8 points) Use the partitioning method to derive an equivalent, minimal DFA. You must show the partitioning steps and draw the minimal DFA.
Problem 2. (32 points) Consider the following context-free grammar.
1. S ::= A a 2.A::=b B 3.A::=c B 4. A ::= ¦Å 5.B::=c A 6.B::=d B 7. B ::= ¦Å
a. (8 points) Compute the first sets for S, A, and B. You must show the iterations of the algorithm separately.
b. (8 points) Compute the follow sets for S, A, and B. You must show the iterations of the algorithm separately.
c. (8 points) Construct the LL(1) parsing table for the grammar.
d. (8 points) Show the steps in parsing the input string c d c b a.
Exam 1 (Sample) Problem 3. (36 points) The Action and Goto tables for the grammar
0. S¡¯ ::= S
1. S ::= ( L ) 2.S ::=a
3. L ::= L , S 4.L ::=S
are shown below.
a. (12 points) Show the steps in parsing the input string ( ( a ) ). b. (8 points) Compute the itemset s0 = closure({[S¡ä ¡ú ¡¤S, #]}).
c. (16 points) Compute the following itemsets:
i s1 = goto(s0, S) ii s2 = goto(s0, () iii s3 = goto(s0, a) iv s6 = goto(s2, ()