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](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-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](http://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": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "nt1.symbol()"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "nt1 == Nonterminal('NP')"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "nt1 == nt2"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "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": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "prod1.lhs()"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "prod1.rhs()"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "prod1 == Production(S, [NP, VP])"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "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": null,
   "metadata": {},
   "outputs": [],
   "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": null,
   "metadata": {},
   "outputs": [],
   "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": null,
   "metadata": {},
   "outputs": [],
   "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": null,
   "metadata": {},
   "outputs": [],
   "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](http://www.nltk.org/howto/parse.html) page."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "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": null,
   "metadata": {},
   "outputs": [],
   "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": null,
   "metadata": {},
   "outputs": [],
   "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": null,
   "metadata": {},
   "outputs": [],
   "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": null,
   "metadata": {},
   "outputs": [],
   "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": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "\"los mujeres adoran Lucas\".split()"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "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": null,
   "metadata": {},
   "outputs": [],
   "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": null,
   "metadata": {},
   "outputs": [],
   "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](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/))"
   ]
  }
 ],
 "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
}