• One year of college-level calculus (NMTH 1111 and NMTH 1112)
• An undergraduate course in Discrete Mathematics (like NCSC 2201) covering sets, sequences, functions and relations, undirected and directed graphs, asymptotic notation for the running time of algorithms, (concept of proof, and techniques for constructing proofs (by contradiction, by induction)

• An undergraduate course in Theory of Computation (Formal Languages and Automata Theory), like NCSC 3001, covering topics such as regular expressions, context-free grammars, language classes, finite automata, push-down automata

• Experience with some high-level programming languages

• General prerequisite: Students must have the knowledge resulting from completing all coursework in the curriculum for a BS degree in Computer Science from a regionally-accredited institution in the United States or the equivalent from a foreign institution; performance level in this coursework should be equivalent to a cumulative undergraduate GPA of 2.9 or better on 4.0 scale
  

Course Objectives

At the end of this course, students should be able to:

• Understand the central issues and principles governing the design of modern programming languages.
• Understand the fundamental differences between the four major programming language paradigms.
• Understand the value of operational and denotational semantic specifications of programming language constructs.
• Implement a syntax analyzer for any reasonable programming language.
• Understand the process of translation of a program in a high-level language to a low-level language.

Course Topics

The following topics will be covered in the order given.

• Introduction, Paradigms
• Overview of Compilation
• Context-free languages and LL1() grammars
• Recursive descent parsing, elimination of left recursion and common prefices
• String-to-tree transduction
• Generating Abstract Syntax Trees
• Introduction to the RPAL language
• Building RPAL programs
• Building AST's for RPAL programs
• Name binding and object lifetimes
• Scope rules
• Binding of reference environments
• Functional graphs and evaluation algorithms
• Attribute grammars
• An attribute grammar for binary numbers
• A Tiny language, its syntax, target machine, and attributes
• An attribute grammar for Tiny
• Extending Tiny
• Expression evaluation
• Control flow, selection, and iteration
• Recursion
• Type systems and type checking
• Records and arrays
• Pointers and recursive types
• Stack layout, static links, and displays
• Parameter passing
• Generics and exceptions
• RPAL tree standardization
• Lambda expressions and the subst function
• Lambda calculus
• The RPAL CSE machine
• Optimizations of the CSE machine
• Recursion
• Semantic domains and semantic functions
• Denotational semantics of Tiny
• The RPAL denotational description of Tiny
• Adding new expressions and statements
• Adding the for statement in C and Pascal
• Expanding Tiny into Medium
• C++ as a better C
• Object-oriented programming in C++
• Logic Programming