Preparation for CSCI 439 Quiz 3 (2025)
As per the exams page,
the quiz will be closed book, closed notes, no electronics, and held in the lab
during your scheduled lab section. You will have 50 minutes to complete the quiz.
You are permitted one double-sided 8.5x11" page of notes ('cheat sheet').
This third quiz is again primarily theory, focused on the lecture material through Mar. 19th,
emphasizing recent material on top-down and bottom-up parsing.
There will be three questions worth 4 marks each asking you to give a short explanation
of different aspects of parsing/grammars, plus one longer 12-mark question asking you
to apply a stack-based algorithm for top-down parsing.
The three shorter written questions can cover topics like
- LL(k) (and particularly LL(1)) grammars and their relevance to parsing
- LR(k) (and particularly LR(1)) grammars and their relevance to parsing
- recursive descent parsing
- top-down parsing using a stack-based approach
- bottom-up parsing using a stack-based approach
- the use of action/goto tables to make bottom-up parsing more efficient
(you will not be asked to construct action/goto tables)
In terms of preparation for these questions I would simply recommend reviewing the lecture
content since the study break, with an emphasis on the content covering top-down and bottom-up
parsing and the LL(k), LR(k) grammars.
For the longer (applied) question, you'll be given a stack-based top-down parsing algorithm
(quite similar to those we discussed in class: repeatedly matching/consuming tokens or picking a rule
and pushing its RHS elements), a grammar/token set for a language,
and a set of input for the language.
You'll then be asked to follow the algorithm to
parse the input, showing your work along the way, and possibly asked to discuss the
circumstances under which the algorithm should halt and accept.
In terms of practicing for the quiz, the algorithm will be something similar to the following:
current = starting nonterminal
stack is initially empty
repeat until done
if current is a token then match against the next input token
if they don't match then reject
otherwise consume the input
otherwise (current is a nonterminal)
pick a rule whose LHS matches current (basing your choice on the next input token)
push the RHS elements of the rule (right-to-left)
pop the top of stack item into current
I would recommend creating one or two simple grammars and a couple of valid token sequences
for each, then practice following the algorithm to parse the token sequences.