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.