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 5	Job Search w/ Career Center
Sat May 3	Final Exam	The final exam is scheduled for May 3 7-9PM, in AH133. 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 Apr 30	Quiz 3	Here is a list of learning goals covered by the second quiz.
Wed Apr 30	Last lecture day
Mon Apr 28	Lecture	LG Assignment: lga-quiz-prep-3
Fri Apr 25	PC Codes	LG Assignment: lga-code-generation Individual Assignment: I'll except late submissions of CZAR (due Wed Apr 30 by 11:59PM) without penalty, so long as I get them *before* grades are due, which this semester is 12 May.	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? What function specific information is commonly stored in the *symbol table? Why is the symbol table the ideal structure? 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? How are `JUMP`s for programmatic control structures (conditional branches, loops) calculated? Understand how the `treeCG` algorithm operates, its parameters. Understand how the `functionCall` steps of lecture are incorporated into the `treeCG` code generation algorithm. Understand how the `treeCG` algorithm can be modified to support different types of operators. Understand how the `registerNeeds` Sethi-Ullman algorithm can be modified to account for other types of operations (assignment, cast).
Lecture slides for program counter manipulations, `CALL`, `RETURN`, more stack frame managment, `JUMP`s in control structures.
Wed Apr 23	Detailed Function Calls	LG Assignment: No LGA, work on ZOBOS (due Wed Apr 30 by 11:59PM) or WRECK (due Tue Apr 8 by 11:59PM) or CZAR (due Wed Apr 30 by 11:59PM)! Individual Assignment: I'll except late submissions of CZAR (due Wed Apr 30 by 11:59PM) without penalty, so long as I get them *before* grades are due, which this semester is 12 May.	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? What function specific information is commonly stored in the *symbol table? Why is the symbol table the ideal structure? 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? How are `JUMP`s for programmatic control structures (conditional branches, loops) calculated? Understand how the `functionCall` steps of lecture are incorporated into the `treeCG` code generation algorithm.
Group question slides can be downloaded. Lecture slides for program counter manipulations, `CALL`, `RETURN`, more stack frame managment, `JUMP`s in control structures.
Mon Apr 21	Register Counting and Allocation	LG Assignment: lga-register-allocation Individual Assignment: I'll except late submissions of CZAR (due Wed Apr 30 by 11:59PM) without penalty, so long as I get them *before* grades are due, which this semester is 12 May.	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 Sethi-Ullman 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 on-the-fly register allocation, what are allocatable registers, reserved registers, and work registers. What is a pseudo register or virtual register?
Slides for register management and expression tree code generation and pseudo code: Sethi-Ullman counting (including function calls), treeCG() expression tree code generation or treeVR() using virtual registers.
Fri Apr 18	Lecture continued	LG Assignment: No LGA, due to my horrible planning.
Wed Apr 16	Ooopsie Lecture
No LGA today, get WRECK (due Tue Apr 8 by 11:59PM) wrapped up or start ZOBOS (due Wed Apr 30 by 11:59PM)! The author's efficient symbol table design.
Mon Apr 14	ZOBOS	Individual Assignment: ZOBOS (due Wed Apr 30 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 Apr 30 by 11:59PM)
Fri Apr 11 – Sun Apr 13	E-Days - No Friday lectures
Fri Apr 11	Last Day to Withdrawal from Courses (No Refund)
Wed Apr 9	Stack Management	LG Assignment: lga-framed-stack Individual Assignment: ZOBOS (due Wed Apr 30 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. Slides for register management and expression tree code generation and pseudo code: Sethi-Ullman counting (including function calls), treeCG() expression tree code generation or treeVR() using virtual registers. ZOBOS (due Wed Apr 30 by 11:59PM)
Mon Apr 7	Partial lecture lga-stack-management	LG Assignment: No LGA
Fri Apr 4	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.
Wed Apr 2	ASTs and Visitor Patterns for Conventional Languages	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? 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.
The trove of lecture slides on SDT implementations in LR parsers.
Mon Mar 31	SDT and Semantic Actions	Individual Assignment: lga-code-prep (basically a laundry list of "code goals")	What are semantic actions? What are semantic values? What is syntax directed translation (SDT)? How are semantic actions different than syntactic actions? 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? 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.
SDT nitty-gritty details and terms, example of textbook's semantic actions. The trove of lecture slides on SDT implementations in LR parsers.
Fri Mar 28	Quiz 2	Individual Assignment: WRECK (due Tue Apr 8 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. Parsing steps for quiz question 5(a) and 5(b). Note that 5(b) ends with a syntax error which means the parsing slide show simply stops without further processing.
Wed Mar 26	NFAMATCH	LG Assignment: lga-quiz-prep-2 Individual Assignment: WRECK (due Tue Apr 8 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)? 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.
Mon Mar 24	NFAs from RE expression trees	LG Assignment: lga-re-nfagen Individual Assignment: WRECK (due Tue Apr 8 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)?
Lecture slides for generating NFAs from RE ASTs.
Sat Mar 15 – Sun Mar 23	Spring Break
Fri Mar 14	SDT and ASTs	LG Assignment: lga-re-sdt	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.
Wed Mar 12	SLR(1) Wrap up	LG Assignment: No LGA	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 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?
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. 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).
Mon Mar 10	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.
Fri Mar 7	LR Knitting	LG Assignment: 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? 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 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 reduce-reduce conflict in an LR table construction algorithm? What is a shift-reduce conflict in LR table construction? 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)? 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?
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. *Recall that you can post a single archive (tarball, zip) or several individual files to each upload slot* --- the system will sort it out. 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. There are *two* things for the *lgcRegExCFG* slot (you can probably guess this one) --- post your RE cfg with any appropriate commentary to assist in my deciphering and the result of your group's code set's First and Follow set analysis. post your group's repo change log and/or a summary of which group members worked on which questions. 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). Pseudo code for shift-reduce parsing.
Wed Mar 5	The Knitting Parser		Be able to eliminate left recursion from a grammar in order to make it LL(1) Understand the shift-reduce parsing algorithm (given a LR parsing table and a simple grammar). How are left recursive rules refactored so that a grammar might be processed with an LL(1) parser?
LR Parsing Algorithm slides and pseudo code as well. Enjoy! Group question non-trivial left factorization
Mon Mar 3	Midterm Exam	Learning goals covered by the exam are here. A review video is available.
Fri Feb 28	LL(1) Parsing	LG Assignment: lga-ll1-parsing (see below for when this LGA will be checked).	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 is a syntax error and how is it detected in LL table based parsing methods? Be able to write a non-trivial LL(1) language with recursive rules and operators (precedence and associativity).
lga-ll1-parsing The coding questions will be checked on Friday, the 7th. The RE Grammar question will be checked on Wednesday the 5th. 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`
Wed Feb 26	LL Limitations	LG Assignment: lga-ll1-limitations; ignore q2	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 is a predict set calculated from first sets, follow sets, and "derives to λ"? What does a production rule written with left recursion look like? What is a predict set? 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?
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.
Mon Feb 24	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?
Submit to the course website *two things* 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. 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.
Fri Feb 21	No Lecture: snow day
On Monday I'll ask to see results from your group's deriveToLambda, firstSet and followSet.
Wed Feb 19	Predict Sets	LG Assignment: lga-predict-sets	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)?
"Introducing predict sets" slides.
Mon Feb 17 – Tue Feb 18	Presidents' Day Break - No Lectures
Fri Feb 14	CFG Algorithms	LG Assignment: lga-cfg-code	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. Gain experience and insight into the software design and trade-offs of a context free grammar class (object, API).
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... Some pseudo code for derives to lambda, first sets and follow sets; and some lecture slides. 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.
Wed Feb 12	Quiz 1	Here is a list of learning goals covered by the first quiz.
Tue Feb 11	TA Trin will hold "bonus" office hours 3:20-4:30(ish) in the BBW lobby near the piano.
Mon Feb 10	Quiz prep	LG Assignment: lga-quiz-prep-1 Individual Assignment: NFAMATCH (due Fri 21 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.
Fri Feb 7	Grammar Symbol Sets (cont)	LG Assignment: lga-grammar-follows Individual Assignment: NFAMATCH (due Fri 21 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 λ". Given a grammar, be able to derive a valid sentence of the grammar. 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.
Introduction to CFG algorithm analysis (first and follow sets).... 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 5	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 λ". Given a grammar, be able to derive a valid sentence of the grammar. 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).... Some pseudo code for derives to lambda, first sets and follow sets; and some lecture slides.
Mon Feb 3		Individual Assignment: LUTHOR (due Fri 7 by 11:59PM)!	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. Be able to write a non-trivial LL(1) language with recursive rules and operators (precedence and associativity).
Regular volleyball group question slides. Lecture slides for arithmetic precedence and associativity expressed through context free grammars.
Fri Jan 31	Ambiguity in Grammars	LG Assignment: lga-grammar-ambiguity Individual Assignment: Read through project prompt for NFAMATCH (due Fri 21 by 11:59PM).	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). 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?
RL limitations and the pumping lemma. Lecture slides for ambiguous grammars. Lecture slides for arithmetic precedence and associativity expressed through context free grammars.
Tue Jan 28 – Wed Jan 29	Career Days (no Compilers lecture)
Mon Jan 27	Context Free Grammars	LG Assignment: lga-cfgs Individual Assignment: Read through project prompt for NFAMATCH (due Fri 21 by 11:59PM).	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?
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 on the course homepage in the "lgcOptimalDFA" slot. You can upload each result file individually --- just be sure they are named differently! This "learning group check" is worth four participation points for all members in attendance today. My solutions for the learning group check: dfa0-optdfa-tt.txt, dfa1-optdfa-tt.txt, dfa2-optdfa-tt.txt. Challenge question matching nested structures with regular expressions. You may want to download and have at the ready this grammar from the lecture. Here are the context free grammar intro slides.
Fri Jan 24	Optimizing DFAs	LG Assignment: lga-optimal-dfa	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? Be able to cite examples of implementation challenges and techniques for "production" token scanner.
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 22	NFA to DFA	LG Assignment: lga-nfa-to-dfa Individual Assignment: LUTHOR (due Fri 7 by 11:59PM). A video review (19m @ 2x speed) of 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.	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.
Wed Jan 22	Census day
Mon Jan 20	MLK Holiday - Campus closed
Fri Jan 17	NFAs	LG Assignment: lga-nfa Individual Assignment: LUTHOR (due Fri 7 by 11:59PM). A video review (19m @ 2x speed) of 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.	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.
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⁺.
Wed Jan 15	LUTHOR!	LG Assignment: lga-alphabet-encoding Individual Assignment: LUTHOR (due Fri 7 by 11:59PM). A video review (19m @ 2x speed) of 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.	Know how to develop COMPILER projects on alamode, run a `grader.sh` script and test your submission archive. 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. {delay+Be sure to check your solution to question one!} As promised, my solutions to lga-df. Here is the AlphabetEncoding sample project write-up.
Wed Jan 15	Last day to DROP
Mon Jan 13	DFAs ≡ REs	LG Assignment: lga-dfa Individual Assignment: Read through the at least the first half of LUTHOR, our first project (due Fri 7 by 11:59PM). We will review the requirements and example output next lecture.	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.
Fri Jan 10	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 8	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.
Mon Jan 6	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 6	Classes Start

Compiler Design

Due Dates

Semester Calendar

lga-ll1-parsing