Exercises for Week 43

Exercises for Week 43#

Important

We recommend you attempt to do these exercises by hand, and check your solutions with online tools such as https://mdaines.github.io/grammophone/

Lexing#

Recall the following example regular expression

(a|b)* a (a|b)^n

This regexp is exponential in n. Create an equivalent ocamlllex representation that exhibits a crashing behavior in ocamllex.

Parsing#

Exercise 1#

Consider the following grammar and its associated LR(1) automaton that has 9 states, numbered 0 - 8.

T -> x | y | z
T -> T + x 
T -> y * T
../_images/LRAutomataWithConflict.png

Are there any conflicts in this grammar? If so, what are the problematic automaton states and their conflict kind (i.e., shift/reduce or reduce/reduce), and what is the shortest example showcasing the conflict?

Exercises from Appel’s textbook#

  • Ex 3.1

  • Ex 3.3: a, b, c, e, f, g

  • Ex 3.5

  • Ex 3.6: a, b, c

  • Ex 3.10

  • Ex 3.12: a, b, d.

Note that when Appel’s textbook refers to yacc, think of menhir.

Contents