cky.ipynb

{
 "cells": [
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "## Context-free grammars and CKY parsing"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "## Load grammar, data and pre-processing\n",
    "\n",
    "\n",
    "### The CNF Grammar file\n",
    "\n",
    "\n",
    "First we read the grammar file provided to us and check all the details of the grammar that we need in this assignment."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 8,
   "metadata": {},
   "outputs": [],
   "source": [
    "'''\n",
    "We will use NLTK.CFG library to read the CNF grammar file \n",
    "provided to us for this assignment.\n",
    "'''\n",
    "\n",
    "import nltk\n",
    "filepath_grammar = 'atis/atis-grammar-cnf.cfg'\n",
    "file = open(filepath_grammar, 'r', encoding='utf-8')"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 9,
   "metadata": {},
   "outputs": [
    {
     "data": {
      "text/plain": [
       "<Grammar with 20326 productions>"
      ]
     },
     "execution_count": 9,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "'''\n",
    "We read the grammar file here\n",
    "'''\n",
    "\n",
    "grammar = CFG.fromstring(file)\n",
    "grammar"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 10,
   "metadata": {},
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "Starting symbol: SIGMA\n",
      "Data type of the symbol: <class 'nltk.grammar.Nonterminal'>\n"
     ]
    }
   ],
   "source": [
    "'''\n",
    "Here we check the starting symbol of the grammar.\n",
    "We also check the data type of the symbols in the grammar. We will need this in the CYK algorithm later on.\n",
    "'''\n",
    "\n",
    "print('Starting symbol:', grammar.start())\n",
    "print('Data type of the symbol:', type(grammar.start()))"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 11,
   "metadata": {},
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "SIGMA -> ADJ_ABL JYL\n",
      "GCC -> AVP_RB GCD\n",
      "GCD -> NP_DTS pt_char_per\n",
      "GCA -> AVP_RB GCB\n",
      "GCB -> COMPCL_VBZ pt_char_per\n",
      "GCK -> NP_NNS GCL\n",
      "GCL -> AJP_JJ pt_char_per\n",
      "GCI -> NP_DTS GCJ\n",
      "GCJ -> AJP_JJR pt_char_per\n",
      "GCG -> NP_DT GCH\n"
     ]
    }
   ],
   "source": [
    "'''\n",
    "We read the production rules of the grammar and print some of them to check the rules.\n",
    "'''\n",
    "\n",
    "productions = grammar.productions()\n",
    "for rule in productions[:10]:\n",
    "    print(rule)"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "### The ATIS test data\n",
    "\n",
    "Here we get the ATIS test data file"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 12,
   "metadata": {},
   "outputs": [],
   "source": [
    "'''\n",
    "We read the ATIS sentences and parse them into a readable format \n",
    "with each sentence with its number of parse trees.\n",
    "'''\n",
    "\n",
    "atis_sents = nltk.parse.util.extract_test_sentences(nltk.data.load('grammars/large_grammars/atis_sentences.txt'))"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 73,
   "metadata": {},
   "outputs": [
    {
     "data": {
      "text/plain": [
       "(['can',\n",
       "  'you',\n",
       "  'tell',\n",
       "  'me',\n",
       "  'about',\n",
       "  'the',\n",
       "  'flights',\n",
       "  'from',\n",
       "  'saint',\n",
       "  'petersburg',\n",
       "  'to',\n",
       "  'toronto',\n",
       "  'again',\n",
       "  '.'],\n",
       " 3)"
      ]
     },
     "execution_count": 73,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "'''\n",
    "Check some sample sentences in the ATIS data set\n",
    "'''\n",
    "\n",
    "atis_sents[15]"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "## Code and Implementation\n",
    "\n",
    "\n",
    "### Node class (for backpointers and parse trees):\n",
    "We will be using this Node class to instantiate each node for holding backpointers to the previous node. This will help us in creating the parse trees later on."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 14,
   "metadata": {},
   "outputs": [],
   "source": [
    "'''\n",
    "Node class definition\n",
    "'''\n",
    "class Node:\n",
    "\n",
    "    '''\n",
    "    Constructor method which initializes the root,\n",
    "    left child, right child, terminal and the status\n",
    "    of the node.\n",
    "    '''\n",
    "    def __init__(self, root, left, right, end):\n",
    "        self._root = root\n",
    "        self._left = left\n",
    "        self._right = right\n",
    "        self._terminal = end\n",
    "        self._status = True\n",
    "        if end == None:\n",
    "            self._status = False\n",
    "\n",
    "    '''\n",
    "    Class property root that returns the root of the node\n",
    "    '''\n",
    "    @property\n",
    "    def root(self):\n",
    "        return self._root\n",
    "\n",
    "    '''\n",
    "    Class property left that returns the left child of the node\n",
    "    '''\n",
    "    @property\n",
    "    def left(self):\n",
    "        return self._left\n",
    "\n",
    "    '''\n",
    "    Class property right that returns the right child of the node\n",
    "    '''\n",
    "    @property\n",
    "    def right(self):\n",
    "        return self._right\n",
    "\n",
    "    '''\n",
    "    Class property status that returns the status of the node\n",
    "    '''\n",
    "    @property\n",
    "    def status(self):\n",
    "        return self._status\n",
    "\n",
    "    '''\n",
    "    Class property terminal that returns the terminal of the node\n",
    "    '''\n",
    "    @property\n",
    "    def terminal(self):\n",
    "        return self._terminal"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "### Function getTrees(nodes_back):\n",
    "This function takes the **[0][n] cell of the backpointers** chart (returned from the CKY algorithm) as input. Now, using those backpointers, we backtrack and find the parse trees using the **getAllParseTrees(root, indent)** function recursively."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 15,
   "metadata": {},
   "outputs": [],
   "source": [
    "'''\n",
    "getTrees(back_nodes) definition:\n",
    "'''\n",
    "def getTrees(back_nodes):\n",
    "    \n",
    "    INDENT = 3\n",
    "    '''\n",
    "    Check boolean variable initially set to False\n",
    "    '''\n",
    "    check = False\n",
    "    \n",
    "    '''\n",
    "    Initialize the count of parse trees to 0\n",
    "    '''\n",
    "    countOfParseTrees = 0\n",
    "    \n",
    "    '''\n",
    "    For each of the nodes in the backpointer nodes,\n",
    "    we check if its a root node (SIGMA). If yes, then\n",
    "    we print it get all the parse trees for that recursively\n",
    "    using the getAllParseTrees(node) function and set the \n",
    "    check varuable to True.\n",
    "    '''\n",
    "    for node in back_nodes:\n",
    "        '''\n",
    "        Check if the node is root node (SIGMA)\n",
    "        '''\n",
    "        if node.root == grammar.start():\n",
    "            print(node.root)\n",
    "            '''\n",
    "            This will be a recursive call inside the function\n",
    "            '''\n",
    "            print(getAllParseTrees(node, INDENT))\n",
    "            print()\n",
    "            countOfParseTrees += 1\n",
    "            check = True\n",
    "\n",
    "    '''\n",
    "    If the check variable is still False, then the given\n",
    "    sentence is not in the given grammar.\n",
    "    '''\n",
    "    if not check:\n",
    "        print('The sentence is not in the grammar!')\n",
    "    return countOfParseTrees"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "### Function getAllParseTrees(root):\n",
    "This is the function which actually is called recursively inside its body. This takes root of the tree as input. We call this function **recursively** to print the parse trees for the given sentence according to the given grammar."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 16,
   "metadata": {},
   "outputs": [],
   "source": [
    "'''\n",
    "getAllParseTrees(root) definition:\n",
    "'''\n",
    "def getAllParseTrees(root, indent):\n",
    "    \n",
    "    '''\n",
    "    Printing the tree at a specific level where there are 2 nodes\n",
    "    '''\n",
    "    if root.status:\n",
    "        return '(' + str(root.root) + ' ' + root.terminal + ')'\n",
    "    \n",
    "    '''\n",
    "    Left subtree of the root input node\n",
    "    '''\n",
    "    new1 = indent + 2 + len(str(root.left.root))\n",
    "    \n",
    "    '''\n",
    "    Right subtree of the root input node\n",
    "    '''\n",
    "    new2 = indent + 2 + len(str(root.right.root))\n",
    "    \n",
    "    '''\n",
    "    This prints the left subtree of the root input node\n",
    "    '''\n",
    "    left = getAllParseTrees(root.left, new1)\n",
    "    \n",
    "    '''\n",
    "    This prints the right subtree of the root input node\n",
    "    '''\n",
    "    right = getAllParseTrees(root.right, new2)\n",
    "    \n",
    "    '''\n",
    "    Printing the tree at a specific level where there are 3 nodes\n",
    "    '''\n",
    "    return '(' + str(root.root) + ' ' + left + '\\n' + ' '*indent + right + ')'"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "### CKY algorithm / CYK algorithm\n",
    "This is the implementation of the CKY algorithm (sometimes also known as the CYK algorithm). All the details of the code have been specifically mentioned in the comments below."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 33,
   "metadata": {
    "scrolled": false
   },
   "outputs": [],
   "source": [
    "'''\n",
    "Function cky(grammar, sentence) definition\n",
    "- takes the CNF-form grammar and a sentence as inputs\n",
    "'''\n",
    "def cky(grammar, sentence):\n",
    "    \n",
    "    n = len(sentence)\n",
    "    \n",
    "    '''\n",
    "    Here we create the chart of POS tags and the chart of the backpointers\n",
    "    with n + 1 rows and columns each. Each of the cell is a set().\n",
    "    '''\n",
    "    chart = [[set() for i in range(n + 1)] for i in range(n + 1)]\n",
    "    nodes_back = [[set() for i in range(n + 1)] for j in range(n + 1)]\n",
    "    \n",
    "    '''\n",
    "    Here we initialize the diagonal elements of the chart with the single terminal \n",
    "    rules of the words in the sentence. Also, we initialize the diagonal backpointers\n",
    "    with the Non-Terminal of the rule.\n",
    "    '''\n",
    "    for i in range(n):\n",
    "        for production in grammar.productions(rhs=sentence[i]):\n",
    "                chart[i][i + 1].add(production.lhs())\n",
    "                nodes_back[i][i + 1].add(Node(production.lhs(), None, None, sentence[i]))\n",
    "\n",
    "    '''\n",
    "    This is the main implementation of the CKY/CYK algorithm.\n",
    "    \n",
    "    COPYRIGHT DISCLAIMER:\n",
    "    ---------------------\n",
    "    This implementation is inspired by Professor Koller's sample implementation \n",
    "    of the CKY algorithm from the lecture slides of University of Potsdam \n",
    "    which can be found here: http://www.ling.uni-potsdam.de/tcl/clt14/vorlesungen/05%20CKY-Parsing.pdf\n",
    "    \n",
    "    However, I have just taken inspiration of the code and not copied it. I have implemented the code myself.\n",
    "    I have also implemented the backpointers logic by myself completely.\n",
    "    '''\n",
    "    for width in range(2, n + 1):\n",
    "        for i in range(0, n - width + 1):\n",
    "            for j in range(1, width):\n",
    "                nts1, nts2 = chart[i][i + j], chart[i + j][i + width]\n",
    "                for nt1 in nts1:\n",
    "                    productions = grammar.productions(rhs=nt1)\n",
    "                    for production in productions:\n",
    "                        if production.rhs()[1] in nts2:\n",
    "                            chart[i][i + width].add(production.lhs())\n",
    "                            \n",
    "                            '''\n",
    "                            Here we update the corresponding backpointer chart for the corresponding \n",
    "                            update in the POS tag chart.\n",
    "                            '''\n",
    "                            for b in nodes_back[i][i + j]:\n",
    "                                for c in nodes_back[i + j][i + width]:\n",
    "                                    if b.root == production.rhs()[0] and c.root == production.rhs()[1]:\n",
    "                                        nodes_back[i][i + width].add(Node(production.lhs(), b, c, None))\n",
    "\n",
    "    print()\n",
    "    \n",
    "    '''\n",
    "    Here, the CKY algorithm just tells whether an input sentence\n",
    "    is in the given input grammar or not.\n",
    "    '''\n",
    "    START_SYMBOL = nltk.grammar.Nonterminal('SIGMA')\n",
    "    if START_SYMBOL in chart[0][n]:\n",
    "        print('The sentence is in the grammar!')\n",
    "    else:\n",
    "        print('The sentence is not in the grammar!')\n",
    "    print()\n",
    "    \n",
    "    '''\n",
    "    We return the chart as well as the node [0][n] of the backpointers chart which\n",
    "    we will use later on to print the parse trees.\n",
    "    '''\n",
    "    return chart, nodes_back[0][n]"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "### Testing the CKY algorithm\n",
    "We here test our implementation of the CKY algorithm with some sample sentences. Here are the sample sentences:\n",
    "\n",
    "\n",
    "1. **prices .**  - (proper sentence in the grammar)\n",
    "2. **the school is closed .** - (proper sentence but not in the grammar)\n",
    "3. **flights please .** - (proper sentence in the grammar)\n",
    "4. **closed flight is .** - (Ungrammatical sentence)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 18,
   "metadata": {},
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "SENTENCE: prices .\n",
      "\n",
      "The sentence is in the grammar!\n",
      "\n",
      "------------------------------------------------------------------------------------------------\n",
      "| set()| {VP_VBZ, pt207, AVPNP_NNS, SIGMA, VERB_VBZ, NOUN_NNS, NP_NNS}| {GNN, BID, KBW, BJJ, KAN, JIB, DPR, GRP, AQP, GLH, AJV, GIT, JIP, BHB, DAF, GUJ, DZA, DBA, GIJ, GBN, JJL, DOE, DON, GJF, GDR, DLW, BFZ, HYH, GOB, CZT, JJD, AYD, GLZ, GSH, HFD, KCD, GAF, CSP, JZK, HVH, EZX, AXJ, KAT, CTK, KCJ, GFD, KDT, CWW, JSB, UQ, GSN, BRR, ES, EEI, CXI, GXB, GYR, JIR, BOT, EEU, JZY, SI, KDH, HYJ, CXR, GHT, RY, JJP, BQH, GIN, IQ, GWH, GAP, DAL, GRB, CRF, KAL, GCR, GBB, DECL_VBZ, JKB, DZJ, DPF, RE, SIGMA, DRB, BQL, CZZ, NP_NNS, GCF, GFN, DXT, GBV, GXX, DDI, HFB, GJZ}\n",
      "------------------------------------------------------------------------------------------------\n",
      "| set()| set()| {pt_char_per}\n",
      "------------------------------------------------------------------------------------------------\n",
      "| set()| set()| set()\n",
      "------------------------------------------------------------------------------------------------\n",
      "\n",
      "\n",
      "SENTENCE: the school is closed .\n",
      "\n",
      "The sentence is not in the grammar!\n",
      "\n",
      "------------------------------------------------------------------------------------------------\n",
      "| set()| {the, AVP_RB, ADV_RB, ADJ_AT}| set()| set()| set()| set()\n",
      "------------------------------------------------------------------------------------------------\n",
      "| set()| set()| set()| set()| set()| set()\n",
      "------------------------------------------------------------------------------------------------\n",
      "| set()| set()| set()| {pt_verb_bez, VERB_BEZ}| set()| set()\n",
      "------------------------------------------------------------------------------------------------\n",
      "| set()| set()| set()| set()| set()| set()\n",
      "------------------------------------------------------------------------------------------------\n",
      "| set()| set()| set()| set()| set()| {pt_char_per}\n",
      "------------------------------------------------------------------------------------------------\n",
      "| set()| set()| set()| set()| set()| set()\n",
      "------------------------------------------------------------------------------------------------\n",
      "\n",
      "\n",
      "SENTENCE: flights please .\n",
      "\n",
      "The sentence is in the grammar!\n",
      "\n",
      "------------------------------------------------------------------------------------------------\n",
      "| set()| {VP_VBZ, pt207, AVPNP_NNS, SIGMA, VERB_VBZ, NOUN_NNS, NP_NNS}| {KGK, KQB, KQQ, JEJ, SIGMA, FWH, KGJ, NREL_VB, KQO, JHU, HYB, KQX, KDV, FPM, NP_NNS, ABE}| {GNN, BID, BJJ, JIB, DPR, GRP, AQP, GLH, AJV, GIT, EDG, GRG, JIP, BHB, DAF, GUJ, DZA, GIJ, DBA, GBN, ASK, JJL, DOE, DON, GJF, GDR, DEC, DLW, BFZ, GOB, CZT, BFE, JJD, AYD, GLZ, GSH, BLU, HFD, GAF, CSP, BIS, AXJ, GFD, JSB, DQR, GTG, UQ, DDW, DHR, GSN, BRR, EEI, BKD, GSA, GXB, GYR, JIR, BOT, EEU, SI, HWY, RY, JJP, GWA, BQH, GIN, GWH, GAP, GQU, DAL, CRF, GCR, EF, GBB, DECL_VBZ, JKB, DZJ, DPF, RE, BSW, SIGMA, DPU, DRB, BQL, CZZ, GCF, GFN, GBV, GXX, SN, DGB, GYF, DDI, HFB, GJZ}\n",
      "------------------------------------------------------------------------------------------------\n",
      "| set()| set()| {AVP_RB, INFCL_VB, VP_VB, please, ADV_RB, VERB_VB}| {GWB, EAN, CVD, GAB, GTZ, EDH, DEJ, AWT, DGL, BSX, JIQ, AVR, DIB, EY, GNX, HWZ, ARV, LU, GSB, DQA, DBV, QF, DGO, CUC, DZV, AUX, AOX, DDR, DDU, JJI, DDX, CYA, DGC, APZ, GNT, DQM, GRH, CFZ, BOX, DIE, GGV, DHS, AQH, ND, JJN, DDL, DHV, AZF, DEA, DFN, BWP, BG, DED, CYD, AUL, DKY, CXO, DLE, CQH, GAV, DAX, GHJ, IMPR_VB, AOP, DFW, GNJ, DQS, BYH, HIV, GJR, GVD, APV, DLN, BGD, GTH, AVB, DND, DXW, DQJ, GGJ, JJB, DSL, DQD, IEF, BFF, JJQ, JJU, DNS, DES, OH, CXX, BLV, DCN, DFQ, CSM, AVV, BIT, GYP, GTJ, MJ, GKX, GIF, AXN, CYG, GHP, ECG, DIT, BHJ, CXC, DAR, BGT, DUH, CXU, GGR, GXH, GTN, DQV, NN, FFI, AZB, DQG, DFT, GGL, EG, DFH, SIGMA, EAK, ASL, JIL, AYL, GLN, CWZ, DQP, DIZ, CYJ, GQV, OM, GKP, AUT, BEL, AVJ, ATV, DOB}\n",
      "------------------------------------------------------------------------------------------------\n",
      "| set()| set()| set()| {pt_char_per}\n",
      "------------------------------------------------------------------------------------------------\n",
      "| set()| set()| set()| set()\n",
      "------------------------------------------------------------------------------------------------\n",
      "\n",
      "\n",
      "SENTENCE: closed flight is .\n",
      "\n",
      "The sentence is not in the grammar!\n",
      "\n",
      "------------------------------------------------------------------------------------------------\n",
      "| set()| set()| set()| set()| set()\n",
      "------------------------------------------------------------------------------------------------\n",
      "| set()| set()| {NP_NN, flight, SIGMA, INFCL_VB, VP_VB, NOUN_NN, AVPNP_NN, VERB_VB}| {SIGMA, NREL_BEZ}| {GC, GVJ}\n",
      "------------------------------------------------------------------------------------------------\n",
      "| set()| set()| set()| {pt_verb_bez, VERB_BEZ}| set()\n",
      "------------------------------------------------------------------------------------------------\n",
      "| set()| set()| set()| set()| {pt_char_per}\n",
      "------------------------------------------------------------------------------------------------\n",
      "| set()| set()| set()| set()| set()\n",
      "------------------------------------------------------------------------------------------------\n",
      "\n",
      "\n"
     ]
    }
   ],
   "source": [
    "'''\n",
    "All the sample sentences\n",
    "'''\n",
    "sentences = [\n",
    "    ['prices', '.'],\n",
    "    ['the', 'school', 'is', 'closed', '.'],\n",
    "    ['flights', 'please', '.'],\n",
    "    ['closed', 'flight', 'is', '.']\n",
    "           ]\n",
    "'''\n",
    "Run the CKY algorithm for each of the sentence\n",
    "'''\n",
    "for sentence in sentences:\n",
    "    '''\n",
    "    Print the chart to check the output.\n",
    "    '''\n",
    "    print('SENTENCE:', ' '.join(sentence))\n",
    "    chart, backpointers = cky(grammar, sentence)\n",
    "    print('------------------------------------------------------------------------------------------------')\n",
    "    for i in range(len(chart)):\n",
    "        for j in range(len(chart[0])):\n",
    "            print('|', chart[i][j], end='')\n",
    "        print()\n",
    "        print('------------------------------------------------------------------------------------------------')\n",
    "    print()\n",
    "    print()"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "### Ungrammatical sentences\n",
    "\n",
    "Here are some ungrammatical sentences that we tried to feed to the CKY algorithm:\n",
    "\n",
    "\n",
    "1. **. prices** --> Result: **NO**\n",
    "2. **flights . please** --> Result: **YES** *(Surprising!)*\n",
    "3. **closed flight is .** --> Result: **NO**\n",
    "4. **are cancel flight .** --> Result: **NO**\n",
    "5. **cancel is flight** --> Result: **NO**"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 19,
   "metadata": {
    "scrolled": false
   },
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "SENTENCE: . prices\n",
      "\n",
      "The sentence is not in the grammar!\n",
      "\n",
      "------------------------------------------------------------------------------------------------\n",
      "| set()| {pt_char_per}| set()\n",
      "------------------------------------------------------------------------------------------------\n",
      "| set()| set()| {VP_VBZ, pt207, AVPNP_NNS, SIGMA, VERB_VBZ, NOUN_NNS, NP_NNS}\n",
      "------------------------------------------------------------------------------------------------\n",
      "| set()| set()| set()\n",
      "------------------------------------------------------------------------------------------------\n",
      "\n",
      "\n",
      "================================================================================================\n",
      "\n",
      "\n",
      "SENTENCE: flights . please\n",
      "\n",
      "The sentence is in the grammar!\n",
      "\n",
      "------------------------------------------------------------------------------------------------\n",
      "| set()| {VP_VBZ, pt207, AVPNP_NNS, SIGMA, VERB_VBZ, NOUN_NNS, NP_NNS}| {GNN, BID, KBW, BJJ, KAN, JIB, DPR, GRP, AQP, GLH, AJV, GIT, JIP, BHB, DAF, GUJ, DZA, DBA, GIJ, GBN, JJL, DOE, DON, GJF, GDR, DLW, BFZ, HYH, GOB, CZT, JJD, AYD, GLZ, GSH, HFD, KCD, GAF, CSP, JZK, HVH, EZX, AXJ, KAT, CTK, KCJ, GFD, KDT, CWW, JSB, UQ, GSN, BRR, ES, EEI, CXI, GXB, GYR, JIR, BOT, EEU, JZY, SI, KDH, HYJ, CXR, GHT, RY, JJP, BQH, GIN, IQ, GWH, GAP, DAL, GRB, CRF, KAL, GCR, GBB, DECL_VBZ, JKB, DZJ, DPF, RE, SIGMA, DRB, BQL, CZZ, NP_NNS, GCF, GFN, DXT, GBV, GXX, DDI, HFB, GJZ}| {KQB, JEJ, SIGMA, FWH, KGJ, NREL_VB, ABE, KQO}\n",
      "------------------------------------------------------------------------------------------------\n",
      "| set()| set()| {pt_char_per}| set()\n",
      "------------------------------------------------------------------------------------------------\n",
      "| set()| set()| set()| {AVP_RB, INFCL_VB, VP_VB, please, ADV_RB, VERB_VB}\n",
      "------------------------------------------------------------------------------------------------\n",
      "| set()| set()| set()| set()\n",
      "------------------------------------------------------------------------------------------------\n",
      "\n",
      "\n",
      "================================================================================================\n",
      "\n",
      "\n",
      "SENTENCE: closed flight is .\n",
      "\n",
      "The sentence is not in the grammar!\n",
      "\n",
      "------------------------------------------------------------------------------------------------\n",
      "| set()| set()| set()| set()| set()\n",
      "------------------------------------------------------------------------------------------------\n",
      "| set()| set()| {NP_NN, flight, SIGMA, INFCL_VB, VP_VB, NOUN_NN, AVPNP_NN, VERB_VB}| {SIGMA, NREL_BEZ}| {GC, GVJ}\n",
      "------------------------------------------------------------------------------------------------\n",
      "| set()| set()| set()| {pt_verb_bez, VERB_BEZ}| set()\n",
      "------------------------------------------------------------------------------------------------\n",
      "| set()| set()| set()| set()| {pt_char_per}\n",
      "------------------------------------------------------------------------------------------------\n",
      "| set()| set()| set()| set()| set()\n",
      "------------------------------------------------------------------------------------------------\n",
      "\n",
      "\n",
      "================================================================================================\n",
      "\n",
      "\n",
      "SENTENCE: are cancel flight .\n",
      "\n",
      "The sentence is not in the grammar!\n",
      "\n",
      "------------------------------------------------------------------------------------------------\n",
      "| set()| {pt_verb_ber}| set()| set()| set()\n",
      "------------------------------------------------------------------------------------------------\n",
      "| set()| set()| set()| set()| set()\n",
      "------------------------------------------------------------------------------------------------\n",
      "| set()| set()| set()| {NP_NN, flight, SIGMA, INFCL_VB, VP_VB, NOUN_NN, AVPNP_NN, VERB_VB}| {CVM, GDH, EBU, AWX, GJJ, DEJ, GFL, JXN, BRN, AWT, AYT, DGL, GGB, DPI, AVR, DIB, GNX, CZK, JVX, JR, AXR, GUR, HWZ, JYF, DFZ, GHV, CYP, JXV, GUH, DRW, DDF, AYP, DQA, DFE, GJD, DRZ, GLX, BHV, DOB, DGO, AUX, AOX, GEB, GIX, DDR, JJO, JJI, DDU, BCP, DDX, DGI, CYA, GCT, DPL, DGC, DQM, DOK, CZN, DPO, GIL, HEZ, GDP, GQX, DAU, AVF, GGF, GOV, BGL, GPV, DNA, DIE, JUO, AWP, GGV, AQH, DHS, CVP, DAC, ND, EYE, DXB, APN, JJN, DDL, EKO, DHV, AZF, GTP, GKR, DEA, DFN, GTX, DPC, DED, GOP, CYD, HPB, DZG, GCX, AQX, ALN, DBG, JXZ, GLF, BEH, GJH, CXO, DLE, HOR, CZQ, ALB, DKY, AZB, GVH, DXK, DAX, CZW, DRN, GHJ, EDB, IMPR_VB, CWK, GHX, BY, AOP, HPH, GVX, DFW, GNJ, SD, GMP, DQS, DDO, GWF, DSO, GJR, JKA, CTT, GSL, GOT, HIV, EME, BQP, DLN, BGD, JIC, JWB, GKV, AVB, DRT, DXW, DQJ, BKL, CPY, GGJ, DSL, GBT, NP_NN, DQD, GFT, CQN, HEX, GID, AXZ, BDV, JJQ, DNV, JIH, APR, JXI, JJU, JJM, DQY, GNL, DES, OH, DAI, CSY, DNS, CXX, DFQ, GEN, AVV, GUX, BJF, RJ, GKX, DIQ, DOT, BGX, GTF, AXB, AXN, CYG, CFV, CTW, GHP, BHJ, GJX, DTG, HMN, DDC, JVI, GKN, HNH, JVU, CXC, DAR, GIB, HOV, JIK, BGT, JVN, EA, DMR, CXU, GGR, DLT, GCP, GFB, AQT, GNZ, JYI, GTN, DQV, GXV, CVY, NN, FFI, ESZ, OR, DFT, DQG, CVJ, CZH, BHR, DEY, GCZ, FFF, GGL, GIH, GPB, DBP, SIGMA, GIR, GOR, HMV, DBY, DNJ, ANR, LP, AAA, DHJ, HKZ, JIL, NS, AYL, GLN, ARR, CWZ, DQP, GWZ, CYJ, ANF, GKP, AUT, AVJ, ATV, GRN}\n",
      "------------------------------------------------------------------------------------------------\n",
      "| set()| set()| set()| set()| {pt_char_per}\n",
      "------------------------------------------------------------------------------------------------\n",
      "| set()| set()| set()| set()| set()\n",
      "------------------------------------------------------------------------------------------------\n",
      "\n",
      "\n",
      "================================================================================================\n",
      "\n",
      "\n",
      "SENTENCE: cancel is flight\n",
      "\n",
      "The sentence is not in the grammar!\n",
      "\n",
      "------------------------------------------------------------------------------------------------\n",
      "| set()| set()| set()| set()\n",
      "------------------------------------------------------------------------------------------------\n",
      "| set()| set()| {pt_verb_bez, VERB_BEZ}| {KGC, KRQ, KPC}\n",
      "------------------------------------------------------------------------------------------------\n",
      "| set()| set()| set()| {NP_NN, flight, SIGMA, INFCL_VB, VP_VB, NOUN_NN, AVPNP_NN, VERB_VB}\n",
      "------------------------------------------------------------------------------------------------\n",
      "| set()| set()| set()| set()\n",
      "------------------------------------------------------------------------------------------------\n",
      "\n",
      "\n",
      "================================================================================================\n",
      "\n",
      "\n"
     ]
    }
   ],
   "source": [
    "'''\n",
    "All the sample sentences\n",
    "'''\n",
    "sentences = [\n",
    "    ['.', 'prices'],\n",
    "    ['flights', '.', 'please'],\n",
    "    ['closed', 'flight', 'is', '.'],\n",
    "    ['are', 'cancel', 'flight', '.'],\n",
    "    ['cancel', 'is', 'flight']\n",
    "           ]\n",
    "'''\n",
    "Run the CKY algorithm for each of the sentence\n",
    "'''\n",
    "for sentence in sentences:\n",
    "    '''\n",
    "    Print the chart to check the output.\n",
    "    '''\n",
    "    print('SENTENCE:', ' '.join(sentence))\n",
    "    chart, backpointers = cky(grammar, sentence)\n",
    "    print('------------------------------------------------------------------------------------------------')\n",
    "    for i in range(len(chart)):\n",
    "        for j in range(len(chart[0])):\n",
    "            print('|', chart[i][j], end='')\n",
    "        print()\n",
    "        print('------------------------------------------------------------------------------------------------')\n",
    "    print('\\n\\n================================================================================================\\n\\n')"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "### Test the parse tree printing algorithm\n",
    "\n",
    "\n",
    "Sample sentence: **prices .**\n",
    "\n",
    "\n",
    "Number of total parse trees: 2"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 20,
   "metadata": {},
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "\n",
      "The sentence is in the grammar!\n",
      "\n",
      "SIGMA\n",
      "(SIGMA (NOUN_NNS prices)\n",
      "   (pt_char_per .))\n",
      "\n",
      "SIGMA\n",
      "(SIGMA (VERB_VBZ prices)\n",
      "   (pt_char_per .))\n",
      "\n",
      "Number of total parse trees:  2\n"
     ]
    }
   ],
   "source": [
    "sample_sentence = ['prices', '.']\n",
    "chart, backpointers = cky(grammar, sample_sentence)\n",
    "countOfParseTrees = getTrees(backpointers)\n",
    "\n",
    "print('Number of total parse trees: ', countOfParseTrees)"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "### Some sentences with less than 5 parse trees:\n",
    "\n",
    "We are going to use 5 sentences which have less than 5 total parse trees according to the ATIS CNF Grammar. The sentences are as follows:\n",
    "\n",
    "\n",
    "1. **what is the fare .** --> Number of parse trees: 2\n",
    "2. **can you tell me about the flights from saint petersberg to toronto again .** --> Number of parse trees: 3\n",
    "3. **show availability .** --> Number of parse trees: 3\n",
    "4. **show the flights .** --> Number of parse trees: 2\n",
    "5. **what is the cheapest ticket from memphis to miami .** --> Number of parse trees: 5"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 21,
   "metadata": {},
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "SENTENCE:  what is the fare .\n",
      "\n",
      "The sentence is in the grammar!\n",
      "\n",
      "SIGMA\n",
      "(SIGMA (NP_DT what)\n",
      "   (GDO (VERB_BEZ is)\n",
      "        (GDP (NP_NN (ADJ_AT the)\n",
      "                    (NOUN_NN fare))\n",
      "             (pt_char_per .))))\n",
      "\n",
      "SIGMA\n",
      "(SIGMA (NP_DT what)\n",
      "   (KGC (VERB_BEZ is)\n",
      "        (NP_NN (ADJ_AT the)\n",
      "               (JUO (NOUN_NN fare)\n",
      "                    (pt_char_per .)))))\n",
      "\n",
      "Number of total parse trees:  2\n",
      "\n",
      "\n",
      "=======================================================\n",
      "\n",
      "\n",
      "SENTENCE:  can you tell me about the flights from saint petersburg to toronto again .\n",
      "\n",
      "The sentence is in the grammar!\n",
      "\n",
      "SIGMA\n",
      "(SIGMA (VERB_MD can)\n",
      "   (BJG (NP_PPSS you)\n",
      "        (BJH (VERB_VB tell)\n",
      "             (BJI (NP_PPO me)\n",
      "                  (BJJ (NP_NNS (AVP_RB (AVP_RB about)\n",
      "                                       (ADV_RB the))\n",
      "                               (KAS (NOUN_NNS flights)\n",
      "                                    (PP_NP (PREP_IN from)\n",
      "                                           (ITY (NP_NP saint)\n",
      "                                                (ITZ (NOUN_NP petersburg)\n",
      "                                                     (PP_NP (PREP_IN to)\n",
      "                                                            (KKY (NOUN_NP toronto)\n",
      "                                                                 (AVP_RB again))))))))\n",
      "                       (pt_char_per .))))))\n",
      "\n",
      "SIGMA\n",
      "(SIGMA (VERB_MD can)\n",
      "   (BJG (NP_PPSS you)\n",
      "        (BJH (VERB_VB tell)\n",
      "             (BJI (NP_PPO me)\n",
      "                  (BJJ (NP_NNS (AVP_RB (AVP_RB about)\n",
      "                                       (ADV_RB the))\n",
      "                               (KAS (NOUN_NNS flights)\n",
      "                                    (PP_NP (PREP_IN from)\n",
      "                                           (KLJ (NOUN_NP (saint saint)\n",
      "                                                         (petersburg petersburg))\n",
      "                                                (PP_NP (PREP_IN to)\n",
      "                                                       (KKY (NOUN_NP toronto)\n",
      "                                                            (AVP_RB again)))))))\n",
      "                       (pt_char_per .))))))\n",
      "\n",
      "SIGMA\n",
      "(SIGMA (VERB_MD can)\n",
      "   (BJG (NP_PPSS you)\n",
      "        (BJH (VERB_VB tell)\n",
      "             (BJI (NP_PPO me)\n",
      "                  (BJJ (NP_NNS (AVP_RB (AVP_RB about)\n",
      "                                       (ADV_RB the))\n",
      "                               (KAS (NOUN_NNS flights)\n",
      "                                    (PP_NP (PREP_IN from)\n",
      "                                           (KLD (NOUN_NP saint)\n",
      "                                                (NAPPOS_NP (NOUN_NP petersburg)\n",
      "                                                           (PP_NP (PREP_IN to)\n",
      "                                                                  (KKY (NOUN_NP toronto)\n",
      "                                                                       (AVP_RB again))))))))\n",
      "                       (pt_char_per .))))))\n",
      "\n",
      "Number of total parse trees:  3\n",
      "\n",
      "\n",
      "=======================================================\n",
      "\n",
      "\n",
      "SENTENCE:  show availability .\n",
      "\n",
      "The sentence is in the grammar!\n",
      "\n",
      "SIGMA\n",
      "(SIGMA (NOUN_NN show)\n",
      "   (JWB (AVPNP_NN availability)\n",
      "        (pt_char_per .)))\n",
      "\n",
      "SIGMA\n",
      "(SIGMA (NP_NN show)\n",
      "   (JXI (NOUN_NN availability)\n",
      "        (pt_char_per .)))\n",
      "\n",
      "SIGMA\n",
      "(SIGMA (VERB_VB show)\n",
      "   (JKA (NP_NN availability)\n",
      "        (pt_char_per .)))\n",
      "\n",
      "Number of total parse trees:  3\n",
      "\n",
      "\n",
      "=======================================================\n",
      "\n",
      "\n",
      "SENTENCE:  show the flights .\n",
      "\n",
      "The sentence is in the grammar!\n",
      "\n",
      "SIGMA\n",
      "(SIGMA (VERB_VB show)\n",
      "   (JKB (NP_NNS (ADJ_AT the)\n",
      "                (NOUN_NNS flights))\n",
      "        (pt_char_per .)))\n",
      "\n",
      "SIGMA\n",
      "(SIGMA (VERB_VB show)\n",
      "   (JKB (NP_NNS (AVP_RB the)\n",
      "                (NOUN_NNS flights))\n",
      "        (pt_char_per .)))\n",
      "\n",
      "Number of total parse trees:  2\n",
      "\n",
      "\n",
      "=======================================================\n",
      "\n",
      "\n",
      "SENTENCE:  what is the cheapest ticket from memphis to miami .\n",
      "\n",
      "The sentence is in the grammar!\n",
      "\n",
      "SIGMA\n",
      "(SIGMA (NP_DT what)\n",
      "   (CUM (VERB_BEZ is)\n",
      "        (CUN (NP_NN (ADJ_AT the)\n",
      "                    (HIE (AJP_JJT cheapest)\n",
      "                         (HIF (NOUN_NN ticket)\n",
      "                              (PP_NP (PREP_IN from)\n",
      "                                     (NOUN_NP memphis)))))\n",
      "             (CUO (PP_NPS (PREP_IN to)\n",
      "                          (NOUN_NPS miami))\n",
      "                  (pt_char_per .)))))\n",
      "\n",
      "SIGMA\n",
      "(SIGMA (NP_DT what)\n",
      "   (GDO (VERB_BEZ is)\n",
      "        (GDP (NP_NN (ADJ_AT the)\n",
      "                    (HIE (AJP_JJT cheapest)\n",
      "                         (HIF (NOUN_NN ticket)\n",
      "                              (PP_NP (PREP_IN from)\n",
      "                                     (KLK (NOUN_NP memphis)\n",
      "                                          (PP_NPS (PREP_IN to)\n",
      "                                                  (NOUN_NPS miami)))))))\n",
      "             (pt_char_per .))))\n",
      "\n",
      "SIGMA\n",
      "(SIGMA (NP_DT what)\n",
      "   (GDS (VERB_BEZ is)\n",
      "        (GDT (NP_NP (NP_NN (ADJ_AT the)\n",
      "                           (HIG (AJP_JJT cheapest)\n",
      "                                (HIH (NOUN_NN ticket)\n",
      "                                     (PREP_IN from))))\n",
      "                    (KEZ (NOUN_NP memphis)\n",
      "                         (PP_NPS (PREP_IN to)\n",
      "                                 (NOUN_NPS miami))))\n",
      "             (pt_char_per .))))\n",
      "\n",
      "SIGMA\n",
      "(SIGMA (NP_DT what)\n",
      "   (CUJ (VERB_BEZ is)\n",
      "        (CUK (NP_NN (ADJ_AT the)\n",
      "                    (JTT (AJP_JJT cheapest)\n",
      "                         (NOUN_NN ticket)))\n",
      "             (CUL (PP_NP (PREP_IN from)\n",
      "                         (KLK (NOUN_NP memphis)\n",
      "                              (PP_NPS (PREP_IN to)\n",
      "                                      (NOUN_NPS miami))))\n",
      "                  (pt_char_per .)))))\n",
      "\n",
      "SIGMA\n",
      "(SIGMA (NP_DT what)\n",
      "   (CUM (VERB_BEZ is)\n",
      "        (CUN (NP_NN (ADJ_AT the)\n",
      "                    (JTT (AJP_JJT cheapest)\n",
      "                         (NOUN_NN ticket)))\n",
      "             (CUO (PP_NPS (PREP_IN from)\n",
      "                          (KMH (NP_NP (NOUN_NP memphis)\n",
      "                                      (PREP_IN to))\n",
      "                               (NOUN_NPS miami)))\n",
      "                  (pt_char_per .)))))\n",
      "\n",
      "Number of total parse trees:  5\n",
      "\n",
      "\n",
      "=======================================================\n",
      "\n",
      "\n"
     ]
    }
   ],
   "source": [
    "'''\n",
    "All the sample sentences\n",
    "'''\n",
    "sentences = [\n",
    "    ['what', 'is', 'the', 'fare', '.'],\n",
    "    ['can', 'you', 'tell', 'me', 'about', 'the', 'flights', 'from', 'saint', 'petersburg', 'to', 'toronto', 'again', '.'],\n",
    "    ['show', 'availability', '.'],\n",
    "    ['show', 'the', 'flights', '.'],\n",
    "    ['what', 'is', 'the', 'cheapest', 'ticket', 'from', 'memphis', 'to', 'miami', '.']\n",
    "           ]\n",
    "'''\n",
    "Run the CKY algorithm for each of the sentence\n",
    "'''\n",
    "for sentence in sentences:\n",
    "    print('SENTENCE: ', ' '.join(sentence))\n",
    "    chart, backpointers = cky(grammar, sentence)\n",
    "    countOfParseTrees = getTrees(backpointers)\n",
    "    print('Number of total parse trees: ', countOfParseTrees)\n",
    "    print('\\n\\n=======================================================\\n\\n')\n",
    "    "
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "### Running the code on all the 98 ATIS test sentences:"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 22,
   "metadata": {},
   "outputs": [],
   "source": [
    "import pandas as pd\n",
    "sentences, countOfTrees = [], []"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 74,
   "metadata": {},
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "\n",
      "The sentence is in the grammar!\n",
      "\n",
      "SIGMA\n",
      "(SIGMA (VERB_MD can)\n",
      "   (BJG (NP_PPSS you)\n",
      "        (BJH (VERB_VB tell)\n",
      "             (BJI (NP_PPO me)\n",
      "                  (BJJ (NP_NNS (AVP_RB (AVP_RB about)\n",
      "                                       (ADV_RB the))\n",
      "                               (KAS (NOUN_NNS flights)\n",
      "                                    (PP_NP (PREP_IN from)\n",
      "                                           (KLJ (NOUN_NP (saint saint)\n",
      "                                                         (petersburg petersburg))\n",
      "                                                (PP_NP (PREP_IN to)\n",
      "                                                       (KKY (NOUN_NP toronto)\n",
      "                                                            (AVP_RB again)))))))\n",
      "                       (pt_char_per .))))))\n",
      "\n",
      "SIGMA\n",
      "(SIGMA (VERB_MD can)\n",
      "   (BJG (NP_PPSS you)\n",
      "        (BJH (VERB_VB tell)\n",
      "             (BJI (NP_PPO me)\n",
      "                  (BJJ (NP_NNS (AVP_RB (AVP_RB about)\n",
      "                                       (ADV_RB the))\n",
      "                               (KAS (NOUN_NNS flights)\n",
      "                                    (PP_NP (PREP_IN from)\n",
      "                                           (KLD (NOUN_NP saint)\n",
      "                                                (NAPPOS_NP (NOUN_NP petersburg)\n",
      "                                                           (PP_NP (PREP_IN to)\n",
      "                                                                  (KKY (NOUN_NP toronto)\n",
      "                                                                       (AVP_RB again))))))))\n",
      "                       (pt_char_per .))))))\n",
      "\n",
      "SIGMA\n",
      "(SIGMA (VERB_MD can)\n",
      "   (BJG (NP_PPSS you)\n",
      "        (BJH (VERB_VB tell)\n",
      "             (BJI (NP_PPO me)\n",
      "                  (BJJ (NP_NNS (AVP_RB (AVP_RB about)\n",
      "                                       (ADV_RB the))\n",
      "                               (KAS (NOUN_NNS flights)\n",
      "                                    (PP_NP (PREP_IN from)\n",
      "                                           (ITY (NP_NP saint)\n",
      "                                                (ITZ (NOUN_NP petersburg)\n",
      "                                                     (PP_NP (PREP_IN to)\n",
      "                                                            (KKY (NOUN_NP toronto)\n",
      "                                                                 (AVP_RB again))))))))\n",
      "                       (pt_char_per .))))))\n",
      "\n"
     ]
    }
   ],
   "source": [
    "for sentence in atis_sents[15:16]:      \n",
    "    \n",
    "    complete_sentence = ' '.join(sentence[0])\n",
    "    sentences.append(complete_sentence)\n",
    "    \n",
    "    chart, backpointers = cky(grammar, sentence[0])\n",
    "    countOfParseTrees = getTrees(backpointers)\n",
    "    countOfTrees.append(countOfParseTrees)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 57,
   "metadata": {},
   "outputs": [
    {
     "data": {
      "text/html": [
       "<div>\n",
       "<style scoped>\n",
       "    .dataframe tbody tr th:only-of-type {\n",
       "        vertical-align: middle;\n",
       "    }\n",
       "\n",
       "    .dataframe tbody tr th {\n",
       "        vertical-align: top;\n",
       "    }\n",
       "\n",
       "    .dataframe thead th {\n",
       "        text-align: right;\n",
       "    }\n",
       "</style>\n",
       "<table border=\"1\" class=\"dataframe\">\n",
       "  <thead>\n",
       "    <tr style=\"text-align: right;\">\n",
       "      <th></th>\n",
       "      <th>Sentence</th>\n",
       "      <th># Parse Trees</th>\n",
       "    </tr>\n",
       "  </thead>\n",
       "  <tbody>\n",
       "    <tr>\n",
       "      <th>0</th>\n",
       "      <td>does united flight four seven four slash fourt...</td>\n",
       "      <td>0</td>\n",
       "    </tr>\n",
       "    <tr>\n",
       "      <th>1</th>\n",
       "      <td>what kind of aircraft is american 's flight fi...</td>\n",
       "      <td>0</td>\n",
       "    </tr>\n",
       "    <tr>\n",
       "      <th>2</th>\n",
       "      <td>show me flights from detroit to san diego on t...</td>\n",
       "      <td>0</td>\n",
       "    </tr>\n",
       "    <tr>\n",
       "      <th>3</th>\n",
       "      <td>i 'd like to fly from indianapolis to houston ...</td>\n",
       "      <td>0</td>\n",
       "    </tr>\n",
       "    <tr>\n",
       "      <th>4</th>\n",
       "      <td>how much does first class on that flight cost ...</td>\n",
       "      <td>54</td>\n",
       "    </tr>\n",
       "    <tr>\n",
       "      <th>5</th>\n",
       "      <td>can you tell me about the flights from saint p...</td>\n",
       "      <td>3</td>\n",
       "    </tr>\n",
       "    <tr>\n",
       "      <th>6</th>\n",
       "      <td>i would like to find a flight from charlotte t...</td>\n",
       "      <td>55</td>\n",
       "    </tr>\n",
       "    <tr>\n",
       "      <th>7</th>\n",
       "      <td>what if i wanted to leave on may fifth .</td>\n",
       "      <td>0</td>\n",
       "    </tr>\n",
       "    <tr>\n",
       "      <th>8</th>\n",
       "      <td>i would like to leave on thursday morning may ...</td>\n",
       "      <td>0</td>\n",
       "    </tr>\n",
       "    <tr>\n",
       "      <th>9</th>\n",
       "      <td>how far is it from the airport to the city .</td>\n",
       "      <td>1</td>\n",
       "    </tr>\n",
       "    <tr>\n",
       "      <th>10</th>\n",
       "      <td>can i have the fare .</td>\n",
       "      <td>1</td>\n",
       "    </tr>\n",
       "    <tr>\n",
       "      <th>11</th>\n",
       "      <td>show availability .</td>\n",
       "      <td>3</td>\n",
       "    </tr>\n",
       "    <tr>\n",
       "      <th>12</th>\n",
       "      <td>show me northwest flights to detroit .</td>\n",
       "      <td>17</td>\n",
       "    </tr>\n",
       "    <tr>\n",
       "      <th>13</th>\n",
       "      <td>show the flights .</td>\n",
       "      <td>2</td>\n",
       "    </tr>\n",
       "    <tr>\n",
       "      <th>14</th>\n",
       "      <td>prices .</td>\n",
       "      <td>2</td>\n",
       "    </tr>\n",
       "    <tr>\n",
       "      <th>15</th>\n",
       "      <td>list those flights that stop over in salt lake...</td>\n",
       "      <td>11</td>\n",
       "    </tr>\n",
       "    <tr>\n",
       "      <th>16</th>\n",
       "      <td>list these economy fares .</td>\n",
       "      <td>0</td>\n",
       "    </tr>\n",
       "    <tr>\n",
       "      <th>17</th>\n",
       "      <td>what is e w r .</td>\n",
       "      <td>1</td>\n",
       "    </tr>\n",
       "    <tr>\n",
       "      <th>18</th>\n",
       "      <td>list these city destinations .</td>\n",
       "      <td>0</td>\n",
       "    </tr>\n",
       "    <tr>\n",
       "      <th>19</th>\n",
       "      <td>please list the flights leaving newark stoppin...</td>\n",
       "      <td>44</td>\n",
       "    </tr>\n",
       "    <tr>\n",
       "      <th>20</th>\n",
       "      <td>what area does canadian airlines international...</td>\n",
       "      <td>0</td>\n",
       "    </tr>\n",
       "    <tr>\n",
       "      <th>21</th>\n",
       "      <td>i want to leave before noon .</td>\n",
       "      <td>1</td>\n",
       "    </tr>\n",
       "    <tr>\n",
       "      <th>22</th>\n",
       "      <td>how long is the stop in dallas on flight d l n...</td>\n",
       "      <td>6</td>\n",
       "    </tr>\n",
       "    <tr>\n",
       "      <th>23</th>\n",
       "      <td>i want first class on flight one one one nine .</td>\n",
       "      <td>15</td>\n",
       "    </tr>\n",
       "    <tr>\n",
       "      <th>24</th>\n",
       "      <td>count the number of flights between nine a.m. ...</td>\n",
       "      <td>0</td>\n",
       "    </tr>\n",
       "    <tr>\n",
       "      <th>25</th>\n",
       "      <td>please give me the number of flights that depa...</td>\n",
       "      <td>0</td>\n",
       "    </tr>\n",
       "    <tr>\n",
       "      <th>26</th>\n",
       "      <td>how many flights leave from lester b pearson i...</td>\n",
       "      <td>0</td>\n",
       "    </tr>\n",
       "    <tr>\n",
       "      <th>27</th>\n",
       "      <td>i need the shortest evening flight from tampa ...</td>\n",
       "      <td>32</td>\n",
       "    </tr>\n",
       "    <tr>\n",
       "      <th>28</th>\n",
       "      <td>how far is the airport from new york 's la gua...</td>\n",
       "      <td>7</td>\n",
       "    </tr>\n",
       "    <tr>\n",
       "      <th>29</th>\n",
       "      <td>how much is the fare limousine san francisco t...</td>\n",
       "      <td>8</td>\n",
       "    </tr>\n",
       "  </tbody>\n",
       "</table>\n",
       "</div>"
      ],
      "text/plain": [
       "                                             Sentence  # Parse Trees\n",
       "0   does united flight four seven four slash fourt...              0\n",
       "1   what kind of aircraft is american 's flight fi...              0\n",
       "2   show me flights from detroit to san diego on t...              0\n",
       "3   i 'd like to fly from indianapolis to houston ...              0\n",
       "4   how much does first class on that flight cost ...             54\n",
       "5   can you tell me about the flights from saint p...              3\n",
       "6   i would like to find a flight from charlotte t...             55\n",
       "7            what if i wanted to leave on may fifth .              0\n",
       "8   i would like to leave on thursday morning may ...              0\n",
       "9        how far is it from the airport to the city .              1\n",
       "10                              can i have the fare .              1\n",
       "11                                show availability .              3\n",
       "12             show me northwest flights to detroit .             17\n",
       "13                                 show the flights .              2\n",
       "14                                           prices .              2\n",
       "15  list those flights that stop over in salt lake...             11\n",
       "16                         list these economy fares .              0\n",
       "17                                    what is e w r .              1\n",
       "18                     list these city destinations .              0\n",
       "19  please list the flights leaving newark stoppin...             44\n",
       "20  what area does canadian airlines international...              0\n",
       "21                      i want to leave before noon .              1\n",
       "22  how long is the stop in dallas on flight d l n...              6\n",
       "23    i want first class on flight one one one nine .             15\n",
       "24  count the number of flights between nine a.m. ...              0\n",
       "25  please give me the number of flights that depa...              0\n",
       "26  how many flights leave from lester b pearson i...              0\n",
       "27  i need the shortest evening flight from tampa ...             32\n",
       "28  how far is the airport from new york 's la gua...              7\n",
       "29  how much is the fare limousine san francisco t...              8"
      ]
     },
     "execution_count": 57,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "data = {'Sentence': sentences, '# Parse Trees': countOfTrees}\n",
    "final_table = pd.DataFrame(data=data)\n",
    "final_table"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 64,
   "metadata": {},
   "outputs": [],
   "source": [
    "writer = pd.ExcelWriter('output.xlsx')\n",
    "final_table.to_excel(writer,'Sheet1')\n",
    "writer.save()"
   ]
  }
 ],
 "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.6.5"
  }
 },
 "nbformat": 4,
 "nbformat_minor": 2
}