📚 Tutorial
- Topics
- The Plan
- Regular Expressions, Finite Automata, Lexing
- Context-Free Grammars
- Bottom-Up Parsing
- Abstract Syntax Trees, Symbol Tables
- Scope and Types
- Project Workshop
- Scope and Types
- Type Polymorphism, Information Flow
- Project Workshop
- Tiny Back End (and Revised End-of-Term Plan)
- Beyond 301 (this term)
- Tutorial Reviews
Topics
Readings and problem sets to prepare in advance of class/tutorial meetings on the listed dates. You do not need polished solutions for the meeting. A rough draft or attempted solution is the goal. Sometimes you will have unsolved problems.
The Plan
Materials: plan.pdf
Agenda:
In Class:
- Course logistics and overview.
- Start Tiny compiler front end exercises
- Preview of regular expressions and finite automata (next tutorial).
Regular Expressions, Finite Automata, Lexing
Materials: regex.pdf
Solutions: regex-soln.pdf
Agenda:
Before Tutorial: Readings and exercises
In Tutorial: Discuss exercises
Videos 1-3 review the construction and operation of a lexer DFA from the lexer specification in exercise 6, and relevant to the Lexer in the Front End implementation.
Videos:
☰ yt playlist
Regular Expressions, Finite Automata, Lexing
Context-Free Grammars
Materials: grammar.pdf
Solutions: grammar-soln.pdf
Agenda:
Before Class:
- Try to complete IntelliJ setup (updated instructions) if you did not succeed last time. Get in touch if you have trouble.
- Readings from grammar.pdf.
- Look over exercises from grammar.pdf.
In Class:
- Quick overview/review of context-free grammars.
- Breakout: work on exercises 1-3 from grammar.pdf and exercise 6 from the previous tutorial.
- Review exercises 1-3 from grammar.pdf and exercise 6 from the previous tutorial.
- Preview of bottom-up parsing (next tutorial).
- Launch the implementation project.
- Breakout: open work/help time.
By end of Tuesday:
- Create a https://github.com account if you do not have one.
- Form project teams of 3 (maybe 2) students.
- You can use this Zulip stream to find teammates.
- If you really want to work alone, please talk to me.
- Register your team membership, GitHub usernames, and a team name using this project team registration form. I will use this to create a project repository that you will use for the rest of the term.
Bottom-Up Parsing
Materials: parse-up.pdf
Solutions: parse-up-soln.pdf
Agenda:
Before Tutorial: Readings and exercises
In Tutorial: Discuss exercises
Videos 1-4 review FIRST and FOLLOW, LR(0) sets of items/automaton construction, SLR parsing table construction, and SLR parsing from exercise 5.
Videos:
☰ yt playlist
Bottom-Up Parsing
Abstract Syntax Trees, Symbol Tables
Materials: ast-symbol.pdf
Agenda:
Before Class: Skim readings from ast-symbol.pdf
In Class:
- LR parsing review
- Breakout exercises from ast-symbol.pdf
- Logistics:
- Lexer submission
- Starting the parser
- Planning for ASTs
- Preview upcoming tutorial
(Starter code will be posted shortly before class.)
Scope and Types
Materials: scope-type.pdf
Agenda:
Before Tutorial: Readings and exercises
In Tutorial: Discuss exercises
We mainly covered scope and symbol tables in April 29-30 tutorials. We will use May 6-7 tutorial for types, focusing on the second half of this material.
If you had mostly wrapped up the type material last time, try out the Type Polymorphism, Information Flow material.
Project Workshop
Agenda:
Time to get support and make project progress.
Scope and Types
Materials: scope-type.pdf
Agenda:
Before Tutorial: Readings and exercises
In Tutorial: Discuss exercises
We mainly covered scope and symbol tables in April 29-30 tutorials. We will use May 6-7 tutorial for types, focusing on the second half of this material.
If you had mostly wrapped up the type material last time, try out the Type Polymorphism, Information Flow material.
Type Polymorphism, Information Flow
Materials: polytype.pdf
Agenda:
The main material for this tutorial is to repeat the types portion of the previous tutorial’s material. The new material listed here is now optional. It explores generic types and subtyping, as well as applications of type systems to security, approximate programming, and performance.
Project Workshop
← Tuesday, 11 May - Thursday, 13 May
Agenda:
Time to get support and make project progress.
Tiny Back End (and Revised End-of-Term Plan)
← Tuesday, 18 May - Thursday, 20 May
Materials: tiny-back.pdf
Agenda:
In class: Tiny Back End (Note: this was originally written as the second part of a pair of activities for the first week, so some of the text sounds like the first week.)
Tutorials will be replaced by general work time and availability for questions, as with last week.
End of Term Plan:
Project reality in week 6:
- A majority of teams have completed AST construction; some have scope complete or in progress.
- Most teams have had difficulty finding time collaborate in real time or strategies to collaborate asynchronously; some have split/reorganized.
- Based on current pace, multiple intermediate project plans (drop the feature; drop the optimizer; provide a working front-end; provide a fill-in-the-blank translator and code generator to be completed) are no longer feasible in the remaining time.
New plan to embrace reality:
- No team will complete a working Roost compiler.
- Instead of pushing for the infeasible reward of a working compiler,
we will wrap up by having teams/individuals complete 3 small
end-of-term work items:
- Complete the Roost Compiler Front End checkpoint that your team is currently closest to completing (if substantial progress has been made and it is closer to done than started) or has most recently completed (if the current checkpoint in progress is not close to done).
- With your current team, a new team, or on your own, complete the back end for the Tiny compiler to produce working x86 executables compiled from Tiny programs. (Second part of the first-week guided exercises, much smaller than the Roost compiler.)
- With your current team, a new team, or on you own, complete a small feature extension (more detail here).
- For all work, consider May 28 the standard deadline. If really necessary, work can be accepted until 4 PM Tuesday June 1 ET, but I cannot guarantee to be available for assistance during this extended window.
Grading:
- I will provide up-to-date grade information to you no later than Monday, May 24.
- Grading of project work will accommodate the realities of what teams have been able to accomplish: it’s based mainly on the quality of what you accomplished, not much on how much you accomplished. Consult with me for questions!
- The above components will count primarily toward the project component of your course grade; the Tiny Back End will count partly toward the project component and partly toward the tutorial component.
Beyond 301 (this term)
Agenda:
Wrap up and project work. Reminder, there are 3 main items to complete for the end of the term.
If you are curious, here’s some more depth on a few ideas just touched on briefly in our “Compilers Lite” adjustments for the term system:
- Intermediate Representations, etc. – used the Tiny compiler back end instead
- Optimization – used the Tiny compiler back end instead
- Data Flow Analysis
- Runtime Systems
Tutorial Reviews
Tutorial reviews are clear written solutions to a subset of problems from the tutorial assignment selected during each tutorial meeting and submitted after each tutorial meeting.
- Reviews are intended to help package up loose ends and capture your understanding of key concepts that we focused on in the tutorial meeting. They should be prepared carefully, but efficiently.
- Reviews are evaluated based on the accuracy, and, where relevant, the insightfulness of discussion or elegance of solutions.
- Reviews must be written clearly and submitted as a PDF file. I suggest (but will not require) that you typeset them with LaTeX. You may also use other document preparation software or write by hand and scan.
- For Spring 2021, reviews are due by Sunday night, but I suggest completing them ASAP after your tutorial session while the ideas are fresh in your mind.
Submitting
Submit a tutorial review by uploading the PDF to GradeScope under your @wellesley.edu ID.
LaTeX
LaTeX is the canonical system for typesetting technical material with a mathematical bent. Most papers (and many books) on programming languages, compilers, runtime systems, and most other fields of CS are prepared with LaTeX. I suggest using it to prepare your tutorial review. Here is a silly example tutorial review to demonstrate some common LaTeX features, and Overleaf, one easy way to use LaTeX.
Getting Started
LaTeX takes a little learning, but these days, tools make it straightforward to get started easily.
- Options for running LaTeX:
- Use Overleaf
- Use LaTeX on the lab workstations (your favorite editor +
pdflatex) - Install LaTeX on your own computer
- Sample Review Document in Tongue-in-Cheek Style
- Learn LaTeX in 30 Minutes (Overleaf)
Reference
- LaTeX Documentation (Overleaf)
- LaTeX WikiBook
- LaTeX Cheatsheet
- All the symbols!
- LaTeX Stack Exchange
- If you use Emacs, try AUCTeX.