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 |
E-Days |
||
| 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:
lga-lr-itemsets (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:
lga-lr-itemsets (checked on Monday the 30th) |
How are Follow Sets used in SLR to resolve reduce-reduce or shift-reduce 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 shift-reduce 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 shift-reduce 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 "bottum-up" 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 non-trivial 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 if-else in programming? |
|
Group participation points for the correct first and follow sets: submit your results for predict-set-test0.cfg and predict-set-test1.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 non-trivial LL(1) language with recursive rules and operators (precedence and associativity). |
|
Students may find my python script tree-to-graphvis 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_chl-predict-sets.pdf group question from today. Download lecture notes, or all the lecture resources. |
|||
| Fri Feb 21 | Predict Sets | LG Assignment: |
How are top-down 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 trade-offs 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 write-up 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 write-up (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 left-associative and right-associative 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, non-terminals, λ, 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 §4--4.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, non-terminals, λ, 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, A|B, 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 (non-semantic 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 |
||