Compiler Design Schedule

Date	Lecture Title	Assignment(s)	Lecture & Assignment Goals
Notes
Wed May 5	Quiz 3	Individual Assignment: CZAR (due Wed May 12 by 11:59PM) is a curved and beneficial point, see the write-up for details.
Here is a list of learning goals covered by the last quiz. The Quiz
Wed May 5	Classes end
Mon May 3	Lecture	LG Assignment: lga-quiz-prep-3 Individual Assignment: CZAR (due Wed May 12 by 11:59PM) is a curved and beneficial point, see the write-up for details.
Fri Apr 30	PC Codes	LG Assignment: lga-code-generation Sorry for the delay getting this out `:(`	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 variablle? 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).
Group question slides can be downloaded. Lecture slides for program counter manipulations, `CALL`, `RETURN`, more stack frame managment, `JUMP`s in control structures.
Wed Apr 28	Expression Evaluation	LG Assignment: lga-register-allocation	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 pseudo code: Sethi-Ullman counting (including function calls), treeCG() expression tree evaluation or treeVR() using virtual registers.
Mon Apr 26	Register Counting and Allocation	LG Assignment: No LGA, work on ZOBOS (due Thu May 6 by 11:59PM)!	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).
LL vs LR SDT slides. Slides for register management and pseudo code: Sethi-Ullman counting (including function calls), treeCG() expression tree evaluation or treeVR() using virtual registers.
Fri Apr 23	Lecture continued	LG Assignment: lga-framed-stack (not due till Monday) Individual Assignment: ZOBOS (due Thu May 6 by 11:59PM)	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 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 variablle? 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?
Slides for basic stack management.
Wed Apr 21	Stack Management	LG Assignment: lga-framed-stack (not due till Monday)	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 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 variablle? 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?
Slides for basic stack management.
Mon Apr 19	ZOBOS	LG Assignment: lga-zobos Individual Assignment: ZOBOS (due Thu May 6 by 11:59PM) will be due on the last lecture day of the semester.
Mon Apr 19	E-Days - no exams
Fri Apr 16	E-Days - no lecture
Fri Apr 16	Last day to withdraw for all students
Wed Apr 14	Symbol Tables Wrap-Up	LG Assignment: No LGA --- work on WRECK (due Wed Apr 21 by 11:59PM)!	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 data structure 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
Mon Apr 12	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 data structure 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
Fri Apr 9	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 can the RHS of an `=`-operation represet? Cite two examples. What does the LHS of an `=`-operation represent? Given a grammar for assignment operations, identify the rule that permits dereferencing. What is the definition of dereferencing? 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?
Students might want to make sure their last round of learning group evaluations have been completed before lecture --- you won't be able to upload learning group check solutions before doing this. LGA check resources: everything in one tarball or individual downloads: lgc-silly-lexing.txt, fischer-4-1.cfg, fischer-4-1t_src.tok, cytron-67.cfg, ptvis-check.pdf. Lecture slides for l-values, r-values, and dereferencing.
Wed Apr 7	SDT Nitty Gritty		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?
SDT nitty-gritty details and terms.
Mon Apr 5	Silly Lexing	LG Assignment: LGA will be checked on Friday; you should all have full blown "rich" LL(1) compilers by then! lga-silly-lexing Individual Assignment: WRECK (due Wed Apr 21 by 11:59PM)	What is the difference between a concrete syntax tree and an abstract syntax tree (AST)? 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 λ"? How are Item Follow Sets formed? Know what an Item Set and its Progress Marker represent. Be able to calculate Closure and Goto for LR Item Sets. How are Follow Sets and the grammar's Item Set graph (CFSM) used to construct SLR parsing tables? What is syntax directed translation (SDT)? Learn how to express logic for parse tree simplification during construction (AKA: syntax directed translation). What is a token and a token stream in "compiler speak"?
Sat Mar 27 – Sun Apr 4	Spring Break
Fri Mar 26	RE Trees to NFAs	LG Assignment: lga-re-nfagen Individual Assignment: WRECK (due Wed Apr 21 by 11:59PM)	Be able to process a parse-tree for REs creating a structure for an equivilant NFA. Be able to convert a RE (in the book's notation) to an equivalent NFA.
Lecture slides for generating NFAs from RE ASTs.
Wed Mar 24	Quiz 2	Here is a list of learning goals covered by the second quiz. For your planning purposes: the quiz consists of 4 questions. A partitioning for approximately equal time would (1), (2), (3&4).
Mon Mar 22	SDT Nitty Gritty	LG Assignment: lga-quiz-prep-2
Fri Mar 19	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).
Download the slides for RE Grammar and LL(1) SDT to the RE's AST.
Wed Mar 17	SLR(1) Wrap Up		Know what an Item Set and its Progress Marker represent. 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) tabless? How are Follow Sets and the grammar's Item Set graph (CFSM) used to construct SLR parsing tables?
Process the following grammars prefix-sum_grammar.cfg, precexpr_grammar.cfg and biglanguage_grammar.cfg and upload evidence of your Item Sets and GoTo calculations to the `lgcLRItemSets` slot on the course website. The `biglanguage.cfg` grammar contains λ-rules, which we haven't covered in lecture yet, so I won't grade down if your results for this grammar are incorrect --- but I would still like to see what your code generates (or the error messages). Shift-reduce table generation lecture slides are here. 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 15	No lecture - snow day
Fri Mar 12	LR Item Sets	LG Assignment: lga-lr-itemsets (checked on Wednesday 17th)	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? How are Follow Sets used in SLR to resolve reduce-reduce or shift-reduce conflicts in *LR(0) tabless? 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. Here are my description of the critical algorithms, both prosey as well as pseudo code for Closure, GoTo and forming the SLR table. Shift-reduce table generation lecture slides are here.
Wed Mar 10	The Knitting Parser	LG Assignment: lga-lr-knitting	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? How are Follow Sets used in SLR to resolve reduce-reduce or shift-reduce conflicts in *LR(0) tabless? How are Follow Sets and the grammar's Item Set graph (CFSM) used to construct SLR parsing tables?
Lecture slides for LR(0) tables and "shift-reduce" parsing. Shift-reduce table generation lecture slides are here.
Mon Mar 8	No lecture
Fri Mar 5	LL(1) Limitations	LG Assignment: lga-ll1-limitations	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? 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 type of derivation do "bottum-up" parsers use (generate)?
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. Lecture slides for LR(0) tables and "shift-reduce" parsing.
Wed Mar 3	LL Wrap & LR(0) Parsing		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 type of derivation do "bottum-up" parsers use (generate)?
Lecture slides for LR(0) tables and "shift-reduce" parsing.
Mon Mar 1	LL(1) Parsing	LG Assignment: lga-ll1-parsing (checked in two days, Friday 5 March)	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? 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? Be able to write a non-trivial LL(1) language with recursive rules and operators (precedence and associativity). 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?
Lecture notes for LL1 limitations and the Dangling Bracket Language. 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 26	LL(1) Tables	LG Assignment: lga-ll1-tables Individual Assignment: LUTHER (due Thu 11 by 11:59PM).	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? Be able to cite examples of implementation challenges and techniques for "production" token scanner.
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. CFG for challenge question. show_chl-predict-sets.pdf group question from today.
Wed Feb 24	LUTHER	Individual Assignment: LUTHER (due Thu 11 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)? Be able to cite examples of implementation challenges and techniques for "production" token scanner.
Reminder: lga-predict-sets will be "checked" at the next lecture. At least one group member should bring a computing device with an Internet connection and capable of running your current code base. 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.
Mon Feb 22	Predict Sets	LG Assignment: lga-predict-sets (checked in two lectures)	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 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)?
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 19	Return Quiz & New Groups	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).
For those of you who don't like typing, here is the sample grammar used in the LGA. Some pseudo code for derives to lambda, first sets and follow sets; and some lecture slides (BEWARE the lecture slides no longer match the recorded video, I changed symbol names in the grammar so there were no duplicates between the grammar and variables in p/code.) 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...
Wed Feb 17	Quiz 1	Here is a list of learning goals covered by the first quiz.
Mon Feb 15 – Tue Feb 16	Presidents' Day break
Fri Feb 12	Quiz prep	LG Assignment: lga-quiz-prep-1	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)?
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 10	Grammar Follows	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 (BEWARE the lecture slides no longer match the recorded video, I changed symbol names in the grammar so there were no duplicates between the grammar and variables in p/code.) 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 construction algorithm needs this tweak. The end result will be the same as other texts and references --- but I think more intuitive for the student.
Mon Feb 8	Grammar Firsts	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?
Slides for operator grammar patterns. CFG implementation in code (group question). Critical CFG algorithm ideas....
Fri Feb 5	Ambiguity in Grammars	LG Assignment: lga-grammar-ambiguity	Be able to identify 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? What does it mean when 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. What is a reduced grammar? Can a BNF grammar represent different languages than a CFG? What is different between a BNF grammar and a CFG?
Reduced grammar group question. Lecture slides for ambiguous grammars.
Wed Feb 3	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?
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.
Tue Feb 2	Career Day - no exams
Mon Feb 1	NFAMATCH	LG Assignment: No LGA today - that doesn't mean you get an attendance pass for Learning Group Time next lecture `:)` Individual Assignment: Read through NFAMATCH (due Wed Feb 10 by 11:59PM) and project submission requirements. NFAMATCH (due Wed Feb 10 by 11:59PM) (startin' the fire `:)`)	Be able to optimize a DFA to a smaller form by reconciling non-distinguishable 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.
I've set up two Matrix rooms: NFAMATCH and Requirements to handle questions, answers and discussion. You've all been invited. Three DFA transition tables for you to test your LGA code on: dfa0.tt, dfa1.tt, dfa2.tt. 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.
Fri Jan 29	Optimizing DFAs	LG Assignment: lga-optimal-dfa Individual Assignment: NFAMATCH (due Wed Feb 10 by 11:59PM) (startin' the fire `:)`)	Be able to optimize a DFA to a smaller form by reconciling non-distinguishable 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. Be able to convert an NFA to a (unoptimized) DFA. Understand and implement token matching given an optimized DFA transition table.
Pseudo code for DFA "optimization" (you might want to download and have this available during lecture). Slides for "optimizing" DFAs for (almost) optimizing DFAs. Regular volleyball group question slides.
Wed Jan 27	NFA to DFA	LG Assignment: lga-nfa-to-dfa	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?
`/` 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 27	Census Day
Mon Jan 25	NFAs	LG Assignment: lga-nfa	Be able to optimize a DFA to a smaller form by reconciling non-distinguishable states. 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.
Lecture slides on NFAs and REs→NFAs, and 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 22	DFAs ≡ REs	LG Assignment: lga-dfa	What are runtime semantics? 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?
Foreign Calls and Runtime Semantics slides. Finite Automata and DFA slides.
Wed Jan 20	Regular Expressions	LG Assignment: lga-regex	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.
Regular Expressions lecture slides
Mon Jan 18	Martin Luther King Day Holiday
Fri Jan 15	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.
Fri Jan 15	Graduate student registration deadline
Wed Jan 13	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.
Tue Jan 12	Classes begin

Mon May 3

Lecture

LG Assignment:

lga-quiz-prep-3

Individual Assignment:

CZAR (due Wed May 12 by 11:59PM) is a curved and beneficial point, see the write-up for details.

Fri Apr 30

PC Codes

LG Assignment:

lga-code-generation Sorry for the delay getting this out :(

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 variablle? 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 JUMPs 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).

Group question slides can be downloaded.

Lecture slides for program counter manipulations, CALL, RETURN, more stack frame managment, JUMPs in control structures.

Wed Apr 28

Expression Evaluation

LG Assignment:

lga-register-allocation

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 pseudo code: Sethi-Ullman counting (including function calls), treeCG() expression tree evaluation or treeVR() using virtual registers.

Mon Apr 26

Register Counting and Allocation

LG Assignment:

No LGA, work on ZOBOS (due Thu May 6 by 11:59PM)!

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).

LL vs LR SDT slides.

Slides for register management and pseudo code: Sethi-Ullman counting (including function calls), treeCG() expression tree evaluation or treeVR() using virtual registers.

Fri Apr 23

Lecture continued

LG Assignment:

lga-framed-stack (not due till Monday)

Individual Assignment:

ZOBOS (due Thu May 6 by 11:59PM)

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 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 variablle? 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?

Slides for basic stack management.

Wed Apr 21

Stack Management