CS 3723
Programming Languages  
Fall 2014
  Course Outline  

This Fall 2014 iteration of the course has 3 main objectives:

  • Present syntax-directed translation. Here is an online definition: In simplest terms, 'Syntax Directed Translation' means driving the entire compilation (translation) process with the syntax recognizer (the parser). Using specific examples we will see how this works in practice.

  • Work with the Python Programming Language. I intend for all but special-purpose programming to be in Python, with no programming at all in C or Java. Of course you are not assumed to know any Python. The first homework (Homework 0:Copy) starts the work on Python.

  • Study automata theory as a tool for writing software to process general regular expressions. (It will not be feasible to cover this topic in its full scope.)

1. Python Programming. We will start with this and keep working on Python through at least the first two-thirds of the course.

2. Using Automata Theory to Implement Regular Expressions.
  1. Finite automata (DFAs, NFAs, subset algorithm, ε-moves)
  2. Translate arbitrary regular expression into an NFA with ε-moves
  3. Interpret the states of the NFA as it processes input.
  4. Regular expresions in Python.
3. Formal Grammars and Parsing.
  1. Basic definitions
  2. Derivations, parse trees, ambiguity
  3. Shift-reduce parsing
4. Compiler for a Small Language.
  1. Recursive-descent parsing
  2. MIPS assembly language (emphasis on doubles)
  3. Construct a compiler from the parser (syntax-directed compilation)
5. Unusual Languages. Depending on the time available, perhaps Lisp (emphasis on recursive programming), Postscript, or Prolog

( Revision date: 2014-05-21. Please use ISO 8601, the International Standard.)