notebooks/PCFG Parsing with NLTK.ipynb

{
 "cells": [
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "# PCFG Parsing using NLTK"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "**(C) 2018-2019 by [Damir Cavar](http://damir.cavar.me/)**"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "**Download:** This and various other Jupyter notebooks are available from my [GitHub repo](https://github.com/dcavar/python-tutorial-for-ipython)."
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "**License:** [Creative Commons Attribution-ShareAlike 4.0 International License](https://creativecommons.org/licenses/by-sa/4.0/) ([CA BY-SA 4.0](https://creativecommons.org/licenses/by-sa/4.0/))"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "This notebook is based on [my](http://damir.cavar.me/) own NLTK notebooks and [Michael Elhadad](https://www.cs.bgu.ac.il/~elhadad/)'s notebook *[Constituent-based Syntactic Parsing with NLTK](https://www.cs.bgu.ac.il/~elhadad/nlp16/nltk-pcfg.html)*.  See for related material:\n",
    "\n",
    "1. [Python Parsing with NLTK](https://github.com/dcavar/python-tutorial-for-ipython/blob/master/notebooks/Python%20Parsing%20with%20NLTK.ipynb)\n",
    "1. [Python Parsing with NLTK and Foma](https://github.com/dcavar/python-tutorial-for-ipython/blob/master/notebooks/Python%20Parsing%20with%20NLTK%20and%20Foma.ipynb)"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "This is a tutorial related to the discussion of grammar engineering and parsing in the class Alternative Syntactic Theories and Advanced Natural Language Processing taught at Indiana University in Spring 2017 and Fall 2018 and 2019."
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "The examples presuppose an installed Python 3.x [NLTK](https://www.nltk.org/) module with all the dependent modules and packages, as well as the [data set for NLTK](https://www.nltk.org/data.html)."
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "## Using the Penn-Treebank"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "You can use the NLTK *corpus* module to read and use the different corpora in the NLTK [data set](https://www.nltk.org/data.html)."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 1,
   "metadata": {},
   "outputs": [],
   "source": [
    "import nltk.corpus"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "We can load the portion of the Penn Treebank:"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 2,
   "metadata": {},
   "outputs": [],
   "source": [
    "ptb = nltk.corpus.treebank"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "The corpus consists of a collection of files. Each file has an ID (file name). You can print the IDs using the *fileids* method:"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 3,
   "metadata": {},
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "['wsj_0001.mrg', 'wsj_0002.mrg', 'wsj_0003.mrg', 'wsj_0004.mrg', 'wsj_0005.mrg', 'wsj_0006.mrg', 'wsj_0007.mrg', 'wsj_0008.mrg', 'wsj_0009.mrg', 'wsj_0010.mrg', 'wsj_0011.mrg', 'wsj_0012.mrg', 'wsj_0013.mrg', 'wsj_0014.mrg', 'wsj_0015.mrg', 'wsj_0016.mrg', 'wsj_0017.mrg', 'wsj_0018.mrg', 'wsj_0019.mrg', 'wsj_0020.mrg', 'wsj_0021.mrg', 'wsj_0022.mrg', 'wsj_0023.mrg', 'wsj_0024.mrg', 'wsj_0025.mrg', 'wsj_0026.mrg', 'wsj_0027.mrg', 'wsj_0028.mrg', 'wsj_0029.mrg', 'wsj_0030.mrg', 'wsj_0031.mrg', 'wsj_0032.mrg', 'wsj_0033.mrg', 'wsj_0034.mrg', 'wsj_0035.mrg', 'wsj_0036.mrg', 'wsj_0037.mrg', 'wsj_0038.mrg', 'wsj_0039.mrg', 'wsj_0040.mrg', 'wsj_0041.mrg', 'wsj_0042.mrg', 'wsj_0043.mrg', 'wsj_0044.mrg', 'wsj_0045.mrg', 'wsj_0046.mrg', 'wsj_0047.mrg', 'wsj_0048.mrg', 'wsj_0049.mrg', 'wsj_0050.mrg', 'wsj_0051.mrg', 'wsj_0052.mrg', 'wsj_0053.mrg', 'wsj_0054.mrg', 'wsj_0055.mrg', 'wsj_0056.mrg', 'wsj_0057.mrg', 'wsj_0058.mrg', 'wsj_0059.mrg', 'wsj_0060.mrg', 'wsj_0061.mrg', 'wsj_0062.mrg', 'wsj_0063.mrg', 'wsj_0064.mrg', 'wsj_0065.mrg', 'wsj_0066.mrg', 'wsj_0067.mrg', 'wsj_0068.mrg', 'wsj_0069.mrg', 'wsj_0070.mrg', 'wsj_0071.mrg', 'wsj_0072.mrg', 'wsj_0073.mrg', 'wsj_0074.mrg', 'wsj_0075.mrg', 'wsj_0076.mrg', 'wsj_0077.mrg', 'wsj_0078.mrg', 'wsj_0079.mrg', 'wsj_0080.mrg', 'wsj_0081.mrg', 'wsj_0082.mrg', 'wsj_0083.mrg', 'wsj_0084.mrg', 'wsj_0085.mrg', 'wsj_0086.mrg', 'wsj_0087.mrg', 'wsj_0088.mrg', 'wsj_0089.mrg', 'wsj_0090.mrg', 'wsj_0091.mrg', 'wsj_0092.mrg', 'wsj_0093.mrg', 'wsj_0094.mrg', 'wsj_0095.mrg', 'wsj_0096.mrg', 'wsj_0097.mrg', 'wsj_0098.mrg', 'wsj_0099.mrg', 'wsj_0100.mrg', 'wsj_0101.mrg', 'wsj_0102.mrg', 'wsj_0103.mrg', 'wsj_0104.mrg', 'wsj_0105.mrg', 'wsj_0106.mrg', 'wsj_0107.mrg', 'wsj_0108.mrg', 'wsj_0109.mrg', 'wsj_0110.mrg', 'wsj_0111.mrg', 'wsj_0112.mrg', 'wsj_0113.mrg', 'wsj_0114.mrg', 'wsj_0115.mrg', 'wsj_0116.mrg', 'wsj_0117.mrg', 'wsj_0118.mrg', 'wsj_0119.mrg', 'wsj_0120.mrg', 'wsj_0121.mrg', 'wsj_0122.mrg', 'wsj_0123.mrg', 'wsj_0124.mrg', 'wsj_0125.mrg', 'wsj_0126.mrg', 'wsj_0127.mrg', 'wsj_0128.mrg', 'wsj_0129.mrg', 'wsj_0130.mrg', 'wsj_0131.mrg', 'wsj_0132.mrg', 'wsj_0133.mrg', 'wsj_0134.mrg', 'wsj_0135.mrg', 'wsj_0136.mrg', 'wsj_0137.mrg', 'wsj_0138.mrg', 'wsj_0139.mrg', 'wsj_0140.mrg', 'wsj_0141.mrg', 'wsj_0142.mrg', 'wsj_0143.mrg', 'wsj_0144.mrg', 'wsj_0145.mrg', 'wsj_0146.mrg', 'wsj_0147.mrg', 'wsj_0148.mrg', 'wsj_0149.mrg', 'wsj_0150.mrg', 'wsj_0151.mrg', 'wsj_0152.mrg', 'wsj_0153.mrg', 'wsj_0154.mrg', 'wsj_0155.mrg', 'wsj_0156.mrg', 'wsj_0157.mrg', 'wsj_0158.mrg', 'wsj_0159.mrg', 'wsj_0160.mrg', 'wsj_0161.mrg', 'wsj_0162.mrg', 'wsj_0163.mrg', 'wsj_0164.mrg', 'wsj_0165.mrg', 'wsj_0166.mrg', 'wsj_0167.mrg', 'wsj_0168.mrg', 'wsj_0169.mrg', 'wsj_0170.mrg', 'wsj_0171.mrg', 'wsj_0172.mrg', 'wsj_0173.mrg', 'wsj_0174.mrg', 'wsj_0175.mrg', 'wsj_0176.mrg', 'wsj_0177.mrg', 'wsj_0178.mrg', 'wsj_0179.mrg', 'wsj_0180.mrg', 'wsj_0181.mrg', 'wsj_0182.mrg', 'wsj_0183.mrg', 'wsj_0184.mrg', 'wsj_0185.mrg', 'wsj_0186.mrg', 'wsj_0187.mrg', 'wsj_0188.mrg', 'wsj_0189.mrg', 'wsj_0190.mrg', 'wsj_0191.mrg', 'wsj_0192.mrg', 'wsj_0193.mrg', 'wsj_0194.mrg', 'wsj_0195.mrg', 'wsj_0196.mrg', 'wsj_0197.mrg', 'wsj_0198.mrg', 'wsj_0199.mrg']\n"
     ]
    }
   ],
   "source": [
    "print(ptb.fileids())"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "We can print out the content of a particular file:"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 4,
   "metadata": {},
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "\n",
      "( (S \n",
      "    (NP-SBJ \n",
      "      (NP (NNP Pierre) (NNP Vinken) )\n",
      "      (, ,) \n",
      "      (ADJP \n",
      "        (NP (CD 61) (NNS years) )\n",
      "        (JJ old) )\n",
      "      (, ,) )\n",
      "    (VP (MD will) \n",
      "      (VP (VB join) \n",
      "        (NP (DT the) (NN board) )\n",
      "        (PP-CLR (IN as) \n",
      "          (NP (DT a) (JJ nonexecutive) (NN director) ))\n",
      "        (NP-TMP (NNP Nov.) (CD 29) )))\n",
      "    (. .) ))\n",
      "( (S \n",
      "    (NP-SBJ (NNP Mr.) (NNP Vinken) )\n",
      "    (VP (VBZ is) \n",
      "      (NP-PRD \n",
      "        (NP (NN chairman) )\n",
      "        (PP (IN of) \n",
      "          (NP \n",
      "            (NP (NNP Elsevier) (NNP N.V.) )\n",
      "            (, ,) \n",
      "            (NP (DT the) (NNP Dutch) (VBG publishing) (NN group) )))))\n",
      "    (. .) ))\n",
      "\n"
     ]
    }
   ],
   "source": [
    "print(ptb.raw('wsj_0001.mrg'))"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "As you can see, the file *wsj_0001.mrg* contains two sentence trees. You can access each sentence tree individually. Here we print out the first sentence:"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 5,
   "metadata": {},
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "(S\n",
      "  (NP-SBJ\n",
      "    (NP (NNP Pierre) (NNP Vinken))\n",
      "    (, ,)\n",
      "    (ADJP (NP (CD 61) (NNS years)) (JJ old))\n",
      "    (, ,))\n",
      "  (VP\n",
      "    (MD will)\n",
      "    (VP\n",
      "      (VB join)\n",
      "      (NP (DT the) (NN board))\n",
      "      (PP-CLR (IN as) (NP (DT a) (JJ nonexecutive) (NN director)))\n",
      "      (NP-TMP (NNP Nov.) (CD 29))))\n",
      "  (. .))\n"
     ]
    }
   ],
   "source": [
    "print(ptb.parsed_sents('wsj_0001.mrg')[0])"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "And in the following code we print the second tree:"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 6,
   "metadata": {},
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "(S\n",
      "  (NP-SBJ (NNP Mr.) (NNP Vinken))\n",
      "  (VP\n",
      "    (VBZ is)\n",
      "    (NP-PRD\n",
      "      (NP (NN chairman))\n",
      "      (PP\n",
      "        (IN of)\n",
      "        (NP\n",
      "          (NP (NNP Elsevier) (NNP N.V.))\n",
      "          (, ,)\n",
      "          (NP (DT the) (NNP Dutch) (VBG publishing) (NN group))))))\n",
      "  (. .))\n"
     ]
    }
   ],
   "source": [
    "print(ptb.parsed_sents('wsj_0001.mrg')[1])"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "To see the tree structure as a graphic, you can apply the *draw()* method to the particular tree. The following code will open up a window with the drawing of the first tree in the file *wsj_0001.mrg*."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 7,
   "metadata": {},
   "outputs": [],
   "source": [
    "ptb.parsed_sents('wsj_0001.mrg')[0].draw()"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Notice that in the menu of the window you can export the drawing of the tree as a Postscript file."
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "NLTK allows you to define your own tree using the bracketed notation and the *[Tree](http://www.nltk.org/_modules/nltk/tree.html)* class."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 6,
   "metadata": {},
   "outputs": [],
   "source": [
    "from nltk import Tree"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "We can define a string variable with a syntactic tree and create a Tree object by applying the *fromstring* method from the *Tree* class:"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 7,
   "metadata": {},
   "outputs": [],
   "source": [
    "trees = \"(S (NP (NN cats ) ) (VP (V chase ) (NP (NN mice ) ) ))\"\n",
    "myTree = Tree.fromstring(trees)"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "We can print the tree in bracketed notation:"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 8,
   "metadata": {},
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "(S (NP (NN cats)) (VP (V chase) (NP (NN mice))))\n"
     ]
    }
   ],
   "source": [
    "print(myTree)"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "The internal representation of the tree looks as follows:"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 9,
   "metadata": {},
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "Tree('S', [Tree('NP', [Tree('NN', ['cats'])]), Tree('VP', [Tree('V', ['chase']), Tree('NP', [Tree('NN', ['mice'])])])])\n"
     ]
    }
   ],
   "source": [
    "print(myTree.__repr__())"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "The tree can be written in LaTeX format for the *qtree* package:"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 10,
   "metadata": {},
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "\\Tree [.S [.NP [.NN cats ] ] [.VP [.V chase ] [.NP [.NN mice ] ] ] ]\n"
     ]
    }
   ],
   "source": [
    "print(myTree.pformat_latex_qtree())"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "We can draw the tree by applying the *draw()* method to the tree object. The following code will open up a window with the drawing of the corresponding tree:"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 11,
   "metadata": {},
   "outputs": [],
   "source": [
    "myTree.draw()"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "We can print the label of a tree or subtrees using the *label* method:"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 12,
   "metadata": {},
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "S\n"
     ]
    }
   ],
   "source": [
    "print(myTree.label())"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "A daughter of the root node of the tree can be accessed using the list index notation:"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 13,
   "metadata": {},
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "(NP (NN cats))\n",
      "(VP (V chase) (NP (NN mice)))\n"
     ]
    }
   ],
   "source": [
    "print(myTree[0])\n",
    "print(myTree[1])"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "We can print out the label of these subtrees by applying the *label* method to them:"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 14,
   "metadata": {},
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "NP\n",
      "VP\n"
     ]
    }
   ],
   "source": [
    "print(myTree[0].label())\n",
    "print(myTree[1].label())"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "We can traverse the tree using these bracketed index operators:"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 15,
   "metadata": {},
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "(NP (NN cats))\n",
      "(NN cats)\n",
      "cats\n"
     ]
    }
   ],
   "source": [
    "print(myTree[0])\n",
    "print(myTree[0,0])\n",
    "print(myTree[0,0,0])"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Sections of the tree can be modified or replaced using the index notation. We replace the subject *(NN cats)* with *(NN dogs)* in the following code:"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 16,
   "metadata": {},
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "(S (NP (NN dogs)) (VP (V chase) (NP (NN mice))))\n"
     ]
    }
   ],
   "source": [
    "myTree[0,0] = Tree.fromstring('(NN dogs)')\n",
    "print(myTree)"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Various details about the tree can be accessed. We can extract the leaves of the tree using the *leaves* method:"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 17,
   "metadata": {},
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "['dogs', 'chase', 'mice']\n"
     ]
    }
   ],
   "source": [
    "print(myTree.leaves())"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "We can query the height of a tree:"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 18,
   "metadata": {},
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "5\n"
     ]
    }
   ],
   "source": [
    "print(myTree.height())"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "For specific purposes and some specific algorithms one might want to convert the tree to remove all unary relations between symbols. To collapse for example *(NP (NP (NN dogs )))* to *(NP+NP (NN cats ))*:"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 19,
   "metadata": {},
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "(S (NP+NP (NN cats)) (VP (V chase) (NP (NN mice))))\n"
     ]
    }
   ],
   "source": [
    "trees2 = \"(S (NP (NP (NN cats ) ) ) (VP (V chase ) (NP (NN mice ) ) ))\"\n",
    "myTree2 = Tree.fromstring(trees2)\n",
    "myTree2.collapse_unary()\n",
    "print(myTree2)"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "We can convert a tree to Chomsky Normal Form as well. In the following tree we have a subject NP branching into three daughter nodes. This is converted to a binary branching structure:"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 20,
   "metadata": {},
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "(S\n",
      "  (NP (NP (DET the) (NP|<JJ-NN> (JJ big) (NN cats))))\n",
      "  (VP (V chase) (NP (NN mice))))\n"
     ]
    }
   ],
   "source": [
    "trees2 = \"(S (NP (NP (DET the ) (JJ big ) (NN cats ) ) ) (VP (V chase ) (NP (NN mice ) ) ))\"\n",
    "myTree2 = Tree.fromstring(trees2)\n",
    "myTree2.chomsky_normal_form()\n",
    "print(myTree2)"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "We can generate all production rules for a tree:"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 21,
   "metadata": {},
   "outputs": [
    {
     "data": {
      "text/plain": [
       "[S -> NP VP,\n",
       " NP -> NN,\n",
       " NN -> 'dogs',\n",
       " VP -> V NP,\n",
       " V -> 'chase',\n",
       " NP -> NN,\n",
       " NN -> 'mice']"
      ]
     },
     "execution_count": 21,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "myTree.productions()"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Trees can contain nodes that are complex objects. Nodes do not have to be strings. In the following code we replace the root node of our tree with a tuple of string and integer:"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 22,
   "metadata": {},
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "(('S', 3) (NP (NN dogs)) (VP (V chase) (NP (NN mice))))\n"
     ]
    }
   ],
   "source": [
    "myTree.set_label( ('S', 3) )\n",
    "print(myTree)"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Probabilistic rules or trees can be defined in the following way:"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 23,
   "metadata": {},
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "(NP DET N) (p=0.5)\n"
     ]
    }
   ],
   "source": [
    "pt = nltk.tree.ProbabilisticTree('NP', ['DET', 'N'], prob=0.5)\n",
    "print(pt)"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Draw the tree:"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 24,
   "metadata": {},
   "outputs": [],
   "source": [
    "pt.draw()"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "In the previous sections (see links to the other notebooks above), we have seen how CFGs can be defined, read from a file, or used in a parser."
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "PCFG rules are defined in the same way. In addition a probability is assigned to each right-hand side of a rule. All probabilities for one particular left-hand side have to sum up to 1. The following code imports the PCFG class from NLTK:"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 25,
   "metadata": {},
   "outputs": [],
   "source": [
    "from nltk import PCFG"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "We can define a grammar:"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 28,
   "metadata": {},
   "outputs": [],
   "source": [
    "pcfg1 = PCFG.fromstring(\"\"\"\n",
    "    S -> NP VP [1.0]\n",
    "    NP -> Det N [0.5] | NP PP [0.25] | N [0.25]\n",
    "    PP -> P NP [1.0]\n",
    "    VP -> VP PP [0.1] | V NP [0.7] | V [0.2]\n",
    "    N -> 'woman' [0.3] | 'man' [0.3] | 'telescope' [0.3] | 'mixer' [0.1]\n",
    "    Det -> 'the' [0.6] | 'a' [0.2] | 'my' [0.2]\n",
    "    V -> 'killed' [0.35] | 'saw' [0.65]\n",
    "    P -> 'with' [0.61] | 'under' [0.39]\n",
    "\"\"\")"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "We can print out the productions:"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 29,
   "metadata": {},
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "Grammar with 19 productions (start state = S)\n",
      "    S -> NP VP [1.0]\n",
      "    NP -> Det N [0.5]\n",
      "    NP -> NP PP [0.25]\n",
      "    NP -> N [0.25]\n",
      "    PP -> P NP [1.0]\n",
      "    VP -> VP PP [0.1]\n",
      "    VP -> V NP [0.7]\n",
      "    VP -> V [0.2]\n",
      "    N -> 'woman' [0.3]\n",
      "    N -> 'man' [0.3]\n",
      "    N -> 'telescope' [0.3]\n",
      "    N -> 'mixer' [0.1]\n",
      "    Det -> 'the' [0.6]\n",
      "    Det -> 'a' [0.2]\n",
      "    Det -> 'my' [0.2]\n",
      "    V -> 'killed' [0.35]\n",
      "    V -> 'saw' [0.65]\n",
      "    P -> 'with' [0.61]\n",
      "    P -> 'under' [0.39]\n"
     ]
    }
   ],
   "source": [
    "print(pcfg1)"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "We can import the portion of the Penn Treebank as *treebank*:"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 30,
   "metadata": {},
   "outputs": [],
   "source": [
    "from nltk.corpus import treebank"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "We can now loop over all files, read the sentences in, extract all production rules from them, and aggregate the production rules in a list:"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 31,
   "metadata": {},
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "[S -> NP-SBJ VP ., NP-SBJ -> NP , ADJP ,, NP -> NNP NNP, NNP -> 'Pierre', NNP -> 'Vinken', , -> ',', ADJP -> NP JJ, NP -> CD NNS, CD -> '61', NNS -> 'years', JJ -> 'old', , -> ',', VP -> MD VP, MD -> 'will', VP -> VB NP PP-CLR NP-TMP, VB -> 'join', NP -> DT NN, DT -> 'the', NN -> 'board', PP-CLR -> IN NP, IN -> 'as', NP -> DT JJ NN, DT -> 'a', JJ -> 'nonexecutive', NN -> 'director', NP-TMP -> NNP CD, NNP -> 'Nov.', CD -> '29', . -> '.', S -> NP-SBJ VP ., NP-SBJ -> NNP NNP, NNP -> 'Mr.', NNP -> 'Vinken', VP -> VBZ NP-PRD, VBZ -> 'is', NP-PRD -> NP PP, NP -> NN, NN -> 'chairman', PP -> IN NP, IN -> 'of', NP -> NP , NP, NP -> NNP NNP, NNP -> 'Elsevier', NNP -> 'N.V.', , -> ',', NP -> DT NNP VBG NN, DT -> 'the', NNP -> 'Dutch', VBG -> 'publishing', NN -> 'group', . -> '.', S -> NP-SBJ-1 VP ., NP-SBJ-1 -> NP , UCP ,, NP -> NNP NNP, NNP -> 'Rudolph', NNP -> 'Agnew', , -> ',', UCP -> ADJP CC NP, ADJP -> NP JJ, NP -> CD NNS, CD -> '55', NNS -> 'years', JJ -> 'old', CC -> 'and', NP -> NP PP, NP -> JJ NN, JJ -> 'former', NN -> 'chairman', PP -> IN NP, IN -> 'of', NP -> NNP NNP NNP NNP, NNP -> 'Consolidated', NNP -> 'Gold', NNP -> 'Fields', NNP -> 'PLC', , -> ',', VP -> VBD VP, VBD -> 'was', VP -> VBN S, VBN -> 'named', S -> NP-SBJ NP-PRD, NP-SBJ -> -NONE-, -NONE- -> '*-1', NP-PRD -> NP PP, NP -> DT JJ NN, DT -> 'a', JJ -> 'nonexecutive', NN -> 'director', PP -> IN NP, IN -> 'of', NP -> DT JJ JJ NN, DT -> 'this', JJ -> 'British', JJ -> 'industrial', NN -> 'conglomerate', . -> '.']\n"
     ]
    }
   ],
   "source": [
    "productions = []\n",
    "for t in treebank.fileids()[:2]:\n",
    "    for x in treebank.parsed_sents(t):\n",
    "        productions += x.productions()\n",
    "print(productions)"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "To be able to induce the PCFG, we need to define a *Nonterminal* object with the start symbol as label:"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 32,
   "metadata": {},
   "outputs": [],
   "source": [
    "from nltk import Nonterminal\n",
    "S = Nonterminal('S')"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "We can now induce the PCFG using the *Nonterminal* start symbol and the list of production rules:"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 33,
   "metadata": {},
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "Grammar with 71 productions (start state = S)\n",
      "    S -> NP-SBJ VP . [0.5]\n",
      "    NP-SBJ -> NP , ADJP , [0.333333]\n",
      "    NP -> NNP NNP [0.2]\n",
      "    NNP -> 'Pierre' [0.0714286]\n",
      "    NNP -> 'Vinken' [0.142857]\n",
      "    , -> ',' [1.0]\n",
      "    ADJP -> NP JJ [1.0]\n",
      "    NP -> CD NNS [0.133333]\n",
      "    CD -> '61' [0.333333]\n",
      "    NNS -> 'years' [1.0]\n",
      "    JJ -> 'old' [0.285714]\n",
      "    VP -> MD VP [0.2]\n",
      "    MD -> 'will' [1.0]\n",
      "    VP -> VB NP PP-CLR NP-TMP [0.2]\n",
      "    VB -> 'join' [1.0]\n",
      "    NP -> DT NN [0.0666667]\n",
      "    DT -> 'the' [0.4]\n",
      "    NN -> 'board' [0.142857]\n",
      "    PP-CLR -> IN NP [1.0]\n",
      "    IN -> 'as' [0.25]\n",
      "    NP -> DT JJ NN [0.133333]\n",
      "    DT -> 'a' [0.4]\n",
      "    JJ -> 'nonexecutive' [0.285714]\n",
      "    NN -> 'director' [0.285714]\n",
      "    NP-TMP -> NNP CD [1.0]\n",
      "    NNP -> 'Nov.' [0.0714286]\n",
      "    CD -> '29' [0.333333]\n",
      "    . -> '.' [1.0]\n",
      "    NP-SBJ -> NNP NNP [0.333333]\n",
      "    NNP -> 'Mr.' [0.0714286]\n",
      "    VP -> VBZ NP-PRD [0.2]\n",
      "    VBZ -> 'is' [1.0]\n",
      "    NP-PRD -> NP PP [1.0]\n",
      "    NP -> NN [0.0666667]\n",
      "    NN -> 'chairman' [0.285714]\n",
      "    PP -> IN NP [1.0]\n",
      "    IN -> 'of' [0.75]\n",
      "    NP -> NP , NP [0.0666667]\n",
      "    NNP -> 'Elsevier' [0.0714286]\n",
      "    NNP -> 'N.V.' [0.0714286]\n",
      "    NP -> DT NNP VBG NN [0.0666667]\n",
      "    NNP -> 'Dutch' [0.0714286]\n",
      "    VBG -> 'publishing' [1.0]\n",
      "    NN -> 'group' [0.142857]\n",
      "    S -> NP-SBJ-1 VP . [0.25]\n",
      "    NP-SBJ-1 -> NP , UCP , [1.0]\n",
      "    NNP -> 'Rudolph' [0.0714286]\n",
      "    NNP -> 'Agnew' [0.0714286]\n",
      "    UCP -> ADJP CC NP [1.0]\n",
      "    CD -> '55' [0.333333]\n",
      "    CC -> 'and' [1.0]\n",
      "    NP -> NP PP [0.0666667]\n",
      "    NP -> JJ NN [0.0666667]\n",
      "    JJ -> 'former' [0.142857]\n",
      "    NP -> NNP NNP NNP NNP [0.0666667]\n",
      "    NNP -> 'Consolidated' [0.0714286]\n",
      "    NNP -> 'Gold' [0.0714286]\n",
      "    NNP -> 'Fields' [0.0714286]\n",
      "    NNP -> 'PLC' [0.0714286]\n",
      "    VP -> VBD VP [0.2]\n",
      "    VBD -> 'was' [1.0]\n",
      "    VP -> VBN S [0.2]\n",
      "    VBN -> 'named' [1.0]\n",
      "    S -> NP-SBJ NP-PRD [0.25]\n",
      "    NP-SBJ -> -NONE- [0.333333]\n",
      "    -NONE- -> '*-1' [1.0]\n",
      "    NP -> DT JJ JJ NN [0.0666667]\n",
      "    DT -> 'this' [0.2]\n",
      "    JJ -> 'British' [0.142857]\n",
      "    JJ -> 'industrial' [0.142857]\n",
      "    NN -> 'conglomerate' [0.142857]\n"
     ]
    }
   ],
   "source": [
    "grammar = nltk.induce_pcfg(S, productions)\n",
    "print(grammar)"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "We can normalize the trees by collapsing unary branches and converting them to Chomsky Normal Form before we extract the production rules and induce the grammar:"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 34,
   "metadata": {},
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "Grammar with 86 productions (start state = S)\n",
      "    S -> NP-SBJ S|<VP-.> [0.5]\n",
      "    NP-SBJ -> NP NP-SBJ|<,-ADJP> [0.333333]\n",
      "    NP -> NNP NNP [0.2]\n",
      "    NNP -> 'Pierre' [0.0714286]\n",
      "    NNP -> 'Vinken' [0.142857]\n",
      "    NP-SBJ|<,-ADJP> -> , NP-SBJ|<ADJP-,> [1.0]\n",
      "    , -> ',' [1.0]\n",
      "    NP-SBJ|<ADJP-,> -> ADJP , [1.0]\n",
      "    ADJP -> NP JJ [1.0]\n",
      "    NP -> CD NNS [0.133333]\n",
      "    CD -> '61' [0.333333]\n",
      "    NNS -> 'years' [1.0]\n",
      "    JJ -> 'old' [0.285714]\n",
      "    S|<VP-.> -> VP . [1.0]\n",
      "    VP -> MD VP [0.2]\n",
      "    MD -> 'will' [1.0]\n",
      "    VP -> VB VP|<NP-PP-CLR> [0.2]\n",
      "    VB -> 'join' [1.0]\n",
      "    VP|<NP-PP-CLR> -> NP VP|<PP-CLR-NP-TMP> [1.0]\n",
      "    NP -> DT NN [0.0666667]\n",
      "    DT -> 'the' [0.4]\n",
      "    NN -> 'board' [0.142857]\n",
      "    VP|<PP-CLR-NP-TMP> -> PP-CLR NP-TMP [1.0]\n",
      "    PP-CLR -> IN NP [1.0]\n",
      "    IN -> 'as' [0.25]\n",
      "    NP -> DT NP|<JJ-NN> [0.133333]\n",
      "    DT -> 'a' [0.4]\n",
      "    NP|<JJ-NN> -> JJ NN [1.0]\n",
      "    JJ -> 'nonexecutive' [0.285714]\n",
      "    NN -> 'director' [0.285714]\n",
      "    NP-TMP -> NNP CD [1.0]\n",
      "    NNP -> 'Nov.' [0.0714286]\n",
      "    CD -> '29' [0.333333]\n",
      "    . -> '.' [1.0]\n",
      "    NP-SBJ -> NNP NNP [0.333333]\n",
      "    NNP -> 'Mr.' [0.0714286]\n",
      "    VP -> VBZ NP-PRD [0.2]\n",
      "    VBZ -> 'is' [1.0]\n",
      "    NP-PRD -> NP PP [1.0]\n",
      "    NP -> NN [0.0666667]\n",
      "    NN -> 'chairman' [0.285714]\n",
      "    PP -> IN NP [1.0]\n",
      "    IN -> 'of' [0.75]\n",
      "    NP -> NP NP|<,-NP> [0.0666667]\n",
      "    NNP -> 'Elsevier' [0.0714286]\n",
      "    NNP -> 'N.V.' [0.0714286]\n",
      "    NP|<,-NP> -> , NP [1.0]\n",
      "    NP -> DT NP|<NNP-VBG> [0.0666667]\n",
      "    NP|<NNP-VBG> -> NNP NP|<VBG-NN> [1.0]\n",
      "    NNP -> 'Dutch' [0.0714286]\n",
      "    NP|<VBG-NN> -> VBG NN [1.0]\n",
      "    VBG -> 'publishing' [1.0]\n",
      "    NN -> 'group' [0.142857]\n",
      "    S -> NP-SBJ-1 S|<VP-.> [0.25]\n",
      "    NP-SBJ-1 -> NP NP-SBJ-1|<,-UCP> [1.0]\n",
      "    NNP -> 'Rudolph' [0.0714286]\n",
      "    NNP -> 'Agnew' [0.0714286]\n",
      "    NP-SBJ-1|<,-UCP> -> , NP-SBJ-1|<UCP-,> [1.0]\n",
      "    NP-SBJ-1|<UCP-,> -> UCP , [1.0]\n",
      "    UCP -> ADJP UCP|<CC-NP> [1.0]\n",
      "    CD -> '55' [0.333333]\n",
      "    UCP|<CC-NP> -> CC NP [1.0]\n",
      "    CC -> 'and' [1.0]\n",
      "    NP -> NP PP [0.0666667]\n",
      "    NP -> JJ NN [0.0666667]\n",
      "    JJ -> 'former' [0.142857]\n",
      "    NP -> NNP NP|<NNP-NNP> [0.0666667]\n",
      "    NNP -> 'Consolidated' [0.0714286]\n",
      "    NP|<NNP-NNP> -> NNP NP|<NNP-NNP> [0.5]\n",
      "    NNP -> 'Gold' [0.0714286]\n",
      "    NP|<NNP-NNP> -> NNP NNP [0.5]\n",
      "    NNP -> 'Fields' [0.0714286]\n",
      "    NNP -> 'PLC' [0.0714286]\n",
      "    VP -> VBD VP [0.2]\n",
      "    VBD -> 'was' [1.0]\n",
      "    VP -> VBN S [0.2]\n",
      "    VBN -> 'named' [1.0]\n",
      "    S -> NP-SBJ NP-PRD [0.25]\n",
      "    NP-SBJ -> -NONE- [0.333333]\n",
      "    -NONE- -> '*-1' [1.0]\n",
      "    NP -> DT NP|<JJ-JJ> [0.0666667]\n",
      "    DT -> 'this' [0.2]\n",
      "    NP|<JJ-JJ> -> JJ NP|<JJ-NN> [1.0]\n",
      "    JJ -> 'British' [0.142857]\n",
      "    JJ -> 'industrial' [0.142857]\n",
      "    NN -> 'conglomerate' [0.142857]\n"
     ]
    }
   ],
   "source": [
    "productions = []\n",
    "for t in treebank.fileids()[:2]:\n",
    "    for x in treebank.parsed_sents(t):\n",
    "        x.collapse_unary(collapsePOS = False)\n",
    "        x.chomsky_normal_form(horzMarkov = 2)\n",
    "        productions += x.productions()\n",
    "grammar = nltk.induce_pcfg(S, productions)\n",
    "print(grammar)"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "## Parsing with PCFGs"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "NLTK provides various parser implementations. One that implements the Viterbi CKY n-best parses over a PCFG is available in the [parse.viterbi](http://www.nltk.org/_modules/nltk/parse/viterbi.html) module. (See [Michael Elhadad](https://www.cs.bgu.ac.il/~elhadad/)'s notebook *[Constituent-based Syntactic Parsing with NLTK](https://www.cs.bgu.ac.il/~elhadad/nlp16/nltk-pcfg.html)* for more details.)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 35,
   "metadata": {},
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "Parse sentence using induced grammar:\n",
      "['Pierre', 'Vinken', ',', '61', 'years', 'old', ',', 'will', 'join', 'the', 'board', 'as', 'a', 'nonexecutive', 'director', 'Nov.', '29', '.']\n",
      "  |[-] . . . . . . . . . . . . . . . . .| [0:1] 'Pierre' [1.0]\n",
      "  |. [-] . . . . . . . . . . . . . . . .| [1:2] 'Vinken' [1.0]\n",
      "  |. . [-] . . . . . . . . . . . . . . .| [2:3] ','  [1.0]\n",
      "  |. . . [-] . . . . . . . . . . . . . .| [3:4] '61' [1.0]\n",
      "  |. . . . [-] . . . . . . . . . . . . .| [4:5] 'years' [1.0]\n",
      "  |. . . . . [-] . . . . . . . . . . . .| [5:6] 'old' [1.0]\n",
      "  |. . . . . . [-] . . . . . . . . . . .| [6:7] ','  [1.0]\n",
      "  |. . . . . . . [-] . . . . . . . . . .| [7:8] 'will' [1.0]\n",
      "  |. . . . . . . . [-] . . . . . . . . .| [8:9] 'join' [1.0]\n",
      "  |. . . . . . . . . [-] . . . . . . . .| [9:10] 'the' [1.0]\n",
      "  |. . . . . . . . . . [-] . . . . . . .| [10:11] 'board' [1.0]\n",
      "  |. . . . . . . . . . . [-] . . . . . .| [11:12] 'as' [1.0]\n",
      "  |. . . . . . . . . . . . [-] . . . . .| [12:13] 'a' [1.0]\n",
      "  |. . . . . . . . . . . . . [-] . . . .| [13:14] 'nonexecutive' [1.0]\n",
      "  |. . . . . . . . . . . . . . [-] . . .| [14:15] 'director' [1.0]\n",
      "  |. . . . . . . . . . . . . . . [-] . .| [15:16] 'Nov.' [1.0]\n",
      "  |. . . . . . . . . . . . . . . . [-] .| [16:17] '29' [1.0]\n",
      "  |. . . . . . . . . . . . . . . . . [-]| [17:18] '.' [1.0]\n",
      "  |. . . . . . . . . . . . . . . . . [-]| [17:18] '.' [1.0]\n",
      "  |. . . . . . . . . . . . . . . . . [-]| [17:18] .  -> '.' * [1.0]\n",
      "  |. . . . . . . . . . . . . . . . . > .| [17:17] .  -> * '.' [1.0]\n",
      "  |. . . . . . . . . . . . . . . . [-] .| [16:17] '29' [1.0]\n",
      "  |. . . . . . . . . . . . . . . [-] . .| [15:16] 'Nov.' [1.0]\n",
      "  |. . . . . . . . . . . . . . [-] . . .| [14:15] 'director' [1.0]\n",
      "  |. . . . . . . . . . . . . [-] . . . .| [13:14] 'nonexecutive' [1.0]\n",
      "  |. . . . . . . . . . . . [-] . . . . .| [12:13] 'a' [1.0]\n",
      "  |. . . . . . . . . . . [-] . . . . . .| [11:12] 'as' [1.0]\n",
      "  |. . . . . . . . . . [-] . . . . . . .| [10:11] 'board' [1.0]\n",
      "  |. . . . . . . . . [-] . . . . . . . .| [9:10] 'the' [1.0]\n",
      "  |. . . . . . . . [-] . . . . . . . . .| [8:9] 'join' [1.0]\n",
      "  |. . . . . . . . [-] . . . . . . . . .| [8:9] VB -> 'join' * [1.0]\n",
      "  |. . . . . . . . > . . . . . . . . . .| [8:8] VB -> * 'join' [1.0]\n",
      "  |. . . . . . . [-] . . . . . . . . . .| [7:8] 'will' [1.0]\n",
      "  |. . . . . . . [-] . . . . . . . . . .| [7:8] MD -> 'will' * [1.0]\n",
      "  |. . . . . . . > . . . . . . . . . . .| [7:7] MD -> * 'will' [1.0]\n",
      "  |. . . . . . [-] . . . . . . . . . . .| [6:7] ','  [1.0]\n",
      "  |. . . . . . [-] . . . . . . . . . . .| [6:7] ,  -> ',' * [1.0]\n",
      "  |. . . . . . [-> . . . . . . . . . . .| [6:7] NP-SBJ-1|<,-UCP> -> , * NP-SBJ-1|<UCP-,> [1.0]\n",
      "  |. . . . . . [-> . . . . . . . . . . .| [6:7] NP|<,-NP> -> , * NP [1.0]\n",
      "  |. . . . . . [-> . . . . . . . . . . .| [6:7] NP-SBJ|<,-ADJP> -> , * NP-SBJ|<ADJP-,> [1.0]\n",
      "  |. . . . . . > . . . . . . . . . . . .| [6:6] NP-SBJ-1|<,-UCP> -> * , NP-SBJ-1|<UCP-,> [1.0]\n",
      "  |. . . . . . > . . . . . . . . . . . .| [6:6] NP|<,-NP> -> * , NP [1.0]\n",
      "  |. . . . . . > . . . . . . . . . . . .| [6:6] NP-SBJ|<,-ADJP> -> * , NP-SBJ|<ADJP-,> [1.0]\n",
      "  |. . . . . . > . . . . . . . . . . . .| [6:6] ,  -> * ',' [1.0]\n",
      "  |. . . . . [-] . . . . . . . . . . . .| [5:6] 'old' [1.0]\n",
      "  |. . . . [-] . . . . . . . . . . . . .| [4:5] 'years' [1.0]\n",
      "  |. . . . [-] . . . . . . . . . . . . .| [4:5] NNS -> 'years' * [1.0]\n",
      "  |. . . . > . . . . . . . . . . . . . .| [4:4] NNS -> * 'years' [1.0]\n",
      "  |. . . [-] . . . . . . . . . . . . . .| [3:4] '61' [1.0]\n",
      "  |. . [-] . . . . . . . . . . . . . . .| [2:3] ','  [1.0]\n",
      "  |. . [-] . . . . . . . . . . . . . . .| [2:3] ,  -> ',' * [1.0]\n",
      "  |. . [-> . . . . . . . . . . . . . . .| [2:3] NP-SBJ-1|<,-UCP> -> , * NP-SBJ-1|<UCP-,> [1.0]\n",
      "  |. . [-> . . . . . . . . . . . . . . .| [2:3] NP|<,-NP> -> , * NP [1.0]\n",
      "  |. . [-> . . . . . . . . . . . . . . .| [2:3] NP-SBJ|<,-ADJP> -> , * NP-SBJ|<ADJP-,> [1.0]\n",
      "  |. . > . . . . . . . . . . . . . . . .| [2:2] NP-SBJ-1|<,-UCP> -> * , NP-SBJ-1|<UCP-,> [1.0]\n",
      "  |. . > . . . . . . . . . . . . . . . .| [2:2] NP|<,-NP> -> * , NP [1.0]\n",
      "  |. . > . . . . . . . . . . . . . . . .| [2:2] NP-SBJ|<,-ADJP> -> * , NP-SBJ|<ADJP-,> [1.0]\n",
      "  |. . > . . . . . . . . . . . . . . . .| [2:2] ,  -> * ',' [1.0]\n",
      "  |. [-] . . . . . . . . . . . . . . . .| [1:2] 'Vinken' [1.0]\n",
      "  |[-] . . . . . . . . . . . . . . . . .| [0:1] 'Pierre' [1.0]\n",
      "  |. . . . . . . . . [-] . . . . . . . .| [9:10] DT -> 'the' * [0.4]\n",
      "  |. . . . . . . . . > . . . . . . . . .| [9:9] DT -> * 'the' [0.4]\n",
      "  |. . . . . . . . . . . . [-] . . . . .| [12:13] DT -> 'a' * [0.4]\n",
      "  |. . . . . . . . . . . . > . . . . . .| [12:12] DT -> * 'a' [0.4]\n",
      "  |. . . [-] . . . . . . . . . . . . . .| [3:4] CD -> '61' * [0.3333333333333333]\n",
      "  |. . . > . . . . . . . . . . . . . . .| [3:3] CD -> * '61' [0.3333333333333333]\n",
      "  |. . . . . . . . . . . . . . . . [-] .| [16:17] CD -> '29' * [0.3333333333333333]\n",
      "  |. . . . . . . . . . . . . . . . > . .| [16:16] CD -> * '29' [0.3333333333333333]\n",
      "  |. . . . . [-] . . . . . . . . . . . .| [5:6] JJ -> 'old' * [0.2857142857142857]\n",
      "  |. . . . . > . . . . . . . . . . . . .| [5:5] NP|<JJ-JJ> -> * JJ NP|<JJ-NN> [1.0]\n",
      "  |. . . . . > . . . . . . . . . . . . .| [5:5] NP|<JJ-NN> -> * JJ NN [1.0]\n",
      "  |. . . . . [-> . . . . . . . . . . . .| [5:6] NP|<JJ-JJ> -> JJ * NP|<JJ-NN> [0.2857142857142857]\n",
      "  |. . . . . [-> . . . . . . . . . . . .| [5:6] NP|<JJ-NN> -> JJ * NN [0.2857142857142857]\n",
      "  |. . . . . > . . . . . . . . . . . . .| [5:5] JJ -> * 'old' [0.2857142857142857]\n",
      "  |. . . . . . . . . . . . . [-] . . . .| [13:14] JJ -> 'nonexecutive' * [0.2857142857142857]\n",
      "  |. . . . . . . . . . . . . > . . . . .| [13:13] NP|<JJ-JJ> -> * JJ NP|<JJ-NN> [1.0]\n",
      "  |. . . . . . . . . . . . . > . . . . .| [13:13] NP|<JJ-NN> -> * JJ NN [1.0]\n",
      "  |. . . . . . . . . . . . . [-> . . . .| [13:14] NP|<JJ-JJ> -> JJ * NP|<JJ-NN> [0.2857142857142857]\n",
      "  |. . . . . . . . . . . . . [-> . . . .| [13:14] NP|<JJ-NN> -> JJ * NN [0.2857142857142857]\n",
      "  |. . . . . . . . . . . . . > . . . . .| [13:13] JJ -> * 'nonexecutive' [0.2857142857142857]\n",
      "  |. . . . . . . . . . . . . . [-] . . .| [14:15] NN -> 'director' * [0.2857142857142857]\n",
      "  |. . . . . . . . . . . . . . > . . . .| [14:14] NN -> * 'director' [0.2857142857142857]\n",
      "  |. . . . . . . . . . . [-] . . . . . .| [11:12] IN -> 'as' * [0.25]\n",
      "  |. . . . . . . . . . . > . . . . . . .| [11:11] PP -> * IN NP [1.0]\n",
      "  |. . . . . . . . . . . > . . . . . . .| [11:11] PP-CLR -> * IN NP [1.0]\n",
      "  |. . . . . . . . . . . [-> . . . . . .| [11:12] PP -> IN * NP [0.25]\n",
      "  |. . . . . . . . . . . [-> . . . . . .| [11:12] PP-CLR -> IN * NP [0.25]\n",
      "  |. . . . . . . . . . . > . . . . . . .| [11:11] IN -> * 'as' [0.25]\n",
      "  |. . . . . . . [-> . . . . . . . . . .| [7:8] VP -> MD * VP [0.2]\n",
      "  |. . . . . . . > . . . . . . . . . . .| [7:7] VP -> * MD VP [0.2]\n",
      "  |. . . . . . . . [-> . . . . . . . . .| [8:9] VP -> VB * VP|<NP-PP-CLR> [0.2]\n",
      "  |. . . . . . . . > . . . . . . . . . .| [8:8] VP -> * VB VP|<NP-PP-CLR> [0.2]\n",
      "  |. [-] . . . . . . . . . . . . . . . .| [1:2] NNP -> 'Vinken' * [0.14285714285714285]\n",
      "  |. > . . . . . . . . . . . . . . . . .| [1:1] NP|<NNP-VBG> -> * NNP NP|<VBG-NN> [1.0]\n",
      "  |. > . . . . . . . . . . . . . . . . .| [1:1] NP-TMP -> * NNP CD [1.0]\n",
      "  |. > . . . . . . . . . . . . . . . . .| [1:1] NP|<NNP-NNP> -> * NNP NNP [0.5]\n",
      "  |. > . . . . . . . . . . . . . . . . .| [1:1] NP|<NNP-NNP> -> * NNP NP|<NNP-NNP> [0.5]\n",
      "  |. > . . . . . . . . . . . . . . . . .| [1:1] NP-SBJ -> * NNP NNP [0.3333333333333333]\n",
      "  |. > . . . . . . . . . . . . . . . . .| [1:1] NP -> * NNP NNP [0.2]\n",
      "  |. [-> . . . . . . . . . . . . . . . .| [1:2] NP|<NNP-VBG> -> NNP * NP|<VBG-NN> [0.14285714285714285]\n",
      "  |. [-> . . . . . . . . . . . . . . . .| [1:2] NP-TMP -> NNP * CD [0.14285714285714285]\n",
      "  |. > . . . . . . . . . . . . . . . . .| [1:1] NNP -> * 'Vinken' [0.14285714285714285]\n",
      "  |. . . . . . . . . . [-] . . . . . . .| [10:11] NN -> 'board' * [0.14285714285714285]\n",
      "  |. . . . . . . . . . > . . . . . . . .| [10:10] NN -> * 'board' [0.14285714285714285]\n",
      "  |. . . . . . . . . . . . . . . . > . .| [16:16] NP -> * CD NNS [0.13333333333333333]\n",
      "  |. . . > . . . . . . . . . . . . . . .| [3:3] NP -> * CD NNS [0.13333333333333333]\n",
      "  |. . . . . . . . . . . . > . . . . . .| [12:12] NP -> * DT NP|<JJ-NN> [0.13333333333333333]\n",
      "  |. . . . . . . . . > . . . . . . . . .| [9:9] NP -> * DT NP|<JJ-NN> [0.13333333333333333]\n",
      "  |. . . . . . . . . . . . . [---] . . .| [13:15] NP|<JJ-NN> -> JJ NN * [0.08163265306122448]\n",
      "  |. [-> . . . . . . . . . . . . . . . .| [1:2] NP|<NNP-NNP> -> NNP * NNP [0.07142857142857142]\n",
      "  |. [-> . . . . . . . . . . . . . . . .| [1:2] NP|<NNP-NNP> -> NNP * NP|<NNP-NNP> [0.07142857142857142]\n",
      "  |[-] . . . . . . . . . . . . . . . . .| [0:1] NNP -> 'Pierre' * [0.07142857142857142]\n",
      "  |> . . . . . . . . . . . . . . . . . .| [0:0] NP|<NNP-VBG> -> * NNP NP|<VBG-NN> [1.0]\n",
      "  |> . . . . . . . . . . . . . . . . . .| [0:0] NP-TMP -> * NNP CD [1.0]\n",
      "  |> . . . . . . . . . . . . . . . . . .| [0:0] NP|<NNP-NNP> -> * NNP NNP [0.5]\n",
      "  |> . . . . . . . . . . . . . . . . . .| [0:0] NP|<NNP-NNP> -> * NNP NP|<NNP-NNP> [0.5]\n",
      "  |> . . . . . . . . . . . . . . . . . .| [0:0] NP-SBJ -> * NNP NNP [0.3333333333333333]\n",
      "  |> . . . . . . . . . . . . . . . . . .| [0:0] NP -> * NNP NNP [0.2]\n",
      "  |[-> . . . . . . . . . . . . . . . . .| [0:1] NP|<NNP-VBG> -> NNP * NP|<VBG-NN> [0.07142857142857142]\n",
      "  |[-> . . . . . . . . . . . . . . . . .| [0:1] NP-TMP -> NNP * CD [0.07142857142857142]\n",
      "  |> . . . . . . . . . . . . . . . . . .| [0:0] NNP -> * 'Pierre' [0.07142857142857142]\n",
      "  |. . . . . . . . . . . . . . . [-] . .| [15:16] NNP -> 'Nov.' * [0.07142857142857142]\n",
      "  |. . . . . . . . . . . . . . . > . . .| [15:15] NP|<NNP-VBG> -> * NNP NP|<VBG-NN> [1.0]\n",
      "  |. . . . . . . . . . . . . . . > . . .| [15:15] NP-TMP -> * NNP CD [1.0]\n",
      "  |. . . . . . . . . . . . . . . > . . .| [15:15] NP|<NNP-NNP> -> * NNP NNP [0.5]\n",
      "  |. . . . . . . . . . . . . . . > . . .| [15:15] NP|<NNP-NNP> -> * NNP NP|<NNP-NNP> [0.5]\n",
      "  |. . . . . . . . . . . . . . . > . . .| [15:15] NP-SBJ -> * NNP NNP [0.3333333333333333]\n",
      "  |. . . . . . . . . . . . . . . > . . .| [15:15] NP -> * NNP NNP [0.2]\n",
      "  |. . . . . . . . . . . . . . . [-> . .| [15:16] NP|<NNP-VBG> -> NNP * NP|<VBG-NN> [0.07142857142857142]\n",
      "  |. . . . . . . . . . . . . . . [-> . .| [15:16] NP-TMP -> NNP * CD [0.07142857142857142]\n",
      "  |. . . . . . . . . . . . . . . > . . .| [15:15] NNP -> * 'Nov.' [0.07142857142857142]\n",
      "  |. . . . . . . . . . . . . . . > . . .| [15:15] NP -> * NNP NP|<NNP-NNP> [0.06666666666666667]\n",
      "  |> . . . . . . . . . . . . . . . . . .| [0:0] NP -> * NNP NP|<NNP-NNP> [0.06666666666666667]\n",
      "  |. . . . . . . . . . > . . . . . . . .| [10:10] NP -> * NN [0.06666666666666667]\n",
      "  |. > . . . . . . . . . . . . . . . . .| [1:1] NP -> * NNP NP|<NNP-NNP> [0.06666666666666667]\n",
      "  |. . . . . . . . . . . . . . > . . . .| [14:14] NP -> * NN [0.06666666666666667]\n",
      "  |. . . . . . . . . . . . . > . . . . .| [13:13] NP -> * JJ NN [0.06666666666666667]\n",
      "  |. . . . . > . . . . . . . . . . . . .| [5:5] NP -> * JJ NN [0.06666666666666667]\n",
      "  |. . . . . . . . . . . . > . . . . . .| [12:12] NP -> * DT NP|<JJ-JJ> [0.06666666666666667]\n",
      "  |. . . . . . . . . . . . > . . . . . .| [12:12] NP -> * DT NP|<NNP-VBG> [0.06666666666666667]\n",
      "  |. . . . . . . . . . . . > . . . . . .| [12:12] NP -> * DT NN [0.06666666666666667]\n",
      "  |. . . . . . . . . > . . . . . . . . .| [9:9] NP -> * DT NP|<JJ-JJ> [0.06666666666666667]\n",
      "  |. . . . . . . . . > . . . . . . . . .| [9:9] NP -> * DT NP|<NNP-VBG> [0.06666666666666667]\n",
      "  |. . . . . . . . . > . . . . . . . . .| [9:9] NP -> * DT NN [0.06666666666666667]\n",
      "  |. . . . . . . . . . . . [-> . . . . .| [12:13] NP -> DT * NP|<JJ-NN> [0.05333333333333334]\n",
      "  |. . . . . . . . . [-> . . . . . . . .| [9:10] NP -> DT * NP|<JJ-NN> [0.05333333333333334]\n",
      "  |. [-> . . . . . . . . . . . . . . . .| [1:2] NP-SBJ -> NNP * NNP [0.047619047619047616]\n",
      "  |. . . . . . . . . . . . . . . . [-> .| [16:17] NP -> CD * NNS [0.04444444444444444]\n",
      "  |. . . [-> . . . . . . . . . . . . . .| [3:4] NP -> CD * NNS [0.04444444444444444]\n",
      "  |. . . [---] . . . . . . . . . . . . .| [3:5] NP -> CD NNS * [0.04444444444444444]\n",
      "  |. . . > . . . . . . . . . . . . . . .| [3:3] NP-SBJ-1 -> * NP NP-SBJ-1|<,-UCP> [1.0]\n",
      "  |. . . > . . . . . . . . . . . . . . .| [3:3] NP-PRD -> * NP PP [1.0]\n",
      "  |. . . > . . . . . . . . . . . . . . .| [3:3] VP|<NP-PP-CLR> -> * NP VP|<PP-CLR-NP-TMP> [1.0]\n",
      "  |. . . > . . . . . . . . . . . . . . .| [3:3] ADJP -> * NP JJ [1.0]\n",
      "  |. . . > . . . . . . . . . . . . . . .| [3:3] NP-SBJ -> * NP NP-SBJ|<,-ADJP> [0.3333333333333333]\n",
      "  |. . . > . . . . . . . . . . . . . . .| [3:3] NP -> * NP PP [0.06666666666666667]\n",
      "  |. . . > . . . . . . . . . . . . . . .| [3:3] NP -> * NP NP|<,-NP> [0.06666666666666667]\n",
      "  |. . . [---> . . . . . . . . . . . . .| [3:5] NP-SBJ-1 -> NP * NP-SBJ-1|<,-UCP> [0.04444444444444444]\n",
      "  |. . . [---> . . . . . . . . . . . . .| [3:5] NP-PRD -> NP * PP [0.04444444444444444]\n",
      "  |. . . [---> . . . . . . . . . . . . .| [3:5] VP|<NP-PP-CLR> -> NP * VP|<PP-CLR-NP-TMP> [0.04444444444444444]\n",
      "  |. . . [---> . . . . . . . . . . . . .| [3:5] ADJP -> NP * JJ [0.04444444444444444]\n",
      "  |. . [-----] . . . . . . . . . . . . .| [2:5] NP|<,-NP> -> , NP * [0.04444444444444444]\n",
      "  |. . . . . . . . . . . . . . . [-> . .| [15:16] NP|<NNP-NNP> -> NNP * NNP [0.03571428571428571]\n",
      "  |. . . . . . . . . . . . . . . [-> . .| [15:16] NP|<NNP-NNP> -> NNP * NP|<NNP-NNP> [0.03571428571428571]\n",
      "  |[-> . . . . . . . . . . . . . . . . .| [0:1] NP|<NNP-NNP> -> NNP * NNP [0.03571428571428571]\n",
      "  |[-> . . . . . . . . . . . . . . . . .| [0:1] NP|<NNP-NNP> -> NNP * NP|<NNP-NNP> [0.03571428571428571]\n",
      "  |. [-> . . . . . . . . . . . . . . . .| [1:2] NP -> NNP * NNP [0.02857142857142857]\n",
      "  |. . . . . . . . . . . . [-> . . . . .| [12:13] NP -> DT * NP|<JJ-JJ> [0.02666666666666667]\n",
      "  |. . . . . . . . . . . . [-> . . . . .| [12:13] NP -> DT * NP|<NNP-VBG> [0.02666666666666667]\n",
      "  |. . . . . . . . . . . . [-> . . . . .| [12:13] NP -> DT * NN [0.02666666666666667]\n",
      "  |. . . . . . . . . [-> . . . . . . . .| [9:10] NP -> DT * NP|<JJ-JJ> [0.02666666666666667]\n",
      "  |. . . . . . . . . [-> . . . . . . . .| [9:10] NP -> DT * NP|<NNP-VBG> [0.02666666666666667]\n",
      "  |. . . . . . . . . [-> . . . . . . . .| [9:10] NP -> DT * NN [0.02666666666666667]\n",
      "  |. . . . . . . . . . . . . . . [---] .| [15:17] NP-TMP -> NNP CD * [0.023809523809523808]\n",
      "  |. . . . . . . . . . . . . . . [-> . .| [15:16] NP-SBJ -> NNP * NNP [0.023809523809523808]\n",
      "  |[-> . . . . . . . . . . . . . . . . .| [0:1] NP-SBJ -> NNP * NNP [0.023809523809523808]\n",
      "  |. . . . . . . . . . . . . . [-] . . .| [14:15] NP -> NN * [0.019047619047619046]\n",
      "  |. . . . . . . . . . . . . . > . . . .| [14:14] NP-SBJ-1 -> * NP NP-SBJ-1|<,-UCP> [1.0]\n",
      "  |. . . . . . . . . . . . . . > . . . .| [14:14] NP-PRD -> * NP PP [1.0]\n",
      "  |. . . . . . . . . . . . . . > . . . .| [14:14] VP|<NP-PP-CLR> -> * NP VP|<PP-CLR-NP-TMP> [1.0]\n",
      "  |. . . . . . . . . . . . . . > . . . .| [14:14] ADJP -> * NP JJ [1.0]\n",
      "  |. . . . . . . . . . . . . . > . . . .| [14:14] NP-SBJ -> * NP NP-SBJ|<,-ADJP> [0.3333333333333333]\n",
      "  |. . . . . . . . . . . . . . > . . . .| [14:14] NP -> * NP PP [0.06666666666666667]\n",
      "  |. . . . . . . . . . . . . . > . . . .| [14:14] NP -> * NP NP|<,-NP> [0.06666666666666667]\n",
      "  |. . . . . . . . . . . . . . [-> . . .| [14:15] NP-SBJ-1 -> NP * NP-SBJ-1|<,-UCP> [0.019047619047619046]\n",
      "  |. . . . . . . . . . . . . . [-> . . .| [14:15] NP-PRD -> NP * PP [0.019047619047619046]\n",
      "  |. . . . . . . . . . . . . . [-> . . .| [14:15] VP|<NP-PP-CLR> -> NP * VP|<PP-CLR-NP-TMP> [0.019047619047619046]\n",
      "  |. . . . . . . . . . . . . . [-> . . .| [14:15] ADJP -> NP * JJ [0.019047619047619046]\n",
      "  |. . . . . . . . . . . . . [-> . . . .| [13:14] NP -> JJ * NN [0.019047619047619046]\n",
      "  |. . . . . [-> . . . . . . . . . . . .| [5:6] NP -> JJ * NN [0.019047619047619046]\n",
      "  |. . . [---> . . . . . . . . . . . . .| [3:5] NP-SBJ -> NP * NP-SBJ|<,-ADJP> [0.014814814814814812]\n",
      "  |. . . . . . . . . . . . . . . [-> . .| [15:16] NP -> NNP * NNP [0.014285714285714285]\n",
      "  |[-> . . . . . . . . . . . . . . . . .| [0:1] NP -> NNP * NNP [0.014285714285714285]\n",
      "  |. . . [-----] . . . . . . . . . . . .| [3:6] ADJP -> NP JJ * [0.012698412698412697]\n",
      "  |. . . > . . . . . . . . . . . . . . .| [3:3] UCP -> * ADJP UCP|<CC-NP> [1.0]\n",
      "  |. . . > . . . . . . . . . . . . . . .| [3:3] NP-SBJ|<ADJP-,> -> * ADJP , [1.0]\n",
      "  |. . . [-----> . . . . . . . . . . . .| [3:6] UCP -> ADJP * UCP|<CC-NP> [0.012698412698412697]\n",
      "  |. . . [-----> . . . . . . . . . . . .| [3:6] NP-SBJ|<ADJP-,> -> ADJP * , [0.012698412698412697]\n",
      "  |. . . [-------] . . . . . . . . . . .| [3:7] NP-SBJ|<ADJP-,> -> ADJP , * [0.012698412698412697]\n",
      "  |. . [---------] . . . . . . . . . . .| [2:7] NP-SBJ|<,-ADJP> -> , NP-SBJ|<ADJP-,> * [0.012698412698412697]\n",
      "  |. . . . . . . . . . [-] . . . . . . .| [10:11] NP -> NN * [0.009523809523809523]\n",
      "  |. . . . . . . . . . > . . . . . . . .| [10:10] NP-SBJ-1 -> * NP NP-SBJ-1|<,-UCP> [1.0]\n",
      "  |. . . . . . . . . . > . . . . . . . .| [10:10] NP-PRD -> * NP PP [1.0]\n",
      "  |. . . . . . . . . . > . . . . . . . .| [10:10] VP|<NP-PP-CLR> -> * NP VP|<PP-CLR-NP-TMP> [1.0]\n",
      "  |. . . . . . . . . . > . . . . . . . .| [10:10] ADJP -> * NP JJ [1.0]\n",
      "  |. . . . . . . . . . > . . . . . . . .| [10:10] NP-SBJ -> * NP NP-SBJ|<,-ADJP> [0.3333333333333333]\n",
      "  |. . . . . . . . . . > . . . . . . . .| [10:10] NP -> * NP PP [0.06666666666666667]\n",
      "  |. . . . . . . . . . > . . . . . . . .| [10:10] NP -> * NP NP|<,-NP> [0.06666666666666667]\n",
      "  |. . . . . . . . . . [-> . . . . . . .| [10:11] NP-SBJ-1 -> NP * NP-SBJ-1|<,-UCP> [0.009523809523809523]\n",
      "  |. . . . . . . . . . [-> . . . . . . .| [10:11] NP-PRD -> NP * PP [0.009523809523809523]\n",
      "  |. . . . . . . . . . [-> . . . . . . .| [10:11] VP|<NP-PP-CLR> -> NP * VP|<PP-CLR-NP-TMP> [0.009523809523809523]\n",
      "  |. . . . . . . . . . [-> . . . . . . .| [10:11] ADJP -> NP * JJ [0.009523809523809523]\n",
      "  |. [-> . . . . . . . . . . . . . . . .| [1:2] NP -> NNP * NP|<NNP-NNP> [0.009523809523809523]\n",
      "  |. . . . . . . . . . . . . . [-> . . .| [14:15] NP-SBJ -> NP * NP-SBJ|<,-ADJP> [0.006349206349206348]\n",
      "  |. . . . . . . . . . . . . [---] . . .| [13:15] NP -> JJ NN * [0.005442176870748299]\n",
      "  |. . . . . . . . . . . . . > . . . . .| [13:13] NP-SBJ-1 -> * NP NP-SBJ-1|<,-UCP> [1.0]\n",
      "  |. . . . . . . . . . . . . > . . . . .| [13:13] NP-PRD -> * NP PP [1.0]\n",
      "  |. . . . . . . . . . . . . > . . . . .| [13:13] VP|<NP-PP-CLR> -> * NP VP|<PP-CLR-NP-TMP> [1.0]\n",
      "  |. . . . . . . . . . . . . > . . . . .| [13:13] ADJP -> * NP JJ [1.0]\n",
      "  |. . . . . . . . . . . . . > . . . . .| [13:13] NP-SBJ -> * NP NP-SBJ|<,-ADJP> [0.3333333333333333]\n",
      "  |. . . . . . . . . . . . . > . . . . .| [13:13] NP -> * NP PP [0.06666666666666667]\n",
      "  |. . . . . . . . . . . . . > . . . . .| [13:13] NP -> * NP NP|<,-NP> [0.06666666666666667]\n",
      "  |. . . . . . . . . . . . . [---> . . .| [13:15] NP-SBJ-1 -> NP * NP-SBJ-1|<,-UCP> [0.005442176870748299]\n",
      "  |. . . . . . . . . . . . . [---> . . .| [13:15] NP-PRD -> NP * PP [0.005442176870748299]\n",
      "  |. . . . . . . . . . . . . [---> . . .| [13:15] VP|<NP-PP-CLR> -> NP * VP|<PP-CLR-NP-TMP> [0.005442176870748299]\n",
      "  |. . . . . . . . . . . . . [---> . . .| [13:15] ADJP -> NP * JJ [0.005442176870748299]\n",
      "  |[---] . . . . . . . . . . . . . . . .| [0:2] NP|<NNP-NNP> -> NNP NNP * [0.00510204081632653]\n",
      "  |. . . . . . . . . . . . . . . [-> . .| [15:16] NP -> NNP * NP|<NNP-NNP> [0.0047619047619047615]\n",
      "  |[-> . . . . . . . . . . . . . . . . .| [0:1] NP -> NNP * NP|<NNP-NNP> [0.0047619047619047615]\n",
      "  |. . . . . . . . . . . . [-----] . . .| [12:15] NP -> DT NP|<JJ-NN> * [0.004353741496598639]\n",
      "  |. . . . . . . . . . . . > . . . . . .| [12:12] NP-SBJ-1 -> * NP NP-SBJ-1|<,-UCP> [1.0]\n",
      "  |. . . . . . . . . . . . > . . . . . .| [12:12] NP-PRD -> * NP PP [1.0]\n",
      "  |. . . . . . . . . . . . > . . . . . .| [12:12] VP|<NP-PP-CLR> -> * NP VP|<PP-CLR-NP-TMP> [1.0]\n",
      "  |. . . . . . . . . . . . > . . . . . .| [12:12] ADJP -> * NP JJ [1.0]\n",
      "  |. . . . . . . . . . . . > . . . . . .| [12:12] NP-SBJ -> * NP NP-SBJ|<,-ADJP> [0.3333333333333333]\n",
      "  |. . . . . . . . . . . . > . . . . . .| [12:12] NP -> * NP PP [0.06666666666666667]\n",
      "  |. . . . . . . . . . . . > . . . . . .| [12:12] NP -> * NP NP|<,-NP> [0.06666666666666667]\n",
      "  |. . . . . . . . . . . . [-----> . . .| [12:15] NP-SBJ-1 -> NP * NP-SBJ-1|<,-UCP> [0.004353741496598639]\n",
      "  |. . . . . . . . . . . . [-----> . . .| [12:15] NP-PRD -> NP * PP [0.004353741496598639]\n",
      "  |. . . . . . . . . . . . [-----> . . .| [12:15] VP|<NP-PP-CLR> -> NP * VP|<PP-CLR-NP-TMP> [0.004353741496598639]\n",
      "  |. . . . . . . . . . . . [-----> . . .| [12:15] ADJP -> NP * JJ [0.004353741496598639]\n",
      "  |. . . . . . . . . [---] . . . . . . .| [9:11] NP -> DT NN * [0.0038095238095238095]\n",
      "  |. . . . . . . . . > . . . . . . . . .| [9:9] NP-SBJ-1 -> * NP NP-SBJ-1|<,-UCP> [1.0]\n",
      "  |. . . . . . . . . > . . . . . . . . .| [9:9] NP-PRD -> * NP PP [1.0]\n",
      "  |. . . . . . . . . > . . . . . . . . .| [9:9] VP|<NP-PP-CLR> -> * NP VP|<PP-CLR-NP-TMP> [1.0]\n",
      "  |. . . . . . . . . > . . . . . . . . .| [9:9] ADJP -> * NP JJ [1.0]\n",
      "  |. . . . . . . . . > . . . . . . . . .| [9:9] NP-SBJ -> * NP NP-SBJ|<,-ADJP> [0.3333333333333333]\n",
      "  |. . . . . . . . . > . . . . . . . . .| [9:9] NP -> * NP PP [0.06666666666666667]\n",
      "  |. . . . . . . . . > . . . . . . . . .| [9:9] NP -> * NP NP|<,-NP> [0.06666666666666667]\n",
      "  |. . . . . . . . . [---> . . . . . . .| [9:11] NP-SBJ-1 -> NP * NP-SBJ-1|<,-UCP> [0.0038095238095238095]\n",
      "  |. . . . . . . . . [---> . . . . . . .| [9:11] NP-PRD -> NP * PP [0.0038095238095238095]\n",
      "  |. . . . . . . . . [---> . . . . . . .| [9:11] VP|<NP-PP-CLR> -> NP * VP|<PP-CLR-NP-TMP> [0.0038095238095238095]\n",
      "  |. . . . . . . . . [---> . . . . . . .| [9:11] ADJP -> NP * JJ [0.0038095238095238095]\n",
      "  |[---] . . . . . . . . . . . . . . . .| [0:2] NP-SBJ -> NNP NNP * [0.0034013605442176865]\n",
      "  |> . . . . . . . . . . . . . . . . . .| [0:0] S  -> * NP-SBJ S|<VP-.> [0.5]\n",
      "  |> . . . . . . . . . . . . . . . . . .| [0:0] S  -> * NP-SBJ NP-PRD [0.25]\n",
      "  |. . . . . . . . . . [-> . . . . . . .| [10:11] NP-SBJ -> NP * NP-SBJ|<,-ADJP> [0.003174603174603174]\n",
      "  |. . . [---> . . . . . . . . . . . . .| [3:5] NP -> NP * PP [0.0029629629629629624]\n",
      "  |. . . [---> . . . . . . . . . . . . .| [3:5] NP -> NP * NP|<,-NP> [0.0029629629629629624]\n",
      "  |[---] . . . . . . . . . . . . . . . .| [0:2] NP -> NNP NNP * [0.002040816326530612]\n",
      "  |> . . . . . . . . . . . . . . . . . .| [0:0] NP-SBJ-1 -> * NP NP-SBJ-1|<,-UCP> [1.0]\n",
      "  |> . . . . . . . . . . . . . . . . . .| [0:0] NP-PRD -> * NP PP [1.0]\n",
      "  |> . . . . . . . . . . . . . . . . . .| [0:0] VP|<NP-PP-CLR> -> * NP VP|<PP-CLR-NP-TMP> [1.0]\n",
      "  |> . . . . . . . . . . . . . . . . . .| [0:0] ADJP -> * NP JJ [1.0]\n",
      "  |> . . . . . . . . . . . . . . . . . .| [0:0] NP-SBJ -> * NP NP-SBJ|<,-ADJP> [0.3333333333333333]\n",
      "  |> . . . . . . . . . . . . . . . . . .| [0:0] NP -> * NP PP [0.06666666666666667]\n",
      "  |> . . . . . . . . . . . . . . . . . .| [0:0] NP -> * NP NP|<,-NP> [0.06666666666666667]\n",
      "  |[---> . . . . . . . . . . . . . . . .| [0:2] NP-SBJ-1 -> NP * NP-SBJ-1|<,-UCP> [0.002040816326530612]\n",
      "  |[---> . . . . . . . . . . . . . . . .| [0:2] NP-PRD -> NP * PP [0.002040816326530612]\n",
      "  |[---> . . . . . . . . . . . . . . . .| [0:2] VP|<NP-PP-CLR> -> NP * VP|<PP-CLR-NP-TMP> [0.002040816326530612]\n",
      "  |[---> . . . . . . . . . . . . . . . .| [0:2] ADJP -> NP * JJ [0.002040816326530612]\n",
      "  |. . . . . . . . . . . . . [---> . . .| [13:15] NP-SBJ -> NP * NP-SBJ|<,-ADJP> [0.0018140589569160996]\n",
      "  |[---> . . . . . . . . . . . . . . . .| [0:2] S  -> NP-SBJ * S|<VP-.> [0.0017006802721088433]\n",
      "  |. . . . . . . . . . . . [-----> . . .| [12:15] NP-SBJ -> NP * NP-SBJ|<,-ADJP> [0.0014512471655328796]\n",
      "  |. . . . . . . . . [---> . . . . . . .| [9:11] NP-SBJ -> NP * NP-SBJ|<,-ADJP> [0.0012698412698412698]\n",
      "  |. . . . . . . . . . . . . . [-> . . .| [14:15] NP -> NP * PP [0.0012698412698412696]\n",
      "  |. . . . . . . . . . . . . . [-> . . .| [14:15] NP -> NP * NP|<,-NP> [0.0012698412698412696]\n",
      "  |. . . . . . . . . . . [-------] . . .| [11:15] PP -> IN NP * [0.0010884353741496598]\n",
      "  |. . . . . . . . . . . [-------] . . .| [11:15] PP-CLR -> IN NP * [0.0010884353741496598]\n",
      "  |. . . . . . . . . . . > . . . . . . .| [11:11] VP|<PP-CLR-NP-TMP> -> * PP-CLR NP-TMP [1.0]\n",
      "  |. . . . . . . . . . . [-------> . . .| [11:15] VP|<PP-CLR-NP-TMP> -> PP-CLR * NP-TMP [0.0010884353741496598]\n",
      "  |[---> . . . . . . . . . . . . . . . .| [0:2] S  -> NP-SBJ * NP-PRD [0.0008503401360544216]\n",
      "  |[---> . . . . . . . . . . . . . . . .| [0:2] NP-SBJ -> NP * NP-SBJ|<,-ADJP> [0.0006802721088435373]\n",
      "  |. . . . . . . . . . [-> . . . . . . .| [10:11] NP -> NP * PP [0.0006349206349206348]\n",
      "  |. . . . . . . . . . [-> . . . . . . .| [10:11] NP -> NP * NP|<,-NP> [0.0006349206349206348]\n",
      "  |. . . . . . . . . . . . . [---> . . .| [13:15] NP -> NP * PP [0.0003628117913832199]\n",
      "  |. . . . . . . . . . . . . [---> . . .| [13:15] NP -> NP * NP|<,-NP> [0.0003628117913832199]\n",
      "  |. . . . . . . . . . . . [-----> . . .| [12:15] NP -> NP * PP [0.00029024943310657596]\n",
      "  |. . . . . . . . . . . . [-----> . . .| [12:15] NP -> NP * NP|<,-NP> [0.00029024943310657596]\n",
      "  |. . . . . . . . . [---> . . . . . . .| [9:11] NP -> NP * PP [0.00025396825396825396]\n",
      "  |. . . . . . . . . [---> . . . . . . .| [9:11] NP -> NP * NP|<,-NP> [0.00025396825396825396]\n",
      "  |[---> . . . . . . . . . . . . . . . .| [0:2] NP -> NP * PP [0.00013605442176870745]\n",
      "  |[---> . . . . . . . . . . . . . . . .| [0:2] NP -> NP * NP|<,-NP> [0.00013605442176870745]\n",
      "  |. . . . . . . . . . . [-----------] .| [11:17] VP|<PP-CLR-NP-TMP> -> PP-CLR NP-TMP * [2.591512795594428e-05]\n",
      "  |. . . . . . . . . . [---------] . . .| [10:15] NP-PRD -> NP PP * [1.0366051182377711e-05]\n",
      "  |[-------------] . . . . . . . . . . .| [0:7] NP-SBJ -> NP NP-SBJ|<,-ADJP> * [8.638375985314757e-06]\n",
      "  |[---------] . . . . . . . . . . . . .| [0:5] NP -> NP NP|<,-NP> * [6.04686318972033e-06]\n",
      "  |[---------> . . . . . . . . . . . . .| [0:5] NP-SBJ-1 -> NP * NP-SBJ-1|<,-UCP> [6.04686318972033e-06]\n",
      "  |[---------> . . . . . . . . . . . . .| [0:5] NP-PRD -> NP * PP [6.04686318972033e-06]\n",
      "  |[---------> . . . . . . . . . . . . .| [0:5] VP|<NP-PP-CLR> -> NP * VP|<PP-CLR-NP-TMP> [6.04686318972033e-06]\n",
      "  |[---------> . . . . . . . . . . . . .| [0:5] ADJP -> NP * JJ [6.04686318972033e-06]\n",
      "  |[-------------> . . . . . . . . . . .| [0:7] S  -> NP-SBJ * S|<VP-.> [4.319187992657379e-06]\n",
      "  |. . . . . . . . . [-----------] . . .| [9:15] NP-PRD -> NP PP * [4.146420472951085e-06]\n",
      "  |[-------------> . . . . . . . . . . .| [0:7] S  -> NP-SBJ * NP-PRD [2.1595939963286893e-06]\n",
      "  |[---------> . . . . . . . . . . . . .| [0:5] NP-SBJ -> NP * NP-SBJ|<,-ADJP> [2.01562106324011e-06]\n",
      "  |[-----------] . . . . . . . . . . . .| [0:6] ADJP -> NP JJ * [1.7276751970629514e-06]\n",
      "  |> . . . . . . . . . . . . . . . . . .| [0:0] UCP -> * ADJP UCP|<CC-NP> [1.0]\n",
      "  |> . . . . . . . . . . . . . . . . . .| [0:0] NP-SBJ|<ADJP-,> -> * ADJP , [1.0]\n",
      "  |[-----------> . . . . . . . . . . . .| [0:6] UCP -> ADJP * UCP|<CC-NP> [1.7276751970629514e-06]\n",
      "  |[-----------> . . . . . . . . . . . .| [0:6] NP-SBJ|<ADJP-,> -> ADJP * , [1.7276751970629514e-06]\n",
      "  |[-------------] . . . . . . . . . . .| [0:7] NP-SBJ|<ADJP-,> -> ADJP , * [1.7276751970629514e-06]\n",
      "  |. . . . . . . . . . [---------] . . .| [10:15] NP -> NP PP * [6.910700788251807e-07]\n",
      "  |. . . . . . . . . . [---------> . . .| [10:15] NP-SBJ-1 -> NP * NP-SBJ-1|<,-UCP> [6.910700788251807e-07]\n",
      "  |. . . . . . . . . . [---------> . . .| [10:15] NP-PRD -> NP * PP [6.910700788251807e-07]\n",
      "  |. . . . . . . . . . [---------> . . .| [10:15] VP|<NP-PP-CLR> -> NP * VP|<PP-CLR-NP-TMP> [6.910700788251807e-07]\n",
      "  |. . . . . . . . . . [---------> . . .| [10:15] ADJP -> NP * JJ [6.910700788251807e-07]\n",
      "  |[---------> . . . . . . . . . . . . .| [0:5] NP -> NP * PP [4.0312421264802203e-07]\n",
      "  |[---------> . . . . . . . . . . . . .| [0:5] NP -> NP * NP|<,-NP> [4.0312421264802203e-07]\n",
      "  |. . . . . . . . . [-----------] . . .| [9:15] NP -> NP PP * [2.764280315300723e-07]\n",
      "  |. . . . . . . . . [-----------> . . .| [9:15] NP-SBJ-1 -> NP * NP-SBJ-1|<,-UCP> [2.764280315300723e-07]\n",
      "  |. . . . . . . . . [-----------> . . .| [9:15] NP-PRD -> NP * PP [2.764280315300723e-07]\n",
      "  |. . . . . . . . . [-----------> . . .| [9:15] VP|<NP-PP-CLR> -> NP * VP|<PP-CLR-NP-TMP> [2.764280315300723e-07]\n",
      "  |. . . . . . . . . [-----------> . . .| [9:15] ADJP -> NP * JJ [2.764280315300723e-07]\n",
      "  |. . . . . . . . . . [-------------] .| [10:17] VP|<NP-PP-CLR> -> NP VP|<PP-CLR-NP-TMP> * [2.4681074243756453e-07]\n",
      "  |. . . . . . . . . . [---------> . . .| [10:15] NP-SBJ -> NP * NP-SBJ|<,-ADJP> [2.303566929417269e-07]\n",
      "  |. . . . . . . . . [---------------] .| [9:17] VP|<NP-PP-CLR> -> NP VP|<PP-CLR-NP-TMP> * [9.872429697502583e-08]\n",
      "  |. . . . . . . . . [-----------> . . .| [9:15] NP-SBJ -> NP * NP-SBJ|<,-ADJP> [9.214267717669077e-08]\n",
      "  |. . . . . . . . . . [---------> . . .| [10:15] NP -> NP * PP [4.607133858834538e-08]\n",
      "  |. . . . . . . . . . [---------> . . .| [10:15] NP -> NP * NP|<,-NP> [4.607133858834538e-08]\n",
      "  |. . . . . . . . [-----------------] .| [8:17] VP -> VB VP|<NP-PP-CLR> * [1.9744859395005166e-08]\n",
      "  |. . . . . . . . > . . . . . . . . . .| [8:8] S|<VP-.> -> * VP . [1.0]\n",
      "  |. . . . . . . . [-----------------> .| [8:17] S|<VP-.> -> VP * . [1.9744859395005166e-08]\n",
      "  |. . . . . . . . [-------------------]| [8:18] S|<VP-.> -> VP . * [1.9744859395005166e-08]\n",
      "  |. . . . . . . . . [-----------> . . .| [9:15] NP -> NP * PP [1.8428535435338155e-08]\n",
      "  |. . . . . . . . . [-----------> . . .| [9:15] NP -> NP * NP|<,-NP> [1.8428535435338155e-08]\n",
      "  |. . . . . . . [-------------------] .| [7:17] VP -> MD VP * [3.948971879001034e-09]\n",
      "  |. . . . . . . > . . . . . . . . . . .| [7:7] S|<VP-.> -> * VP . [1.0]\n",
      "  |. . . . . . . [-------------------> .| [7:17] S|<VP-.> -> VP * . [3.948971879001034e-09]\n",
      "  |. . . . . . . [---------------------]| [7:18] S|<VP-.> -> VP . * [3.948971879001034e-09]\n",
      "  |[===================================]| [0:18] S  -> NP-SBJ S|<VP-.> * [1.705635192312291e-14]\n",
      "(S\n",
      "  (NP-SBJ\n",
      "    (NP (NNP Pierre) (NNP Vinken))\n",
      "    (NP-SBJ|<,-ADJP>\n",
      "      (, ,)\n",
      "      (NP-SBJ|<ADJP-,>\n",
      "        (ADJP (NP (CD 61) (NNS years)) (JJ old))\n",
      "        (, ,))))\n",
      "  (S|<VP-.>\n",
      "    (VP\n",
      "      (MD will)\n",
      "      (VP\n",
      "        (VB join)\n",
      "        (VP|<NP-PP-CLR>\n",
      "          (NP (DT the) (NN board))\n",
      "          (VP|<PP-CLR-NP-TMP>\n",
      "            (PP-CLR\n",
      "              (IN as)\n",
      "              (NP\n",
      "                (DT a)\n",
      "                (NP|<JJ-NN>\n",
      "                  (JJ nonexecutive)\n",
      "                  (NN director))))\n",
      "            (NP-TMP (NNP Nov.) (CD 29))))))\n",
      "    (. .))) (p=1.70564e-14)\n"
     ]
    }
   ],
   "source": [
    "\n",
    "print(\"Parse sentence using induced grammar:\")\n",
    "\n",
    "parser = nltk.pchart.InsideChartParser(grammar)\n",
    "parser.trace(3)\n",
    "\n",
    "sent = treebank.parsed_sents('wsj_0001.mrg')[0].leaves()\n",
    "print(sent)\n",
    "\n",
    "for parse in parser.parse(sent):\n",
    "  print(parse)"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "The other parsers are defined in the *nltk.parse* module."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 36,
   "metadata": {},
   "outputs": [],
   "source": [
    "import sys, time\n",
    "from nltk import tokenize\n",
    "from nltk.grammar import toy_pcfg1\n",
    "from nltk.parse import pchart\n",
    "from nltk.parse import ViterbiParser\n",
    "\n",
    "demos = [('I saw John with my telescope', toy_pcfg1)]\n",
    "sent, grammar = demos[0]\n",
    "\n",
    "# Tokenize the sentence.\n",
    "tokens = sent.split()\n",
    "\n",
    "# Define a list of parsers.  We'll use all parsers.\n",
    "parsers = [\n",
    "ViterbiParser(grammar),\n",
    "pchart.InsideChartParser(grammar),\n",
    "pchart.RandomChartParser(grammar),\n",
    "pchart.UnsortedChartParser(grammar),\n",
    "pchart.LongestChartParser(grammar),\n",
    "pchart.InsideChartParser(grammar, beam_size = len(tokens)+1)\n",
    "]"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "We can now loop over the different parsers and compare the output and performance:"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 37,
   "metadata": {},
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "\n",
      "s: I saw John with my telescope\n",
      "parser: <ViterbiParser for <Grammar with 17 productions>>\n",
      "grammar: Grammar with 17 productions (start state = S)\n",
      "    S -> NP VP [1.0]\n",
      "    NP -> Det N [0.5]\n",
      "    NP -> NP PP [0.25]\n",
      "    NP -> 'John' [0.1]\n",
      "    NP -> 'I' [0.15]\n",
      "    Det -> 'the' [0.8]\n",
      "    Det -> 'my' [0.2]\n",
      "    N -> 'man' [0.5]\n",
      "    N -> 'telescope' [0.5]\n",
      "    VP -> VP PP [0.1]\n",
      "    VP -> V NP [0.7]\n",
      "    VP -> V [0.2]\n",
      "    V -> 'ate' [0.35]\n",
      "    V -> 'saw' [0.65]\n",
      "    PP -> P NP [1.0]\n",
      "    P -> 'with' [0.61]\n",
      "    P -> 'under' [0.39]\n",
      "Inserting tokens into the most likely constituents table...\n",
      "   Insert: |=.....| I\n",
      "   Insert: |.=....| saw\n",
      "   Insert: |..=...| John\n",
      "   Insert: |...=..| with\n",
      "   Insert: |....=.| my\n",
      "   Insert: |.....=| telescope\n",
      "Finding the most likely constituents spanning 1 text elements...\n",
      "   Insert: |=.....| NP -> 'I' [0.15]                0.1500000000 \n",
      "   Insert: |.=....| V -> 'saw' [0.65]               0.6500000000 \n",
      "   Insert: |.=....| VP -> V [0.2]                   0.1300000000 \n",
      "   Insert: |..=...| NP -> 'John' [0.1]              0.1000000000 \n",
      "   Insert: |...=..| P -> 'with' [0.61]              0.6100000000 \n",
      "   Insert: |....=.| Det -> 'my' [0.2]               0.2000000000 \n",
      "   Insert: |.....=| N -> 'telescope' [0.5]          0.5000000000 \n",
      "Finding the most likely constituents spanning 2 text elements...\n",
      "   Insert: |==....| S -> NP VP [1.0]                0.0195000000 \n",
      "   Insert: |.==...| VP -> V NP [0.7]                0.0455000000 \n",
      "   Insert: |....==| NP -> Det N [0.5]               0.0500000000 \n",
      "Finding the most likely constituents spanning 3 text elements...\n",
      "   Insert: |===...| S -> NP VP [1.0]                0.0068250000 \n",
      "   Insert: |...===| PP -> P NP [1.0]                0.0305000000 \n",
      "Finding the most likely constituents spanning 4 text elements...\n",
      "   Insert: |..====| NP -> NP PP [0.25]              0.0007625000 \n",
      "Finding the most likely constituents spanning 5 text elements...\n",
      "   Insert: |.=====| VP -> VP PP [0.1]               0.0001387750 \n",
      "   Insert: |.=====| VP -> V NP [0.7]                0.0003469375 \n",
      "  Discard: |.=====| VP -> VP PP [0.1]               0.0001387750 \n",
      "Finding the most likely constituents spanning 6 text elements...\n",
      "   Insert: |======| S -> NP VP [1.0]                0.0000520406 \n",
      "\n",
      "s: I saw John with my telescope\n",
      "parser: <nltk.parse.pchart.InsideChartParser object at 0x00000263D2359748>\n",
      "grammar: Grammar with 17 productions (start state = S)\n",
      "    S -> NP VP [1.0]\n",
      "    NP -> Det N [0.5]\n",
      "    NP -> NP PP [0.25]\n",
      "    NP -> 'John' [0.1]\n",
      "    NP -> 'I' [0.15]\n",
      "    Det -> 'the' [0.8]\n",
      "    Det -> 'my' [0.2]\n",
      "    N -> 'man' [0.5]\n",
      "    N -> 'telescope' [0.5]\n",
      "    VP -> VP PP [0.1]\n",
      "    VP -> V NP [0.7]\n",
      "    VP -> V [0.2]\n",
      "    V -> 'ate' [0.35]\n",
      "    V -> 'saw' [0.65]\n",
      "    PP -> P NP [1.0]\n",
      "    P -> 'with' [0.61]\n",
      "    P -> 'under' [0.39]\n",
      "  |[-] . . . . .| [0:1] 'I'                          [1.0]\n",
      "  |. [-] . . . .| [1:2] 'saw'                        [1.0]\n",
      "  |. . [-] . . .| [2:3] 'John'                       [1.0]\n",
      "  |. . . [-] . .| [3:4] 'with'                       [1.0]\n",
      "  |. . . . [-] .| [4:5] 'my'                         [1.0]\n",
      "  |. . . . . [-]| [5:6] 'telescope'                  [1.0]\n",
      "  |. . . . . [-]| [5:6] 'telescope'                  [1.0]\n",
      "  |. . . . [-] .| [4:5] 'my'                         [1.0]\n",
      "  |. . . [-] . .| [3:4] 'with'                       [1.0]\n",
      "  |. . [-] . . .| [2:3] 'John'                       [1.0]\n",
      "  |. [-] . . . .| [1:2] 'saw'                        [1.0]\n",
      "  |[-] . . . . .| [0:1] 'I'                          [1.0]\n",
      "  |. [-] . . . .| [1:2] V  -> 'saw' *                [0.65]\n",
      "  |. > . . . . .| [1:1] VP -> * V NP                 [0.7]\n",
      "  |. > . . . . .| [1:1] V  -> * 'saw'                [0.65]\n",
      "  |. . . [-] . .| [3:4] P  -> 'with' *               [0.61]\n",
      "  |. . . > . . .| [3:3] PP -> * P NP                 [1.0]\n",
      "  |. . . [-> . .| [3:4] PP -> P * NP                 [0.61]\n",
      "  |. . . > . . .| [3:3] P  -> * 'with'               [0.61]\n",
      "  |. . . . . [-]| [5:6] N  -> 'telescope' *          [0.5]\n",
      "  |. . . . . > .| [5:5] N  -> * 'telescope'          [0.5]\n",
      "  |. [-> . . . .| [1:2] VP -> V * NP                 [0.45499999999999996]\n",
      "  |. > . . . . .| [1:1] VP -> * V                    [0.2]\n",
      "  |. . . . [-] .| [4:5] Det -> 'my' *                [0.2]\n",
      "  |. . . . > . .| [4:4] NP -> * Det N                [0.5]\n",
      "  |. . . . > . .| [4:4] Det -> * 'my'                [0.2]\n",
      "  |[-] . . . . .| [0:1] NP -> 'I' *                  [0.15]\n",
      "  |> . . . . . .| [0:0] S  -> * NP VP                [1.0]\n",
      "  |> . . . . . .| [0:0] NP -> * NP PP                [0.25]\n",
      "  |[-> . . . . .| [0:1] S  -> NP * VP                [0.15]\n",
      "  |> . . . . . .| [0:0] NP -> * 'I'                  [0.15]\n",
      "  |. [-] . . . .| [1:2] VP -> V *                    [0.13]\n",
      "  |. > . . . . .| [1:1] VP -> * VP PP                [0.1]\n",
      "  |. . . . [-> .| [4:5] NP -> Det * N                [0.1]\n",
      "  |. . [-] . . .| [2:3] NP -> 'John' *               [0.1]\n",
      "  |. . > . . . .| [2:2] S  -> * NP VP                [1.0]\n",
      "  |. . > . . . .| [2:2] NP -> * NP PP                [0.25]\n",
      "  |. . [-> . . .| [2:3] S  -> NP * VP                [0.1]\n",
      "  |. . > . . . .| [2:2] NP -> * 'John'               [0.1]\n",
      "  |. . . . [---]| [4:6] NP -> Det N *                [0.05]\n",
      "  |. . . . > . .| [4:4] S  -> * NP VP                [1.0]\n",
      "  |. . . . > . .| [4:4] NP -> * NP PP                [0.25]\n",
      "  |. . . . [--->| [4:6] S  -> NP * VP                [0.05]\n",
      "  |. [---] . . .| [1:3] VP -> V NP *                 [0.0455]\n",
      "  |[-> . . . . .| [0:1] NP -> NP * PP                [0.0375]\n",
      "  |. . . [-----]| [3:6] PP -> P NP *                 [0.0305]\n",
      "  |. . [-> . . .| [2:3] NP -> NP * PP                [0.025]\n",
      "  |[---] . . . .| [0:2] S  -> NP VP *                [0.0195]\n",
      "  |. [-> . . . .| [1:2] VP -> VP * PP                [0.013000000000000001]\n",
      "  |. . . . [--->| [4:6] NP -> NP * PP                [0.0125]\n",
      "  |[-----] . . .| [0:3] S  -> NP VP *                [0.0068249999999999995]\n",
      "  |. [---> . . .| [1:3] VP -> VP * PP                [0.00455]\n",
      "  |. . [-------]| [2:6] NP -> NP PP *                [0.0007625]\n",
      "  |. . [------->| [2:6] S  -> NP * VP                [0.0007625]\n",
      "  |. [---------]| [1:6] VP -> V NP *                 [0.00034693749999999997]\n",
      "  |. . [------->| [2:6] NP -> NP * PP                [0.000190625]\n",
      "  |. [---------]| [1:6] VP -> VP PP *                [0.000138775]\n",
      "  |[===========]| [0:6] S  -> NP VP *                [5.204062499999999e-05]\n",
      "  |. [--------->| [1:6] VP -> VP * PP                [3.469375e-05]\n",
      "  |[===========]| [0:6] S  -> NP VP *                [2.081625e-05]\n",
      "  |. [--------->| [1:6] VP -> VP * PP                [1.38775e-05]\n",
      "\n",
      "s: I saw John with my telescope\n",
      "parser: <nltk.parse.pchart.RandomChartParser object at 0x00000263D2367208>\n",
      "grammar: Grammar with 17 productions (start state = S)\n",
      "    S -> NP VP [1.0]\n",
      "    NP -> Det N [0.5]\n",
      "    NP -> NP PP [0.25]\n",
      "    NP -> 'John' [0.1]\n",
      "    NP -> 'I' [0.15]\n",
      "    Det -> 'the' [0.8]\n",
      "    Det -> 'my' [0.2]\n",
      "    N -> 'man' [0.5]\n",
      "    N -> 'telescope' [0.5]\n",
      "    VP -> VP PP [0.1]\n",
      "    VP -> V NP [0.7]\n",
      "    VP -> V [0.2]\n",
      "    V -> 'ate' [0.35]\n",
      "    V -> 'saw' [0.65]\n",
      "    PP -> P NP [1.0]\n",
      "    P -> 'with' [0.61]\n",
      "    P -> 'under' [0.39]\n",
      "  |[-] . . . . .| [0:1] 'I'                          [1.0]\n",
      "  |. [-] . . . .| [1:2] 'saw'                        [1.0]\n",
      "  |. . [-] . . .| [2:3] 'John'                       [1.0]\n",
      "  |. . . [-] . .| [3:4] 'with'                       [1.0]\n",
      "  |. . . . [-] .| [4:5] 'my'                         [1.0]\n",
      "  |. . . . . [-]| [5:6] 'telescope'                  [1.0]\n",
      "  |[-] . . . . .| [0:1] 'I'                          [1.0]\n",
      "  |. . . [-] . .| [3:4] 'with'                       [1.0]\n",
      "  |> . . . . . .| [0:0] NP -> * 'I'                  [0.15]\n",
      "  |. . . [-] . .| [3:4] P  -> 'with' *               [0.61]\n",
      "  |. . . . [-] .| [4:5] 'my'                         [1.0]\n",
      "  |. . . . [-] .| [4:5] Det -> 'my' *                [0.2]\n",
      "  |. . . . > . .| [4:4] NP -> * Det N                [0.5]\n",
      "  |[-] . . . . .| [0:1] NP -> 'I' *                  [0.15]\n",
      "  |> . . . . . .| [0:0] NP -> * NP PP                [0.25]\n",
      "  |. [-] . . . .| [1:2] 'saw'                        [1.0]\n",
      "  |. . . . [-> .| [4:5] NP -> Det * N                [0.1]\n",
      "  |[-> . . . . .| [0:1] NP -> NP * PP                [0.0375]\n",
      "  |[-> . . . . .| [0:1] S  -> NP * VP                [0.15]\n",
      "  |. . . . . [-]| [5:6] 'telescope'                  [1.0]\n",
      "  |. . . . > . .| [4:4] Det -> * 'my'                [0.2]\n",
      "  |. . . > . . .| [3:3] PP -> * P NP                 [1.0]\n",
      "  |. . . [-> . .| [3:4] PP -> P * NP                 [0.61]\n",
      "  |. [-] . . . .| [1:2] V  -> 'saw' *                [0.65]\n",
      "  |. > . . . . .| [1:1] VP -> * V NP                 [0.7]\n",
      "  |. > . . . . .| [1:1] V  -> * 'saw'                [0.65]\n",
      "  |. [-> . . . .| [1:2] VP -> V * NP                 [0.45499999999999996]\n",
      "  |. . . . . > .| [5:5] N  -> * 'telescope'          [0.5]\n",
      "  |> . . . . . .| [0:0] S  -> * NP VP                [1.0]\n",
      "  |. . [-] . . .| [2:3] 'John'                       [1.0]\n",
      "  |. . [-] . . .| [2:3] NP -> 'John' *               [0.1]\n",
      "  |. . > . . . .| [2:2] NP -> * 'John'               [0.1]\n",
      "  |. . . . . [-]| [5:6] N  -> 'telescope' *          [0.5]\n",
      "  |. . . > . . .| [3:3] P  -> * 'with'               [0.61]\n",
      "  |. . [-> . . .| [2:3] S  -> NP * VP                [0.1]\n",
      "  |. . [-> . . .| [2:3] NP -> NP * PP                [0.025]\n",
      "  |. . > . . . .| [2:2] S  -> * NP VP                [1.0]\n",
      "  |. . > . . . .| [2:2] NP -> * NP PP                [0.25]\n",
      "  |. . . . [---]| [4:6] NP -> Det N *                [0.05]\n",
      "  |. . . . [--->| [4:6] NP -> NP * PP                [0.0125]\n",
      "  |. > . . . . .| [1:1] VP -> * V                    [0.2]\n",
      "  |. [-] . . . .| [1:2] VP -> V *                    [0.13]\n",
      "  |. . . . > . .| [4:4] NP -> * NP PP                [0.25]\n",
      "  |. [-> . . . .| [1:2] VP -> VP * PP                [0.013000000000000001]\n",
      "  |. > . . . . .| [1:1] VP -> * VP PP                [0.1]\n",
      "  |. [---] . . .| [1:3] VP -> V NP *                 [0.0455]\n",
      "  |. [---> . . .| [1:3] VP -> VP * PP                [0.00455]\n",
      "  |. . . . [--->| [4:6] S  -> NP * VP                [0.05]\n",
      "  |[---] . . . .| [0:2] S  -> NP VP *                [0.0195]\n",
      "  |[-----] . . .| [0:3] S  -> NP VP *                [0.0068249999999999995]\n",
      "  |. . . [-----]| [3:6] PP -> P NP *                 [0.0305]\n",
      "  |. . . . > . .| [4:4] S  -> * NP VP                [1.0]\n",
      "  |. [---------]| [1:6] VP -> VP PP *                [0.000138775]\n",
      "  |[===========]| [0:6] S  -> NP VP *                [2.081625e-05]\n",
      "  |. . [-------]| [2:6] NP -> NP PP *                [0.0007625]\n",
      "  |. [---------]| [1:6] VP -> V NP *                 [0.00034693749999999997]\n",
      "  |. [--------->| [1:6] VP -> VP * PP                [3.469375e-05]\n",
      "  |. . [------->| [2:6] NP -> NP * PP                [0.000190625]\n",
      "  |. [--------->| [1:6] VP -> VP * PP                [1.38775e-05]\n",
      "  |[===========]| [0:6] S  -> NP VP *                [5.204062499999999e-05]\n",
      "  |. . [------->| [2:6] S  -> NP * VP                [0.0007625]\n",
      "\n",
      "s: I saw John with my telescope\n",
      "parser: <nltk.parse.pchart.UnsortedChartParser object at 0x00000263D2367248>\n",
      "grammar: Grammar with 17 productions (start state = S)\n",
      "    S -> NP VP [1.0]\n",
      "    NP -> Det N [0.5]\n",
      "    NP -> NP PP [0.25]\n",
      "    NP -> 'John' [0.1]\n",
      "    NP -> 'I' [0.15]\n",
      "    Det -> 'the' [0.8]\n",
      "    Det -> 'my' [0.2]\n",
      "    N -> 'man' [0.5]\n",
      "    N -> 'telescope' [0.5]\n",
      "    VP -> VP PP [0.1]\n",
      "    VP -> V NP [0.7]\n",
      "    VP -> V [0.2]\n",
      "    V -> 'ate' [0.35]\n",
      "    V -> 'saw' [0.65]\n",
      "    PP -> P NP [1.0]\n",
      "    P -> 'with' [0.61]\n",
      "    P -> 'under' [0.39]\n",
      "  |[-] . . . . .| [0:1] 'I'                          [1.0]\n",
      "  |. [-] . . . .| [1:2] 'saw'                        [1.0]\n",
      "  |. . [-] . . .| [2:3] 'John'                       [1.0]\n",
      "  |. . . [-] . .| [3:4] 'with'                       [1.0]\n",
      "  |. . . . [-] .| [4:5] 'my'                         [1.0]\n",
      "  |. . . . . [-]| [5:6] 'telescope'                  [1.0]\n",
      "  |. . . . . [-]| [5:6] 'telescope'                  [1.0]\n",
      "  |. . . . . [-]| [5:6] N  -> 'telescope' *          [0.5]\n",
      "  |. . . . . > .| [5:5] N  -> * 'telescope'          [0.5]\n",
      "  |. . . . [-] .| [4:5] 'my'                         [1.0]\n",
      "  |. . . . [-] .| [4:5] Det -> 'my' *                [0.2]\n",
      "  |. . . . [-> .| [4:5] NP -> Det * N                [0.1]\n",
      "  |. . . . [---]| [4:6] NP -> Det N *                [0.05]\n",
      "  |. . . . [--->| [4:6] NP -> NP * PP                [0.0125]\n",
      "  |. . . . [--->| [4:6] S  -> NP * VP                [0.05]\n",
      "  |. . . . > . .| [4:4] NP -> * NP PP                [0.25]\n",
      "  |. . . . > . .| [4:4] S  -> * NP VP                [1.0]\n",
      "  |. . . . > . .| [4:4] NP -> * Det N                [0.5]\n",
      "  |. . . . > . .| [4:4] Det -> * 'my'                [0.2]\n",
      "  |. . . [-] . .| [3:4] 'with'                       [1.0]\n",
      "  |. . . [-] . .| [3:4] P  -> 'with' *               [0.61]\n",
      "  |. . . [-> . .| [3:4] PP -> P * NP                 [0.61]\n",
      "  |. . . [-----]| [3:6] PP -> P NP *                 [0.0305]\n",
      "  |. . . > . . .| [3:3] PP -> * P NP                 [1.0]\n",
      "  |. . . > . . .| [3:3] P  -> * 'with'               [0.61]\n",
      "  |. . [-] . . .| [2:3] 'John'                       [1.0]\n",
      "  |. . [-] . . .| [2:3] NP -> 'John' *               [0.1]\n",
      "  |. . [-> . . .| [2:3] NP -> NP * PP                [0.025]\n",
      "  |. . [-------]| [2:6] NP -> NP PP *                [0.0007625]\n",
      "  |. . [------->| [2:6] NP -> NP * PP                [0.000190625]\n",
      "  |. . [------->| [2:6] S  -> NP * VP                [0.0007625]\n",
      "  |. . [-> . . .| [2:3] S  -> NP * VP                [0.1]\n",
      "  |. . > . . . .| [2:2] NP -> * NP PP                [0.25]\n",
      "  |. . > . . . .| [2:2] S  -> * NP VP                [1.0]\n",
      "  |. . > . . . .| [2:2] NP -> * 'John'               [0.1]\n",
      "  |. [-] . . . .| [1:2] 'saw'                        [1.0]\n",
      "  |. [-] . . . .| [1:2] V  -> 'saw' *                [0.65]\n",
      "  |. [-] . . . .| [1:2] VP -> V *                    [0.13]\n",
      "  |. [-> . . . .| [1:2] VP -> VP * PP                [0.013000000000000001]\n",
      "  |. > . . . . .| [1:1] VP -> * VP PP                [0.1]\n",
      "  |. [-> . . . .| [1:2] VP -> V * NP                 [0.45499999999999996]\n",
      "  |. [---------]| [1:6] VP -> V NP *                 [0.00034693749999999997]\n",
      "  |. [--------->| [1:6] VP -> VP * PP                [3.469375e-05]\n",
      "  |. [---] . . .| [1:3] VP -> V NP *                 [0.0455]\n",
      "  |. [---> . . .| [1:3] VP -> VP * PP                [0.00455]\n",
      "  |. [---------]| [1:6] VP -> VP PP *                [0.000138775]\n",
      "  |. [--------->| [1:6] VP -> VP * PP                [1.38775e-05]\n",
      "  |. > . . . . .| [1:1] VP -> * V                    [0.2]\n",
      "  |. > . . . . .| [1:1] VP -> * V NP                 [0.7]\n",
      "  |. > . . . . .| [1:1] V  -> * 'saw'                [0.65]\n",
      "  |[-] . . . . .| [0:1] 'I'                          [1.0]\n",
      "  |[-] . . . . .| [0:1] NP -> 'I' *                  [0.15]\n",
      "  |[-> . . . . .| [0:1] NP -> NP * PP                [0.0375]\n",
      "  |[-> . . . . .| [0:1] S  -> NP * VP                [0.15]\n",
      "  |[===========]| [0:6] S  -> NP VP *                [2.081625e-05]\n",
      "  |[===========]| [0:6] S  -> NP VP *                [5.204062499999999e-05]\n",
      "  |[-----] . . .| [0:3] S  -> NP VP *                [0.0068249999999999995]\n",
      "  |[---] . . . .| [0:2] S  -> NP VP *                [0.0195]\n",
      "  |> . . . . . .| [0:0] NP -> * NP PP                [0.25]\n",
      "  |> . . . . . .| [0:0] S  -> * NP VP                [1.0]\n",
      "  |> . . . . . .| [0:0] NP -> * 'I'                  [0.15]\n",
      "\n",
      "s: I saw John with my telescope\n",
      "parser: <nltk.parse.pchart.LongestChartParser object at 0x00000263D2367388>\n",
      "grammar: Grammar with 17 productions (start state = S)\n",
      "    S -> NP VP [1.0]\n",
      "    NP -> Det N [0.5]\n",
      "    NP -> NP PP [0.25]\n",
      "    NP -> 'John' [0.1]\n",
      "    NP -> 'I' [0.15]\n",
      "    Det -> 'the' [0.8]\n",
      "    Det -> 'my' [0.2]\n",
      "    N -> 'man' [0.5]\n",
      "    N -> 'telescope' [0.5]\n",
      "    VP -> VP PP [0.1]\n",
      "    VP -> V NP [0.7]\n",
      "    VP -> V [0.2]\n",
      "    V -> 'ate' [0.35]\n",
      "    V -> 'saw' [0.65]\n",
      "    PP -> P NP [1.0]\n",
      "    P -> 'with' [0.61]\n",
      "    P -> 'under' [0.39]\n",
      "  |[-] . . . . .| [0:1] 'I'                          [1.0]\n",
      "  |. [-] . . . .| [1:2] 'saw'                        [1.0]\n",
      "  |. . [-] . . .| [2:3] 'John'                       [1.0]\n",
      "  |. . . [-] . .| [3:4] 'with'                       [1.0]\n",
      "  |. . . . [-] .| [4:5] 'my'                         [1.0]\n",
      "  |. . . . . [-]| [5:6] 'telescope'                  [1.0]\n",
      "  |. . . . . [-]| [5:6] 'telescope'                  [1.0]\n",
      "  |. . . . . [-]| [5:6] N  -> 'telescope' *          [0.5]\n",
      "  |. . . . [-] .| [4:5] 'my'                         [1.0]\n",
      "  |. . . . [-] .| [4:5] Det -> 'my' *                [0.2]\n",
      "  |. . . . [-> .| [4:5] NP -> Det * N                [0.1]\n",
      "  |. . . . [---]| [4:6] NP -> Det N *                [0.05]\n",
      "  |. . . . [--->| [4:6] NP -> NP * PP                [0.0125]\n",
      "  |. . . . [--->| [4:6] S  -> NP * VP                [0.05]\n",
      "  |. . . [-] . .| [3:4] 'with'                       [1.0]\n",
      "  |. . . [-] . .| [3:4] P  -> 'with' *               [0.61]\n",
      "  |. . . [-> . .| [3:4] PP -> P * NP                 [0.61]\n",
      "  |. . . [-----]| [3:6] PP -> P NP *                 [0.0305]\n",
      "  |. . [-] . . .| [2:3] 'John'                       [1.0]\n",
      "  |. . [-] . . .| [2:3] NP -> 'John' *               [0.1]\n",
      "  |. . [-> . . .| [2:3] NP -> NP * PP                [0.025]\n",
      "  |. . [-------]| [2:6] NP -> NP PP *                [0.0007625]\n",
      "  |. . [------->| [2:6] NP -> NP * PP                [0.000190625]\n",
      "  |. . [------->| [2:6] S  -> NP * VP                [0.0007625]\n",
      "  |. . [-> . . .| [2:3] S  -> NP * VP                [0.1]\n",
      "  |. [-] . . . .| [1:2] 'saw'                        [1.0]\n",
      "  |. [-] . . . .| [1:2] V  -> 'saw' *                [0.65]\n",
      "  |. [-] . . . .| [1:2] VP -> V *                    [0.13]\n",
      "  |. [-> . . . .| [1:2] VP -> VP * PP                [0.013000000000000001]\n",
      "  |. [-> . . . .| [1:2] VP -> V * NP                 [0.45499999999999996]\n",
      "  |. [---------]| [1:6] VP -> V NP *                 [0.00034693749999999997]\n",
      "  |. [--------->| [1:6] VP -> VP * PP                [3.469375e-05]\n",
      "  |. [---] . . .| [1:3] VP -> V NP *                 [0.0455]\n",
      "  |. [---> . . .| [1:3] VP -> VP * PP                [0.00455]\n",
      "  |. [---------]| [1:6] VP -> VP PP *                [0.000138775]\n",
      "  |. [--------->| [1:6] VP -> VP * PP                [1.38775e-05]\n",
      "  |[-] . . . . .| [0:1] 'I'                          [1.0]\n",
      "  |[-] . . . . .| [0:1] NP -> 'I' *                  [0.15]\n",
      "  |[-> . . . . .| [0:1] NP -> NP * PP                [0.0375]\n",
      "  |[-> . . . . .| [0:1] S  -> NP * VP                [0.15]\n",
      "  |[===========]| [0:6] S  -> NP VP *                [2.081625e-05]\n",
      "  |[===========]| [0:6] S  -> NP VP *                [5.204062499999999e-05]\n",
      "  |[-----] . . .| [0:3] S  -> NP VP *                [0.0068249999999999995]\n",
      "  |[---] . . . .| [0:2] S  -> NP VP *                [0.0195]\n",
      "  |> . . . . . .| [0:0] NP -> * NP PP                [0.25]\n",
      "  |> . . . . . .| [0:0] S  -> * NP VP                [1.0]\n",
      "  |> . . . . . .| [0:0] NP -> * 'I'                  [0.15]\n",
      "  |. > . . . . .| [1:1] VP -> * VP PP                [0.1]\n",
      "  |. > . . . . .| [1:1] VP -> * V                    [0.2]\n",
      "  |. > . . . . .| [1:1] VP -> * V NP                 [0.7]\n",
      "  |. > . . . . .| [1:1] V  -> * 'saw'                [0.65]\n",
      "  |. . > . . . .| [2:2] NP -> * NP PP                [0.25]\n",
      "  |. . > . . . .| [2:2] S  -> * NP VP                [1.0]\n",
      "  |. . > . . . .| [2:2] NP -> * 'John'               [0.1]\n",
      "  |. . . > . . .| [3:3] PP -> * P NP                 [1.0]\n",
      "  |. . . > . . .| [3:3] P  -> * 'with'               [0.61]\n",
      "  |. . . . > . .| [4:4] NP -> * NP PP                [0.25]\n",
      "  |. . . . > . .| [4:4] S  -> * NP VP                [1.0]\n",
      "  |. . . . > . .| [4:4] NP -> * Det N                [0.5]\n",
      "  |. . . . > . .| [4:4] Det -> * 'my'                [0.2]\n",
      "  |. . . . . > .| [5:5] N  -> * 'telescope'          [0.5]\n",
      "\n",
      "s: I saw John with my telescope\n",
      "parser: <nltk.parse.pchart.InsideChartParser object at 0x00000263D2C20BC8>\n",
      "grammar: Grammar with 17 productions (start state = S)\n",
      "    S -> NP VP [1.0]\n",
      "    NP -> Det N [0.5]\n",
      "    NP -> NP PP [0.25]\n",
      "    NP -> 'John' [0.1]\n",
      "    NP -> 'I' [0.15]\n",
      "    Det -> 'the' [0.8]\n",
      "    Det -> 'my' [0.2]\n",
      "    N -> 'man' [0.5]\n",
      "    N -> 'telescope' [0.5]\n",
      "    VP -> VP PP [0.1]\n",
      "    VP -> V NP [0.7]\n",
      "    VP -> V [0.2]\n",
      "    V -> 'ate' [0.35]\n",
      "    V -> 'saw' [0.65]\n",
      "    PP -> P NP [1.0]\n",
      "    P -> 'with' [0.61]\n",
      "    P -> 'under' [0.39]\n",
      "  |[-] . . . . .| [0:1] 'I'                          [1.0]\n",
      "  |. [-] . . . .| [1:2] 'saw'                        [1.0]\n",
      "  |. . [-] . . .| [2:3] 'John'                       [1.0]\n",
      "  |. . . [-] . .| [3:4] 'with'                       [1.0]\n",
      "  |. . . . [-] .| [4:5] 'my'                         [1.0]\n",
      "  |. . . . . [-]| [5:6] 'telescope'                  [1.0]\n",
      "  |. . . . . [-]| [5:6] 'telescope'                  [1.0]\n",
      "  |. . . . [-] .| [4:5] 'my'                         [1.0]\n",
      "  |. . . . > . .| [4:4] Det -> * 'my'                [DISCARDED]\n",
      "  |. . . [-] . .| [3:4] 'with'                       [1.0]\n",
      "  |. . . . [-] .| [4:5] Det -> 'my' *                [DISCARDED]\n",
      "  |. . [-] . . .| [2:3] 'John'                       [1.0]\n",
      "  |. . > . . . .| [2:2] NP -> * 'John'               [DISCARDED]\n",
      "  |. [-] . . . .| [1:2] 'saw'                        [1.0]\n",
      "  |. . [-] . . .| [2:3] NP -> 'John' *               [DISCARDED]\n",
      "  |[-] . . . . .| [0:1] 'I'                          [1.0]\n",
      "  |> . . . . . .| [0:0] NP -> * 'I'                  [DISCARDED]\n",
      "  |. [-] . . . .| [1:2] V  -> 'saw' *                [0.65]\n",
      "  |. [-] . . . .| [1:2] VP -> V *                    [DISCARDED]\n",
      "  |[-] . . . . .| [0:1] NP -> 'I' *                  [DISCARDED]\n",
      "  |. > . . . . .| [1:1] VP -> * V                    [DISCARDED]\n",
      "  |. > . . . . .| [1:1] VP -> * V NP                 [0.7]\n",
      "  |. > . . . . .| [1:1] V  -> * 'saw'                [0.65]\n",
      "  |. . . [-] . .| [3:4] P  -> 'with' *               [0.61]\n",
      "  |. . . > . . .| [3:3] PP -> * P NP                 [1.0]\n",
      "  |. . . [-> . .| [3:4] PP -> P * NP                 [0.61]\n",
      "  |. . . > . . .| [3:3] P  -> * 'with'               [0.61]\n",
      "  |. . . . . [-]| [5:6] N  -> 'telescope' *          [0.5]\n",
      "  |. . . . . > .| [5:5] N  -> * 'telescope'          [0.5]\n",
      "  |. [-> . . . .| [1:2] VP -> V * NP                 [0.45499999999999996]\n",
      "  |. [---] . . .| [1:3] VP -> V NP *                 [0.0455]\n",
      "  |. > . . . . .| [1:1] VP -> * VP PP                [0.1]\n",
      "  |. [-> . . . .| [1:2] VP -> VP * PP                [0.013000000000000001]\n",
      "  |. [---> . . .| [1:3] VP -> VP * PP                [0.00455]\n",
      "\n",
      "-------------------------+------------------------------------------\n",
      "   Parser           Beam | Time (secs)   # Parses   Average P(parse)\n",
      "-------------------------+------------------------------------------\n",
      "      ViterbiParser    0 |     0.0060          1   0.00005204062500\n",
      "  InsideChartParser    0 |     0.0100          2   0.00007285687500\n",
      "  RandomChartParser    0 |     0.0070          2   0.00007285687500\n",
      "UnsortedChartParser    0 |     0.0070          2   0.00007285687500\n",
      " LongestChartParser    0 |     0.0110          2   0.00007285687500\n",
      "  InsideChartParser    0 |     0.0040          0   0.00000000000000\n",
      "-------------------------+------------------------------------------\n",
      "       (All Parses)      |        n/a          2   0.00003642843750\n",
      "\n",
      "(S\n",
      "  (NP I)\n",
      "  (VP\n",
      "    (V saw)\n",
      "    (NP\n",
      "      (NP John)\n",
      "      (PP (P with) (NP (Det my) (N telescope)))))) [5.204062499999999e-05]\n",
      "(S\n",
      "  (NP I)\n",
      "  (VP\n",
      "    (VP (V saw) (NP John))\n",
      "    (PP (P with) (NP (Det my) (N telescope))))) [2.081625e-05]\n"
     ]
    }
   ],
   "source": [
    "# Run the parsers on the tokenized sentence.\n",
    "from functools import reduce\n",
    "times = []\n",
    "average_p = []\n",
    "num_parses = []\n",
    "all_parses = {}\n",
    "for parser in parsers:\n",
    "    print('\\ns: %s\\nparser: %s\\ngrammar: %s' % (sent,parser,grammar))\n",
    "    parser.trace(3)\n",
    "    t = time.time()\n",
    "    parses = parser.parse_all(tokens)\n",
    "    times.append(time.time()-t)\n",
    "    if parses: \n",
    "        lp = len(parses)\n",
    "        p = reduce(lambda a,b:a+b.prob(), parses, 0.0)\n",
    "    else: \n",
    "        p = 0\n",
    "    average_p.append(p)\n",
    "    num_parses.append(len(parses))\n",
    "    for p in parses: \n",
    "        all_parses[p.freeze()] = 1\n",
    "\n",
    "# Print summary statistics\n",
    "print()\n",
    "print('-------------------------+------------------------------------------')\n",
    "print('   Parser           Beam | Time (secs)   # Parses   Average P(parse)')\n",
    "print('-------------------------+------------------------------------------')\n",
    "for i in range(len(parsers)):\n",
    "    print('%19s %4d |%11.4f%11d%19.14f' % (parsers[i].__class__.__name__,\n",
    "      getattr(parsers[0], \"beam_size\", 0),\n",
    "      times[i], \n",
    "      num_parses[i], \n",
    "      average_p[i]))\n",
    "parses = all_parses.keys()\n",
    "if parses: \n",
    "    p = reduce(lambda a,b:a+b.prob(), parses, 0)/len(parses)\n",
    "else: \n",
    "    p = 0\n",
    "print('-------------------------+------------------------------------------')\n",
    "print('%19s      |%11s%11d%19.14f' % ('(All Parses)', 'n/a', len(parses), p))\n",
    "print()\n",
    "\n",
    "for parse in parses:\n",
    "    print(parse)\n"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "(C) 2018-2019 by [Damir Cavar](http://damir.cavar.me/) - [Creative Commons Attribution-ShareAlike 4.0 International License](https://creativecommons.org/licenses/by-sa/4.0/) ([CA BY-SA 4.0](https://creativecommons.org/licenses/by-sa/4.0/)). Parts of the code are taken from [Michael Elhadad](https://www.cs.bgu.ac.il/~elhadad/)'s notebook *[Constituent-based Syntactic Parsing with NLTK](https://www.cs.bgu.ac.il/~elhadad/nlp16/nltk-pcfg.html)*. Please consult him for details about the copyright."
   ]
  }
 ],
 "metadata": {
  "kernelspec": {
   "display_name": "Python 3",
   "language": "python",
   "name": "python3"
  },
  "language_info": {
   "codemirror_mode": {
    "name": "ipython",
    "version": 3
   },
   "file_extension": ".py",
   "mimetype": "text/x-python",
   "name": "python",
   "nbconvert_exporter": "python",
   "pygments_lexer": "ipython3",
   "version": "3.7.3"
  },
  "latex_envs": {
   "LaTeX_envs_menu_present": true,
   "autoclose": false,
   "autocomplete": true,
   "bibliofile": "biblio.bib",
   "cite_by": "apalike",
   "current_citInitial": 1,
   "eqLabelWithNumbers": true,
   "eqNumInitial": 1,
   "hotkeys": {
    "equation": "Ctrl-E",
    "itemize": "Ctrl-I"
   },
   "labels_anchors": false,
   "latex_user_defs": false,
   "report_style_numbering": false,
   "user_envs_cfg": false
  },
  "toc": {
   "base_numbering": 1,
   "nav_menu": {},
   "number_sections": false,
   "sideBar": false,
   "skip_h1_title": false,
   "title_cell": "Table of Contents",
   "title_sidebar": "Contents",
   "toc_cell": false,
   "toc_position": {},
   "toc_section_display": false,
   "toc_window_display": false
  }
 },
 "nbformat": 4,
 "nbformat_minor": 1
}