CSCE 531 (Spring 2020): Lecture Log

January 14 (Tue), 2020 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 16 (Thu), 2013 Example of using a loop invariant to prove the correctness of a program fragment. Ch.1 [W]: levels of programming languages. Command, expression, declaration. Context-free grammars and BNF notation. Derivation. Sentence. Sentential form.

January 21 (Tue), 2020 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. Syntax trees (also called parse trees). Slides based on Ch.2 [W] (Language processors, including tombstone diagrams, bootstrapping, etc.). Note that Ch.13 of the 2010 edition of Mogesen's textbook is on bootstrapping; this older edition of [M] is available from the author at

January 23 (Thu), 2020 HW1 assigned: exercise 1.4 [M], due on Thursday, January 30. This is also exercise 2.3 in the free version of Torben Mogensen's textbook, which we refer to as [M10] and is linked to the Time Allocation Framework of the course website. Static and dynamic scope: slides 40-46 Ch.3[W]. Phases of the compilation process: slides 4-9 Ch.3[W] and section 1.4[R]. An example of compilation through the three main phases: slides 23-30 Ch.3[W]. Lexical analysis input and output: slides 7-8 Ch.4[W]. Lexical analysis details: regular expressions with examples: slides 1-11 CB13-1-Lexing.pdf; section 1.1 [M].

January 28 (Tue), 2020 Non-deterministic Finite-state Automata (NFAs). Definition and examples. Converting a regular expression to an NFA. Deterministic Finite-state Automata (DFAs). Converting an NFA to a DFA. (Sections 1.2-1.5 [M].)

January 30 (Thu), 2020 HW2 assigned: exercises 1.6, 1.8, 1.9 [M] (2.5, 2.7, 2.8 [M10]), due on Thursday, February 6. Note: you are not required to go through the NFA-to-DFA construction when solving exercises 1.8 and 1.9; please try to construct the DFAs directly. Exploiting the distributive property in the solution of set equations: using a worklist. Minimization of DFAs. Lexers. Properties of regular languages. CB13-1-Lexing.pdf slides completed; Ch.1 [M] completed.

February 4 (Tue), 2020 Project 1a (PR1a) assigned. HW1 solution discussed. Several examples of use of DFA minimization using algorithm 1.4 [M], including: the DFA resulting from exercise 1.4, the DFA of figure 1.9 [M], and exercise 1.7 [M]. Syntax analysis (Ch.2 [M]) started, using slides 16-18 from Cosmin Oancea's set "An Intutitive View of Lexical and Syntax Analysis."

February 6 (Thu), 2020 Syntax analysis (Ch.2 [M]): slides from Cosmin Oancea's set completed. Ambiguous grammars, precedence, associativity, and the complete CF (in EBNF) grammar of the simple programming language CLite (described in: Allen Tucker and Robert Noonan. _Programming Languages: Principles and Paradigms_, 2nd ed. McGraw-Hill, 2007.), using the slides in 330Syntax.pptx.

February 11 (Tue), 2020 HW3 assigned: exercises 2.6 and 2.7 [M], due on Tuesday, February 18. Top-down and bottom-up parsers: the micro-English example from ch.4 [W]. Constructing a top-down recursive descent parser for mini-Triangle, from ch.4 [W]. Slides by Jost Berthold to accompany ch. 2 [M] through the computation of NULLABLE sets using set equations.

February 13 (Thu), 2020 Project 1b (PR1c) assigned, due on Thursday, February 20. LL(1) parsing: an (almost) full example based on Grammars 2.4 and 2.9. Recursive descent and table-driven LL(1) parsers.

February 18 (Tue), 2020 The midterm exam will be on either March 3 or March 5. SLR grammars: Sections 2.13 and 2.14 (partly) [M] with examples.

February 20 (Thu), 2020 Project 1c (PR1c) assigned, due on Thursday, February 27. HW4 assigned: Exercises 2.14 and 2.19 [M], due on Thursday, February 27. For exercise 2.19 part (c), show all steps and, in partocular, draw the NFA for all productions, the NFA with epsilon-transitions, and the DFA obtained by converting the NFA with epsilon-transitions.` Correction of HW3. bnfc with Haskell and the grammar of section 2.10.

February 25 (Tue), 2020 Discussion of updates of PR1c. Exercise 2.14 parts (a) and (b). Please use the grammar shown in class in parts (c) and (d) when completing HW4. Type checking: slides from [W] (chapter 5: slides 1-22), with an emphasis on attribute grammars. Slides 9-11 from Cosmin Oancea's set to support Chapter 5 ("Type Checking") [M].

February 27 (Thu), 2020 The midterm exam will be on Tuesday, March 3. It will cover the material presented through the lecture of February 20. Both textbooks ([M], [R]) are allowed. If students do not have the books, they can bring photocopies of the first two chapters "Lexical Analysis" and "Syntax Analysis" of [M], Appendix A ("Set Notations and Concepts") of [M], and the first two chapters ("Compilation Phases" and "Grammars") of [R]. Type checking: presentation based on ch.4 [R], up to the middle of Section 4.9.

March 3 (Tue), 2020 MIdterm.

March 3 (Tue), 2020 Correction of midterm.

March 24 (Tue), 2020 First class meeting after extended spring break. Classes will be conducted online using Blackboard Collaborated Ultra from today. PR2a assigned, due 2020-03-31. Symbol tables (ch.3 [M]). Items 1-7, 10-11 in the agenda were covered.

March 26 (Thu), 2020 HW5 assigned: Exercises 4.0-4.4 [R], due 2020-04-02. Type checking as presented in Ch.4 [R] through section 4.8, with a detailed example of a proof tree. Starting next Monday, the instructor will have virtual office hours on Blackboard Collaborate Ultra at the usual time for office hours. Items 1-7, 8 through section 4.8 [R], 9, 10, and 12 in the agenda were covered.

March 31 (Tue), 2020 HW6 assigned: Exercise 5.0 [R], due 2020-04-09. PR2b assigned, due 2020-04-14. Starting tomorrow (Wednesday), the instructor will have virtual office hours on Blackboard Collaborate Ultra at the usual time for office hours. Ch.4 [R] was completed. Here is the agenda for the day; we did not do items 9 and 10.

April 2 (Thu), 2020 Ch.4 [M] (Interpretation) in full. Some comments on iterative interpretation. Ch.5 [R] (Interpreters) through section 5.2. Q&A on HW5. Here is the agenda for the day.

April 7 (Tue), 2020 HW7 will consist of exercises 6.1, 6.2, and 6.3 [M]. It is likely to be due in one week. Ch.5 [R] (Interpreters) through section 5.2. Solution for HW5 after the end of class, on recorded lecture. Here is the agenda for the day; we did not do items 10 and 12.

April 9 (Thu), 2020 HW7 assigned: exercises 6.1, 6.2, and 6.3 [M], due on April 16, 2020. Ch.6 [M] (Intermediate Code Generation) in full. Here is the agenda for the day; we did not do item 10.

April 14 (Tue), 2020 PR2b due date moved to April 21, 2020. Update of 2020-04-20: moved to April 23, 2020. Discussion of changes to the syllabus. Ch.7 [M] (Machine Code Generation) in full. Ch.8 [M] (Register Allocation (and Liveness Analysis)) started. Here is the agenda for the day.

April 16 (Thu), 2020 Ch.8 [M] (Register Allocation (and Liveness Analysis)) completed. Here is the agenda for the day. Please note item 10 in the agenda.

April 21 (Tue), 2020 PR2b due date moved to April 23, 2020. Functions (Ch. 9 [M]). Presentation based on Sections 6.2-6.5 [W] and on figures from: Ghezzi, Carlo and Mehdi Jazayeri. _Programming Language Concepts_, 3rd ed. Wiley, 1998. Examples of function execution in machine-like language using the Simplesem simulator. Here is the agenda for the day, with some slight edits.

April 23 (Thu), 2020 Discussion of preliminary version of the final exam. This version may be modified by adding some questions; a new question on functions is likely. The questions already on the preliminary version are almost certainly going to remain. Q&A on PR2b submission. Review of liveness analysis and graph coloring algorithm from [M], Ch.8. Overview of Ch.6 [R] on Code Generation, using the author's slides. Students are reminded of the importance of course evaluations, which are done online using a survey tool in Blackboard. End of course. Here is the agenda for the day, with some edits.