Example.ipynb

{
 "cells": [
  {
   "attachments": {},
   "cell_type": "markdown",
   "id": "f9ee1605",
   "metadata": {},
   "source": [
    "### Example usage\n",
    "First, define a weighted context free grammar as follows:"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 1,
   "id": "1858fc62",
   "metadata": {},
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "N → fruit\t0.5\n",
      "N → flies\t0.25\n",
      "N → banana\t0.25\n",
      "S → NP VP\t1.0\n",
      "V → like\t0.5\n",
      "V → flies\t0.5\n",
      "NP → N N\t0.25\n",
      "NP → Det N\t0.25\n",
      "NP → Adj N\t0.25\n",
      "NP → Det NP\t0.25\n",
      "VP → V NP\t1.0\n",
      "Adj → green\t1.0\n",
      "Adv → like\t1.0\n",
      "Det → a\t1.0\n",
      "AdvP → Adv NP\t1.0\n"
     ]
    }
   ],
   "source": [
    "from fastlri.parsing.parser import Parser\n",
    "from fastlri.base.cfg import CFG\n",
    "from fastlri.base.nonterminal import S, NT\n",
    "from fastlri.base.symbol import Sym\n",
    "\n",
    "# define the nonterminals of the grammar\n",
    "NP = NT(\"NP\")\n",
    "VP = NT(\"VP\")\n",
    "Det = NT(\"Det\")\n",
    "N = NT(\"N\")\n",
    "PP = NT(\"PP\")\n",
    "V = NT(\"V\")\n",
    "Adj = NT(\"Adj\")\n",
    "Adv = NT(\"Adv\")\n",
    "AdvP = NT(\"AdvP\")\n",
    "\n",
    "# define the terminals of the grammar\n",
    "fruit = Sym(\"fruit\")\n",
    "flies = Sym(\"flies\")\n",
    "like = Sym(\"like\")\n",
    "a = Sym(\"a\")\n",
    "green = Sym(\"green\")\n",
    "banana = Sym(\"banana\")\n",
    "\n",
    "# define the rules of the grammar\n",
    "cfg = CFG()\n",
    "cfg.add(1, cfg.S, NP, VP)\n",
    "cfg.add(0.25, NP, Det, N)\n",
    "cfg.add(0.25, NP, Det, NP)\n",
    "cfg.add(0.25, NP, N, N)\n",
    "cfg.add(0.25, NP, Adj, N)\n",
    "cfg.add(1, VP, V, NP)\n",
    "cfg.add(1, AdvP, Adv, NP)\n",
    "cfg.add(0.5, N, fruit)\n",
    "cfg.add(0.25, N, flies)\n",
    "cfg.add(0.25, N, banana)\n",
    "cfg.add(0.5, V, flies)\n",
    "cfg.add(0.5, V, like)\n",
    "cfg.add(1, Det, a)\n",
    "cfg.add(1, Adj, green)\n",
    "cfg.add(1, Adv, like)\n",
    "\n",
    "print(cfg)"
   ]
  },
  {
   "attachments": {},
   "cell_type": "markdown",
   "id": "07c79cd4",
   "metadata": {},
   "source": [
    "Then, create a parser for this CFG:"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 2,
   "id": "b7076495",
   "metadata": {},
   "outputs": [],
   "source": [
    "parser = Parser(cfg)"
   ]
  },
  {
   "attachments": {},
   "cell_type": "markdown",
   "id": "5aa3b97d",
   "metadata": {},
   "source": [
    " Now you can parse input strings using CKY:"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 3,
   "id": "6fdd1e66",
   "metadata": {},
   "outputs": [
    {
     "data": {
      "text/plain": [
       "0.000244140625"
      ]
     },
     "execution_count": 3,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "parser.cky(\"fruit flies like a green banana\")"
   ]
  },
  {
   "attachments": {},
   "cell_type": "markdown",
   "id": "4b7fae32",
   "metadata": {},
   "source": [
    "Similarly for lri and fast lri:"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 4,
   "id": "45ef18c1",
   "metadata": {},
   "outputs": [
    {
     "data": {
      "text/plain": [
       "0.000244140625"
      ]
     },
     "execution_count": 4,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "parser.lri(\"fruit flies like a green banana\")"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 5,
   "id": "b936664e",
   "metadata": {},
   "outputs": [
    {
     "data": {
      "text/plain": [
       "0.000244140625"
      ]
     },
     "execution_count": 5,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "parser.lri_fast(\"fruit flies like a green banana\")"
   ]
  },
  {
   "attachments": {},
   "cell_type": "markdown",
   "id": "732b3068",
   "metadata": {},
   "source": [
    "For a prefix that has no rooted parse tree under the CFG, cky will return 0, while lri returns a positive probability:"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 6,
   "id": "c46879d0",
   "metadata": {},
   "outputs": [
    {
     "data": {
      "text/plain": [
       "0.0"
      ]
     },
     "execution_count": 6,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "parser.cky(\"fruit flies like\")"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 7,
   "id": "20d8a2ac",
   "metadata": {},
   "outputs": [
    {
     "data": {
      "text/plain": [
       "0.015625"
      ]
     },
     "execution_count": 7,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "parser.lri_fast(\"fruit flies like\")"
   ]
  },
  {
   "attachments": {},
   "cell_type": "markdown",
   "id": "055d6853",
   "metadata": {},
   "source": [
    "It is also possible to get the full dynamic programming chart by setting a flag:"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 8,
   "id": "43bc3276",
   "metadata": {},
   "outputs": [
    {
     "data": {
      "text/plain": [
       "defaultdict(<function fastlri.parsing.parser.Parser.lri_fast.<locals>.<lambda>()>,\n",
       "            {(VP, 0, 0): 0.0,\n",
       "             (VP, 1, 1): 0.5,\n",
       "             (NP, 0, 0): 0.125,\n",
       "             (NP, 1, 1): 0.0625,\n",
       "             (Adj, 0, 0): 0.0,\n",
       "             (Adj, 1, 1): 0.0,\n",
       "             (AdvP, 0, 0): 0.0,\n",
       "             (AdvP, 1, 1): 0.0,\n",
       "             (V, 0, 0): 0.0,\n",
       "             (V, 1, 1): 0.5,\n",
       "             (N, 0, 0): 0.5,\n",
       "             (N, 1, 1): 0.25,\n",
       "             (Adv, 0, 0): 0.0,\n",
       "             (Adv, 1, 1): 0.0,\n",
       "             (S, 0, 0): 0.125,\n",
       "             (S, 1, 1): 0.0625,\n",
       "             (Det, 0, 0): 0.0,\n",
       "             (Det, 1, 1): 0.0,\n",
       "             (VP, 0, 1): 0.0,\n",
       "             (NP, 0, 1): 0.03125,\n",
       "             (Adj, 0, 1): 0.0,\n",
       "             (AdvP, 0, 1): 0.0,\n",
       "             (V, 0, 1): 0.0,\n",
       "             (N, 0, 1): 0.0,\n",
       "             (Adv, 0, 1): 0.0,\n",
       "             (S, 0, 1): 0.03125,\n",
       "             (Det, 0, 1): 0.0})"
      ]
     },
     "execution_count": 8,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "parser.lri_fast(\"fruit flies\", chart=True)"
   ]
  }
 ],
 "metadata": {
  "kernelspec": {
   "display_name": "Python 3 (ipykernel)",
   "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.10.11"
  }
 },
 "nbformat": 4,
 "nbformat_minor": 5
}