CYK_Parser.ipynb

{
 "cells": [
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "### Author\n",
    "Iker García Ferrero\n",
    "\n",
    "Github: https://github.com/ikergarcia1996\n",
    "\n",
    "# Example Of Use\n",
    " \n",
    " \n",
    "```\n",
    "# Initialize the grammar and read the rules from a file\n",
    "g = Grammar('example_grammar1.txt')\n",
    "\n",
    "# Parse a sentence\n",
    "g.parse('astronomers saw stars with ears')\n",
    "\n",
    "# Print the table used for parsing the sentence\n",
    "g.print_parse_table()\n",
    "\n",
    "# Get the list of trees generated for the sentence\n",
    "trees = g.get_trees()\n",
    "\n",
    "# Get the result of the production rule, VP, S, NP... \n",
    "p = trees[0].get_type\n",
    "\n",
    "# Get the left child of the production rule\n",
    "l = trees[0].get_left\n",
    "\n",
    "# Get the right child of the production rule\n",
    "d = trees[0].get_right\n",
    "```\n",
    " \n",
    "\n",
    "\n",
    " ## Expected output\n",
    "\n",
    " \n",
    "```\n",
    "Grammar file readed succesfully. Rules readed:\n",
    "S --> NP VP\n",
    "PP --> P NP\n",
    "VP --> V NP\n",
    "VP --> VP PP\n",
    "NP --> NP PP\n",
    "NP --> astronomers\n",
    "NP --> ears\n",
    "NP --> saw\n",
    "V --> saw\n",
    "NP --> telescope\n",
    "NP --> stars\n",
    "P --> with\n",
    "\n",
    "Applied Rule: VP[2,2] --> V[1,2] NP[1,3]\n",
    "Applied Rule: PP[2,4] --> P[1,4] NP[1,5]\n",
    "Applied Rule: S[3,1] --> NP[1,1] VP[2,2]\n",
    "Applied Rule: NP[3,3] --> NP[1,3] PP[2,4]\n",
    "Applied Rule: VP[4,2] --> V[1,2] NP[3,3]\n",
    "Applied Rule: VP[4,2] --> VP[2,2] PP[2,4]\n",
    "Applied Rule: S[5,1] --> NP[1,1] VP[4,2]\n",
    "Applied Rule: S[5,1] --> NP[1,1] VP[4,2]\n",
    "----------------------------------------\n",
    "The sentence IS accepted in the language\n",
    "Number of possible trees: 2\n",
    "----------------------------------------\n",
    "\n",
    "-----------  ------------  ------  ------  ------\n",
    "['S', 'S']\n",
    "[]           ['VP', 'VP']\n",
    "['S']        []            ['NP']\n",
    "[]           ['VP']        []      ['PP']\n",
    "['NP']       ['NP', 'V']   ['NP']  ['P']   ['NP']\n",
    "astronomers  saw           stars   with    ears\n",
    "-----------  ------------  ------  ------  ------\n",
    "```\n",
    "\n",
    "\n",
    "# Example of grammar file\n",
    "```\n",
    "S -> NP VP\n",
    "PP -> P NP\n",
    "VP -> V NP\n",
    "VP -> VP PP\n",
    "NP-> NP PP\n",
    "NP -> astronomers\n",
    "NP -> ears\n",
    "NP -> saw\n",
    "NP-> telescope\n",
    "NP -> stars\n",
    "P -> with\n",
    "V -> saw\n",
    "```\n",
    "\n",
    "\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 7,
   "metadata": {},
   "outputs": [],
   "source": [
    "class Dictlist(dict):\n",
    "    \n",
    "    def __setitem__(self, key, value):\n",
    "        try:\n",
    "            self[key]\n",
    "        except KeyError:\n",
    "            super(Dictlist, self).__setitem__(key, [])\n",
    "        self[key].append(value)\n",
    "\n",
    "\n",
    "class production_rule(object):\n",
    "    \n",
    "    result = None\n",
    "    p1 = None\n",
    "    p2 = None\n",
    "    \n",
    "    #Parameters:\n",
    "    #   Result: String\n",
    "    #   p1: Production rule (left child of the production rule)\n",
    "    #   p2: Production rule (right child of the production rule)\n",
    "    def __init__(self,result,p1,p2):\n",
    "        self.result = result\n",
    "        self.p1 = p1\n",
    "        self.p2 = p2\n",
    "    \n",
    "    #Returns the result of the production rule, VP, S, NP... \n",
    "    @property\n",
    "    def get_type(self):\n",
    "        return self.result\n",
    "    \n",
    "    #Returns the left child of the production rule\n",
    "    @property\n",
    "    def get_left(self):\n",
    "        return self.p1\n",
    "    \n",
    "    #Returns the right child of the production rule\n",
    "    @property\n",
    "    def get_right(self):\n",
    "        return self.p2\n",
    "\n",
    "class Cell(object):\n",
    "    productions = []\n",
    "    \n",
    "    \n",
    "    #Parameters:\n",
    "    #   Productions: List of production rules\n",
    "    \n",
    "    def __init__(self, productions=None):\n",
    "        if productions is None:\n",
    "            self.productions = []\n",
    "        else:\n",
    "            self.productions = productions\n",
    "            \n",
    "    def add_production(self, result,p1,p2):\n",
    "        self.productions.append(production_rule(result,p1,p2))\n",
    "    \n",
    "    def set_productions(self, p):\n",
    "        self.productions = p\n",
    "    \n",
    "    @property\n",
    "    def get_types(self):\n",
    "        types = []\n",
    "        for p in self.productions:\n",
    "            types.append(p.result)\n",
    "        return types\n",
    "    @property\n",
    "    def get_rules(self):       \n",
    "        return self.productions\n",
    "\n",
    "\n",
    "class Grammar(object):\n",
    "    \n",
    "    grammar_rules = Dictlist()\n",
    "    parse_table = None\n",
    "    length = 0\n",
    "    tokens = []\n",
    "    number_of_trees = 0\n",
    "    \n",
    "    #Parameters:\n",
    "    #   Filename: file containing a grammar\n",
    "    \n",
    "    def __init__(self, filename):\n",
    "        self.grammar_rules = Dictlist()\n",
    "        self.parse_table = None\n",
    "        self.length = 0\n",
    "        for line in open(filename):\n",
    "            a, b = line.split(\"->\")\n",
    "            self.grammar_rules[b.rstrip().strip()]=a.rstrip().strip()\n",
    "        \n",
    "        if len(self.grammar_rules) == 0:\n",
    "            raise ValueError(\"No rules found in the grammar file\")\n",
    "        print('')\n",
    "        print('Grammar file readed succesfully. Rules readed:')\n",
    "        self.print_rules()\n",
    "        print('')\n",
    "    \n",
    "    #Print the production rules in the grammar\n",
    "    \n",
    "    def print_rules(self):\n",
    "        for r in self.grammar_rules:\n",
    "            for p in self.grammar_rules[r]:\n",
    "                print(str(p) + ' --> ' + str(r))\n",
    "        \n",
    "    def apply_rules(self,t):\n",
    "        try:\n",
    "            return self.grammar_rules[t]\n",
    "        except KeyError as r:\n",
    "            return None\n",
    "            \n",
    "    #Parse a sentence (string) with the CYK algorithm   \n",
    "    def parse(self,sentence):\n",
    "        self.number_of_trees = 0\n",
    "        self.tokens = sentence.split()\n",
    "        self.length = len(self.tokens)\n",
    "        if self.length < 1:\n",
    "            raise ValueError(\"The sentence could no be read\")\n",
    "        self.parse_table = [ [Cell() for x in range(self.length - y)] for y in range(self.length) ]\n",
    "        \n",
    "         #Process the first line\n",
    "        \n",
    "        for x, t in enumerate(self.tokens):\n",
    "            \n",
    "            r = self.apply_rules(t)\n",
    "            if r == None:\n",
    "                raise ValueError(\"The word \" + str(t) + \" is not in the grammar\")\n",
    "            else:\n",
    "                for w in r: \n",
    "                    self.parse_table[0][x].add_production(w,production_rule(t,None,None),None)\n",
    "        \n",
    "        \n",
    "        #Run CYK-Parser\n",
    "        \n",
    "        \n",
    "        for l in range(2,self.length+1):\n",
    "            for s in range(1,self.length-l+2):\n",
    "                for p in range(1,l-1+1):\n",
    "                    \n",
    "                    t1 = self.parse_table[p-1][s-1].get_rules\n",
    "                    t2 = self.parse_table[l-p-1][s+p-1].get_rules\n",
    "                            \n",
    "                    for a in t1:\n",
    "                        for b in t2:\n",
    "                            r = self.apply_rules(str(a.get_type) + \" \" + str(b.get_type))\n",
    "                                    \n",
    "                            if r is not None:\n",
    "                                for w in r:\n",
    "                                    print('Applied Rule: ' + str(w) + '[' + str(l) + ',' + str(s) + ']' + ' --> ' + str(a.get_type) + '[' + str(p) + ',' + str(s) + ']' + ' ' + str(b.get_type)+ '[' + str(l-p) + ',' + str(s+p) + ']')\n",
    "                                    self.parse_table[l-1][s-1].add_production(w,a,b)\n",
    "                               \n",
    "        self.number_of_trees = len(self.parse_table[self.length-1][0].get_types)\n",
    "        if  self.number_of_trees > 0:\n",
    "            print(\"----------------------------------------\")\n",
    "            print('The sentence IS accepted in the language')\n",
    "            print('Number of possible trees: ' + str(self.number_of_trees))\n",
    "            print(\"----------------------------------------\")\n",
    "        else:\n",
    "            print(\"--------------------------------------------\")\n",
    "            print('The sentence IS NOT accepted in the language')\n",
    "            print(\"--------------------------------------------\")\n",
    "        \n",
    "        \n",
    "    #Returns a list containing the parent of the possible trees that we can generate for the last sentence that have been parsed\n",
    "    def get_trees(self):\n",
    "        return self.parse_table[self.length-1][0].productions\n",
    "                \n",
    "                \n",
    "    #@TODO\n",
    "    def print_trees(self):\n",
    "        pass\n",
    "                      \n",
    "    #Print the CYK parse trable for the last sentence that have been parsed.             \n",
    "    def print_parse_table(self):\n",
    "        try:\n",
    "            from tabulate import tabulate\n",
    "        except (ModuleNotFoundError,ImportError) as r:\n",
    "            import subprocess\n",
    "            import sys\n",
    "            import logging\n",
    "            logging.warning('To print the CYK parser table the Tabulate module is necessary, trying to install it...')\n",
    "            subprocess.call([sys.executable, \"-m\", \"pip\", \"install\", 'tabulate'])\n",
    "\n",
    "            try:\n",
    "                from tabulate import tabulate\n",
    "                logging.warning('The tabulate module has been instaled succesfuly!')\n",
    "\n",
    "            except (ModuleNotFoundError,ImportError) as r:\n",
    "                logging.warning('Unable to install the tabulate module, please run the command \\'pip install tabulate\\' in a command line')\n",
    "\n",
    "        \n",
    "        lines = [] \n",
    "        \n",
    "        \n",
    "        \n",
    "        for row in reversed(self.parse_table):\n",
    "            l = []\n",
    "            for cell in row:\n",
    "                l.append(cell.get_types)\n",
    "            lines.append(l)\n",
    "        \n",
    "        lines.append(self.tokens)\n",
    "        print('')\n",
    "        print(tabulate(lines))\n",
    "        print('')\n",
    "        \n",
    "        \n",
    "        \n",
    "     "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 14,
   "metadata": {},
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "\n",
      "Grammar file readed succesfully. Rules readed:\n",
      "S --> NP VP\n",
      "PP --> P NP\n",
      "VP --> V NP\n",
      "VP --> VP PP\n",
      "NP --> NP PP\n",
      "NP --> astronomers\n",
      "NP --> ears\n",
      "NP --> saw\n",
      "V --> saw\n",
      "NP --> telescope\n",
      "NP --> stars\n",
      "P --> with\n",
      "\n",
      "Applied Rule: VP[2,2] --> V[1,2] NP[1,3]\n",
      "Applied Rule: PP[2,4] --> P[1,4] NP[1,5]\n",
      "Applied Rule: S[3,1] --> NP[1,1] VP[2,2]\n",
      "Applied Rule: NP[3,3] --> NP[1,3] PP[2,4]\n",
      "Applied Rule: VP[4,2] --> V[1,2] NP[3,3]\n",
      "Applied Rule: VP[4,2] --> VP[2,2] PP[2,4]\n",
      "Applied Rule: S[5,1] --> NP[1,1] VP[4,2]\n",
      "Applied Rule: S[5,1] --> NP[1,1] VP[4,2]\n",
      "----------------------------------------\n",
      "The sentence IS accepted in the language\n",
      "Number of possible trees: 2\n",
      "----------------------------------------\n",
      "\n",
      "-----------  ------------  ------  ------  ------\n",
      "['S', 'S']\n",
      "[]           ['VP', 'VP']\n",
      "['S']        []            ['NP']\n",
      "[]           ['VP']        []      ['PP']\n",
      "['NP']       ['NP', 'V']   ['NP']  ['P']   ['NP']\n",
      "astronomers  saw           stars   with    ears\n",
      "-----------  ------------  ------  ------  ------\n",
      "\n"
     ]
    }
   ],
   "source": [
    "g = Grammar('example_grammar1.txt')\n",
    "g.parse('astronomers saw stars with ears')\n",
    "g.print_parse_table()\n",
    "trees = g.get_trees()\n",
    "p = trees[0].get_type\n",
    "l = trees[0].get_left\n",
    "d = trees[0].get_right\n",
    "p = trees[1].get_type\n",
    "l = trees[1].get_left\n",
    "d = trees[1].get_right"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 11,
   "metadata": {},
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "\n",
      "Grammar file readed succesfully. Rules readed:\n",
      "S --> NP VP\n",
      "VP --> VP PP\n",
      "VP --> V NP\n",
      "VP --> eats\n",
      "V --> eats\n",
      "PP --> P NP\n",
      "NP --> Det N\n",
      "NP --> she\n",
      "P --> with\n",
      "N --> fish\n",
      "N --> fork\n",
      "Det --> a\n",
      "\n",
      "Applied Rule: S[2,1] --> NP[1,1] VP[1,2]\n",
      "Applied Rule: NP[2,3] --> Det[1,3] N[1,4]\n",
      "Applied Rule: NP[2,6] --> Det[1,6] N[1,7]\n",
      "Applied Rule: VP[3,2] --> V[1,2] NP[2,3]\n",
      "Applied Rule: PP[3,5] --> P[1,5] NP[2,6]\n",
      "Applied Rule: S[4,1] --> NP[1,1] VP[3,2]\n",
      "Applied Rule: VP[6,2] --> VP[3,2] PP[3,5]\n",
      "Applied Rule: S[7,1] --> NP[1,1] VP[6,2]\n",
      "----------------------------------------\n",
      "The sentence IS accepted in the language\n",
      "Number of possible trees: 1\n",
      "----------------------------------------\n",
      "\n",
      "------  -----------  -------  -----  ------  -------  -----\n",
      "['S']\n",
      "[]      ['VP']\n",
      "[]      []           []\n",
      "['S']   []           []       []\n",
      "[]      ['VP']       []       []     ['PP']\n",
      "['S']   []           ['NP']   []     []      ['NP']\n",
      "['NP']  ['VP', 'V']  ['Det']  ['N']  ['P']   ['Det']  ['N']\n",
      "she     eats         a        fish   with    a        fork\n",
      "------  -----------  -------  -----  ------  -------  -----\n",
      "\n"
     ]
    },
    {
     "ename": "AttributeError",
     "evalue": "'list' object has no attribute 'left'",
     "output_type": "error",
     "traceback": [
      "\u001b[0;31m---------------------------------------------------------------------------\u001b[0m",
      "\u001b[0;31mAttributeError\u001b[0m                            Traceback (most recent call last)",
      "\u001b[0;32m<ipython-input-11-4677f4880d1c>\u001b[0m in \u001b[0;36m<module>\u001b[0;34m()\u001b[0m\n\u001b[1;32m      2\u001b[0m \u001b[0mg\u001b[0m\u001b[0;34m.\u001b[0m\u001b[0mparse\u001b[0m\u001b[0;34m(\u001b[0m\u001b[0;34m'she eats a fish with a fork'\u001b[0m\u001b[0;34m)\u001b[0m\u001b[0;34m\u001b[0m\u001b[0m\n\u001b[1;32m      3\u001b[0m \u001b[0mg\u001b[0m\u001b[0;34m.\u001b[0m\u001b[0mprint_parse_table\u001b[0m\u001b[0;34m(\u001b[0m\u001b[0;34m)\u001b[0m\u001b[0;34m\u001b[0m\u001b[0m\n\u001b[0;32m----> 4\u001b[0;31m \u001b[0mg\u001b[0m\u001b[0;34m.\u001b[0m\u001b[0mget_trees\u001b[0m\u001b[0;34m(\u001b[0m\u001b[0;34m)\u001b[0m\u001b[0;34m.\u001b[0m\u001b[0mleft\u001b[0m\u001b[0;34m\u001b[0m\u001b[0m\n\u001b[0m",
      "\u001b[0;31mAttributeError\u001b[0m: 'list' object has no attribute 'left'"
     ]
    }
   ],
   "source": [
    "g = Grammar('example_grammar2.txt')\n",
    "g.parse('she eats a fish with a fork')\n",
    "g.print_parse_table()\n",
    "g.get_trees().left"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 12,
   "metadata": {},
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "\n",
      "Grammar file readed succesfully. Rules readed:\n",
      "S --> NP VP\n",
      "VP --> VP PP\n",
      "VP --> V NP\n",
      "VP --> eats\n",
      "V --> eats\n",
      "PP --> P NP\n",
      "NP --> Det N\n",
      "NP --> she\n",
      "P --> with\n",
      "N --> fish\n",
      "N --> fork\n",
      "Det --> a\n",
      "\n",
      "Applied Rule: VP[2,1] --> V[1,1] NP[1,2]\n",
      "Applied Rule: NP[2,4] --> Det[1,4] N[1,5]\n",
      "--------------------------------------------\n",
      "The sentence IS NOT accepted in the language\n",
      "--------------------------------------------\n",
      "\n",
      "-----------  ------  -----  -------  -----\n",
      "[]\n",
      "[]           []\n",
      "[]           []      []\n",
      "['VP']       []      []     ['NP']\n",
      "['VP', 'V']  ['NP']  ['N']  ['Det']  ['N']\n",
      "eats         she     fork   a        fish\n",
      "-----------  ------  -----  -------  -----\n",
      "\n"
     ]
    },
    {
     "data": {
      "text/plain": [
       "[]"
      ]
     },
     "execution_count": 12,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "g = Grammar('example_grammar2.txt')\n",
    "g.parse('eats she fork a fish')\n",
    "g.print_parse_table()\n",
    "g.get_trees()"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": []
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": []
  }
 ],
 "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
}