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
Sat May 9	Final Exam	The final exam is scheduled for May 9 8-10AM, in VC160 (our lecture room, I believe). A reminder: you can complete either the final project or the final exam, but you can't do both. DSA Students: you may not know whether you plan on doing the final project or sitting for the written exam --- but be smart and make a reservation with the testing center now! These are easy to cancel but very hard to make at the last minute!
Wed May 6	Quiz 3
Wed May 6	Classes End
Wed Apr 22	ZOBOS	Individual Assignment: ZOBOS (due Wed May 6 by 11:59PM)	What is a semantic error? At what stage of parsing might it be detected? Understand the shift-reduce parsing algorithm (given a LR parsing table and a simple grammar). What is a lexical error? Know the (limited) capabilities of semantic actions in a simply implemented LR parser. Understand the delayed execution technique of implementing SDT and semantic actions in an LR parse.
ZOBOS (due Wed May 6 by 11:59PM)
Mon Apr 20	Stack Management	LG Assignment: lga-framed-stack Individual Assignment: ZOBOS (due Wed May 6 by 11:59PM)	What is a semantic error? At what stage of parsing might it be detected? Cite two pieces of information stored as *control information* in a stack frame. How is the *location* of local variables in a function determined? How are these addresses accessed in modern CPUs? Know the difference between procedure level and block level frame allocation. What function specific information is commonly stored in the *symbol table? Why is the symbol table the ideal structure? What is a dynamic link* of a stack frame? Why is it dynamic? What is a frame or *stack frame? What language construct implies the use of stack frames? What is a local variable? Where in memory is a local variable typically stored? What is the difference between callee* and caller saved registers? Which might not exist for a function and why? An activation record is another name for what stack associated term? Distinguish between the stack-top register and a frame pointer. How are each used in stack and procedure management? Distinguish the use of data areas: global data, heap allocated data, stack allocated data. When are each used? What is an *object pointer, how is it used in the addressing of variables in modern CPUs? Understand the shift-reduce* parsing algorithm (given a LR parsing table and a simple grammar). What is a lexical error? Know the (limited) capabilities of semantic actions in a simply implemented LR parser. Understand the delayed execution technique of implementing SDT and semantic actions in an LR parse.
Slides for basic stack management. ZOBOS (due Wed May 6 by 11:59PM)
Mon Apr 20	E-Days (no Assessment)
Fri Apr 17 – Sun Apr 19	E-Days (No Class Days)
Wed Apr 15	Efficient Symbol Tables	LG Assignment: No LGA	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 namespace data structure can be used? What are *active scopes? What is a shadowed identifier? What is the current scope? What is the downside to implementing a full blown symbol table for each scope* vs one global table? What operations (API) is required of a symbol table implementation? Cite or describe a simple data structure to manage symbols and their attributes. In the author's SymTable structure, what steps are required to open or close as scope? In the author's SymTable structure, what steps are required to determine if an identifier is shadowed? What are V, L, and H in the author's SymTable structure? What is the scope display of the authors SymTable structure? What is it used for? What is static scoping?
Symbols and Names slides.
Mon Apr 13	Symbol Tables	LG Assignment: lga-symbol-tables	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 namespace data structure can be used? What are *active scopes? What is a shadowed identifier? What is the current scope? What is the downside to implementing a full blown symbol table for each scope* vs one global table? What operations (API) is required of a symbol table implementation? Cite or describe a simple data structure to manage symbols and their attributes. In the author's SymTable structure, what steps are required to open or close as scope? In the author's SymTable structure, what steps are required to determine if an identifier is shadowed? What are V, L, and H in the author's SymTable structure? What is the scope display of the authors SymTable structure? What is it used for? What is static scoping?
Symbols and Names slides.
Fri Apr 10	SDT and Semantic Actions	LG Assignment: lga-sdt	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 `repeat-until` or `repeat-while` post-test loop? What is the common AST node structure associated with a `while-do-done` pre-test loop? What is the common AST node structure associated with an `if-then` or `if-then-else` structure? What is the common AST node structure associated with a `switch` or `if-elif-elif-elif-else` multi-way branch? What is the difference between a concrete syntax tree and an abstract syntax tree (AST)? What four critical functions does the author recommend for AST processing? What do they do? 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? 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 namespace data structure can be used? What are *active scopes? What is a shadowed identifier? What is the current scope? What is the downside to implementing a full blown symbol table for each scope* vs one global table? What operations (API) is required of a symbol table implementation? Cite or describe a simple data structure to manage symbols and their attributes. In the author's SymTable structure, what steps are required to open or close as scope? In the author's SymTable structure, what steps are required to determine if an identifier is shadowed? What are V, L, and H in the author's SymTable structure? What is the scope display of the authors SymTable structure? What is it used for? What is static scoping?
SDT nitty-gritty details and terms, example of textbook's semantic actions. Symbols and Names slides.
Wed Apr 8	No lecture.
(Only four WRECKs turned in so far, hint, hint.)
Mon Apr 6	Quiz 2	Individual Assignment: WRECK (due Fri Apr 10 by 11:59PM)	What is a semantic error? At what stage of parsing might it be detected? What is the difference between a concrete syntax tree and an abstract syntax tree (AST)? What is a syntax error and how is it detected in LL table based parsing methods? Be able to convert a RE (in the book's notation) to an equivalent NFA. Be able to process a parse-tree for REs creating a structure for an equivilant NFA. What is a lexical error? What is syntax directed translation (SDT)?
Here is a list of learning goals covered by the second quiz. A review video is here.
Fri Apr 3	Lecture continued	LG Assignment: lga-quiz-prep-2	How are Item Follow Sets formed? Know what an Item Set and its Progress Marker represent. What is a reduce-reduce conflict in an LR table construction algorithm? What is a shift-reduce conflict in LR table construction? Be able to calculate Closure and Goto for LR Item Sets. How does LALR(1) uses a fine-grained approach to Follow Sets to solve SLR(1) conflicts.? How is the LALR propagation graph formed?
lga-lr-itemsets selected solution resources: question 1a, question 1b, the missing states are `betty`, `angela` and `jacqueline`, questions 2 and 3, question 4 and question 5. As requested: solution page for question 5. Lecture slides for LALR parsing also contain my "prosey" descriptions of LALR algorithms. Pseudo code flavored equivalents are: LALRClosure and LALRGoTo.
Fri Apr 3	Last Day to Withdrawal from Courses
Wed Apr 1	LR Parsing wrap-up	LG Assignment: lga-lr-itemsets	How are Item Follow Sets formed? 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 and a simple grammar). What is a reduce-reduce conflict in an LR table construction algorithm? What is a shift-reduce conflict in LR table construction? Be able to calculate Closure and Goto for LR Item Sets. What important property do LR parsers have with respect to the DBL language? How are Follow Sets used in SLR to resolve reduce-reduce or shift-reduce conflicts in LR(0) tables? How are Follow Sets and the grammar's Item Set graph (CFSM) used to construct SLR parsing tables?
Solutions to lga-lr-knitting knitting-algorithm questions: #1, #2, #3, #4, #5 and #6. Shift-reduce LR(0) and SLR(1) table generation lecture slides are here. I won't require that you implement LR(0) or SLR(1) table generation logic in this course, but you will be expected to know how LR item sets and the CFSM is formed (which is to say, be able to demonstrate this in LGAs, quizzes, or exams). While you aren't required to implement the LR table generation algorithms, this is Mines and some students will really want to implement this stuff. Here are the algorithms in both prose and pseudo code closure, goto and SLR table generation.
Mon Mar 30	Charismatic Flying Spaghetti Machine		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 and a simple grammar). What important property do LR parsers have with respect to the DBL language?
Solutions to lga-lr-knitting knitting-algorithm questions: #1, #2, #3, #4, #5 and #6.
Mon Mar 23 – Fri Mar 27	Spring Break
Fri Mar 20	No lecture	Individual Assignment: WRECK (due Fri Apr 10 by 11:59PM)	What is a semantic error? At what stage of parsing might it be detected? What is the difference between a concrete syntax tree and an abstract syntax tree (AST)? What is a syntax error and how is it detected in LL table based parsing methods? Be able to convert a RE (in the book's notation) to an equivalent NFA. Be able to process a parse-tree for REs creating a structure for an equivilant NFA. What is a lexical error? What is syntax directed translation (SDT)?
Wed Mar 18	The Knitting Parser	LG Assignment: This LGA will be checked on the Monday following spring break. lga-lr-knitting Individual Assignment: Optional reading section 6.3.	If a LR(k) parsing table can be formed from a grammar G that generates or defines language L, what ambiguity conclusion can be made about L? 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 and a simple grammar). What are the LR parsing algorithm's conditions for accepting an input sequence (source) as a sentence in the language? What do to the L, R, and k stand for in LR(k) parsing? What is a syntax error and how is it detected in LR table based parsing methods? What type of derivation do "bottom-up" parsers use (generate)? What important property do LR parsers have with respect to the DBL language?
LR Parsing Algorithm slides and pseudo code as well. Enjoy! Pseudo code for shift-reduce parsing.
Mon Mar 16	WRECK	Individual Assignment: WRECK (due Fri Apr 10 by 11:59PM) lga-code-prep (basically a laundry list of "code goals")	What is a semantic error? At what stage of parsing might it be detected? What is the difference between a concrete syntax tree and an abstract syntax tree (AST)? What is a syntax error and how is it detected in LL table based parsing methods? Be able to convert a RE (in the book's notation) to an equivalent NFA. Be able to process a parse-tree for REs creating a structure for an equivilant NFA. What is a lexical error? What is syntax directed translation (SDT)? Learn how to express logic for parse tree simplification during construction (AKA: syntax directed translation).
Here is the group worksheet for evaluating your peer's pseudo code solutions.
Fri Mar 13	NFAs from RE expression trees	LG Assignment: lga-re-nfagen	Be able to convert a RE (in the book's notation) to an equivalent NFA. Be able to process a parse-tree for REs creating a structure for an equivilant NFA.
Lecture slides for generating NFAs from RE ASTs.
Wed Mar 11	Midterm Exam	Learning goals covered by the exam are here. The video review is here.
Mon Mar 9	SDT and ASTs	LG Assignment: checked on Friday , not exam day lga-re-sdt Individual Assignment: Graduate students only: assign-rlarell.pdf (due Fri 20 by 11:59PM).	What is the difference between a concrete syntax tree and an abstract syntax tree (AST)? What is syntax directed translation (SDT)? Learn how to express logic for parse tree simplification during construction (AKA: syntax directed translation). Be able to express semantic actions in the context of an LL parse where a node's parent, descendents, and left-hand siblings are known.
Download the slides for RE Grammar and LL(1) SDT to the RE's AST.
Fri Mar 6	Lecture continued	LG Assignment: lga-ll1-limitations	Be able to eliminate left recursion from a grammar in order to make it LL(1) How are left recursive rules refactored so that a grammar might be processed with an LL(1) parser?
You have three different submission slots for this learning group check. This is so one person does not have to collect all the responses for a single submission --- these are also nicely partitioned by LGA questions. *Please submit a single archive (tarball, zip) each upload slot. For the lgcPredictSets* slot: post your prediction table or prediction set results for predict-set-test0.cfg and predict-set-test1.cfg. For the *lgcParsing* slot: for full credit run the language described by this cfg and the input source in this file through your parser (of course, you'll probably need to use the predict set code for this). Post evidence of your results. *If this can't be accomplished,* then at least post some evidence of work done or error messages encountered attempting this parse --- you'll get some amount of partial credit at least. For the *lgcChangelog* slot: post your group's repo change log and/or a summary of which group members worked on which questions. Group question non-trivial left factorization
Wed Mar 4	LL(1) Limitations	LG Assignment: No LGA for tonight (lga-ll1-parsing) coding will be checked next lecture.	Be able to factor out common prefixes in order to make an LL(1) grammar. 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? 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?
Lecture notes for LL1 limitations and the Dangling Bracket Language.
Mon Mar 2	LL(1) Parsing	LG Assignment: lga-ll1-parsing (see below for when this LGA will be checked).	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 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 λ"? What are the LL parsing algorithm's conditions for accepting an input sequence (source) as a sentence in the language? What does a production rule written with left recursion look like? What is a predict set? What is a syntax error and how is it detected in LL table based parsing methods? 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? What property of it's predict sets make a grammar not LL(1)? 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? Be able to write a non-trivial LL(1) language with recursive rules and operators (precedence and associativity).
Submit to the course gradescope site in the `lgcFirstFollow` slot (in a .tar, .zip, or compressed tar archive): your derivesToLamba, firstSet and followSet analysis for this grammar. either your group repo's change log (which would be !awesome!), or a description (per member) of contributions made. Submit both as simple text files or screenshots; please no invites to your repo or URLs to pastebins. CFG for challenge question. show_chl-predict-sets.pdf group question from today. Here are the derives to λ, first, and follow sets for the grammar, if you'd like to check them against your lga-predict-sets CFG group code. Lecture notes for LL1 limitations and the Dangling Bracket Language. lga-ll1-parsing The coding questions will be checked on Friday, the 6th. The RE Grammar question will be checked on Wednesday the 4th. Students may find my python script tree-to-graphvis helpful in visualizing their code results. See the pydoc string in the file for example usage. You will want to `$ chmod +x tree-to-graphvis` or invoke as an argument of `python`: `$ python3 tree-to-graphvis <parse.txt \| dot -T png -o parse.png`
Fri Feb 27	Predict Sets & LL(1) Languages Continued	LG Assignment: lga-ll1-tables	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 are the LL parsing algorithm's conditions for accepting an input sequence (source) as a sentence in the language? What does a production rule written with left recursion look like? What is a syntax error and how is it detected in LL table based parsing methods? What property of it's predict sets make a grammar not LL(1)? 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?
Here is pseudo code for the LLT parsing algorithm we'll work through in lecture today. Download lecture slides showing predict calculations and data structure evolution during an LL parse.
Wed Feb 25	Predict Sets	LG Assignment: lga-predict-sets	Given a grammar and its LL(1) parsing table, show how a parse tree is created from a token stream. How are top-down parsers that don't use LL tables constructed? 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 λ"? What are the LL parsing algorithm's conditions for accepting an input sequence (source) as a sentence in the language? What do the two Ls and the k stand for in "LL(k)" parsing? What is a predict set? What is a syntax error and how is it detected in LL table based parsing methods? What property of it's predict sets make a grammar not LL(1)?
Here is pseudo code for the LLT parsing algorithm we'll work through in lecture today. Download lecture slides showing predict calculations and data structure evolution during an LL parse. "Introducing predict sets" slides.
Mon Feb 23	Cfg Code & Predict Sets	LG Assignment: lga-cfg-code	Gain experience and insight into the software design and trade-offs of a context free grammar class (object, API). How is a predict set calculated from first sets, follow sets, and "derives to λ"? What is a predict set?
Students will want to complete their (previous) learning group evaluations sooner than later --- future course uploads (both programming projects and learning group "checks") require your survey to be completed. No reason to stress out over a deadline when you don't need to... For those of you who don't like typing, here is the sample grammar used in the LGA. This LGA is the same assignment for everyone, so there is no reason you need a group to divvy up the work. If you're group has already decided on one or two (three?) preferred languages to share code in, you are welcome to complete this LGA pair-programming style. "Introducing predict sets" slides.
Fri Feb 20	Quiz 1	Here is a list of learning goals covered by the first quiz.
Wed Feb 18	Quiz prep	LG Assignment: lga-quiz-prep-1 Individual Assignment: NFAMATCH (due Wed 4 by 11:59PM).	How is a predict set calculated from first sets, follow sets, and "derives to λ"? What is a predict set? 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. Be able to convert an NFA to a (unoptimized) DFA. Understand and implement token matching given an optimized DFA transition table.
"Introducing predict sets" slides.
Mon Feb 16 – Tue Feb 17	President’s Day Break (No Class Days)
Fri Feb 13	Grammar Symbol Sets (cont)	LG Assignment: lga-grammar-follows	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 λ". Given a grammar, be able to derive a valid sentence of the grammar.
Some pseudo code for derives to lambda, first sets and follow sets; and some lecture slides. Note: many online references put `$` in the FollowSet of S, the starting symbol or goal of a grammar's production rules. Our book does not, it simply complicates the definition of a symbol's FollowSet for no apparent reason or advantage. *Now,* when we get to building a parsing engine, we will need to artificially add `$` to S's FollowSet because it will be painfully obvious the parsing algorithm needs this tweak. The end result will be the same as other texts and references --- but I think more intuitive for the student.
Wed Feb 11	First Sets	LG Assignment: lga-grammar-firsts	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 λ". What are terminals, non-terminals, λ, and $ in a CFG? Gain experience and insight into the software design and trade-offs of a context free grammar class (object, API). What is a parse tree, what characteristics does it have?
CFG implementation in code (group question). Introduction to CFG algorithm analysis (first and follow sets)....
Mon Feb 9	Ambiguity in Grammars	LG Assignment: lga-grammar-ambiguity	Be able to identify (seemingly) ambiguous grammars, what demonstrates an ambiguous grammar? 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? When might we suspect that a grammar is *ambiguous? 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? Be able to write a non-trivial LL(1) language with recursive rules and operators (precedence and associativity).
Lecture slides for ambiguous grammars. Lecture slides for arithmetic precedence and associativity expressed through context free grammars.
Fri Feb 6	Context Free Grammars	LG Assignment: lga-cfgs	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 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? In what way are REs limited in their description of languages? What features of a language are REs able to describe? How are the terms regular language, regular set connected to DFAs? How are the terms regular language, regular set, and regular expression interrelated?
Three DFA transition tables for you to test your LGA code on: dfa0-dfa-tt.txt, dfa1-dfa-tt.txt, dfa2-dfa-tt.txt. Submit your aptly named results (optimized `.tt` files) on the course gradescope server in the "lgcOptimalDFA" slot. Please only one student per group submitting for the entire group. You can upload multiple results or an archive file (`zip`, `tar`, `tar.{gz,Z,bz2,xz`.} My solutions for the learning group check: dfa0-optdfa-tt.txt, dfa1-optdfa-tt.txt, dfa2-optdfa-tt.txt. RL limitations and the pumping lemma. You may want to download and have at the ready this grammar from the lecture. Here are the context free grammar intro slides.
Tue Feb 3 – Wed Feb 4	Career Days (No Assessment Days) - No lecture.
Mon Feb 2	RE/NFA/DFA wrap	LG Assignment: lga-optimal-dfa	In what way are REs limited in their description of languages? What features of a language are REs able to describe? Be able to optimize a DFA to a smaller form by reconciling indistinguishable states. Be able to cite examples of implementation challenges and techniques for "production" token scanner.
Challenge question matching nested structures with regular expressions.
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: lga-nfa-to-dfa 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?
`/` C/C++ comment `/` regex group question. 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: lga-nfa 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: lga-dfa 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 `scanner.l` file, and how it can be compiled with external code modules. How are the terms regular language, regular set connected to DFAs?
Finite Automata and DFA slides.
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: lga-regex	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.
Foreign Calls and Runtime Semantics slides. Regular Expressions lecture slides
Wed Jan 14	Groups!	LG Assignment: lga-compiler-overview	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: Obtain the book. Read from the course website: Syllabus sections "Learning Methods" and "Student Evaluation" Syllabus link "Participation Grade" Syllabus link "Collaboration Policy"	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

Compiler Design

Due Dates

Semester Calendar

lga-ll1-parsing