8 CFG and parse tree.ipynb

{
 "cells": [
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "## Resources\n",
    "- https://www.kaggle.com/general/208640\n",
    "- https://www.javatpoint.com/context-free-grammar\n",
    "- https://www.geeksforgeeks.org/classification-of-context-free-grammars/\n",
    "- https://www.nltk.org/book/ch08.html\n",
    "- https://www.geeksforgeeks.org/syntax-tree-natural-language-processing/"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "## Context Free Grammar\n",
    "- Recursive CFG\n",
    "- Non recursive CFG\n"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "## import libraries"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 1,
   "metadata": {},
   "outputs": [],
   "source": [
    "import nltk"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "## Non Recursive Grammar\n",
    "- Fixed text generation: finite\n",
    "- As an example, a simple CFG\n",
    "    \n",
    "    S->Aa\n",
    "    \n",
    "    A->b|c\n",
    "    \n",
    "- Generated output by non recursive grammars: {ba,ca}"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": []
  },
  {
   "cell_type": "code",
   "execution_count": 2,
   "metadata": {},
   "outputs": [
    {
     "data": {
      "text/plain": [
       "[S -> A 'a', A -> 'b', A -> 'c']"
      ]
     },
     "execution_count": 2,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "non_recursive_cfg=nltk.CFG.fromstring(\"\"\"\n",
    "    S -> A'a'\n",
    "    A -> 'b' | 'c'\n",
    "\"\"\")\n",
    "non_recursive_cfg.productions()"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 22,
   "metadata": {},
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "['b', 'a']\n",
      "(S (A b) a)\n",
      "None\n"
     ]
    }
   ],
   "source": [
    "# parse the text using cfg\n",
    "text=\"b a\"\n",
    "words=text.split()\n",
    "print(words)\n",
    "parser=nltk.ChartParser(non_recursive_cfg)\n",
    "for tree in parser.parse(words):\n",
    "    print(tree)\n",
    "    print(tree.draw())\n"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "## Recursive Grammar\n",
    "- Output of the Recursive Grammar: infinite \n",
    "- As an example\n",
    "   \n",
    "   S-> Aa\n",
    "   \n",
    "   A->Ab|c\n",
    "\n",
    "- Generated output by recursive grammars: {ca, cba, cbba, ...}"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 4,
   "metadata": {},
   "outputs": [
    {
     "data": {
      "text/plain": [
       "[S -> A 'a', A -> A 'b', A -> 'c']"
      ]
     },
     "execution_count": 4,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "recursive_cfg=nltk.CFG.fromstring(\"\"\"\n",
    "    S -> A'a'\n",
    "    A -> A'b' | 'c'\n",
    "\"\"\")\n",
    "recursive_cfg.productions()"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 23,
   "metadata": {},
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "['c', 'b', 'b', 'a']\n",
      "(S (A (A (A c) b) b) a)\n",
      "None\n"
     ]
    }
   ],
   "source": [
    "text='c b b a'\n",
    "words=text.split()\n",
    "print(words)\n",
    "parser=nltk.ChartParser(recursive_cfg)\n",
    "for tree in parser.parse(words):\n",
    "    print(tree)\n",
    "    print(tree.draw())"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "## Define a complex Context Free Grammar\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 17,
   "metadata": {},
   "outputs": [
    {
     "data": {
      "text/plain": [
       "[S -> NP VP,\n",
       " PP -> P NP,\n",
       " NP -> Det N,\n",
       " NP -> Det N PP,\n",
       " NP -> 'I',\n",
       " VP -> V NP,\n",
       " VP -> VP PP,\n",
       " Det -> 'an',\n",
       " Det -> 'my',\n",
       " N -> 'elephant',\n",
       " N -> 'pajamas',\n",
       " V -> 'shot',\n",
       " P -> 'in']"
      ]
     },
     "execution_count": 17,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "conext_free_grammar = nltk.CFG.fromstring(\"\"\"\n",
    "S -> NP VP\n",
    "PP -> P NP\n",
    "NP -> Det N | Det N PP | 'I'\n",
    "VP -> V NP | VP PP\n",
    "Det -> 'an' | 'my'\n",
    "N -> 'elephant' | 'pajamas'\n",
    "V -> 'shot'\n",
    "P -> 'in'\n",
    "\"\"\")\n",
    "conext_free_grammar.productions()"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "## Analysis of CFG"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 18,
   "metadata": {},
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "star of the CGF:  S\n",
      "Max len of CFG:  3\n",
      "Min len of CFG:  1\n"
     ]
    }
   ],
   "source": [
    "print('star of the CGF: ',conext_free_grammar.start())\n",
    "print('Max len of CFG: ',conext_free_grammar.max_len())\n",
    "print('Min len of CFG: ',conext_free_grammar.min_len())"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "## Tokenization with Text"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 20,
   "metadata": {},
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "words:  ['I', 'shot', 'an', 'elephant', 'in', 'my', 'pajamas']\n"
     ]
    }
   ],
   "source": [
    "sentence='I shot an elephant in my pajamas'\n",
    "words=sentence.split()\n",
    "print('words: ',words)"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "## Define Parse Tree"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 21,
   "metadata": {},
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "Parse Tree found:  2\n"
     ]
    }
   ],
   "source": [
    "\n",
    "parser = nltk.ChartParser(conext_free_grammar)\n",
    "\n",
    "parse_trees=[]\n",
    "for tree in parser.parse(words):\n",
    "    parse_trees.append(tree)\n",
    "print('Parse Tree found: ',len(parse_trees))\n"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "## Visualize Parse Tree"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 24,
   "metadata": {},
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "Parse Tree:  (S\n",
      "  (NP I)\n",
      "  (VP\n",
      "    (VP (V shot) (NP (Det an) (N elephant)))\n",
      "    (PP (P in) (NP (Det my) (N pajamas)))))\n",
      "None\n"
     ]
    }
   ],
   "source": [
    "print('Parse Tree: ',parse_trees[0])\n",
    "print(parse_trees[0].draw())"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 25,
   "metadata": {},
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "Parse tree:  0\n",
      "(S\n",
      "  (NP I)\n",
      "  (VP\n",
      "    (VP (V shot) (NP (Det an) (N elephant)))\n",
      "    (PP (P in) (NP (Det my) (N pajamas)))))\n",
      "None\n",
      "\n",
      "\n",
      "Parse tree:  1\n",
      "(S\n",
      "  (NP I)\n",
      "  (VP\n",
      "    (V shot)\n",
      "    (NP (Det an) (N elephant) (PP (P in) (NP (Det my) (N pajamas))))))\n",
      "None\n",
      "\n",
      "\n"
     ]
    }
   ],
   "source": [
    "for index, tree in enumerate(parse_trees):\n",
    "    print('Parse tree: ',index)\n",
    "    print(tree)\n",
    "    print(tree.draw())\n",
    "    print('\\n')"
   ]
  }
 ],
 "metadata": {
  "kernelspec": {
   "display_name": "Python 3.8.13 ('tf-gpu')",
   "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.8.13"
  },
  "orig_nbformat": 4,
  "vscode": {
   "interpreter": {
    "hash": "a42308a4b3b8692f798b54dd71ed0fc43b4ea9aee117f0b02f20461fbf01c221"
   }
  }
 },
 "nbformat": 4,
 "nbformat_minor": 2
}