January 12 (Tue), 2010 HW1 assigned, due 1-21 (Thursday): exercises 1.2, 1.4-1.6 textbook. Administrative information: textbook, syllabus, grading policy. Beginning of course questionnaire, with discussion. Preliminaries: families of languages (imperative, functional, logic); PLs as algorithm description languages.
January 14 (Thu), 2010 Q1 and Q2. Overview of axiomatic, denotational, and operational semantics. Loop invariants: technique and example, with some Q&A.
January 19 (Tue), 2010 HW1 due date changed to 1-26 (Tuesday). Q3. More on loop invariants. Introductory slides concluded. More preliminaries: Languages; various computer architectures. Load-store (register-register), accumulator (single-register), memory-memory, stack instruction sets. The TAM as a Harvard stack machine. Ch.1 [W] started: levels of programming languages.
January 21 (Thu), 2010 No quiz. Expressions vs. commands. The example of Heron's formula in (register-memory) assembly language vs. a block structured language such as ML (or Triangle!). Facilities that are present in HLLs but not (or barely) in machine or assembly languages: expressions, data types, control structures, declarations, abstraction, encapsulation (or data abstraction). Context-free grammars and Backus Normal Form (BNF, also called Backus-Naur Form). BNF grammar for the language mini-Triangle. Examples of derivations and syntax trees (also called parse trees). The ambiguous grammar of if-then-else in the original Algol 60 specification.
January 26 (Tue), 2010 Q4. HW1 collected. HW2 assigned, due 2-2 (Tuesday): exercises 2.2-2.6, 2.8, 2.9 textbook. Please be concise, especially on exercise 2.9, for which I do not expect a long design document. Chapter 2 (Language processors, including tombstone diagrams, bootstrapping, etc.) completed.
January 28 (Thu), 2010 HW1 returned. Discussion of several exercises of HW1. Chapter 3: (Overview of) Compilation started. The phases of compilation: textbook flowchart and examples from [Gries, 1971], [Aho, Sethi, and Ullman, 1986], [Appel, 1998], [Grune, Bal, Jacobs, and Langendoes, 2000]. Definitions of phases are contrasted. Example of Several authors' presentation of the phases of compilation. Chomski's language hierarchy. Terminal symbols, non-terminal symbols, start symbol, production rules.
February 02 (Tue), 2010 HW2 collected. HW3 assigned: exercises 3.1-3.3, 3.5, due on Tuesday, February 9, 2010. Example of compilation of a short program, including a discussion of TAM and its data memory. Compiler design issues. Multi-pass vs. one-pass compilers. Discussion of the operation of a one-pass compiler on a simple example. Trade-offs (speed, space, modularity, flexibility, potential for optimization). Impossibility of one-pass compilation for Java, which allows variables to be declared after they are used. The (531) Triangle compiler is multi-pass. Top-level driver of the Triangle compiler. Organization of the Triangle compiler.
February 04 (Thu), 2010 Syntactic analysis: Ch.4. Tokens for mini-Triangle and their Java representation (Section 4.1.1). Regular expressions. Extended BNF and extended REs. Starters sets. Conceptual introduction to parsing. Bottom-up and top-down parsing, using micro-English as an example. Recursive descent parsing: micro-English. Recursive descent parsers.
February 09 (Tue), 2010 HW2 returned. HW3 collected. Recursive descent parsers: examples with mini-Triangle and Triangle. Construction of ASTs exploiting object-oriented design, in Java. Error reporting for syntax errors.
February 11 (Thu), 2010 PR1 assigned, due Tuesday, February 16 (dropbox). MT1 will be on Thursday, February 18. Lexical analysis (scanning). Systematic construction of a recursive descent scanner (Section 4.5 [W]). (N)FSAs and their use as RE recognizers (Appel's handout).
February 16 (Tue), 2010 PR2 assigned, due Tuesday, February 23 (dropbox). MT1 will be on Thursday, February 18. Lexical analysis (scanning). Systematic construction of a recursive descent scanner (Section 4.5 [W]). (N)FSAs and their use as RE recognizers (Appel's handout).
February 18 (Thu), 2010 MT1.
February 23 (Tue), 2010 MT1 returned. MT1 review, with special comments on the question on static vs. dynamic scope. Problems with the in-room projector required use of a portable one. Presentation by Aspen Olmsted, Devaun McFarland, and Mohamed Alamir Sharaf: "The Design of a PASCAL Compiler." Software: Practice and Experience, Vol. 1, (1971), pp.309-333.
February 25 (Thu), 2010 HW4 assigned: Exercises 4.1-4.4, 4.9, 4.10, due Thursday, March 4, 2010. Presentation by Jason Dew and Gary Fredericks on Parsing Expression Grammars (PEGs), Treetops, and a Regular-Expression-to-NFA translator. Introduction to contextual analysis (Ch. 5 [W]). Attribute grammars, with example of annotated syntax tree for checking of types in assignments.
March 02 (Tue), 2010 Q5. More on attribute grammars. Short discussion of Yacc/CUP. Most of Identification (5.1).
March 04 (Thu), 2010 HW4 collected. HW5 assigned: exercises 4.13 and 4.16 due March 23 (Tuesday---note change!). PR3 assigned, due March 23 (Tuesday---note change!): implement your solution for exercise 4.10 in Java. Design a small test case and capture the interaction in a file using script. Turn in a single file with the source code and the example of interaction. Presentation by Jason Miller: Building a Cross-Compiler. Identification. Type Checking.
March 16 (Tue), 2010 Traversing an AST for identification and contextual analysis: the visitor pattern. Ch.5 (Contextual Analysis) completed.
March 18 (Thu), 2010 Ch 6 (Run-time organization) started: TAM architecture (appendix C), expression evaluation (6.2), data representation (6.1) started.
March 23 (Tue), 2010 HW5 and PR3 collected. Run-time organization: stack storage allocation with dynamic and static links; routines (started).
March 25 (Thu), 2010 Routines, with a complete examples. Heap storage, started.
March 30 (Tue), 2010 HW6 assigned: 6.14, 6.15, 6.18 [W&B], due on Tuesday, April 6, 2010. Heap storage. Simple objects (no inheritance). Garbage collection. Data abstraction mechanisms, towards objects---started.
April 1 (Thu), 2010 Data abstraction. Types and abstypes in ML, with the set of integer example. Limitations of abstract data types. Objects. Messages. Dynamic method dispatch (at run time). Overloading (at compile time). Subtyping (important for users). Inheritance (allows sharing of implementation code).
April 6 (Tue), 2010 HW6 collected. HW7 assigned: exercises 7.1, 7.2, 7.3 [W&B] due Tuesday, April 13, 2010. HW8 assigned: exercises 8.5 and 8.6 [W&B] due Tuesday, April 20, 2010. Term project (PR4) assigned: Exercises 9.6, 9.7, 9.8, 9.12(a), and 9.15 [W&B], due April 29, 2010; details to follow. Denotational semantics, using handout on the web site. Code generation (Chapter 7): Code selection, with mini-Triangle example, through p.257 (approx.)
April 6 (Tue), 2010 Presentations by Neeraj Agrawal and Ankur Jain (T1) and by Miao Xu. (See details on the graduate student presentation page.) Section 7.1 completed.
April 13 (Tue), 2010 Presentation by Zheming Jin, Ibrahim Savran, and N.M. Stiffler on the PTX GPU assembly simulator and interpreter. Section 7.3.1 completed.
April 15 (Thu), 2010 Presentation by Ishtiaq Rouf, Chris Schmidt, Hossen Asiful Mustafa on the Compiler Controlled Threaded Abstract Machine (TAM). Chapter 7 (Code Generation) completed.
April 20 (Tue), 2010 HW8 collected. Presentation by Carroll A. Heath, Paul W. Hanczaryk, and Richard F. Porter on Language Typing. The LISP evaluator (started).
April 22 (Thu), 2010 Presentation by Jeffrey Kirby: "binpac: A yacc for Writing Application Protocol Parsers." Presentation by Hongying Du, Mingzhe Du, and Dharani Chintapatla on Syntax-Based Testing. A little more on LISP eval. Concluding lecture: efficiency (Ch. 9). Code transformation (or "code optimization") (handout). Student course evaluation.