Lab 8: Formal Grammar Worksheet

The following is a small collection of exercises related to formal grammars.

Ambiguity

<a> ::= <b> <c>
<b> ::= <b> y | x
<c> ::= <d> | <d> y
<d> ::= z <b> | z
  1. Give a leftmost derivation of the sentence xyz.
  2. Draw a parse tree for the sentence xyz.
  3. Find the shortest sentence accepted by the above grammar which has multiple parse trees. Draw both parse trees.

Designing Grammars

Design an unambiguous grammar for Boolean expressions over the constants True and False in Python. When you're done, compare with the Python grammar for Boolean operators.

Challenge. We just discussed parser generators in lecture. If you have time, build a parser for these expressions using menhir and ocamllex.