Midterm Study Guide

The midterm will cover scanning and parsing using Flex and Bison.

Be able to write programs using Flex and Bison from scratch.

Concepts that may appear on the exam:

What strings belong to given regular expression? (Study Regular Expressions 1 and 2 on Canvas)

Understand the purpose of the Flex lookahead (peeking). Be able to write regex that has a lookahead operator. (Study the Regular Expressions 3 and 4 quizzes on Canvas)

Flex scans left-to-right and never skips characters. Flex will backtrack and give back consumed characters if all branches of computation die, up to the longest substring matched. Once a rule matches, those characters are never returned (unless we used a lookahead).

 Rule selection order is: 
 1. Earliest string position. 
 2. Longest match 
 3. Earliest rule in the .l file 
 
 Note: 2 includes the length of the trailing characters in a lookahead.

Understand that Flex creates a nondeterministic finite automaton combining all of the rules. Be able to convert an NFA to a regular expression or test for accepting strings (Study Pre-Exam Worksheet and the Automata 1 quiz on Canvas).

Study the Parsing 1, 2, and 3 quizzes on Canvas. Given a grammar and a string, show that multiple valid parse trees exist (and therefore the grammar is ambiguous). Be able to identify a shift/reduce conflict under LALR parsing and write a grammar that does not have conflicts.

Study all notes on my website. Understand that Bison will shift when confronted with a shift-reduce conflict, and therefore parse trees will bound tightly to the right-side by default unless we incorporate precedence.