notebooks/Python Parsing with NLTK.ipynb

{
 "cells": [
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "# Python Parsing with NLTK"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "**(C) 2017-2024 by [Damir Cavar](https://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-notebooks)."
   ]
  },
  {
   "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": [
    "**Prerequisites:**"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "!pip install -U nltk\n",
    "!pip install -U svgling"
   ]
  },
  {
   "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, Fall 2018 and 2020."
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "## Working with Grammars"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "The following examples are taken from the NLTK [parsing HOWTO](https://www.nltk.org/howto/parse.html) page."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 2,
   "metadata": {},
   "outputs": [],
   "source": [
    "import nltk\n",
    "from nltk import Nonterminal, nonterminals, Production, CFG\n",
    "from nltk.grammar import FeatureGrammar as FCFG\n",
    "import svgling"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 3,
   "metadata": {},
   "outputs": [],
   "source": [
    "nt1 = Nonterminal('NP')\n",
    "nt2 = Nonterminal('VP')"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 4,
   "metadata": {},
   "outputs": [
    {
     "data": {
      "text/plain": [
       "'NP'"
      ]
     },
     "execution_count": 4,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "nt1.symbol()"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 5,
   "metadata": {},
   "outputs": [
    {
     "data": {
      "text/plain": [
       "True"
      ]
     },
     "execution_count": 5,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "nt1 == Nonterminal('NP')"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 6,
   "metadata": {},
   "outputs": [
    {
     "data": {
      "text/plain": [
       "False"
      ]
     },
     "execution_count": 6,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "nt1 == nt2"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 7,
   "metadata": {},
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "S\n"
     ]
    }
   ],
   "source": [
    "S, NP, VP, PP = nonterminals('S, NP, VP, PP')\n",
    "print(S.symbol())"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 8,
   "metadata": {},
   "outputs": [],
   "source": [
    "N, V, P, DT = nonterminals('N, V, P, DT')"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 9,
   "metadata": {},
   "outputs": [],
   "source": [
    "prod1 = Production(S, [NP, VP])"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 10,
   "metadata": {},
   "outputs": [],
   "source": [
    "prod2 = Production(NP, [DT, NP])"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 11,
   "metadata": {},
   "outputs": [
    {
     "data": {
      "text/plain": [
       "S"
      ]
     },
     "execution_count": 11,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "prod1.lhs()"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 12,
   "metadata": {},
   "outputs": [
    {
     "data": {
      "text/plain": [
       "(NP, VP)"
      ]
     },
     "execution_count": 12,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "prod1.rhs()"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 13,
   "metadata": {},
   "outputs": [
    {
     "data": {
      "text/plain": [
       "True"
      ]
     },
     "execution_count": 13,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "prod1 == Production(S, [NP, VP])"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 14,
   "metadata": {},
   "outputs": [
    {
     "data": {
      "text/plain": [
       "False"
      ]
     },
     "execution_count": 14,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "prod1 == prod2"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 15,
   "metadata": {},
   "outputs": [],
   "source": [
    "grammar = CFG.fromstring(\"\"\"\n",
    " S -> NP VP\n",
    " PP -> P NP\n",
    " PP -> P NP\n",
    " NP -> 'the' N | N PP | 'the' N PP\n",
    " NP -> D N\n",
    " D -> 'a'\n",
    " VP -> V NP | V PP | V NP PP\n",
    " N -> 'cat'\n",
    " N -> 'fish'\n",
    " N -> 'aligator'\n",
    " N -> 'dog'\n",
    " N -> 'rug'\n",
    " N -> 'mouse'\n",
    " V -> 'chased'\n",
    " V -> 'sat'\n",
    " P -> 'in'\n",
    " P -> 'on'\n",
    "\"\"\")"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 16,
   "metadata": {},
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "Grammar with 21 productions (start state = S)\n",
      "    S -> NP VP\n",
      "    PP -> P NP\n",
      "    PP -> P NP\n",
      "    NP -> 'the' N\n",
      "    NP -> N PP\n",
      "    NP -> 'the' N PP\n",
      "    NP -> D N\n",
      "    D -> 'a'\n",
      "    VP -> V NP\n",
      "    VP -> V PP\n",
      "    VP -> V NP PP\n",
      "    N -> 'cat'\n",
      "    N -> 'fish'\n",
      "    N -> 'aligator'\n",
      "    N -> 'dog'\n",
      "    N -> 'rug'\n",
      "    N -> 'mouse'\n",
      "    V -> 'chased'\n",
      "    V -> 'sat'\n",
      "    P -> 'in'\n",
      "    P -> 'on'\n"
     ]
    }
   ],
   "source": [
    "print(grammar)"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "## Feature Structures"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "One can build complex feature structures using the following strategies:"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 17,
   "metadata": {},
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "[        [ GND = 'fem' ] ]\n",
      "[ AGR  = [ NUM = 'pl'  ] ]\n",
      "[        [ PER = 3     ] ]\n",
      "[                        ]\n",
      "[ POS  = 'N'             ]\n",
      "[ Pred = 'houses'        ]\n"
     ]
    }
   ],
   "source": [
    "fstr = nltk.FeatStruct(\"[Pred='houses', POS='N', AGR=[PER=3, NUM='pl', GND='fem']]\")\n",
    "print(fstr)"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Creating shared paths is also possible:"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 18,
   "metadata": {},
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "[ ADDRESS = (1) [ NUMBER = 74           ] ]\n",
      "[               [ STREET = 'rue Pascal' ] ]\n",
      "[                                         ]\n",
      "[ NAME    = 'Lee'                         ]\n",
      "[                                         ]\n",
      "[ SPOUSE  = [ ADDRESS -> (1)  ]           ]\n",
      "[           [ NAME    = 'Kim' ]           ]\n"
     ]
    }
   ],
   "source": [
    "fstr2 = nltk.FeatStruct(\"\"\"[NAME='Lee', ADDRESS=(1)[NUMBER=74, STREET='rue Pascal'],\n",
    "                          SPOUSE=[NAME='Kim', ADDRESS->(1)]]\"\"\")\n",
    "print(fstr2)"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Let us create feature structures and try out unification:"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 19,
   "metadata": {},
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "[       [ GND = 'fem' ] ]\n",
      "[ AGR = [ NUM = 'pl'  ] ]\n",
      "[       [ PER = 3     ] ]\n",
      "[                       ]\n",
      "[ POS = 'N'             ]\n"
     ]
    }
   ],
   "source": [
    "fs1 = nltk.FeatStruct(\"[AGR=[PER=3, NUM='pl', GND='fem'], POS='N']\")\n",
    "fs2 = nltk.FeatStruct(\"[POS='N', AGR=[PER=3, GND='fem']]\")\n",
    "\n",
    "print(fs1.unify(fs2))"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "## Chart Parser"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "The following examples are taken from the NLTK [parsing HOWTO](https://www.nltk.org/howto/parse.html) page."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 21,
   "metadata": {},
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "* Sentence:\n",
      "I saw a dog\n",
      "['I', 'saw', 'a', 'dog']\n",
      "\n",
      "* Strategy: Bottom-up\n",
      "\n",
      "|.    I    .   saw   .    a    .   dog   .|\n",
      "|[---------]         .         .         .| [0:1] 'I'\n",
      "|.         [---------]         .         .| [1:2] 'saw'\n",
      "|.         .         [---------]         .| [2:3] 'a'\n",
      "|.         .         .         [---------]| [3:4] 'dog'\n",
      "|>         .         .         .         .| [0:0] NP -> * 'I'\n",
      "|[---------]         .         .         .| [0:1] NP -> 'I' *\n",
      "|>         .         .         .         .| [0:0] S  -> * NP VP\n",
      "|>         .         .         .         .| [0:0] NP -> * NP PP\n",
      "|[--------->         .         .         .| [0:1] S  -> NP * VP\n",
      "|[--------->         .         .         .| [0:1] NP -> NP * PP\n",
      "|.         >         .         .         .| [1:1] Verb -> * 'saw'\n",
      "|.         [---------]         .         .| [1:2] Verb -> 'saw' *\n",
      "|.         >         .         .         .| [1:1] VP -> * Verb NP\n",
      "|.         >         .         .         .| [1:1] VP -> * Verb\n",
      "|.         [--------->         .         .| [1:2] VP -> Verb * NP\n",
      "|.         [---------]         .         .| [1:2] VP -> Verb *\n",
      "|.         >         .         .         .| [1:1] VP -> * VP PP\n",
      "|[-------------------]         .         .| [0:2] S  -> NP VP *\n",
      "|.         [--------->         .         .| [1:2] VP -> VP * PP\n",
      "|.         .         >         .         .| [2:2] Det -> * 'a'\n",
      "|.         .         [---------]         .| [2:3] Det -> 'a' *\n",
      "|.         .         >         .         .| [2:2] NP -> * Det Noun\n",
      "|.         .         [--------->         .| [2:3] NP -> Det * Noun\n",
      "|.         .         .         >         .| [3:3] Noun -> * 'dog'\n",
      "|.         .         .         [---------]| [3:4] Noun -> 'dog' *\n",
      "|.         .         [-------------------]| [2:4] NP -> Det Noun *\n",
      "|.         .         >         .         .| [2:2] S  -> * NP VP\n",
      "|.         .         >         .         .| [2:2] NP -> * NP PP\n",
      "|.         [-----------------------------]| [1:4] VP -> Verb NP *\n",
      "|.         .         [------------------->| [2:4] S  -> NP * VP\n",
      "|.         .         [------------------->| [2:4] NP -> NP * PP\n",
      "|[=======================================]| [0:4] S  -> NP VP *\n",
      "|.         [----------------------------->| [1:4] VP -> VP * PP\n",
      "Nr edges in chart: 33\n",
      "(S (NP I) (VP (Verb saw) (NP (Det a) (Noun dog))))\n",
      "\n"
     ]
    }
   ],
   "source": [
    "nltk.parse.chart.demo(2, print_times=False, trace=1,\n",
    "                       sent='I saw a dog', numparses=1)"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "This is an example how to apply top-down parsing:"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 22,
   "metadata": {},
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "* Sentence:\n",
      "she killed the man with the tie\n",
      "['she', 'killed', 'the', 'man', 'with', 'the', 'tie']\n",
      "\n",
      "* Strategy: Top-down\n",
      "\n"
     ]
    },
    {
     "ename": "ValueError",
     "evalue": "Grammar does not cover some of the input words: \"'she', 'killed', 'man', 'tie'\".",
     "output_type": "error",
     "traceback": [
      "\u001b[0;31m---------------------------------------------------------------------------\u001b[0m",
      "\u001b[0;31mValueError\u001b[0m                                Traceback (most recent call last)",
      "Cell \u001b[0;32mIn[22], line 1\u001b[0m\n\u001b[0;32m----> 1\u001b[0m \u001b[43mnltk\u001b[49m\u001b[38;5;241;43m.\u001b[39;49m\u001b[43mparse\u001b[49m\u001b[38;5;241;43m.\u001b[39;49m\u001b[43mchart\u001b[49m\u001b[38;5;241;43m.\u001b[39;49m\u001b[43mdemo\u001b[49m\u001b[43m(\u001b[49m\u001b[38;5;241;43m1\u001b[39;49m\u001b[43m,\u001b[49m\u001b[43m \u001b[49m\u001b[43mprint_times\u001b[49m\u001b[38;5;241;43m=\u001b[39;49m\u001b[38;5;28;43;01mTrue\u001b[39;49;00m\u001b[43m,\u001b[49m\u001b[43m \u001b[49m\u001b[43mtrace\u001b[49m\u001b[38;5;241;43m=\u001b[39;49m\u001b[38;5;241;43m0\u001b[39;49m\u001b[43m,\u001b[49m\n\u001b[1;32m      2\u001b[0m \u001b[43m                       \u001b[49m\u001b[43msent\u001b[49m\u001b[38;5;241;43m=\u001b[39;49m\u001b[38;5;124;43m'\u001b[39;49m\u001b[38;5;124;43mshe killed the man with the tie\u001b[39;49m\u001b[38;5;124;43m'\u001b[39;49m\u001b[43m,\u001b[49m\u001b[43m \u001b[49m\u001b[43mnumparses\u001b[49m\u001b[38;5;241;43m=\u001b[39;49m\u001b[38;5;241;43m2\u001b[39;49m\u001b[43m)\u001b[49m\n",
      "File \u001b[0;32m/usr/lib/python3/dist-packages/nltk/parse/chart.py:1792\u001b[0m, in \u001b[0;36mdemo\u001b[0;34m(choice, print_times, print_grammar, print_trees, trace, sent, numparses)\u001b[0m\n\u001b[1;32m   1790\u001b[0m cp \u001b[38;5;241m=\u001b[39m ChartParser(grammar, strategies[strategy][\u001b[38;5;241m1\u001b[39m], trace\u001b[38;5;241m=\u001b[39mtrace)\n\u001b[1;32m   1791\u001b[0m t \u001b[38;5;241m=\u001b[39m time\u001b[38;5;241m.\u001b[39mtime()\n\u001b[0;32m-> 1792\u001b[0m chart \u001b[38;5;241m=\u001b[39m \u001b[43mcp\u001b[49m\u001b[38;5;241;43m.\u001b[39;49m\u001b[43mchart_parse\u001b[49m\u001b[43m(\u001b[49m\u001b[43mtokens\u001b[49m\u001b[43m)\u001b[49m\n\u001b[1;32m   1793\u001b[0m parses \u001b[38;5;241m=\u001b[39m \u001b[38;5;28mlist\u001b[39m(chart\u001b[38;5;241m.\u001b[39mparses(grammar\u001b[38;5;241m.\u001b[39mstart()))\n\u001b[1;32m   1795\u001b[0m times[strategies[strategy][\u001b[38;5;241m0\u001b[39m]] \u001b[38;5;241m=\u001b[39m time\u001b[38;5;241m.\u001b[39mtime() \u001b[38;5;241m-\u001b[39m t\n",
      "File \u001b[0;32m/usr/lib/python3/dist-packages/nltk/parse/chart.py:1432\u001b[0m, in \u001b[0;36mChartParser.chart_parse\u001b[0;34m(self, tokens, trace)\u001b[0m\n\u001b[1;32m   1429\u001b[0m trace_new_edges \u001b[38;5;241m=\u001b[39m \u001b[38;5;28mself\u001b[39m\u001b[38;5;241m.\u001b[39m_trace_new_edges\n\u001b[1;32m   1431\u001b[0m tokens \u001b[38;5;241m=\u001b[39m \u001b[38;5;28mlist\u001b[39m(tokens)\n\u001b[0;32m-> 1432\u001b[0m \u001b[38;5;28;43mself\u001b[39;49m\u001b[38;5;241;43m.\u001b[39;49m\u001b[43m_grammar\u001b[49m\u001b[38;5;241;43m.\u001b[39;49m\u001b[43mcheck_coverage\u001b[49m\u001b[43m(\u001b[49m\u001b[43mtokens\u001b[49m\u001b[43m)\u001b[49m\n\u001b[1;32m   1433\u001b[0m chart \u001b[38;5;241m=\u001b[39m \u001b[38;5;28mself\u001b[39m\u001b[38;5;241m.\u001b[39m_chart_class(tokens)\n\u001b[1;32m   1434\u001b[0m grammar \u001b[38;5;241m=\u001b[39m \u001b[38;5;28mself\u001b[39m\u001b[38;5;241m.\u001b[39m_grammar\n",
      "File \u001b[0;32m/usr/lib/python3/dist-packages/nltk/grammar.py:665\u001b[0m, in \u001b[0;36mCFG.check_coverage\u001b[0;34m(self, tokens)\u001b[0m\n\u001b[1;32m    663\u001b[0m \u001b[38;5;28;01mif\u001b[39;00m missing:\n\u001b[1;32m    664\u001b[0m     missing \u001b[38;5;241m=\u001b[39m \u001b[38;5;124m\"\u001b[39m\u001b[38;5;124m, \u001b[39m\u001b[38;5;124m\"\u001b[39m\u001b[38;5;241m.\u001b[39mjoin(\u001b[38;5;124mf\u001b[39m\u001b[38;5;124m\"\u001b[39m\u001b[38;5;132;01m{\u001b[39;00mw\u001b[38;5;132;01m!r}\u001b[39;00m\u001b[38;5;124m\"\u001b[39m \u001b[38;5;28;01mfor\u001b[39;00m w \u001b[38;5;129;01min\u001b[39;00m missing)\n\u001b[0;32m--> 665\u001b[0m     \u001b[38;5;28;01mraise\u001b[39;00m \u001b[38;5;167;01mValueError\u001b[39;00m(\n\u001b[1;32m    666\u001b[0m         \u001b[38;5;124m\"\u001b[39m\u001b[38;5;124mGrammar does not cover some of the \u001b[39m\u001b[38;5;124m\"\u001b[39m \u001b[38;5;124m\"\u001b[39m\u001b[38;5;124minput words: \u001b[39m\u001b[38;5;132;01m%r\u001b[39;00m\u001b[38;5;124m.\u001b[39m\u001b[38;5;124m\"\u001b[39m \u001b[38;5;241m%\u001b[39m missing\n\u001b[1;32m    667\u001b[0m     )\n",
      "\u001b[0;31mValueError\u001b[0m: Grammar does not cover some of the input words: \"'she', 'killed', 'man', 'tie'\"."
     ]
    }
   ],
   "source": [
    "nltk.parse.chart.demo(1, print_times=True, trace=0,\n",
    "                       sent='she killed the man with the tie', numparses=2)"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "This is how to apply bottom-up parsing:"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 24,
   "metadata": {},
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "* Sentence:\n",
      "I saw John in the house\n",
      "['I', 'saw', 'John', 'in', 'the', 'house']\n",
      "\n",
      "* Strategy: Bottom-up\n",
      "\n"
     ]
    },
    {
     "ename": "ValueError",
     "evalue": "Grammar does not cover some of the input words: \"'in', 'house'\".",
     "output_type": "error",
     "traceback": [
      "\u001b[0;31m---------------------------------------------------------------------------\u001b[0m",
      "\u001b[0;31mValueError\u001b[0m                                Traceback (most recent call last)",
      "Cell \u001b[0;32mIn[24], line 1\u001b[0m\n\u001b[0;32m----> 1\u001b[0m \u001b[43mnltk\u001b[49m\u001b[38;5;241;43m.\u001b[39;49m\u001b[43mparse\u001b[49m\u001b[38;5;241;43m.\u001b[39;49m\u001b[43mchart\u001b[49m\u001b[38;5;241;43m.\u001b[39;49m\u001b[43mdemo\u001b[49m\u001b[43m(\u001b[49m\u001b[38;5;241;43m2\u001b[39;49m\u001b[43m,\u001b[49m\u001b[43m \u001b[49m\u001b[43mprint_times\u001b[49m\u001b[38;5;241;43m=\u001b[39;49m\u001b[38;5;28;43;01mFalse\u001b[39;49;00m\u001b[43m,\u001b[49m\u001b[43m \u001b[49m\u001b[43mtrace\u001b[49m\u001b[38;5;241;43m=\u001b[39;49m\u001b[38;5;241;43m0\u001b[39;49m\u001b[43m,\u001b[49m\n\u001b[1;32m      2\u001b[0m \u001b[43m                       \u001b[49m\u001b[43msent\u001b[49m\u001b[38;5;241;43m=\u001b[39;49m\u001b[38;5;124;43m'\u001b[39;49m\u001b[38;5;124;43mI saw John in the house\u001b[39;49m\u001b[38;5;124;43m'\u001b[39;49m\u001b[43m,\u001b[49m\u001b[43m \u001b[49m\u001b[43mnumparses\u001b[49m\u001b[38;5;241;43m=\u001b[39;49m\u001b[38;5;241;43m2\u001b[39;49m\u001b[43m)\u001b[49m\n",
      "File \u001b[0;32m/usr/lib/python3.12/site-packages/nltk/parse/chart.py:1792\u001b[0m, in \u001b[0;36mdemo\u001b[0;34m(choice, print_times, print_grammar, print_trees, trace, sent, numparses)\u001b[0m\n\u001b[1;32m   1790\u001b[0m cp \u001b[38;5;241m=\u001b[39m ChartParser(grammar, strategies[strategy][\u001b[38;5;241m1\u001b[39m], trace\u001b[38;5;241m=\u001b[39mtrace)\n\u001b[1;32m   1791\u001b[0m t \u001b[38;5;241m=\u001b[39m time\u001b[38;5;241m.\u001b[39mtime()\n\u001b[0;32m-> 1792\u001b[0m chart \u001b[38;5;241m=\u001b[39m \u001b[43mcp\u001b[49m\u001b[38;5;241;43m.\u001b[39;49m\u001b[43mchart_parse\u001b[49m\u001b[43m(\u001b[49m\u001b[43mtokens\u001b[49m\u001b[43m)\u001b[49m\n\u001b[1;32m   1793\u001b[0m parses \u001b[38;5;241m=\u001b[39m \u001b[38;5;28mlist\u001b[39m(chart\u001b[38;5;241m.\u001b[39mparses(grammar\u001b[38;5;241m.\u001b[39mstart()))\n\u001b[1;32m   1795\u001b[0m times[strategies[strategy][\u001b[38;5;241m0\u001b[39m]] \u001b[38;5;241m=\u001b[39m time\u001b[38;5;241m.\u001b[39mtime() \u001b[38;5;241m-\u001b[39m t\n",
      "File \u001b[0;32m/usr/lib/python3.12/site-packages/nltk/parse/chart.py:1432\u001b[0m, in \u001b[0;36mChartParser.chart_parse\u001b[0;34m(self, tokens, trace)\u001b[0m\n\u001b[1;32m   1429\u001b[0m trace_new_edges \u001b[38;5;241m=\u001b[39m \u001b[38;5;28mself\u001b[39m\u001b[38;5;241m.\u001b[39m_trace_new_edges\n\u001b[1;32m   1431\u001b[0m tokens \u001b[38;5;241m=\u001b[39m \u001b[38;5;28mlist\u001b[39m(tokens)\n\u001b[0;32m-> 1432\u001b[0m \u001b[38;5;28;43mself\u001b[39;49m\u001b[38;5;241;43m.\u001b[39;49m\u001b[43m_grammar\u001b[49m\u001b[38;5;241;43m.\u001b[39;49m\u001b[43mcheck_coverage\u001b[49m\u001b[43m(\u001b[49m\u001b[43mtokens\u001b[49m\u001b[43m)\u001b[49m\n\u001b[1;32m   1433\u001b[0m chart \u001b[38;5;241m=\u001b[39m \u001b[38;5;28mself\u001b[39m\u001b[38;5;241m.\u001b[39m_chart_class(tokens)\n\u001b[1;32m   1434\u001b[0m grammar \u001b[38;5;241m=\u001b[39m \u001b[38;5;28mself\u001b[39m\u001b[38;5;241m.\u001b[39m_grammar\n",
      "File \u001b[0;32m/usr/lib/python3.12/site-packages/nltk/grammar.py:665\u001b[0m, in \u001b[0;36mCFG.check_coverage\u001b[0;34m(self, tokens)\u001b[0m\n\u001b[1;32m    663\u001b[0m \u001b[38;5;28;01mif\u001b[39;00m missing:\n\u001b[1;32m    664\u001b[0m     missing \u001b[38;5;241m=\u001b[39m \u001b[38;5;124m\"\u001b[39m\u001b[38;5;124m, \u001b[39m\u001b[38;5;124m\"\u001b[39m\u001b[38;5;241m.\u001b[39mjoin(\u001b[38;5;124mf\u001b[39m\u001b[38;5;124m\"\u001b[39m\u001b[38;5;132;01m{\u001b[39;00mw\u001b[38;5;132;01m!r}\u001b[39;00m\u001b[38;5;124m\"\u001b[39m \u001b[38;5;28;01mfor\u001b[39;00m w \u001b[38;5;129;01min\u001b[39;00m missing)\n\u001b[0;32m--> 665\u001b[0m     \u001b[38;5;28;01mraise\u001b[39;00m \u001b[38;5;167;01mValueError\u001b[39;00m(\n\u001b[1;32m    666\u001b[0m         \u001b[38;5;124m\"\u001b[39m\u001b[38;5;124mGrammar does not cover some of the \u001b[39m\u001b[38;5;124m\"\u001b[39m \u001b[38;5;124m\"\u001b[39m\u001b[38;5;124minput words: \u001b[39m\u001b[38;5;132;01m%r\u001b[39;00m\u001b[38;5;124m.\u001b[39m\u001b[38;5;124m\"\u001b[39m \u001b[38;5;241m%\u001b[39m missing\n\u001b[1;32m    667\u001b[0m     )\n",
      "\u001b[0;31mValueError\u001b[0m: Grammar does not cover some of the input words: \"'in', 'house'\"."
     ]
    }
   ],
   "source": [
    "nltk.parse.chart.demo(2, print_times=False, trace=0,\n",
    "                       sent='I saw John in the house', numparses=2)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 25,
   "metadata": {},
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "\n",
      "Grammar with 18 productions (start state = S[])\n",
      "    S[] -> NP[] VP[]\n",
      "    PP[] -> Prep[] NP[]\n",
      "    NP[] -> NP[] PP[]\n",
      "    VP[] -> VP[] PP[]\n",
      "    VP[] -> Verb[] NP[]\n",
      "    VP[] -> Verb[]\n",
      "    NP[] -> Det[pl=?x] Noun[pl=?x]\n",
      "    NP[] -> 'John'\n",
      "    NP[] -> 'I'\n",
      "    Det[] -> 'the'\n",
      "    Det[] -> 'my'\n",
      "    Det[-pl] -> 'a'\n",
      "    Noun[-pl] -> 'dog'\n",
      "    Noun[-pl] -> 'cookie'\n",
      "    Verb[] -> 'ate'\n",
      "    Verb[] -> 'saw'\n",
      "    Prep[] -> 'with'\n",
      "    Prep[] -> 'under'\n",
      "\n",
      "* FeatureChartParser\n",
      "Sentence: I saw John with a dog\n",
      "|.I.s.J.w.a.d.|\n",
      "|[-] . . . . .| [0:1] 'I'\n",
      "|. [-] . . . .| [1:2] 'saw'\n",
      "|. . [-] . . .| [2:3] 'John'\n",
      "|. . . [-] . .| [3:4] 'with'\n",
      "|. . . . [-] .| [4:5] 'a'\n",
      "|. . . . . [-]| [5:6] 'dog'\n",
      "|[-] . . . . .| [0:1] NP[] -> 'I' *\n",
      "|[-> . . . . .| [0:1] S[] -> NP[] * VP[] {}\n",
      "|[-> . . . . .| [0:1] NP[] -> NP[] * PP[] {}\n",
      "|. [-] . . . .| [1:2] Verb[] -> 'saw' *\n",
      "|. [-> . . . .| [1:2] VP[] -> Verb[] * NP[] {}\n",
      "|. [-] . . . .| [1:2] VP[] -> Verb[] *\n",
      "|. [-> . . . .| [1:2] VP[] -> VP[] * PP[] {}\n",
      "|[---] . . . .| [0:2] S[] -> NP[] VP[] *\n",
      "|. . [-] . . .| [2:3] NP[] -> 'John' *\n",
      "|. . [-> . . .| [2:3] S[] -> NP[] * VP[] {}\n",
      "|. . [-> . . .| [2:3] NP[] -> NP[] * PP[] {}\n",
      "|. [---] . . .| [1:3] VP[] -> Verb[] NP[] *\n",
      "|. [---> . . .| [1:3] VP[] -> VP[] * PP[] {}\n",
      "|[-----] . . .| [0:3] S[] -> NP[] VP[] *\n",
      "|. . . [-] . .| [3:4] Prep[] -> 'with' *\n",
      "|. . . [-> . .| [3:4] PP[] -> Prep[] * NP[] {}\n",
      "|. . . . [-] .| [4:5] Det[-pl] -> 'a' *\n",
      "|. . . . [-> .| [4:5] NP[] -> Det[pl=?x] * Noun[pl=?x] {?x: False}\n",
      "|. . . . . [-]| [5:6] Noun[-pl] -> 'dog' *\n",
      "|. . . . [---]| [4:6] NP[] -> Det[-pl] Noun[-pl] *\n",
      "|. . . . [--->| [4:6] S[] -> NP[] * VP[] {}\n",
      "|. . . . [--->| [4:6] NP[] -> NP[] * PP[] {}\n",
      "|. . . [-----]| [3:6] PP[] -> Prep[] NP[] *\n",
      "|. . [-------]| [2:6] NP[] -> NP[] PP[] *\n",
      "|. [---------]| [1:6] VP[] -> VP[] PP[] *\n",
      "|. [--------->| [1:6] VP[] -> VP[] * PP[] {}\n",
      "|[===========]| [0:6] S[] -> NP[] VP[] *\n",
      "|. . [------->| [2:6] S[] -> NP[] * VP[] {}\n",
      "|. . [------->| [2:6] NP[] -> NP[] * PP[] {}\n",
      "|. [---------]| [1:6] VP[] -> Verb[] NP[] *\n",
      "|. [--------->| [1:6] VP[] -> VP[] * PP[] {}\n",
      "|[===========]| [0:6] S[] -> NP[] VP[] *\n",
      "(S[]\n",
      "  (NP[] I)\n",
      "  (VP[]\n",
      "    (VP[] (Verb[] saw) (NP[] John))\n",
      "    (PP[] (Prep[] with) (NP[] (Det[-pl] a) (Noun[-pl] dog)))))\n",
      "(S[]\n",
      "  (NP[] I)\n",
      "  (VP[]\n",
      "    (Verb[] saw)\n",
      "    (NP[]\n",
      "      (NP[] John)\n",
      "      (PP[] (Prep[] with) (NP[] (Det[-pl] a) (Noun[-pl] dog))))))\n"
     ]
    }
   ],
   "source": [
    "nltk.parse.featurechart.demo(print_times=False,\n",
    "                              print_grammar=True,\n",
    "                              parser=nltk.parse.featurechart.FeatureChartParser,\n",
    "                              sent='I saw John with a dog')"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "## Loading grammars from files and editing them"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "We will need the following NLTK modules in this section:"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "We can load a *grammar* from a file, that is located in the same folder as the current Jupyter notebook, in the following way:"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 27,
   "metadata": {},
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "Grammar with 32 productions (start state = S)\n",
      "    S -> NP VP\n",
      "    VP -> v NP\n",
      "    VP -> v\n",
      "    NP -> det N\n",
      "    NP -> N\n",
      "    N -> nom_com\n",
      "    N -> nom_prop\n",
      "    det -> 'el'\n",
      "    det -> 'la'\n",
      "    det -> 'los'\n",
      "    det -> 'las'\n",
      "    det -> 'un'\n",
      "    det -> 'una'\n",
      "    det -> 'unos'\n",
      "    det -> 'unas'\n",
      "    nom_com -> 'vecino'\n",
      "    nom_com -> 'ladrones'\n",
      "    nom_com -> 'mujeres'\n",
      "    nom_com -> 'bosques'\n",
      "    nom_com -> 'noche'\n",
      "    nom_com -> 'flauta'\n",
      "    nom_com -> 'ventana'\n",
      "    nom_prop -> 'Jose'\n",
      "    nom_prop -> 'Lucas'\n",
      "    nom_prop -> 'Pedro'\n",
      "    nom_prop -> 'Marta'\n",
      "    v -> 'toca'\n",
      "    v -> 'moja'\n",
      "    v -> 'adoran'\n",
      "    v -> 'robaron'\n",
      "    v -> 'escondieron'\n",
      "    v -> 'rompió'\n"
     ]
    }
   ],
   "source": [
    "cfg = nltk.data.load('spanish2.cfg')\n",
    "print(cfg)"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "We instantiate a ChartParser object with this grammar:"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 28,
   "metadata": {},
   "outputs": [],
   "source": [
    "cp1 = nltk.parse.ChartParser(cfg)"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "The *ChartParser* object has a parse-function that takes a list of tokens as a parameter. The token list can be generated using a language specific tokenizer. In this case we simply tokenize using the Python-function *split* on strings. The output of the parse function is a list of trees. We loop through the list of parse trees and print them out:"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 29,
   "metadata": {},
   "outputs": [
    {
     "data": {
      "text/plain": [
       "['los', 'mujeres', 'adoran', 'Lucas']"
      ]
     },
     "execution_count": 29,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "\"los mujeres adoran Lucas\".split()"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 30,
   "metadata": {},
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "(S\n",
      "  (NP (det los) (N (nom_com mujeres)))\n",
      "  (VP (v adoran) (NP (N (nom_prop Lucas)))))\n"
     ]
    }
   ],
   "source": [
    "for x in cp1.parse(\"los mujeres adoran Lucas\".split()):\n",
    "    print(x)\n",
    "    #print(x._repr_svg_()) # .draw()\n",
    "    nltk.Tree.fromstring(str(x))"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "We can also edit a grammar directly:"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 31,
   "metadata": {},
   "outputs": [],
   "source": [
    "cfg2 = CFG.fromstring(\"\"\"\n",
    " S -> NP VP\n",
    " PP -> P NP\n",
    " NP -> 'the' N | N PP | 'the' N PP\n",
    " VP -> V NP | V PP | V NP PP\n",
    " N -> 'cat'\n",
    " N -> 'dog'\n",
    " N -> 'bird'\n",
    " N -> 'rug'\n",
    " N -> 'woman'\n",
    " N -> 'man'\n",
    " N -> 'tie'\n",
    " V -> 'chased'\n",
    " V -> 'killed'\n",
    " V -> 'sat'\n",
    " V -> 'bit'\n",
    " P -> 'in'\n",
    " P -> 'on'\n",
    " P -> 'with'\n",
    "\"\"\")"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "We parse our example sentences using the same approach as above:"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 32,
   "metadata": {},
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "(S\n",
      "  (NP the (N woman))\n",
      "  (VP (V killed) (NP the (N man)) (PP (P with) (NP the (N tie)))))\n",
      "(S\n",
      "  (NP the (N woman))\n",
      "  (VP (V killed) (NP the (N man) (PP (P with) (NP the (N tie))))))\n"
     ]
    }
   ],
   "source": [
    "cp2 = nltk.parse.ChartParser(cfg2)\n",
    "for x in cp2.parse(\"the woman killed the man with the tie\".split()):\n",
    "    print(x)\n",
    "    nltk.Tree.fromstring(str(x))"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "The previous example included a Context-free grammar. In the following example we load a Context-free Grammar with Features, instantiate a *FeatureChartParser*, and loop through the parse trees that are generated by our grammar to print them out:"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 36,
   "metadata": {},
   "outputs": [],
   "source": [
    "fcfg = nltk.data.load('spanish2.fcfg')\n",
    "fcp1 = nltk.parse.FeatureChartParser(fcfg)\n",
    "for x in fcp1.parse(u\"las profesoras adoran el gato\".split()):\n",
    "    print(x)"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "We can edit a Feature CFG in the same way directly in this notebook and then parse with it:"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 37,
   "metadata": {},
   "outputs": [],
   "source": [
    "fcfg2 = FCFG.fromstring(\"\"\"\n",
    "% start CP\n",
    "# ############################\n",
    "# Grammar Rules\n",
    "# ############################\n",
    "CP -> Cbar[stype=decl]\n",
    "Cbar[stype=decl] -> IP[+TNS]\n",
    "IP[+TNS] -> DP[num=?n,pers=?p,case=nom] VP[num=?n,pers=?p]\n",
    "DP[num=?n,pers=?p,case=?k] ->  Dbar[num=?n,pers=?p,case=?k]\n",
    "Dbar[num=?n,pers=?p] -> D[num=?n,DEF=?d,COUNT=?c] NP[num=?n,pers=?p,DEF=?d,COUNT=?c]\n",
    "Dbar[num=?n,pers=?p] -> NP[num=?n,pers=?p,DEF=?d,COUNT=?c]\n",
    "Dbar[num=?n,pers=?p,case=?k] -> D[num=?n,pers=?p,+DEF,type=pron,case=?k]\n",
    "NP[num=?n,pers=?p,COUNT=?c] -> N[num=?n,pers=?p,type=prop,COUNT=?c]\n",
    "VP[num=?n,pers=?p] -> V[num=?n,pers=?p,val=1]\n",
    "VP[num=?n,pers=?p] -> V[num=?n,pers=?p,val=2] DP[case=acc]\n",
    "PP -> P DP[num=?n,pers=?p,case=acc]\n",
    "#PP -> P DP[num=?n,pers=?p,case=dat]\n",
    "#\n",
    "# ############################\n",
    "# Lexical Rules\n",
    "# ############################\n",
    "D[-DEF,+COUNT,num=sg] -> 'a'\n",
    "D[-DEF,+COUNT,num=sg] -> 'an'\n",
    "D[+DEF] -> 'the'\n",
    "D[+DEF,gen=f,num=sg,case=nom,type=pron] -> 'she'\n",
    "D[+DEF,gen=m,num=sg,case=nom,type=pron] -> 'he'\n",
    "D[+DEF,gen=n,num=sg,type=pron] -> 'it'\n",
    "D[+DEF,gen=f,num=sg,case=acc,type=pron] -> 'her'\n",
    "D[+DEF,gen=m,num=sg,case=acc,type=pron] -> 'him'\n",
    "N[num=sg,pers=3,type=prop] -> 'John' | 'Sara' | 'Mary'\n",
    "V[tns=pres,num=sg,pers=3,val=2] -> 'loves' | 'calls' | 'sees' | 'buys'\n",
    "N[num=sg,pers=3,-COUNT] -> 'furniture' | 'air' | 'justice'\n",
    "N[num=sg,pers=3] -> 'cat' | 'dog' | 'mouse'\n",
    "N[num=pl,pers=3] -> 'cats' | 'dogs' | 'mice'\n",
    "V[tns=pres,num=sg,pers=3,val=1] -> 'sleeps' | 'snores'\n",
    "V[tns=pres,num=sg,pers=1,val=1] -> 'sleep' | 'snore'\n",
    "V[tns=pres,num=sg,pers=2,val=1] -> 'sleep' | 'snore'\n",
    "V[tns=pres,num=pl,val=1] -> 'sleep' | 'snore'\n",
    "V[tns=past,val=1] -> 'slept' | 'snored'\n",
    "V[tns=pres,num=sg,pers=3,val=2] -> 'calls' | 'sees' | 'loves'\n",
    "V[tns=pres,num=sg,pers=1,val=2] -> 'call' | 'see' | 'love'\n",
    "V[tns=pres,num=sg,pers=2,val=2] -> 'call' | 'see' | 'love'\n",
    "V[tns=pres,num=pl,val=2] -> 'call' | 'see' | 'love'\n",
    "V[tns=past,val=2] -> 'called' | 'saw' | 'loved'\n",
    "\"\"\")"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "We can now create a parser instance and parse with this grammar:"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 40,
   "metadata": {},
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "|.Joh.buy.the.fur.|\n",
      "|[---]   .   .   .| [0:1] 'John'\n",
      "|.   [---]   .   .| [1:2] 'buys'\n",
      "|.   .   [---]   .| [2:3] 'the'\n",
      "|.   .   .   [---]| [3:4] 'furniture'\n",
      "|[---]   .   .   .| [0:1] N[num='sg', pers=3, type='prop'] -> 'John' *\n",
      "|[---]   .   .   .| [0:1] NP[COUNT=?c, num='sg', pers=3] -> N[COUNT=?c, num='sg', pers=3, type='prop'] *\n",
      "|[---]   .   .   .| [0:1] Dbar[num='sg', pers=3] -> NP[COUNT=?c, DEF=?d, num='sg', pers=3] *\n",
      "|[---]   .   .   .| [0:1] DP[case=?k, num='sg', pers=3] -> Dbar[case=?k, num='sg', pers=3] *\n",
      "|[--->   .   .   .| [0:1] IP[+TNS] -> DP[case='nom', num=?n, pers=?p] * VP[num=?n, pers=?p] {?k2: 'nom', ?n: 'sg', ?p: 3}\n",
      "|.   [---]   .   .| [1:2] V[num='sg', pers=3, tns='pres', val=2] -> 'buys' *\n",
      "|.   [--->   .   .| [1:2] VP[num=?n, pers=?p] -> V[num=?n, pers=?p, val=2] * DP[case='acc'] {?n: 'sg', ?p: 3}\n",
      "|.   .   [---]   .| [2:3] D[+DEF] -> 'the' *\n",
      "|.   .   [--->   .| [2:3] Dbar[num=?n, pers=?p] -> D[COUNT=?c, DEF=?d, num=?n] * NP[COUNT=?c, DEF=?d, num=?n, pers=?p] {?d: True}\n",
      "|.   .   [---]   .| [2:3] Dbar[case=?k, num=?n, pers=?p] -> D[+DEF, case=?k, num=?n, pers=?p, type='pron'] *\n",
      "|.   .   [---]   .| [2:3] DP[case=?k, num=?n, pers=?p] -> Dbar[case=?k, num=?n, pers=?p] *\n",
      "|.   .   [--->   .| [2:3] IP[+TNS] -> DP[case='nom', num=?n, pers=?p] * VP[num=?n, pers=?p] {?k2: 'nom', ?n2: Variable('?n'), ?p2: Variable('?p')}\n",
      "|.   [-------]   .| [1:3] VP[num='sg', pers=3] -> V[num='sg', pers=3, val=2] DP[case='acc'] *\n",
      "|[-----------]   .| [0:3] IP[+TNS] -> DP[case='nom', num='sg', pers=3] VP[num='sg', pers=3] *\n",
      "|[-----------]   .| [0:3] Cbar[stype='decl'] -> IP[+TNS] *\n",
      "|[-----------]   .| [0:3] CP[] -> Cbar[stype='decl'] *\n",
      "|.   .   .   [---]| [3:4] N[-COUNT, num='sg', pers=3] -> 'furniture' *\n",
      "|.   .   .   [---]| [3:4] NP[-COUNT, num='sg', pers=3] -> N[-COUNT, num='sg', pers=3, type='prop'] *\n",
      "|.   .   .   [---]| [3:4] Dbar[num='sg', pers=3] -> NP[-COUNT, DEF=?d, num='sg', pers=3] *\n",
      "|.   .   [-------]| [2:4] Dbar[num='sg', pers=3] -> D[-COUNT, +DEF, num='sg'] NP[-COUNT, +DEF, num='sg', pers=3] *\n",
      "|.   .   [-------]| [2:4] DP[case=?k, num='sg', pers=3] -> Dbar[case=?k, num='sg', pers=3] *\n",
      "|.   .   [------->| [2:4] IP[+TNS] -> DP[case='nom', num=?n, pers=?p] * VP[num=?n, pers=?p] {?k2: 'nom', ?n: 'sg', ?p: 3}\n",
      "|.   [-----------]| [1:4] VP[num='sg', pers=3] -> V[num='sg', pers=3, val=2] DP[case='acc'] *\n",
      "|[===============]| [0:4] IP[+TNS] -> DP[case='nom', num='sg', pers=3] VP[num='sg', pers=3] *\n",
      "|[===============]| [0:4] Cbar[stype='decl'] -> IP[+TNS] *\n",
      "|[===============]| [0:4] CP[] -> Cbar[stype='decl'] *\n",
      "|.   .   .   [---]| [3:4] DP[case=?k, num='sg', pers=3] -> Dbar[case=?k, num='sg', pers=3] *\n",
      "|.   .   .   [--->| [3:4] IP[+TNS] -> DP[case='nom', num=?n, pers=?p] * VP[num=?n, pers=?p] {?k2: 'nom', ?n: 'sg', ?p: 3}\n",
      "(CP[]\n",
      "  (Cbar[stype='decl']\n",
      "    (IP[+TNS]\n",
      "      (DP[case=?k, num='sg', pers=3]\n",
      "        (Dbar[num='sg', pers=3]\n",
      "          (NP[COUNT=?c, num='sg', pers=3]\n",
      "            (N[num='sg', pers=3, type='prop'] John))))\n",
      "      (VP[num='sg', pers=3]\n",
      "        (V[num='sg', pers=3, tns='pres', val=2] buys)\n",
      "        (DP[case=?k, num='sg', pers=3]\n",
      "          (Dbar[num='sg', pers=3]\n",
      "            (D[+DEF] the)\n",
      "            (NP[-COUNT, num='sg', pers=3]\n",
      "              (N[-COUNT, num='sg', pers=3] furniture))))))))\n"
     ]
    }
   ],
   "source": [
    "fcp2 = nltk.parse.FeatureChartParser(fcfg2, trace=1)\n",
    "sentence = \"John buys the furniture\"\n",
    "result = list(fcp2.parse(sentence.split()))\n",
    "if result:\n",
    "    for x in result:\n",
    "        print(x)\n",
    "else:\n",
    "    print(\"*\", sentence)"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Countable nouns and articles in a DP:"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": []
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "DPs and pronouns"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": []
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "CP/IP sentence structures"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": []
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "## Different Parsers"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "This is a list of the different Feature Parsers in NLTK.\n",
    "\n",
    "- nltk.parse.featurechart.FeatureChartParser\n",
    "- nltk.parse.featurechart.FeatureTopDownChartParser\n",
    "- nltk.parse.featurechart.FeatureBottomUpChartParser\n",
    "- nltk.parse.featurechart.FeatureBottomUpLeftCornerChartParser\n",
    "- nltk.parse.earleychart.FeatureIncrementalChartParser\n",
    "- nltk.parse.earleychart.FeatureEarleyChartParser\n",
    "- nltk.parse.earleychart.FeatureIncrementalTopDownChartParser\n",
    "- nltk.parse.earleychart.FeatureIncrementalBottomUpChartParser\n",
    "- nltk.parse.earleychart.FeatureIncrementalBottomUpLeftCornerChartParser\n",
    "\n",
    "I do not know whether this is an exhaustive list."
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "(C) 2017-2024 by [Damir Cavar](https://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/))"
   ]
  }
 ],
 "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.12.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": 4
}