This test is intended to do two things. First, to help you pull together the ideas that we have studied this term, and try to make them more coherent as a whole. And second, to introduce you to a couple new ideas at an elementary level.

This is a test. Therefore, you may not speak to anyone besides me about this exam. You may use your textbook, other books, the Internet, and your own notes. If you take an idea from a book or website, please provide adequate citation. If you don't know what constitutes adequate citation, ask me.

I. Lexical analysis (10 points)

The algorithms in Chapter 3 give you some tools for creating lexical analyzers based on regular expressions. The flex lexical analyzer generator takes lists of regular expressions and associated actions and produces a lexical analyzer. The astute observer of the situation might reasonably suspect that flex exploits some of the techniques in Chapter 3.

Since you are, I'm sure, an astute observer, I would like you to investigate your suspicion. You have access to flex, and to the lex.yy.c files it generates. Use that access to answer the following questions. (Making slight changes to your flex program and observing the changes in lex.yy.c using diff might be a handy approach to some of these questions.)

1. Does flex use a finite automaton to match the regular expressions you provide? (Let's just say "yes" and get it over with, shall we?)

2. Where is the automaton in the lex.yy.c code? How does it work?

3. Is it a DFA or an NFA? How can you tell?

II. Shift-reduce parsing (20 points)

1. Show how to modify the algorithm on pages 218-219 to allow actions to be taken as they are in bison. In particular, make sure to show how to provide support for the "$$", "$1", etc. constructions.

2. Shift-reduce parse tables provide us more power than just the power to generate rightmost derivations in reverse. They also give us the ability to identify various kinds of parse errors. To illustrate this idea, please modify the program and the parse table on page 219 to implement an error-reporting mechanism. Make your error reports as precise and helpful as possible.

3. What is an ambiguous grammar? Give an example. Why are ambiguous grammars bad? Why might we want to use them, anyway? If we want to use them with shift-reduce parsing, what can we do?

4. When you study the Chomsky hierarchy, it's important to understand the subset relationships between classes of languages. For example, you need to know that every regular language is a context-free language, and you also need to know an example or two of languages that are context-free but not regular, to show that the set of regular languages is a proper subset of the set of context-free languages.

   In Chapter 4, we encountered SLR grammars, LR(0) grammars, LALR grammars, and LR(1) grammars. Show me the subset relationships between these classes of grammars, and make sure to include examples of grammars that fit in one category but not another. (Note, by the way, that we're talking here about grammars--not the languages they generate. It's quite easy to show an example of grammars of two different classes that generate the same language.)

III. Type checking and intermediate code generation (10 points)

Enhance our code generator (generator.y, generator.lex, generator.h, and Makefile) in the following ways. Hand in both a paper copy (2-up or even 4-up is okay) and an HSP copy of your files.

1. Add support for complaining when an assignment or a comparison is attempted between two variables with different types.

2. Add support for short-circuit ANDs and ORs.

IV. Frivolity (2 points)

I'm going to England over spring break, and I don't plan to do any work while I'm gone. What should I read on the plane?

V. Code generation (6 points)

1. Read section 9.7.

2. Do problem 9.8.

3. For the register-interference graph you produced in problem 9.8, provide a coloring using a minimum number of colors.

VI. Other (10 points)

Read Reflections on Trusting Trust, by Ken Thompson.

1. On what occasion did Thompson give this address?

2. List the steps you would need to take if you wanted to install the malicious code described by Thompson onto the Carleton Math/CS Linux systems. For each step, what sort of system access would you require?

3. Why is the self-generating program necessary for this particular piece of nastiness?

4. Paraphrase Thompson's conclusions about how to deal with malicious hacking.

VII. Th-th-that's all, folks

Thanks for joining me on this ride. Have a great break.