CSCE 531 (Spring 2023): Lecture Log

January 10 (Tue), 2023 Administrative information including: textbooks, syllabus, grading policy. A simple compiler for expressions in Haskell and proof of its correctness, through the presentation of all of the code and part of the proof of correctness. Problems with the recording of the course.

January 12 (Thu), 2023 A simple compiler for expressions in Haskell and proof of its correctness, through the presentation of all of the code. The lecture is correctly recorded; a technician is present in the classroom to direct the recording.

January 17 (Tue), 2023 A simple compiler for expressions in Haskell and proof of its correctness, completed. (Accumulator variant only briefly described.) Extensions: adding doubling of (sub-)expressions; adding multiplication of (sub-)expressions.

January 19 (Thu), 2023 HW1 (in the simple compiler for expressions in Haskell) and HW2 (exercises 1-1, 1-2, and 1-3 [R]) assigned, due 2023-01-26. See dropbox for details. Ch.1 [R] completed.

January 24 (Tue), 2023 Language processors and bootstrapping (using slides "Lecture Notes for Chapter 2 [W]" linked to main course website) completed.

January 26 (Thu), 2023 HW3 assigned, due 2022-02-01: Exercises 13.1 and 13.2 [M10] due 2023-02-02. (See syllabus for link to [M10].) Regular expressions from Ch.1 [M], with examples.

January 31 (Tue), 2023 Lexer generators, with a detailed example of use of Alex. Definiton of non-deterministic finite-state automaton (NDA).

February 2 (Thu), 2023 Construction of NFAs from regular expressions. DFAs. Set equations: Monotonicity (and distributivity) of set functions; fixpoints. Epsilon-closure. Conversion of NFAs to DFAs (the subset construction algorithm). Minimization of DFAs.

February 7 (Tue), 2023 HW4 assigned: exercises 1.4, 1.6, 1.8, and 1.9 [M], due 2023-02-14. Blackboard Collaborate Ultra recording not done because of a technical issue; Panopto recording is available in Blackboard. Lexers. Properties of regular languages (very briefly). Syntax analysis (Ch.2 [M]) started. Chmosky's hierarchy using slides from Derivations and syntax trees; ambiguity of context-free grammars.

February 9 (Thu), 2023 Basics of the Happy parser generator, with an example of use, both standalone (with a hardcoded lexer) and using the output from a lexer generated by Alex.

February 14 (Tue), 2023 HW3 hints given. Since the results for HW3 were not good, the students are given a chance to resubmit with 10% penalty by Tuesday of next week (2/21). HW5 assigned: exercises 2.6 and 2.7 [M] due 2023-02-23. The micro-English CFG. Top-dowm vs. bottom-up parsing. A recursive descent parser in Java. More on CFGs: ambiguity, reduced syntax trees, associativity and precedence (binding priority).

February 16 (Thu), 2023 More on associativity and precedence. Nullable, First, and Follow. Look-ahead sets. Recursive-descent parsers using look-ahead sets.

February 21 (Tue), 2023 HW6 assigned: Exercise 2.19 [M] due 23-03-02 (Thursday): see log entry of February 23, 2023 for a change in due date. Top-down (LL(1)) parsing completed with examples. Bottom-up (SLR) parsing started.

February 23 (Thu), 2023 HW7 assigned: Exercise 2.14 [M] due on 2023-03-02. Due date for HW6 changed to 23-03-14; but see entry of 2023-03-14 for update! Midterm exam will be on 2023-03-16; this is a change with respect to the syllabus! SLR parsing completed.

February 28 (Tue), 2023 Declarations and actions in LR Parser Generators; Abstract Syntax (Based on Section 2.16 [M]. HW5 (exercises 2.6 [M] and 2.7 [M]) corrected in class. Discussion of exercise 2.8 [M].

March 2 (Thu), 2023 HW8 assigned, due 2023-03-21 (Tuesday after the midterm exam). BNFC described with a simple example (Ch.2 [R]).

March 14 (Tue), 2023 (First class after spring break) New due dates set: HW6 is due 2023-03-21; HW8 is due 2023-03-28. Discussion of HW7 (Ex. 2.14 [M]). Hints for HW6 (Ex. 2.19 [M]). Q&A about midterm exam.

March 16 (Thu), 2023 Midterm exam.

March 21 (Tue), 2023 Midterm returned and reviewed. Introduction to BNFC (Ch.2 [R]) completed.

March 23 (Thu), 2023 Ch.3 [M] (Scopes and Symbol Tables), completed. Ch.4 [M] (Interpretation), started.

March 28 (Tue), 2023 Ch.4 [M] (Interpretation) completed. Some materials on iterative interpretation from [W] were also used; all are in the slides used in class and available on the main course website. Ch.4 [R] (Type Checking) started; note that we are using the presentation in [R] to introduce type checking.

March 30 (Thu), 2023 Discussion of graduate student work; the main website entry is for spring 2022, but it will remain essentially unchanged for spring 2023. Type checking continued.

April 4 (Tue), 2023 Graduate student work: students taking the course for graduate credit need to email me a choice of extra work by Tuesday, April 11, at start of class; they need to put "531 Graduate Extra Work" followed by their last name in the subject line. Type checking: Ch.4 [R] concluded.

April 6 (Thu), 2023 HW9 assigned: Exercises 4.0-4.4 [R] due on 2023-04-13. Undergraduate students are allowed to do the extra graduate work for extra credit. The amount of extra credit has to be determined later. Type checking: Ch.5 [M]. The slides by Cosmin Oancea are used; they include extra material, particularly on type inference for polymorphic functions using unification.

April 11 (Tue), 2023 Interpretation as presented in Ch.5 [R] with inference rules. We cover up to section 5.5 included. Intermediate code generation: Ch.6 [M] started (through section 6.3).

April 13 (Thu), 2023 HW10 assigned, due April 20: Exercises 6.1-6.3 [M]. Discussion of HW9; no penalty for HW9 turned in by class time next Tuesday. Example of the difference between eager and lazy evaluation: cond/3 vs. if-then-else in ML, shown using the SML-NJ interpreter. Intermediate code generation: Ch.6 [M] through parts of section 6.6.

April 18 (Tue), 2023 Instructor announces that the midterm exam will be open book and notes, but only printed or handwritten material (on paper) is allowed; no electronic devices of any sort. Ch.6 [M] (Intermediate-Code Generation) completed. Ch.7 [M] (Machine-Code Generation) completed. Ch.8 [M] (Register Allocation) started.

April 20 (Thu), 2023 The final will be open book and comprehensive; only the textbooks are allowed; no handwritten notes; no electronic devices. A printout of the textbook is allowed. Students are advised to work out te following problems from [M] to prepare for the exam: 4.2, 5.2, 6.10, 7.2 (do the comparison!), and 8.1. Ch.8 [M] (Register Allocation) completed. Some comments on Functions, using the SimpleSem evaluator to explain the concepts of activation record with return pointers and dynamic links. End of course.