I’ve quietly skipped over some quite important details. Firstly…
The Symbol table
Every subroutine name, variable name, constant and type must be recorded along with information about it. For instance, variable names need the types associated with them, a storage location in memory at runtime and an associated scope. Subroutine names need locations and argument lists annotated with types. This is done by using a “hash map”, which is a table that associates a string (e.g. an identifier) with a structure or list containing this information. Scopes must be taken into account. Finally, if the user requests, all the symbol table data is kept until the code is generated and then annotated to the executable for use by a debugger.
Error detection is an ongoing process occurring throughout the front end. The lexer can detect malformed tokens, the parser can detect syntax errors and the tree can detect annotation type mismatches. The parser should be able to ‘get past’ at least some errors so the user has useful error messages from a long compile.
The next part of this article will deal with optimization and code generation.
http://www.iecc.com – Several resources and archive of the comp.compilers newsgroup.
http://compilers.iecc.com/crenshaw – A tutorial creating a one-pass compiler for a superset of Pascal in Pascal. Free, excellent explanations. Uses a predictive parser and no tree structure.
Computer architecture and Organization: A Quantitative approach, J. Hennessey and D. Patterson. – The bible of computer architecture, contains much material on loop optimizations. Compares compiler methods to hardware methods.
Compilers: Principles, Techniques and Tools, A. Aho, R. Sethi J. Ullman – `The Dragon book’. The bible of compilers, written in 1986 this books information on front end aspects is still solid. Relatively little information on optimization (still more than many compiler books).
http://lambda.uta.edu/cse5317/notes/node1.htm – University of Texas course notes on Compilers by Leonidas Fegaras
Discuss (15 comments)