Assignment 3 - ULL'13

Implement the fold-unfold transform of Johnson'07 (the O(n^3) split-head grammar). Johnson describes his transform in a numbers of stages.

*** Report ***

Handin a single page report with an small example dependency grammar,
the script to transform it and the result. You can use the tree
viewing script to visualize a CFG parse tree to illustrate the
transform.


*** Writing scripts ***

The easiest way to start is to use a series of 'sed' commands, that
transform a dependency grammar into a context-free grammar, and an
input sentence into the funny double word format. You can then put
these commands in a script; the simplest way to create a script is
simply to put your commands in a file and make that file executable by
typing in a terminal window.

chmod a+x myfile.txt

You can then run your commands by typing
./myfile.txt

*** Input and Output ***

The input of the script should be a dependency grammar. Create one
yourself, using a simple format. For instance, a list of
head-dependent pairs with a direction, and a special simple ROOT to mark the head of
the sentence. E.g., this DG:

---
ROOT likes right
likes John left
likes opera right
---
can generate the sentence "John likes opera".

The output is then a CFG that can generate the same sentences in
double-word format (i.e., "John John likes likes opera opera") using
the special nonterminals Johnson describes.