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 4 Final Exam

"Socially distanced" optional final exams, by appointment this week. Please send an Email or Matrix message with:

  1. Three or four preferred times: 1 hour slots between 9AM and 3PM Monday - Thursday
  2. Your preferred face-to-face software

I'll get back to you with an official time.

The final exam is cumulative, here is a list of learning goals covered.
Thu Apr 30

Dead Day
Wed Apr 29 Quiz 3 LG Assignment:

Quiz 3, treeCG

Here is a list of learning goals covered by the last quiz.

Remote Learning Quiz Prep

  • I will try to provide a full 30 minutes for the quiz, because I appreciate there is going to be some "learning overhead" to collaborating successfully for a single answer to each question from your group.
  • Those group members that can, consider starting your quiz review early; the course Matrix server is always up.
  • You could do the usual quiz exchange and everyone works on (|Group|-1) quizzes independently.
  • Or you could group into teams, splitting up the quizzes so that no team sees one of their own member's contribution, and then practice the academics while getting warmed up using messaging and quick uploads for effective collaboration "under pressure."
  • If you're group plans on using JitSi, then you'll need to work out a way to pick the 3 or 4 questions you will all tackle together in A/V collaboration (there isn't more than one instance of JitSi per room, so if you want to split up into groups, you will need to create an appropriate extra room, do so ahead of time).
  • The quiz solutions will be turned in at the course website (or Email'd directly to me, should a catastrophe befall my server), much like learning group checks.
Wed Apr 29

Last Withdrawal - All Students
Mon Apr 27 Lecture LG Assignment:

lga-quiz-prep-3

Individual Assignment:

ZOBOS (due Thu May 7 by 11:59PM) is the (by choice) final project.

ZOBOS (due Thu May 7 by 11:59PM) is available, in stable draft form, for your review.
Fri Apr 24 Register Allocation 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?

show_register-allocation.pdf.
Wed Apr 22 Symbol Tables LG Assignment:

lga-symbol-tables

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?

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?

Symbols and Names
Mon Apr 20 Parsing Wrap-Up LG Assignment:

lga-sdt

Individual Assignment:

WRECK (due Fri May 1 by 11:59PM).

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 an 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 critcal functions does the author recommend for AST processing? What do they do?

Understand the shift-reduce parsing algorithm (given a LR parsing table or a simple grammar).

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?

LGA check resources: everything in one tarball or individual downloads: check-silly-lexing.txt, fischer-4-1.cfg, fischer-4-1t_src.tok, cytron-67.cfg, ptvis-check.pdf.

The LR Parsing Algorithm and pseudo code as well. Yet another example of LR Knitting step by step (textbook grammar 7.14 and figure 7.18).
Fri Apr 17 – Sun Apr 19

E-Days
Wed Apr 15 LALR step-by-step

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 does LALR table generation differ from SLR table generation?

How does LALR(1) uses a fine-grained approach to Follow Sets to solve SLR(1) conflicts.?

How is the LALR propagation graph formed?

Be able to interpret LALR item sets, propagation graphs (Π), and item follow sets to determine their missing elements, flaws, or correctness.

Understand the LALRClosure algorithm and how (why) it is different than SLR Closure.

Understand the LALRGoto algorithm and how (why) it is different than SLR Goto.

LALR step by step lecture slides and example LALR parse with the "knitting algorithm".
Mon Apr 13 Silly Lexing LG Assignment:

LGA will be checked on Monday; some of you might actually have full blown LL(1) compilers by then!

lga-silly-lexing

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 does LALR table generation differ from SLR table generation?

How does LALR(1) uses a fine-grained approach to Follow Sets to solve SLR(1) conflicts.?

How is the LALR propagation graph formed?

How are Follow Sets and the grammar's Item Set graph (CFSM) used to construct SLR parsing tables?

What is a token and a token stream in "compiler speak"?

LALR Challenge Question and lecture slides.

check-silly-lexing-pre.txt is a "prelook" of what your group work check will look like in lecture. Names have been changed to protect the innocent :)
Fri Apr 10 LALR Tables LG Assignment:

lga-lalr-practice

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?

Lecture slides for LALR parsing also contain my "prosey" descriptions of LALR algorithms. Pseudo code flavored equivalents are: LALRClosure and LALRGoTo.
Wed Apr 8 Quiz 2 LG Assignment:

Quiz 3, treeCG

Individual Assignment:

FINALLY, grader.sh is available for LUTHER (due Wed Apr 15 by 11:59PM). As you can see I've pushed the due date as promised. Expect the next programming assignment will see the light of day before LUTHER is due.

Please read §6.5 of the text in the preparation for the next lecture. The first third covers SLR(k=1) table construction, the latter portion covers LALR(k=1) which uses the most fine-grained approach to follow sets we will study.

How do reduce-reduce conflicts arise in the LALR(1) table generation algorithm?

How does LALR(1) uses a fine-grained approach to Follow Sets to solve SLR(1) conflicts.?

How is the LALR propagation graph formed?

Here is a list of learning goals covered by the second quiz.

Remote Learning Quiz Prep

  • I will try to provide a full 30 minutes for the quiz, because I appreciate there is going to be some "learning overhead" to collaborating successfully for a single answer to each question from your group.
  • Those group members that can, consider starting your quiz review early; the course Matrix server is always up.
  • You could do the usual quiz exchange and everyone works on (|Group|-1) quizzes independently.
  • Or you could group into teams, splitting up the quizzes so that no team sees one of their own member's contribution, and then practice the academics while getting warmed up using messaging and quick uploads for effective collaboration "under pressure."
  • If you're group plans on using JitSi, then you'll need to work out a way to pick the 3 or 4 questions you will all tackle together in A/V collaboration (there isn't more than one instance of JitSi per room, so if you want to split up into groups, you will need to create an appropriate extra room, do so ahead of time).
  • The quiz solutions will be turned in at the course website (or Email'd directly to me, should a catastrophe befall my server), much like learning group checks.
Mon Apr 6 !SLR Languages LG Assignment:

lga-quiz-prep-2

What is a reduce-reduce conflict in an LR table construction algorithm?

What is a shift-reduce conflict in LR table construction?

Non SLR languages and LR table construction conflicts
Fri Apr 3 SDT and ASTs LG Assignment:

lga-re-sdt

What is the difference between a concrete syntax tree and an abstract syntax tree (AST)?

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.

What is syntax directed translation (SDT)?

Learn how to express logic for parse tree simplification during construction (AKA: syntax directed translation).

SLR tables from λ rules.
Wed Apr 1 COVID Syllabus Review LG Assignment:

lga-re-semantic-analysis

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.
Mon Mar 30 All Your Matrix are Ours

Matrix Query: I get "Key Backup" admonitions for every device x browser I use, I have done this once --- what is the worst case scenario of not doing this on every device?

check-lr-itemsets.tar.bz2 go go go!
Sat Mar 21 – Sun Mar 29

Spring Break
Mon Mar 16 – Mon Mar 23

COVID19 no lecture; be optimistic! These sorts of things happen, sometimes with awesome results (#3)!
Fri Mar 13 Return Midterm & Remote Learning Update LG Assignment:

lga-lr-itemsets (checked on Monday the 30th)

Individual Assignment:

LUTHER (due Wed Apr 15 by 11:59PM) is official. Grading script arriving soon.

Be able to cite examples of implementation challenges and techniques for "production" token scanner.
Wed Mar 11 LR Item Sets LG Assignment:

lga-lr-itemsets (checked on Monday the 30th)

In terms of deciding which production rule to use, what is the fundamental advantage of LR parsers over LL parsers?

Know what an Item Set and its Progress Marker represent.

Understand the shift-reduce parsing algorithm (given a LR parsing table or a simple grammar).

Be able to calculate Closure and Goto for LR Item Sets.

What important property do LR(1) parsers have with respect to the DBL language?

Here are my description of the critical algorithms, both prosey as well as pseudo code for Closure, GoTo and forming the SLR table.
Mon Mar 9 Knitting a Parser LG Assignment:

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?

LUTHER (due Wed Apr 15 by 11:59PM) is really really close.

LR tables intro slides and parsing steps for the prefix sum and DBL.
Fri Mar 6 Midterm Exam

Learning goals covered by the exam are here.
Wed Mar 4 LR Parsing Intro

No LGA, but there is a midterm on Friday!
Mon Mar 2 LL(1) Limitations LG Assignment:

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?

How are grammars with common prefixes that create intersecting predict sets refactored to become LL(1) languages?

What does a production rule written with left recursion look like?

What important property do LL(k) parsers have with respect to the DBL language?

What is the DBL, how is it connected to the ubiquitious if-else in programming?

Group participation points for the correct first and follow sets: submit your results for predict-set-test0.cfg and predict-set-test1.cfg in a single tarball or zip archive on the course website. Just one submission per group. (Incorrect results do not particularly mean no credit, I just need to see evidence of progress made on your coding assignment).

Group participation points for a reasonable RE grammar: submit your .cfg grammar file for question 4 of lga-ll1-parsing.pdf along with your groups "grammar code" results for its first and follow sets (or if you're feeling brazen, the predict set). Submit your results in a single tarball or zip archive on the course website. Just one submission per group. You don't have to be 100% correct on the grammar, but I'd like to see something reasonable..

Lecture notes for LL1 limitations and the Dangling Bracket Language.
Fri Feb 28 LL(1) Parsing LG Assignment:

lga-ll1-parsing

Given a grammar and its LL(1) parsing table, show how a parse tree is created from a token stream.

How do you build an LL(1) parsing table from a grammar that is LL(1)?

Be able to write a non-trivial LL(1) language with recursive rules and operators (precedence and associativity).

Students may find my python script tree-to-graphvis helpful in visualizing their code results. The the pydoc string in the file for example usage.

You will want to

$ chmod +x tree-to-graphvis

or invoke as an argument of python:

$ python2 tree-to-graphvis <parse.txt | dot -T png -o parse.png
Wed Feb 26 LL(1) parsing 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 are left recursive rules refactored so that a grammar might be processed with an LL(1) parser?

How are grammars with common prefixes that create intersecting predict sets refactored to become LL(1) languages?

How do you build an LL(1) parsing table from a grammar that is LL(1)?

What does a production rule written with left recursion look like?
Mon Feb 24 LL(1) Tables Individual Assignment:

Due date pushed for NFAMATCH... (due Fri Feb 28 by 11:59PM).

Given a grammar and its LL(1) parsing table, show how a parse tree is created from a token stream.

How do you build an LL(1) parsing table from a grammar that is LL(1)?

What property of it's predict sets make a grammar not LL(1)?

CFG for challenge question show_chl-predict-sets.pdf group question from today.

Download lecture notes, or all the lecture resources.
Fri Feb 21 Predict Sets LG Assignment:

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)?
Wed Feb 19 CFG Algorithms in Detail 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 λ".

Gain experience and insight into the software design and trade-offs of a context free grammar class (object, API).

We discussed three algorithms today --- these are critical for our future development of "table driven" parsing engines: derivesToLambda, firstSet and followSet; and the slides of course

For those of you who don't like typing, here is the sample grammar used in the LGA.
Mon Feb 17 – Tue Feb 18

Presidents' Day Break
Fri Feb 14 Return Quiz & New Groups Individual Assignment:

No learning group assignment for Wednesday...

You've been working on NFAMATCH (due Fri Feb 28 by 11:59PM), yes?
Wed Feb 12 Quiz 1

Here is a list of learning goals covered by the first quiz.
Mon Feb 10 Quiz prep LG Assignment:

lga-quiz-prep-1
Fri Feb 7 Grammar Follows LG Assignment:

lga-grammar-follows

Individual Assignment:

NFAMATCH (due date pushed) (due Fri Feb 28 by 11:59PM)

Determine what terminals are in the first set of a grammar sequence.

Determine what terminals are in the follow set of a grammar symbol.

Determine whether a "symbol derives to λ".

Be able to optimize a DFA to its smallest, unique form.

Be able to convert an NFA to a (unoptimized) DFA.

Understand how project submissions will be built, how stdout output must be formatted.

Understand and implement token matching given an optimized DFA transition table.

Critical CFG algorithm ideas....

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.

A grader.sh Linux script will be forthcoming, this will allow you to test your implementation the same way the grader will.

Certainly, reading through the write-up is the first step. You can earn "bounties" (in the for of participation points) if you are the first to report an error or ambiguity in the write-up (or the submission requirements). The caveat being it must be an error that would reasonably lead to misinformation. While I would love to here about typos or misspellings, I'm not sure they the warrant course credit.
Wed Feb 5 Grammar Firsts LG Assignment:

lga-grammar-firsts

Determine what terminals are in the first set of a grammar sequence.

Determine whether a "symbol derives to λ".

What is a parse tree, what characteristics does it have?
Tue Feb 4

Career Day
Mon Feb 3 No Lecture

Sorry for the inconvenience, we will reconvene on Wednesday.
Fri Jan 31 Ambiguity in Grammars LG Assignment:

lga-grammar-ambiguity

Given a grammar, be able to derive a valid sentence of the grammar.

How are left-associative and right-associative connected to recursive production rules?

Be able to deduce associativity and precedence rules for operators in a CFG.

Given a binary operator, △, know how to write its production rule for left or right associativity.

Given two binary operators △ and □ , know how to write a simple grammar to express their relative precedence.

Can a BNF grammar represent different languages than a CFG?

What is different between a BNF grammar and a CFG?

What do the two Ls and the k stand for in "LL(k)" parsing?

In what way are REs limited in their description of languages?

What features of a language are REs able to describe?

Challenge question matching nested structures with regular expressions.

CFG algorithm ideas.
Wed Jan 29 Context Free Grammars LG Assignment:

lga-cfgs

Be able to identify ambiguous grammars, what demonstrates an ambiguous grammar?

Given a grammar, be able to derive a valid sentence of the grammar.

Know the difference between a leftmost derivation and a rightmost derivation.

Know the notational conventions for CFGs used in the book.

What are terminals, non-terminals, λ, and $ in a CFG?

What does it mean when a grammar is ambiguous?

What is a sentential form?

Be able to design simple languages and grammars with nested productions and recursive rules.

What is a regular grammar? What two production rule patterns are associated with regular grammars?
Mon Jan 27 DFAs back to REs LG Assignment:

Read §4--4.1 (inclusive), prepare to discuss next lecture.

Given a grammar, be able to derive a valid sentence of the grammar.

Know the difference between a leftmost derivation and a rightmost derivation.

What are terminals, non-terminals, λ, and $ in a CFG?

What is a sentential form?

Be able to convert a DFA into a RE (in the book's notation).

Know how to convert a DFA to a regular expression using the T1, T2, T3 fundamental operations.

Know the T1, T2, T3 DFA to RE operations --- you don't need to know which is which.

Be familiar with construction algorithms and proofs using the RE≡NFA≡DFA≡RE equivalency.

My p/code for the DFA to RE algorithm.

Reverse(R) solution using the RE≡NFA≡DFA relationship.
Fri Jan 24 Optimizing DFAs LG Assignment:

lga-optimal-dfa

Be able to optimize a DFA to its smallest, unique form.

Be able to cite examples of implementation challenges and techniques for "production" token scanner.

My p/code for (almost) optimizing DFAs.
Wed Jan 22 NFA to DFA LG Assignment:

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.

NFA to DFA lecture notes.
Wed Jan 22

Census Day
Mon Jan 20

Martin Luther King Day Holiday
Fri Jan 17 NFAs LG Assignment:

lga-nfa

Be able to optimize a DFA to its smallest, unique form.

What are dead states and unreachable states in FAs?

What is the difference(s) between a NFA and a DFA?

Be able to convert an NFA to a (unoptimized) DFA.

Be able to convert a RE (in the book's notation) to an equivalent NFA.

Note that figure 3.22 of the text is incorrect. There should be a λ transition from the starting node (to the left of the "FA for A" box) to the accepting node to the right of the box. Without this, the figure actually shows the NFA for A+.
Wed Jan 15 DFAs ≡ REs LG Assignment:

lga-dfa

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?

Some important figures from the text.
Mon Jan 13 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.
Fri Jan 10 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 10

Graduate student registration deadline
Wed Jan 8 Introductions Individual Assignment:

Understand how learning groups will be used in this course, and what the expectations are for your shared work.

Understand how your course grade will be calculated and how your participation points will may affect your grade.

Understand the Collaboration Policy for individual assignments.

What about Canvas? We won't use Canvas in this course. Here are the intro slides from the first lecture.
Tue Jan 7

Classes begin