{
 "cells": [
  {
   "cell_type": "code",
   "execution_count": 1,
   "metadata": {},
   "outputs": [],
   "source": [
    "wlist = \"book the flight through Houston\".split()"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 2,
   "metadata": {},
   "outputs": [],
   "source": [
    "Lexicon = {\n",
    "    \"that | this | the | a\": \"Det\",\n",
    "    \"book | flight | meal | money\": \"Noun\",\n",
    "    \"book | include | prefer\": \"Verb\",\n",
    "    \"I | she | me\": \"Pronoun\",\n",
    "    \"Houston | NWA\": \"Proper-Noun\",\n",
    "    \"does\": \"Aux\",\n",
    "    \"from | to | on | near | through\": \"Preposition\"\n",
    "}"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 3,
   "metadata": {},
   "outputs": [],
   "source": [
    "# Grammar = {\n",
    "#     \"NP VP\": \"S\",\n",
    "#     \"Aux NP VP\": \"S\",\n",
    "#     \"VP\": \"S\",\n",
    "#     \"Pronoun\": \"NP\",\n",
    "#     \"Proper-Noun\": \"NP\",\n",
    "#     \"Det Nominal\": \"NP\",\n",
    "#     \"Noun\": \"Nominal\",\n",
    "#     \"Nominal Noun\": \"Nominal\",\n",
    "#     \"Nominal PP\": \"Nominal\",\n",
    "#     \"Verb\": \"VP\",\n",
    "#     \"Verb NP\": \"VP\",\n",
    "#     \"Verb NP PP\": \"VP\",\n",
    "#     \"Verb PP\": \"VP\",\n",
    "#     \"VP PP\": \"VP\",\n",
    "#     \"Preposition NP\": \"PP\",\n",
    "# }\n",
    "\n",
    "# Grammar = [\n",
    "#     \"S NP VP\",\n",
    "#     \"S Aux NP VP\",\n",
    "#     \"S VP\",\n",
    "#     \"NP Pronoun\",\n",
    "#     \"NP Proper-Noun\",\n",
    "#     \"NPDet Nominal\",\n",
    "#     \"Nominal Noun\",\n",
    "#     \"Nominal Nominal Noun\",\n",
    "#     \"Nominal Nominal PP\",\n",
    "#     \"VP Verb\",\n",
    "#     \"VP Verb NP\",\n",
    "#     \"VP Verb NP PP\",\n",
    "#     \"VP Verb PP\",\n",
    "#     \"VP VP PP\",\n",
    "#     \"PP Preposition NP\",\n",
    "#     ]"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 4,
   "metadata": {},
   "outputs": [],
   "source": [
    "CNF = [\n",
    "    \"S -> NP VP\",\n",
    "    \"S -> X1 VP\",\n",
    "    \"X1 -> Aux NP\",\n",
    "    \"S -> book | inclue | prefer\",\n",
    "    \"S -> Verb NP\",\n",
    "    \"S -> X2 PP\",\n",
    "    \"S -> Verb PP\",\n",
    "    \"S -> VP PP\",\n",
    "    \"NP -> I | she | me\",\n",
    "    \"NP -> TWA | Houston\",\n",
    "    \"NP -> Det Nominal\",\n",
    "    \"Nominal -> book | flight | meal | money\",\n",
    "    \"Nominal -> Nominal Noun\",\n",
    "    \"Nominal -> Nominal PP\",\n",
    "    \"VP -> book | include | prefer\",\n",
    "    \"VP -> Verb NP\",\n",
    "    \"VP -> X2 PP\",\n",
    "    \"X2 -> Verb NP\",\n",
    "    \"VP -> Verb PP\",\n",
    "    \"VP -> VP PP\",\n",
    "    \"PP -> Preposition NP\",\n",
    "    ]"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 5,
   "metadata": {},
   "outputs": [],
   "source": [
    "def get_diag_eles(w):\n",
    "    res = []\n",
    "    for key,value in Lexicon.items():\n",
    "        if w in key:\n",
    "            res.append(value)\n",
    "    for item in CNF:\n",
    "        key, value = item.split(\" -> \")\n",
    "        if w in value:\n",
    "            res.append(key)\n",
    "    return res"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 6,
   "metadata": {},
   "outputs": [],
   "source": [
    "def get_inner_eles(table, i, j, k):\n",
    "    res = []\n",
    "    B = table[i][k].split(',')\n",
    "    C = table[k][j].split(',')\n",
    "    for b in B:\n",
    "        for c in C:\n",
    "            bc = \" \".join((b, c))\n",
    "            for item in CNF:\n",
    "                key, value = item.split(\" -> \")\n",
    "                if bc == value:\n",
    "                    res.append(key)\n",
    "    return res"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 13,
   "metadata": {
    "scrolled": false
   },
   "outputs": [],
   "source": [
    "def cyk(wlist):\n",
    "    lenw = len(wlist)\n",
    "    table = [['' for i in range(lenw+1)] for i in range(lenw)]\n",
    "    for j in range(1, lenw+1):\n",
    "        diag_eles = get_diag_eles(wlist[j-1])\n",
    "        table[j-1][j] = \",\".join(diag_eles)\n",
    "        # j = 1,2,3,4,5\n",
    "        for i in range(j-2, -1, -1):\n",
    "            # i = 3,2,1,0\n",
    "            inner_eles = []\n",
    "            for k in range(i+1, j):\n",
    "    #             print('k',(i,j), (i,k), (k,j))\n",
    "                tmp = get_inner_eles(table, i, j, k)\n",
    "                inner_eles.extend(tmp)\n",
    "            table[i][j] = \",\".join(inner_eles)\n",
    "    return table"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 14,
   "metadata": {},
   "outputs": [
    {
     "data": {
      "text/plain": [
       "[['', 'Noun,Verb,S,Nominal,VP', '', 'S,VP,X2', '', 'S,VP,X2,S,VP,S,VP'],\n",
       " ['', '', 'Det', 'NP', '', 'NP'],\n",
       " ['', '', '', 'Noun,Nominal', '', 'Nominal'],\n",
       " ['', '', '', '', 'Preposition', 'PP'],\n",
       " ['', '', '', '', '', 'Proper-Noun,NP']]"
      ]
     },
     "execution_count": 14,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "cyk(wlist)"
   ]
  },
  {
   "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.7.2"
  },
  "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": true,
   "sideBar": true,
   "skip_h1_title": false,
   "title_cell": "Table of Contents",
   "title_sidebar": "Contents",
   "toc_cell": false,
   "toc_position": {},
   "toc_section_display": true,
   "toc_window_display": false
  }
 },
 "nbformat": 4,
 "nbformat_minor": 2
}