Assignment 8

In this assignment, you will practice writing context-free grammars, and you will write a general parser for an arbitrary context-free grammar.

In A8.scala, complete the implementations of

1. twoXes
2. threeXes
3. tree1
4. tree2

Complete the implementation of parseCYK in Parsing.scala.

You can find the specification of the Lacs language here.

Optionally, for bonus, read this website and/or the first two sections of this paper and/or any other resource about Earley’s algorithm, and complete the implementation of parseEarley in Parsing.scala.