Introduction to Compiler Design

This book is designed primarily for use as a textbook in a one-semester course on compiler design for undergraduate students and beginning graduate students.  The only prerequisites for this book are familiarity with basic algorithms and data structures (lists, maps, recursion, etc.), a rudimentary knowledge of computer architecture and assembly language, and some experience with the Java programming language.A complete study of compilers could easily fill several graduate-level courses, and therefore some simplifications and compromises are necessary for a one-semester course that is accessible to undergraduate students.  Following are some of the decisions made in order to accommodate the goals of this book.The book has a narrow focus as a project-oriented course on compilers. Compiler theory is kept to a minimum, but the project orientation retains the 'fun' part of studying compilers.The source language being compiled is relatively simple, but it is powerful enough to be interesting and challenging. It has basic data types, arrays, procedures, functions, and parameters, but it relegates many other interesting language features to the project exercises.The target language is assembly language for a virtual machine with a stack-based architecture, similar to but much simpler than the Java Virtual Machine (JVM). This approach greatly simplifies code generation. Both an assembler and an emulator for the virtual machine are provided on the course web site.No special compiler-related tools are required or used within the book. Students require access only to a Java compiler and a text editor, but most students will want to use Java with an Integrated Development Environment (IDE).One very important component of a compiler is the parser, which verifies that a source program conforms to the language syntax and produces an intermediate representation of the program that is suitable for additional analysis and code generation. There are several different approaches to parsing, but in keeping with the focus on a one-semester course, this book emphasizes only one approach, recursive descent parsing with one symbol lookahead.