Due Dates
Unless otherwise specified, Learning Group Assignments should be completed for the next lecture day.
Semester Calendar
,Date  Lecture Title  Assignment(s)  Lecture & Assignment Goals 

Notes  
Mon May 4  Final Exam  "Socially distanced" optional final exams, by appointment this week. Please send an Email or Matrix message with:
I'll get back to you with an official time. The final exam is cumulative, here is a list of learning goals covered. 

Thu Apr 30 
Dead Day 

Wed Apr 29  Quiz 3  LG Assignment:  
Here is a list of learning goals covered by the last quiz. Remote Learning Quiz Prep


Wed Apr 29 
Last Withdrawal  All Students 

Mon Apr 27  Lecture 
LG Assignment:
Individual Assignment: ZOBOS (due Thu 7 by 11:59PM) is the (by choice) final project. 

ZOBOS (due Thu 7 by 11:59PM) is available, in stable draft form, for your review. 

Fri Apr 24  Register Allocation  LG Assignment: 
What is an immediate operand of a machine instruction? How do these affect register counting and allocation? How can machine code for expression tree valuation be efficiently constructed? Know the SethiUllman numbering algorithm for expression trees. What is register spilling? What is register targeting in the context of register allocation in expression trees? Why would it be advantageus to reorder (a+b)+(c+d) into ((a+b)+c)+d? Why can this NOT be done by a compiler? In onthefly register allocation, what are allocatable registers, reserved registers, and work registers. What is a pseudo register or virtual register? 
Wed Apr 22  Symbol Tables  LG Assignment: 
What can the RHS of an What does the LHS of an Given a grammar for assignment operations, identify the rule that permits dereferencing. What is the definition of dereferencing? Be able to compare and contrast two approaches: one symbol table for all scopes and separate symbol table for each scope Describe a common simple data structure for maintaining a compiler's namespace. What information is associated with a symbol? Name 3 distinct items. What is the namespace of a compiler? What does the namespace store? What special properties of names suggest a relatively simple data structure be used? 
Mon Apr 20  Parsing WrapUp 
LG Assignment:
Individual Assignment: WRECK (due Fri 1 by 11:59PM). 
The author suggests an AST node have access to what collection of other "nearby" nodes? What is the common AST node structure associated with a sequence or block of statements? What is the common AST node structure associated with a What is the common AST node structure associated with a What is the common AST node structure associated with an What is the common AST node structure associated with an What is the difference between a concrete syntax tree and an abstract syntax tree (AST)? What four critcal functions does the author recommend for AST processing? What do they do? Understand the shiftreduce parsing algorithm (given a LR parsing table or a simple grammar). What are semantic actions? What are semantic values? What is syntax directed translation (SDT)? How are semantic actions different than syntactic actions? Learn how to express logic for parse tree simplification during construction (AKA: syntax directed translation). How are synthesized attributes different than inherited attributes in SDT? How can a λ rule be used to implement forced semantic actions? What is Rule Cloning and what is its downside in parser implementation? 
LGA check resources: everything in one tarball or individual downloads: checksillylexing.txt, fischer41.cfg, fischer41t_src.tok, cytron67.cfg, ptvischeck.pdf. The LR Parsing Algorithm and pseudo code as well. Yet another example of LR Knitting step by step (textbook grammar 7.14 and figure 7.18). 

Fri Apr 17 – Sun Apr 19 
EDays 

Wed Apr 15  LALR stepbystep 
How are Item Follow Sets formed? Know what an Item Set and its Progress Marker represent. Be able to calculate Closure and Goto for LR Item Sets. How does LALR table generation differ from SLR table generation? How does LALR(1) uses a finegrained approach to Follow Sets to solve SLR(1) conflicts.? How is the LALR propagation graph formed? Be able to interpret LALR item sets, propagation graphs (Π), and item follow sets to determine their missing elements, flaws, or correctness. Understand the LALRClosure algorithm and how (why) it is different than SLR Closure. Understand the LALRGoto algorithm and how (why) it is different than SLR Goto. 

LALR step by step lecture slides and example LALR parse with the "knitting algorithm". 

Mon Apr 13  Silly Lexing 
LG Assignment:
LGA will be checked on Monday; some of you might actually have full blown LL(1) compilers by then! 
Given a grammar and its LL(1) parsing table, show how a parse tree is created from a token stream. How do you build an LL(1) parsing table from a grammar that is LL(1)? How is a predict set calculated from first sets, follow sets, and "derives to λ"? How are Item Follow Sets formed? Know what an Item Set and its Progress Marker represent. Be able to calculate Closure and Goto for LR Item Sets. How does LALR table generation differ from SLR table generation? How does LALR(1) uses a finegrained approach to Follow Sets to solve SLR(1) conflicts.? How is the LALR propagation graph formed? How are Follow Sets and the grammar's Item Set graph (CFSM) used to construct SLR parsing tables? What is a token and a token stream in "compiler speak"? 
LALR Challenge Question and lecture slides. checksillylexingpre.txt is a "prelook" of what your group
work check will look like in lecture. Names have been changed to protect the innocent 

Fri Apr 10  LALR Tables  LG Assignment: 
How are Item Follow Sets formed? Know what an Item Set and its Progress Marker represent. What is a reducereduce conflict in an LR table construction algorithm? What is a shiftreduce conflict in LR table construction? Be able to calculate Closure and Goto for LR Item Sets. How does LALR(1) uses a finegrained approach to Follow Sets to solve SLR(1) conflicts.? How is the LALR propagation graph formed? 
Lecture slides for LALR parsing also contain my "prosey" descriptions of LALR algorithms. Pseudo code flavored equivalents are: LALRClosure and LALRGoTo. 

Wed Apr 8  Quiz 2 
LG Assignment:
Individual Assignment: FINALLY, Please read §6.5 of the text in the preparation for the next lecture. The first third covers SLR(k=1) table construction, the latter portion covers LALR(k=1) which uses the most finegrained approach to follow sets we will study. 
How do reducereduce conflicts arise in the LALR(1) table generation algorithm? How does LALR(1) uses a finegrained approach to Follow Sets to solve SLR(1) conflicts.? How is the LALR propagation graph formed? 
Here is a list of learning goals covered by the second quiz. Remote Learning Quiz Prep


Mon Apr 6  !SLR Languages  LG Assignment: 
What is a reducereduce conflict in an LR table construction algorithm? What is a shiftreduce conflict in LR table construction? 
Fri Apr 3  SDT and ASTs  LG Assignment: 
What is the difference between a concrete syntax tree and an abstract syntax tree (AST)? How are Item Follow Sets formed? Know what an Item Set and its Progress Marker represent. Be able to calculate Closure and Goto for LR Item Sets. What is syntax directed translation (SDT)? Learn how to express logic for parse tree simplification during construction (AKA: syntax directed translation). 
Wed Apr 1  COVID Syllabus Review  LG Assignment: 
Be able to process a parsetree for REs creating a structure for an equivilant NFA. Be able to convert a RE (in the book's notation) to an equivalent NFA. 
Mon Mar 30  All Your Matrix are Ours  
Matrix Query: I get "Key Backup" admonitions for every device x browser I use, I have done this once  what is the worst case scenario of not doing this on every device? checklritemsets.tar.bz2 go go go! 

Sat Mar 21 – Sun Mar 29 
Spring Break 

Mon Mar 16 – Mon Mar 23 
COVID19 no lecture; be optimistic! These sorts of things happen, sometimes with awesome results (#3)! 

Fri Mar 13  Return Midterm & Remote Learning Update 
LG Assignment:
lgalritemsets (checked on Monday the 30th) Individual Assignment: LUTHER (due Wed Apr 15 by 11:59PM) is official. Grading script arriving soon. 
Be able to cite examples of implementation challenges and techniques for "production" token scanner. 
Wed Mar 11  LR Item Sets 
LG Assignment:
lgalritemsets (checked on Monday the 30th) 
In terms of deciding which production rule to use, what is the fundamental advantage of LR parsers over LL parsers? Know what an Item Set and its Progress Marker represent. Understand the shiftreduce parsing algorithm (given a LR parsing table or a simple grammar). Be able to calculate Closure and Goto for LR Item Sets. What important property do LR(1) parsers have with respect to the DBL language? 
Here are my description of the critical algorithms, both prosey as well as pseudo code for Closure, GoTo and forming the SLR table. 

Mon Mar 9  Knitting a Parser  LG Assignment: 
If a LR(k) parsing table can be formed from a grammar G, what ambiguity conclusion can be made about G? In terms of deciding which production rule to use, what is the fundamental advantage of LR parsers over LL parsers? Understand the shiftreduce parsing algorithm (given a LR parsing table or a simple grammar). What do to the L, R, and k stand for in LR(k) parsing? What type of derivation do "bottumup" parsers use (generate)? What important property do LR(1) parsers have with respect to the DBL language? 
LUTHER (due Wed Apr 15 by 11:59PM) is really really close. LR tables intro slides and parsing steps for the prefix sum and DBL. 

Fri Mar 6  Midterm Exam  Learning goals covered by the exam are here. 

Wed Mar 4  LR Parsing Intro  
No LGA, but there is a midterm on Friday! 

Mon Mar 2  LL(1) Limitations  LG Assignment: 
Be able to write a nontrivial grammar with recursive rules. Be able to factor out common prefixes in order to make an LL(1) grammar. Given a grammar and its LL(1) parsing table, show how a parse tree is created from a token stream. How are left recursive rules refactored so that a grammar might be processed with an LL(1) parser? How are grammars with common prefixes that create intersecting predict sets refactored to become LL(1) languages? What does a production rule written with left recursion look like? What important property do LL(k) parsers have with respect to the DBL language? What is the DBL, how is it connected to the ubiquitious ifelse in programming? 
Group participation points for the correct first and follow sets: submit your results for predictsettest0.cfg and predictsettest1.cfg in a single tarball or zip archive on the course website. Just one submission per group. (Incorrect results do not particularly mean no credit, I just need to see evidence of progress made on your coding assignment). Group participation points for a reasonable RE grammar: submit your Lecture notes for LL1 limitations and the Dangling Bracket Language. 

Fri Feb 28  LL(1) Parsing  LG Assignment: 
Given a grammar and its LL(1) parsing table, show how a parse tree is created from a token stream. How do you build an LL(1) parsing table from a grammar that is LL(1)? Be able to write a nontrivial LL(1) language with recursive rules and operators (precedence and associativity). 
Students may find my python script treetographvis helpful in visualizing their code results. The the pydoc string in the file for example usage. You will want to
or invoke as an argument of


Wed Feb 26  LL(1) parsing  LG Assignment: 
Given a grammar and its LL(1) parsing table, show how a parse tree is created from a token stream. How are left recursive rules refactored so that a grammar might be processed with an LL(1) parser? How are grammars with common prefixes that create intersecting predict sets refactored to become LL(1) languages? How do you build an LL(1) parsing table from a grammar that is LL(1)? What does a production rule written with left recursion look like? 
Mon Feb 24  LL(1) Tables 
Individual Assignment:
Due date pushed for NFAMATCH... (due Fri Feb 28 by 11:59PM). 
Given a grammar and its LL(1) parsing table, show how a parse tree is created from a token stream. How do you build an LL(1) parsing table from a grammar that is LL(1)? What property of it's predict sets make a grammar not LL(1)? 
CFG for challenge question show_chlpredictsets.pdf group question from today. Download lecture notes, or all the lecture resources. 

Fri Feb 21  Predict Sets  LG Assignment: 
How are topdown parsers that don't use LL tables constructed? How is a predict set calculated from first sets, follow sets, and "derives to λ"? What do the two Ls and the k stand for in "LL(k)" parsing? What is a predict set? What property of it's predict sets make a grammar not LL(1)? 
Wed Feb 19  CFG Algorithms in Detail  LG Assignment: 
Determine what terminals are in the first set of a grammar sequence. Determine what terminals are in the follow set of a grammar symbol. Determine whether a "symbol derives to λ". Gain experience and insight into the software design and tradeoffs of a context free grammar class (object, API). 
We discussed three algorithms today  these are critical for our future development of "table driven" parsing engines: derivesToLambda, firstSet and followSet; and the slides of course For those of you who don't like typing, here is the sample grammar used in the LGA. 

Mon Feb 17 – Tue Feb 18 
Presidents' Day Break 

Fri Feb 14  Return Quiz & New Groups 
Individual Assignment:
No learning group assignment for Wednesday... 

You've been working on NFAMATCH (due Fri Feb 28 by 11:59PM), yes? 

Wed Feb 12  Quiz 1  Here is a list of learning goals covered by the first quiz. 

Mon Feb 10  Quiz prep  LG Assignment:  
Fri Feb 7  Grammar Follows 
LG Assignment:
Individual Assignment: NFAMATCH (due date pushed) (due Fri Feb 28 by 11:59PM) 
Determine what terminals are in the first set of a grammar sequence. Determine what terminals are in the follow set of a grammar symbol. Determine whether a "symbol derives to λ". Be able to optimize a DFA to its smallest, unique form. Be able to convert an NFA to a (unoptimized) DFA. Understand how project submissions will be built, how Understand and implement token matching given an optimized DFA transition table. 
Critical CFG algorithm ideas.... Note: many online references put Now, when we get to building a parsing engine, we will need to artificially add A Certainly, reading through the writeup is the first step. You can earn "bounties" (in the for of participation points) if you are the first to report an error or ambiguity in the writeup (or the submission requirements). The caveat being it must be an error that would reasonably lead to misinformation. While I would love to here about typos or misspellings, I'm not sure they the warrant course credit. 

Wed Feb 5  Grammar Firsts  LG Assignment: 
Determine what terminals are in the first set of a grammar sequence. Determine whether a "symbol derives to λ". What is a parse tree, what characteristics does it have? 
Tue Feb 4 
Career Day 

Mon Feb 3  No Lecture  
Sorry for the inconvenience, we will reconvene on Wednesday. 

Fri Jan 31  Ambiguity in Grammars  LG Assignment: 
Given a grammar, be able to derive a valid sentence of the grammar. How are leftassociative and rightassociative connected to recursive production rules? Be able to deduce associativity and precedence rules for operators in a CFG. Given a binary operator, △, know how to write its production rule for left or right associativity. Given two binary operators △ and □ , know how to write a simple grammar to express their relative precedence. Can a BNF grammar represent different languages than a CFG? What is different between a BNF grammar and a CFG? What do the two Ls and the k stand for in "LL(k)" parsing? In what way are REs limited in their description of languages? What features of a language are REs able to describe? 
Challenge question matching nested structures with regular expressions. CFG algorithm ideas. 

Wed Jan 29  Context Free Grammars  LG Assignment: 
Be able to identify ambiguous grammars, what demonstrates an ambiguous grammar? Given a grammar, be able to derive a valid sentence of the grammar. Know the difference between a leftmost derivation and a rightmost derivation. Know the notational conventions for CFGs used in the book. What are terminals, nonterminals, λ, and $ in a CFG? What does it mean when a grammar is ambiguous? What is a sentential form? Be able to design simple languages and grammars with nested productions and recursive rules. What is a regular grammar? What two production rule patterns are associated with regular grammars? 
Mon Jan 27  DFAs back to REs 
LG Assignment:
Read §44.1 (inclusive), prepare to discuss next lecture. 
Given a grammar, be able to derive a valid sentence of the grammar. Know the difference between a leftmost derivation and a rightmost derivation. What are terminals, nonterminals, λ, and $ in a CFG? What is a sentential form? Be able to convert a DFA into a RE (in the book's notation). Know how to convert a DFA to a regular expression using the T1, T2, T3 fundamental operations. Know the T1, T2, T3 DFA to RE operations  you don't need to know which is which. Be familiar with construction algorithms and proofs using the RE≡NFA≡DFA≡RE equivalency. 
My p/code for the DFA to RE algorithm. Reverse(R) solution using the RE≡NFA≡DFA relationship. 

Fri Jan 24  Optimizing DFAs  LG Assignment: 
Be able to optimize a DFA to its smallest, unique form. Be able to cite examples of implementation challenges and techniques for "production" token scanner. 
My p/code for (almost) optimizing DFAs. 

Wed Jan 22  NFA to DFA  LG Assignment: 
Be able to convert a DFA into a RE (in the book's notation). How are the terms regular language, regular set connected to DFAs? 
NFA to DFA lecture notes. 

Wed Jan 22 
Census Day 

Mon Jan 20 
Martin Luther King Day Holiday 

Fri Jan 17  NFAs  LG Assignment: 
Be able to optimize a DFA to its smallest, unique form. What are dead states and unreachable states in FAs? What is the difference(s) between a NFA and a DFA? Be able to convert an NFA to a (unoptimized) DFA. Be able to convert a RE (in the book's notation) to an equivalent NFA. 
Note that figure 3.22 of the text is incorrect. There should be a λ transition from the starting node (to the left of the "FA for A" box) to the accepting node to the right of the box. Without this, the figure actually shows the NFA for A^{+}. 

Wed Jan 15  DFAs ≡ REs  LG Assignment: 
Cite two ways that a FA (DFA or NFA) may be represented in computer memory. Understand their tradeoffs. Given the rules for Lex, be able to write REs compatible with Lex. Understand the basic constructs in a How are the terms regular language, regular set connected to DFAs? 
Some important figures from the text. 

Mon Jan 13  Regular Expressions  LG Assignment: 
What are runtime semantics? What features of a language are REs able to describe? Be able to construct a RE (in the book's notation) for particular token patterns. How are the terms regular language, regular set, and regular expression interrelated? Know the (book's) notation and terminology for regular expressions. Know the meaning of RE notations: AB, AB, A∗, A^{+} and A^{κ} (κ a constant positive integer) Know the meaning of λ, single characters s ∈ Σ, and T ⊆ Σ as they relate to the book's RE notation. What are the three basic operations in REs from which all other operations may be derived. 
Fri Jan 10  Groups!  LG Assignment: 
A context free grammar defines what particular facet of a programming language? What does a CFG guarantee? Complete the following: "CFGs confirm a program has valid , static semantics confirm a program is . What are static semantics? Cite examples. Other than pure and augmented machine code, what other type of machine code might a compiler generate? What is augmented machine code? How does it differ from pure machine code? What is bootstrapping a compiler? Have all compilers been bootstrapped? What is pure machine code? Be able to cite an example. What is the difference between absolute binary and relocatable binary forms of machine code? What is the difference between the target of a compiler and the kind of machine code generated by the compiler? What other target code format, other than absolute and relocatable is a common output of compilers? How is an interpretter different than a compiler, are there advantages to an interpretted language? What are runtime semantics? 
Grammars to Parse Trees to Code (nonsemantic checking examples). You can also geek out on the shunting yard algorithm but this isn't in the learning goals for the course. 

Fri Jan 10 
Graduate student registration deadline 

Wed Jan 8  Introductions 
Individual Assignment:

Understand how learning groups will be used in this course, and what the expectations are for your shared work. Understand how your course grade will be calculated and how your participation points will may affect your grade. Understand the Collaboration Policy for individual assignments. 
What about Canvas? We won't use Canvas in this course. Here are the intro slides from the first lecture. 

Tue Jan 7 
Classes begin 