A first course in compiler writing
Stuart Greenfield · 1992
The first compiler, developed for the FORTRAN programming language and written in a rather ad hoc manner, was announced in the Fall of 1954. That compiler stands as a testament to the inventiveness of the people involved in the project which took approximately eighteen person-years. Today, almost four decades later, such a compiler project would take but a fraction of the time due to the development of a formal theoretic foundation for compiler writing and the availability of excellent compiler construction methodologies. The primary role of this manuscript is to present to a wide readership, in a pedagogically sound manner, the fundamental concepts associated with the activities that are carried out by a compiler, namely, scanning, parsing, and code generation. This work encompasses some of the more popular compiler construction methodologies employed today. Underlying theoretical material on formal languages and grammars, finite-state machines, and pushdown automata are described when needed, as are the practical necessities of symbol table construction and computing machine architecture. The use of regular grammars and finite-state machines lead to the development of the first phase of compilation called scanning, where a lexical analysis of an input program is conducted. Symbol tables, which are used throughout the entire compilation process, are constructed and filled as needed information is procured. The second phase of compilation, that of parsing, performs a syntactic analysis of the input program and may be accomplished employing a number of different methodologies. The manuscript presents top-down parsing in the form of LL(1) and recursive descent parsing and bottom-up parsing in the form of SLR(1), LALR(1), and LR(1) parsing. In addition, semantic actions are built into the parsing phase so that machine code may be eventually synthesized. The manuscript approaches the final phase of compilation, that of code generation, by indicating how improvements may be made on a simple machine code generator. As the different phases of compilation are considered, a complete compiler is constructed for a simple programming language named Proem. The Proem compiler parts may be used as a template for the design and implementation of a compiler for a student compiler project for a specified language called Lang2.