Preparation for CSCI 330 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 primarily theory, covering regular expressions and context free grammars
from the lecture material up to and including the lecture of Mar. 18th.
There will not be any lex/yacc questions.
Regular expressions (10 marks)
This section of the quiz will cover writing regular expressions to represent four different
token types (specific formats for identifiers, literals, keywords, operators, etc),
then identifying if/which of those regexes conflict/overlap, and suggesting
possible ways to resolve this (e.g. checking the regexes in a specific order and
accepting the first match).
The best form of preparation is to practice writing and understanding regular expressions
for token types, similar to those we attempted for lab 4 (but without the lex complications).
Context free grammars/augmented grammars (14 marks)
In this section you will be given a set of regexes and context free grammar rules
for a language plus a set of input tokens and asked:
(i) to sketch two different valid parse trees for that expression with those grammar rules
(ii) to explain how this shows ambiguity in the grammar and specifically what is
the nature of that ambiguity (which rule(s) are causing the ambiguity).
The best form of practice for this is to take some of the CFGs we've worked with in the
lectures (particularly those regarding expressions) and practice parsing different
sequences of input tokens.
As a rule of thumb, the most obvious causes of ambiguity are rules of the form
x: x something x ; as these create the possibility of recursively
parsing down either the left or right side when faced with input that has the form
x something x something x.