Class Project: This is a project course. The students will form 4 groups, each working on an implementation of the programming language C--: a dumber C. Our goal is to define a C-like language which is idiot proof. Well, almost.

The language should be mostly a compatible subset of C, C++ and Java. It should support a minimum of constructs, and through the use a more limited syntax than C, avoid the common pitfalls of C.

Syllabus:

• Lexical Structure.
  • The Theory of Regular Expressions, Finite state automata, and Kleene's Theorem.
  • Class notes on regular expressions.
  • Presentation of Lex.
  • Formal description of the Java lexical structure.
  • References:
    • Principles of Compiler Design, Aho and Ullman. Pages 74-125.
    • Introduction to Auomata Theory, Languages and Computation, Hopcroft and Ullman. Pages 1-46.
    • Elements of the Theory of Computation, Lewis and Papadimitriou. Pages 49-94.
    • Lex: A Lexical Analyzer Generator by M.E. Lesk and E. Schmidt, Bell Laboratories.
    • lex and yacc by John Levine, Tony March and Doug Brown. (Examples from the book.)
    • The Java Specifications, see java.sun.com.
• Syntatical Structure.
  • Theory of Context-free grammars, Push-down automatas, their equivalence, and applications to LR parsing: SLR(1), LR(1) and LALR(1) parsing tables.
  • Class notes on CFG's and LR parsing
  • Presentation of Yacc. (Example code.) (Example code.)
  • Formal description of the C syntax. The complete YACC Grammar and complete LEX rules are online.
  • References:
    • Principles of Compiler Design, Aho and Ullman. Pages 126-245.
    • Introduction to Auomata Theory, Languages and Computation, Hopcroft and Ullman. Pages 77-124 and pages 234-269.
    • Elements of the Theory of Computation, Lewis and Papadimitriou. Pages 95-167.
    • On the translation of languages from left to right Donald E. Knuth. Information and Control, Vol 8, 1965. Pages 607-639.
    • lex and yacc by John Levine, Tony March and Doug Brown. (Examples from the book.)
    • Yacc: Yet Another Compiler-Compiler, Stephen C. Johnson, Bell Labs.
    • The C Programming Language - Reference Manual, Denise Ritchie, Bell Labs.
• Attribute Grammars
  • References:
    • Semantics of Context-Free Languages, Donald E. Knuth, Mathematical Systems Theory, Vol 2, No 2, 1968. Pp. 127-145.
    • Concepts of Programming Languages, Robert W. Sebesta, Benjamin Cummings Pub. Pp. 109-115.
• Semantics
  • Introduction to Scheme using the implementation Scheme 48.
  • How to Scheme: Class notes introducting Scheme.
  • How to Scheme: the sequel. Class notes continuing the introduction to Scheme.
  • Bindings: Lazy vs. Eager, Deep vs. Shallow.
  • The lambda calculus
  • Denotational Semantics, class notes concerning:
    • Introduction to Denotational Semantics
    • The Denotational Semantics of Scheme (simplified)
    • The theory of least fixed points and applications to recursion.
  • References:
    • The Scheme 48 Users Guide
    • Revised(4) Report on the Algorithmic Language Scheme (HTML), also available in Postscript.
    • Denotational Semantics: The Scott-Strachey Approach to Programming Language Theory, Joseph E. Stoy. MIT Press, 1977.
    • Denotational Semantics: A Methodology for Language Development, David A. Schmidt. Allyn and Bacon, 1986.
    • Structure and Interpretation of Computer Programs, Harold Abelson, Gerald Jay and Julie Sussman. MIT Press 1985.
• Topics
  • ML and Unification
  • Java byte-code security.