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  
Wed May 6  Final Exam  The final exam will be 1PM on Wednesday, May 6 in our usual lecture room. 

Thu Apr 30 
Dead Day 

Wed Apr 29  Quiz 3  
Fri Apr 17 – Sun Apr 19 
EDays 

Fri Apr 10 
Last Withdrawal  All Students 

Wed Apr 1  Quiz 2  
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 Fri Apr 10 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) 
How are Follow Sets used in SLR to resolve reducereduce or shiftreduce conflicts? 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 Fri Apr 10 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 