Week 9 Lab: Formal Grammar Worksheet

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.

Revisiting S-Expressions

Use Menhir and OCamllex to build a parser for S-expressions which targets string sexpr. Recall the ADT definition of sexpr:

type 'a sexpr = Atom of 'a | List of 'a sexpr list

You should use the following regular expression for atoms in your lexer:

let atom = [^ ' ' '\t' '\n' '\r' '(' ')']+

This expression matches any nonempty sequence of non-whitespace non-parentheses characters.

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. Build a parser for these expressions using menhir and ocamllex.