Introducing Fixed-Point Iteration Early in a Compiler Course

The paper "Introducing Fixed-Point Iteration Early in a Compiler Course," by Max Hailperin, appeared in the Proceedings of the Twenty-Eighth SIGCSE Technical Symposium on Computer Science Education, San Jose, California, 1997, pp. 258-261. The definitive version is the one published by ACM, and they hold the copyright as stated in the copyright notice on page one. The PostScript and PDF preprints are provided here as a convenience, as per the following server notice:
The documents distributed by this server have been provided by the contributing authors as a means to ensure timely dissemination of scholarly and technical work on a noncommercial basis. Copyright and all rights therein are maintained by the authors or by other copyright holders, notwithstanding that they have offered their works here electronically. It is understood that all persons copying this information will adhere to the terms and constraints invoked by each author's copyright. These works may not be reposted without the explicit permission of the copyright holder.

A postscript (or afterthought) to the paper

In the paper, I show that fixed-point iteration can be introduced much earlier in a compiler course than is typical. Specifically, I show how to introduce this topic in the context of parsing. More recently it occurred to me that the topic could be pushed even earlier (in the typical compiler course's organization) by covering it in the context of lexical analysis. This is because the epsilon-closure algorithm, which is typically used as a step in building a DFA lexical analyzer from regular expressions, can be formulated as a least fixed-point iteration.