CSCE 531 (Spring 2007): Lecture Log

January 17 (Wed), 2007 Administrative information: textbook, syllabus, grading policy. Beginning of course questionnaire, with discussion.

January 19 (Fri), 2007 Q1. HW1 assigned, due 1-24: exercises 1.2, 1.4-1.6 textbook. More preliminaries: families of languages (imperative, functional, logic); PLs as algorithm description languages.

January 22 (Mon), 2007 HW1 postponed: new due date will be announced in class on Wednesday. Loop invariants: technique and example, with a lot of Q&A.

January 24 (Wed), 2007 HW1 is due on Monday, January 29. Q2, with much discussion. More on preliminaries: computer architectures. Von Neumann vs. Harvard architectures. Direct hardware or architectural support for non-von-Neumann machines: Symbolics, Lambda, PIM-1, Mago's machine. Reasons for failure of this approach.

January 26 (Fri), 2007 HW1 due date postponed to Wednesday, January 31. Assembly language: historical definition. 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). 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. Binding and applied occurrences. Scope and type, with examples.

January 29 (Mon), 2007 Context-free grammars. BNF. EBNF grammar of Mini-Triangle, with examples and comments on Triangle.

January 31 (Wed), 2007 HW1 collected. Language Processors: through section 2.3. Some good questions.

February 2 (Fri), 2007 HW2 assigned: exercises 2.2-2.4. Bootstrapping, with many examples. Good questions. Chapter 2 completed.

February 5 (Mon), 2007 HW2 collected. Compilation: Chapter 3. The phases of compilation: textbook flowchart and examples from [Aho, Sethi, and Ullman, 1986], [Appel, 1998], [Grune, Bal, Jacobs, and Langendoes, 2000]. Definitions of phases are contrasted. Example of 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.

February 7 (Wed), 2007 HW3 assigned: exercises 3.1, 3.2, 3.3, 3.5, due Monday, February 12. Static vs. dynamic scope rules. Compilation (Ch.3) completed. Syntactic analysis: Ch.4. Tokens for mini-Triangle and their Java representation (Section 4.1.1). Regular expressions.

February 9 (Fri), 2007 HW1 returned. Chomski's hierarchy of languages, grammars, and recognizers. Appel Ch.2: regular expressions with examples of tokens, FSAs: definitions, first examples (the keyword if, Pascal identifiers).

February 12 (Mon), 2007 HW3 collected. MT1 will be on Wednesday, February 21. Appel Ch.2: deterministic finite state automata as recognizers, with several examples. Transition tables. Recognizing the longest match. NFAs. Translation of regular expressions to NFAs.

February 14 (Wed), 2007 HW2 returned. HW4 assigned: exercises 2.1, 2.3-2.5 (Appel handout); 4.1, 4.2 (textbook), due Monday, February 19. MT1 will be on Wednesday, February 21. Review of translation of REs to NFAs. Simulation of NFAs. Translation of NFAs to DFAs.

February 16 (Fri), 2007 MT1 will be on Wednesday, February 21. NFAs and DFAs completed. JLex. Extended BNF and extended REs (textbook, through p.82) Starters sets (4.2.4).

February 19 (Mon), 2007 HW3 returned. HW4 collected. MT1's date has been changed to Friday, February 23. Sample MT1 is with answers is posted on the web site. Students are encouraged to study the sample test and the two quizzes carefully. MT1 will be open-book, Students must bring their textbook, (Section 4.2 completed) Conceptual introduction to parsing. Parts of section 4.3: bottom-up and top-down parsing, using micro-English as an example. Recursive descent parsing: micro-English (started).

February 21 (Wed), 2007 Review session led by Mr. Sen Xu.

February 23 (Fri), 2007 MT1.

February 26 (Mon), 2007 MT1 returned. Recursive descent parsers.

February 28 (Wed), 2007 Parsing: Section 4.3 completed, with examples. Section 4.4 (Construction of Abstract Syntax Trees). Remainder of Ch.4 assigned.

March 2 (Fri), 2007 HW5 assigned: Exercise 4.9 due Wednesday, March 7 HW6 assigned: Exercises 4.13 through 4.16 due Wednesday, March 7 PR1 assigned: Exercise 4.20 (and, for graduate students only: 4.22, for Mini-Triangle), due Friday, March 9. Contextual Analysis (ch. 5), started.

March 5 (Mon), 2007 Contextual analysis (ch.5), through justification of visitor pattern.

March 7 (Wed), 2007 HW5 and HW6 collected. PR1 due data changed to midnight on Saturday, March 10. Contextual analysis (ch.5) completed. Run-time organization (ch.6) started.

March 9 (Fri), 2007 PR2 and PR3 assigned, due Wednesday, March 21, 2007, and Friday, March 23, 2007, respectively. Note: PR1 will be due at a later date, as explained in the following email of March 8, 2007: *******email begins*********** Dear CSCE 531 students, I have come to realize that programming assignment 1 is unsuitable as a first assignment. Please keep the work you have done on it. It will come useful later, when it is reassigned. On Friday, I will give you a new, gentler, first programming assignment. This new assignment will be due after the break. There are three submissions of the current programming assignment in the dropbox now. The students who have sent in those submissions should withdraw them, if possible, and keep their work for later submission. I apologize for the inconvenience. Best regards, *******email ends************** Run-time organization continued through stack memory management. (Static links are next.)

March 19 (Mon), 2007 Short lesson, to allow students to attend colloquium at 1400. Review of run-time organization.

March 21 (Wed), 2007 PR2 collected (35/37 placed it in dropbox by start of class!). Run-time organization: static links, routines.

March 23 (Fri), 2007 PR4 (due Wednesday, March 28) and PR5 (due Friday, March 30) assigned. Run-time organization: recursion and heap allocation.

March 26 (Mon), 2007 Heap allocation: garbage collection. Support for object-oriented programming in the heap. Ch. 6 (run-time organization) completed.

March 28 (Wed), 2007 HW5 and HW6 returned. PR4 and PR5 due date changed: Monday, April 2 for PR4, Wednesday, April 4 for PR5. Ch 7 (code generation) started, through code templates for the whole of mini-Triangle.

March 30 (Fri), 2007 HW7 assigned: exercises 7.1, 7.2, 7.3, due Friday, April 6. Code generation: code selection (7.1) completed; code generation algorithm using the visitor pattern (7.2) completed, including backpatching (7.2.3). Storage allocation started.

April 2 (Mon), 2007 Quiz 4. Storage allocation, continued.

April 4 (Wed), 2007 Quiz 5. Program 1 (PR1) reassigned, due Wednesday, April 11: see entries for March 2 and March 9. Chapter 7 (code generation) completed.

April 6 (Fri), 2007 Quiz 6. PR6 assigned, due Monday, April 16: Exercises 7.4 and 7.5 (building on exercises 7.1, 7.2, and 7.3; numbers to be verified!). HW8 assigned, due Friday, April 13: Exercise 7.6 in Ch. 7 on entity descriptors (known value and known address; unknown value and known address; etc.) in various programming languages. Reading assignment: Students are encouraged to read Paul Graham's paper on McCarthy's LISP interpreter, linked to the web site for the course. Interpretation (ch. 8): general comments, difference between iterative and recursive interpreters. Examples of iterative interpreters: the emulator for Hypo (an accumulator machine), the mini-Shell interpreter, initial part of the mini-Basic interpreter.

April 9 (Mon), 2007 Q7. The mini-Basic interpreter, in full detail.

April 11 (Wed), 2007 Q8. How to specify semantics formally: an overview of denotational semantics (handout, based on Ghezzi and Jazayeri, 2nd ed.): the denotational semantics of a simple language with integers, conditionals and pretest (while) loops. Recursive interpretation is similar to denotational semantics.

April 13 (Fri), 2007 Q9. This quiz followed a review of parameter passing, prompted by questions related to HW8. HW8 is now due at midnight. LISP interpreter: (S)-expressions, the first 2 of the 7 primitive functions: quote and atom, in great detail.

April 16 (Mon), 2007 Q10. Extension for PR6 until next class time. It is made clear that code needs to be written only for this exercise. Code that is demonstrated to compile and run (by providing adequate scaffolding for the visitor/encoder) will lead to extra credit. LISP interpreter: all primitive functions, lambda, label, and defun.

April 18 (Wed), 2007 Q11. PR6 due date extended for the extra credit part. Term project assigned. LISP interpreter: examples of functions.

April 20 (Fri), 2007 Q12. LISP interpreter: more examples of functions, beginning of the eval program.

April 23 (Mon), 2007 Q13. LISP eval almost completed.

April 25 (Wed), 2007 Q14. Term project changes and decisions: Exercise 9.12 (first option) replaces 9.9; teams of two (2) students are allowed, individual projects are allowed as well. Students are required to email the composition of each pair. LISP eval completed.

April 27 (Fri), 2007 Q15. Chapter on interpreters completed.

April 30 (Mon), 2007 No Quiz. Due date of project is midnight between Sunday, May 6, and Saturday, May 7. (There was some confusion about this.) Data flow analysis: basic blocks, transformations, live variables: handout from the dragon books (reference in introductory slides).