Six-Week Exam Study Guide

The six-week exam will be held during class time on Friday, September 30.

Policies

The exam will be open-book. This includes not only the textbook but also any course notes, returned work, posted slides, or other printed materials.

However, the use of electronic devices, including calculators, is prohibited.

Coverage

The exam will cover only the material of Weeks 4-6 on Scanning and Parsing. (Weeks 1-3 were covered in the Scheme take-home exam.)

For this exam, you should be able to:

Give a scanner specification (tokens and regular expressions) for a given language.
Understand and use a given scanner specification.
Follow the steps of automatic scanner generation.
Show the steps of a top-down parse and the resulting parse tree.
Determine whether a grammar is LL(1).
Write an LL(1) grammar for a specified language.
Compute PREDICT and FOLLOW sets for a specified grammar.
Show the steps of a bottom-up parse and the resulting parse tree.
Draw the CFSM for a specified LR grammar.
Determine whether a grammar is SLR(1).

You should also have a good understanding of:

The role of scanning and parsing in the broader context of compilation.
The difference between table-driven and hand-coded scanners.
The difference between recursive-descent and table-driven top-down parsers.
Top-down vs. bottom-up parsing, the benefits and limitations of each.
The concept of look-ahead in scanners and parsers.