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 | Quiz 3 | ||
| Wed May 6 |
Classes End |
||
| Mon Apr 20 |
E-Days (no Assessment) |
||
| Fri Apr 17 – Sun Apr 19 |
E-Days (No Class Days) |
||
| Fri Apr 3 |
Last Day to Withdrawal from Courses |
||
| Wed Apr 1 | Quiz 2 - no, it's not a joke. | ||
| Mon Mar 23 – Fri Mar 27 |
Spring Break |
||
| Mon Mar 9 | Midterm Exam | ||
| Wed Feb 18 | Quiz 1 | ||
| Mon Feb 16 – Tue Feb 17 |
President’s Day Break (No Class Days) |
||
| Tue Feb 3 – Wed Feb 4 |
Career Days (No Assessment Days) - No lecture. |
||
| Fri Jan 30 | Optimizing DFAs |
LG Assignment:
No LGA over the weekend --- START ON LUTHOR! |
Be able to optimize a DFA to a smaller form by reconciling indistinguishable states.
Be able to describe an algorithm for removing dead and unreachable states in a DFA.
What are dead states and unreachable states in FAs? |
|
Merging indistinguishable states example. Pseudo code for DFA "optimization" (you might want to download and have this available during lecture). Slides for "mostly optimizing" DFAs with the MergeStates algorithm on DFAs. |
|||
| Wed Jan 28 | NFA to DFA |
LG Assignment:
Individual Assignment: LUTHOR (due Mon Feb 9 by 11:59PM). Please review the lecture write-up (see the video link on this schedule page after lecture as well). I'd like to answer any and all questions about this project on Monday, which is when I should have gradescope fixed up. |
Be able to convert a DFA into a RE (in the book's notation).
What is a lexical error? 
Be able to cite examples of implementation challenges and techniques for "production" token scanner.
How are the terms regular language, regular set connected to DFAs? |
|
You may want to download (before lecture) some algorithm PDFs so you have ready access to them while we tease out how they work. NFA to DFA algorithm lecture slides. I'm sure I won't get through the entirety of the LUTHOR project details. Here is a video review (19m @ 2x speed) from a previous semester (when we were coding in the alamode lab and not with docker and gradescope - but the important elements are the same). The video describes the essential scanner logic for identifying tokens out of an input stream. These are the LUTHOR specific slides used in the video, they are a slightly more visual representation of the write-up explanation in the wiki. |
|||
| Wed Jan 28 |
Census Day |
||
| Mon Jan 26 | NFAs |
LG Assignment:
Individual Assignment: LUTHOR (due Mon Feb 9 by 11:59PM). Please review the lecture write-up (see the video link on this schedule page after lecture as well). I'd like to answer any and all questions about this project on Monday, which is when I should have gradescope fixed up. |
Be able to convert a RE (in the book's notation) to an equivalent NFA.
Be able to optimize a DFA to a smaller form by reconciling indistinguishable states.
What are dead states and unreachable states in FAs?
What is the difference(s) between a NFA and a DFA?
What is a lexical error?
Be able to cite examples of implementation challenges and techniques for "production" token scanner.
Be able to convert an NFA to a (unoptimized) DFA. |
|
I'm sure I won't get through the entirety of the LUTHOR project details. Here is a video review (19m @ 2x speed) from a previous semester (when we were coding in the alamode lab and not with docker and gradescope - but the important elements are the same). The video describes the essential scanner logic for identifying tokens out of an input stream. These are the LUTHOR specific slides used in the video, they are a slightly more visual representation of the write-up explanation in the wiki. Lecture slides on NFAs and REs→NFAs. The motivating challenge question for NFAs. 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+. |
|||
| Fri Jan 23 | LUTHOR! |
Individual Assignment:
LUTHOR (due Mon Feb 9 by 11:59PM). Please review the lecture write-up (see the video link on this schedule page after lecture as well). I'd like to answer any and all questions about this project on Monday, which is when I should have gradescope fixed up. |
What is a lexical error?
Be able to cite examples of implementation challenges and techniques for "production" token scanner. |
|
lga-dfa question three's very large NFA, if you're curious. Be sure to check your solution to question one! I'm sure I won't get through the entirety of the LUTHOR project details. Here is a video review (19m @ 2x speed) from a previous semester (when we were coding in the alamode lab and not with docker and gradescope - but the important elements are the same). The video describes the essential scanner logic for identifying tokens out of an input stream. These are the LUTHOR specific slides used in the video, they are a slightly more visual representation of the write-up explanation in the wiki. |
|||
| Wed Jan 21 | DFAs ≡ REs |
LG Assignment:
Individual Assignment: Complete the "sample" ALPHABETENCODING (due Mon Feb 2 by 11:59PM) assignment. Return to the next lecture with questions or concerns. |
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? |
| Wed Jan 21 |
Last Day to DROP Courses (100% refund) |
||
| Mon Jan 19 |
Martin Luther King Day – Campus Closed |
||
| Fri Jan 16 | 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. |
| Wed Jan 14 | 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. Ugh, I never finished the course overview slides. Here is a video from during the COVID shutdown (eek!). The part where we left off in lecture is about 11m into the video, and slides get wrapped up around 23:45. At 2x speed that's a quick 7m listen |
|||
| Mon Jan 12 | 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. |
|||
| Mon Jan 12 |
Lectures start |
||