COSC4307			TEST-1		7/27/2003

NAME_____________________________________

PART-A. Multiple Choices.			(80 points)

In each question in this PART, check the BEST choice. (Namely, exactly 
one Best choice.)

1.	Which is true of a Scanner?
	a. it recognizes tokens.
	b. it is called a Syntactic Analyzer.
	c. both.		d.  neither.

2.	Which is true of a Parser?
	a. it is called a Semantic Analyzer.
	b. it takes the outputs of a scanner.
	c. both.		d. neither.

3.	Which is a notation for a compiler where?
		S: Source language
		H: Host language
		T: Target language

	a.        S		b.      S		c. Neither
		----		       ----
	         H.T		       T.H

4.	Which is a notation for compiling?
		  
	        S   P                 S   P
	a.  M ---- --        b.   M ---- --	 	c. Neither
       	       M.M  S	             N.M  N

5.	Which is true of an Intermediate Code Generator?
	a. it depends heavily on the machine language.
	b. its outputs can be readily interpreted.
	c. its outputs are very suitable for optimizations.
	d. All above.		e. Two above.		f. None above.

6.	Which is true of interpreters?
	a. They run partially translated programs faster than
	   compiled programs.
	b. They may not be able to handle every thing that compilers do.
	c. both.		d. neither.

7.	Which relation is transitive?
	a. Leftmost-Generating.
	b. Rightmost-Generating.
	c. Adjacent.		d. All above.	e. Two above.	f. None.


8.	Which relation is symmetric?
	a. Leftmost-Generating.
	b. Adjacent.
	c. Next-to.		
	d. All above.		e. Two above		f. None above.

9.	Which is true of Bootstrapping?
	a. it is a shortcut in compiler design.
	b. it enables us to avoid using the intended host language.
	c. both.		d. neither.

10.	Which is true of CFG's?
	a. they have more restrictions imposed on their production
	   rules than CSG's have.
	b. they have more expressive power overall than CSG's have.

11.	Which makes it easier to design scanners?
	a. when blank spaces are totally ignored.
	b. when keywords are strictly reserved.
	c. both.		d. neither.

12.	Which can best represent a class of tokens?
	a. a CFG.		b. a regular expression
	c. cannot tell.		d. neither.

13.	Which is a class of tokens?
	a. comments.	b. keywords.		c. identifiers.
	d. all above.	e. two above.		f. none above.

14.	When blank spaces are not totally ignored,
	a. a blank space must always immediately follow each token.
	b. a blank space is a mandatory token separator.
	c. both.		d. neither.

15.	Which is a subtask of a scanner?
	a. memory allocation when the exact memory size is not known.
	b. symbol table maintaining.
	c. conversions of constants.
	d. all above.		e. two above.		f. none above.

16.	String Derivatives
	a. can be used in converting regular expressions into
	   equivalent DFSA without involving NFSA.
	b. are results of dropping a certain starting character
	   out of strings we have.
	c. both.		d. neither.

17.	Which is true of 'lex'?
	a. it is supported by UNIX
	b. it takes three input parts and produces a wanted scanner.
	c. both.		d. neither.
18.	When is a sentence ambiguous?
	a. it has two different parse trees.
	b. it has two different derivation sequences, not necessarily
	   both leftmost (nor both rightmost).
	c. both.		d. neither.

19.	When is a grammar unambiguous
	a. it generates at least one unambiguous sentence.
	b. it generates no ambiguous sentence.
	c. both.		d. neither.

20.	In a two-pass compiler, the first pass is made typically
	a. by the scanner and the parser.
	b. by the scanner, the parser and the intermediate code generator.
	c. cannot tell.		d. neither.


PART-B.  Other problems.

Do two problems in this PART-B.			(20 points)

A.	In about 12 lines, describe how subprograms affect compiler design.


B.	Show bootstrapping processes involved in importing a compiler of 
	an existing computer to a new computer for the same source 
	language.

C. 	Derive and clearly show a DFSA for the following regular 
	expression:

	(a+b)(c*+d*)