An introduction to theoretical computer science including studies of abstract machines, the language hierarchy from regular languages to recursively enumerable languages, noncomputability and complexity theory.
This course explores the foundations of how compilers work and explores this theory with hands on experience of the concepts. For example, suppose you are asked to create a new programming language for a specific device. How would you write a compiler or interpretor for such a language? You would first start by writing a grammar to define valid constructs in the programming language, similar to a grammar that defines what a sentence is in a spoken language such as English. In order to determine if a program is a valid program for this programming language, one would see if the program fits the rules in the grammar. In particular one would take the following steps. First one would identify the individual words in a program (lexical analysis) and then check to see if those words form valid structures in the grammar defining the programming language (syntax analysis). We will explore the theory and practice of several parsing techniques such as LR and LALR parsing.
To gain experience with the theoretical concepts in this course, we will write an interpretor for a simple programming language in a 3-part programming project, and we will use the software JFLAP 7.1 to experiment with structures and proofs, such as programming finite state machines and Turing machines, or to show that a particular finite state machine is equivalent to a regular expression.
The required work in this course includes in-class group work, online quizzes on the reading, homework consisting of written assignments and JFLAP assignments, and one three-part programming assignment (an interpretor for a new programming language).