COSC4307
TEST-1
Summer 2004
NAME_____________________________________
PART-A. Multiple
Choices.
(92 points)
In each question in this PART, write a big
A or B or C or D or E or F as your BEST choice right by the Question number.
Choose and Answer 23 questions in this
PART.
Key: 1-5:
DACAC
6-10:
AACAD
11-15:
CADCD
16-20:
BAEBC
21-25:
BBCAA
26-30:
BDDCD
1. Which is for compiling a source program?
S P S P
a. M --- - b. N --- - c. both. d. neither
M.M L N.N N
2. L
---
K.M
Above represents a compiler when L is the source language and
a. K is the host language and M the object language.
b. M is the host language and K the object language.
c. both. d. neither.
L S
3. M --- ---
M.M L.M
a. Above may represent converting a compiler into another.
b. Above may produce a compiler that can be run by the same computer being
used. c. both. d. neither.
4. Identifier scope rule is for binding
a. nonlocal names
b. local names and parameters. c. both. d. neither.
5. The Static Scope rule is more suitable than the Dynamic Scope rule when
a. subprograms can be nested.
b. blocks can be nested. c. both. d. neither.
6. Which is true about lex?
a. it is an automatic scanner generator supported by UNIX.
b. it produces a C program all by itself without us providing functions
that the wanted scanner needs.
c. both. d. neither.
7. Which is true of an ambiguous grammar?
a. at least one sentence of the language being defined by the grammar is
ambiguous.
b. no unambiguous grammar may define the same language that the grammar
defines. c. both. d. neither.
8. Which is an advantage of Intermediate Codes?
a. They are suitable for optimizations.
b. They are ready for interpretation.
c. both. d. neither.
9. Bootstrapping enables using the source language also as
a. the host language.
b. the object language. c. both. d. neither.
10. The stack used in Program-3 (Scanner Generator)
a. is to be pushed onto each time a block starts in the source program
being compiled.
b. is to be popped off each time a block ends in the source program.
c. contains the starting symbol table location and the ending symbol
table location of the block, among others
d. All above. e. Two above. f. None above.
11. Which is true for Automatic Scanner Generators?
a. regular expressions are used in their inputs.
b. they essentially convert regular expressions into Finite State Acceptors.
c. both. d. neither.
12. In a two-pass compiler, typically,
a. the scanner and the parser and the intermediate code generator
together make the first pass.
b. the scanner and the parser make the first pass.
c. both. d. neither.
13. A parse tree of a given sentence may show
a. two different leftmost derivation sequences.
b. two different rightmost derivation sequences.
c. both. d. neither.
14. Two different rightmost derivation sequences of a given sentence may imply
a. two different leftmost derivation sequences of the same sentence.
b. two different meanings of the same sentence.
c. both. d. neither.
15. Which makes the task of a scanner design easier and simpler?
a. when blanks are NOT to be totally ignored.
b. when blanks are used as necessary token separators.
c. when keywords are strictly reserved.
d. All above. e. two above. f. None above.
16. Which computes
L+nt
a. L+nn
Lnv
b. L*nn
Lnt
c. neither.
17. Which computes R+nv
a. R*nn
Rnv
b. R+nn
Rnv
c. neither.
18. Which is an
“Any Path”data flow problem?
a.
Live Variable
problem
b.
Reaching
Definition problem
c.
Available
Expression problem.
d.
All above. E. two above.
19. Which is a
forward flow problem?
a.
Live Variable
problem
b.
Copy propagation
problem.
c.
Both. d.
neither.
20. A compiler
tends to make more passes if
a.
more optimization
is required.
b.
The source
language is more complicated.
c.
Both. d.
neither.
21. An advantage of
interpreters over compilers includes
a.
fast execution
speed
b.
more
capability
c.
both. d.
neither.
22. An advantage of
quadruples as intermediate code over triples includes
a.
use of temporary
variables.
b.
Less frequent
references.
c.
Both. d.
neither.
23. Which is a loop
optimization technique?
a.
code
motion.
b.
Induction
variable elimination.
c.
Both. d.
neither.
24. The scope of
local optimization is
a.
each basic
block
b.
a
loop
c.
both. d. neither.
25. Which is for
the top-down parsers?
a.
the leftmost
derivation sequence.
b.
the rightmost
derivation sequence.
c.
Both. d. neither.
26. Which is for
the bottom-up parsers?
a.
the leftmost
derivation sequence in reverse.
b.
the rightmost
derivation sequence in reverse.
c.
Both. d. neither.
For the rest of the test, refer to the following CFG whenever applicable:
S -> R S
S -> R
R -> ( R )
R -> * R *
R -> a
R -> b
27. The nonterminal S leftmost-derives (in one or more steps)
a. R
b. a
c. (
d. All above. e. two above. f. none above.
28. Which is a NEXT-to pair?
a. * (
b. ) *
c. ( *
d. All above. e. Two above f. None.
29. Which is a sentence?
a. * a * b
b. b ( ( * a * ) )
c. both. d. neither.
30. Which is a sentential form?
a. R ( R )
b. ( R ) R
c. * R * ( R )
d. All above. e. Two above. f. None
PART-B. Other Problems.
(8 points)
Do one problem in
this PART-B.
A. Derive and clearly show the NEXT matrix.
It must be 5-by-5.
B. Briefly describe some design issues of a compiler in no more than
10 lines.
C. Briefly describe processes involved in importing an existing
compiler to a new computer for the same source language.