Comp409 - Academics | WPI
Name______________________
CS544
Final
Summer 2006 (Open book, notes etc.)
You may upload this (email me when you do), email it OR print it out to write on it, put it in a 2-day express envelope and mail it to me (Karen Lemone), PO Box 706, Vinalhaven, Maine 04863. Do it right when you finish.
Part 1 (Each worth ½ point)
1. The phase of a compiler that classifies the input stream into a sequence of words called tokens is
a) Lexical Analysis
b) Syntax Analysis
c) Semantic Analysis
d) Optimization
2. The phase of a compiler that finds a variable which has not been declared is:
a) Lexical analysis
b) Syntax analysis
c) Semantic analysis
d) Optimization
3. Parsing is
a) Tractable
b) Intractable
c) NP-Complete
d) Undecidable
4. A regular expression for strings of letters (l), digits (d) and underscores (_) that begin with a letter, end with a letter or digit and have no consecutive underscores is:
a) l (l U d U _ )* (l Ud)
b) l (l U d U _l U _d)+
c) l ( _l U _d)* (l U d)
d) None of these
5. The unix tool lex is:
a) A scanner
b) A scanner generator
c) A Parser
d) A Parser generator
6. The graph
[pic]
is:
a) A minimal deterministic finite automaton
b) A non-minimal deterministic finite automaton
c) A non-deterministic finite automaton
d) None of these
7. The regular expression for the set of strings over {a, b} that do not contain the substring a b a is
a) b* (a U bb+)* b*
b) a* (b U aa+)* a*
c) b+ (a U bb*) b+
d) a+ (b U aa*) a+
e) None of these
8. This course would be better if it included streaming video of the lectures:
a) True
b) False
9. The grammar S( aSbS | ε is
a) Left recursive
b) LL(1)
c) Ambiguous
d) None of these
10. The grammar S( aSb | a is
a) Left recursive
b) LL(1)
c) Ambiguous
d) None of these
11. The grammar S( Sab | ε is
a) Left recursive
b) LL(1)
c) Ambiguous
d) None of these
12. For the grammar S( a S T | ε, T ( a T b | ε, the handle of a S a a T b b is
a) a S a
b) a T b
c) a S a a T b
d) None of these
13. If the items A ( a ( c and S ( c ( occur in the same state, there is
a) A shift-reduce conflict
b) A shift-reduce conflict only if c ε FOLLOW (A)
c) A shift-reduce conflict only if c ε FOLLOW (S)
d) A reduce-reduce error only if c ε FOLLOW (A)
14. Synthesized attributes are computed by
a) The scanner
b) Ascending the tree
c) Descending the tree
d) None of these
15. Where would the element A(3,2,1) of a 4x4x4 array be stored assuming the first element is A(0,0,0)
a) Base(A) + 37
b) Base(A) + 38
c) Base(A) + 57
d) None of these
16. For the program:
I = 2
L1: if I > X
(then) go L2
Fact = Fact * I
I = I + 1
Dumb = 5
go L1
L2: Factorial = Fact
Return
The variables that are live at the top of the program are:
a) I and Fact
b) Fact and X
c) I and X
d) I, X and Fact
e) None of these
17. Loops are
a) Cycles
b) Cycles whose tails dominate their heads
c) Cycles whose heads dominate their tails
d) Cycles with more than one entry
e) None of these
18. Static links show
a) Scoping
b) The previous activation record
c) The return point in the code
d) None of these
19. For a given grammar G with alphabet Σ, L(G) =
a) {w ε Σ * | S ( w}
b) {w ε Σ * | w* = w}
c) {w ε Σ * | ε is in w}
d) {w ε Σ * | length(w) = n}
20. For S ( a S a | b S b | ε, L(G) =
a) (a U b )*
b) (0 U 1 )*
c) {w | number of a’s in w = number of b’s in w}
d) Strings of a’s and b’s that read the same forward as backward
e) None of these
Part 2
#1. (1 point) Eliminate the left recursion from the expression grammar:
E ( E + T |T
T ( T * F | F
F ( (E) | x
#2. Consider the following nfa:
.
[pic]
a) (1 point) Convert it to a dfa. Redraw the graph when you are done Show your work.
b) (1 point) Convert your dfa in part (a) to a minimal dfa. Redraw the graph when you are done. Show your work.
3 - 5. Consider the following grammar, G:
S ( a S | b
3. (1 point) What is L(G)?
4a) (1 point) Create a top down parsing table
4b) (1 point) Use your table to parse aab
5a) (1 point) Create the SLR(1) states (grammar on previous page) Don’t forget to add S’ ( S
5b) (1 point) Create the SLR(1) parse table
c) (1 point) Using your table in 5b, parse aab
#6. Consider the following grammar:
O ( D O
O ( D
D( 0
D( 1
D( 2
D( 3
D( 4
D( 5
D( 6
D( 7
a) (1 point) What is L(G)?
b) (1 point) Show a parse tree for 237
c) (2 points) Create an attribute called value and add semantic functions to the above grammar which will convert an input string to its binary equivalent. Show the computations for 2 3 7.
#7. Consider the following recursive code generator algorithm:
Procedure CodeGen (Node)
{
Case Node Type is:
1. Expression Operator, Op:
IF neither child is a leaf THEN /*Result left in Reg */
{ CodeGen(LeftChild)
Emit “Store Reg, T1 ( = GetTemp)”
CodeGen (RightChild)
Emit “Store Reg, T2 ( = GetTemp)”
Emit “Load Temp1, Reg
Emit “Op T2, Reg”
}
ELSE IF only one child is a leaf THEN
{
CodeGen(Other Child)
Emit “Op LeafChild, Reg”
}
ELSE /* Both children are leaves */
Emit “Load Left Child, Reg
Emit “Op Right Child , Reg”
2. “:=”:
CodeGen (Right Child)
Emit “Store Reg, @LeftChild”
3. IF-then-else:
a) (1 point) Add code above to generate code for an if-then-else
b) (1 point) Create an ast for if (a ................
................
In order to avoid copyright disputes, this page is only a partial summary.
To fulfill the demand for quickly locating and searching documents.
It is intelligent file search solution for home and business.