day 94 - earley parser.ipynb

{
 "cells": [
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "## algorithm"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 1,
   "metadata": {
    "collapsed": true
   },
   "outputs": [],
   "source": [
    "class EarleyParser:\n",
    "\n",
    "    def __init__(self, grammar):\n",
    "        self.grammar = grammar\n",
    "        self.states = []\n",
    "\n",
    "    def parse(self, text):\n",
    "        self.states = [set() for _ in range(len(text) + 1)]\n",
    "        self.states[0].add(State(*grammar.start))\n",
    "\n",
    "        for k, token in enumerate(text + '\\u0000'):\n",
    "            extension = list(self.states[k])\n",
    "            self.states[k].clear()\n",
    "\n",
    "            while extension:\n",
    "                state = extension.pop()\n",
    "                if state in self.states[k]:\n",
    "                    continue\n",
    "\n",
    "                self.states[k].add(state)\n",
    "\n",
    "                if state.finished:\n",
    "                    self._completer(state, extension)\n",
    "                elif state.symbol_is_nonterminal:\n",
    "                    self._predictor(state, k, extension)\n",
    "                else:\n",
    "                    self._scanner(state, k, token)\n",
    "\n",
    "        self._print(text)\n",
    "\n",
    "    def _predictor(self, state, origin, extension):\n",
    "        for rule in self.grammar[state.symbol]:\n",
    "            extension.append(State(*rule, origin=origin))\n",
    "\n",
    "    def _scanner(self, state, origin, token):\n",
    "        if state.symbol == token:\n",
    "            self.states[origin + 1].add(state.shift)\n",
    "\n",
    "    def _completer(self, state, extension):\n",
    "        for reduce in self.states[state.origin]:\n",
    "            if state.nonterminal == reduce.symbol:\n",
    "                extension.append(reduce.shift)\n",
    "\n",
    "    def _print(self, text):\n",
    "        for k, state in enumerate(self.states):\n",
    "            accepts = any(s.nonterminal == '^' and s.finished for s in state)\n",
    "\n",
    "            print('(%d)' % k, end=' ')\n",
    "            print('\"%s.%s\"' % (text[:k], text[k:]), end=' ')\n",
    "            print(accepts and 'ACCEPTS' or '')\n",
    "\n",
    "            for i in state:\n",
    "                print('\\t', i)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 2,
   "metadata": {
    "collapsed": true
   },
   "outputs": [],
   "source": [
    "class State:\n",
    "\n",
    "    def __init__(self, nonterminal, expression, dot=0, origin=0):\n",
    "        self.nonterminal = nonterminal\n",
    "        self.expression = expression\n",
    "        self.dot = dot\n",
    "        self.origin = origin\n",
    "\n",
    "    @property\n",
    "    def finished(self):\n",
    "        return self.dot >= len(self.expression)\n",
    "\n",
    "    @property\n",
    "    def symbol(self):\n",
    "        return None if self.finished else self.expression[self.dot]\n",
    "\n",
    "    @property\n",
    "    def symbol_is_nonterminal(self):\n",
    "        return self.symbol and self.symbol.isalpha() and self.symbol.isupper()\n",
    "\n",
    "    @property\n",
    "    def shift(self):\n",
    "        return State(self.nonterminal, self.expression, self.dot + 1, self.origin)\n",
    "\n",
    "    @property\n",
    "    def tuple(self):\n",
    "        return self.nonterminal, self.expression, self.dot, self.origin\n",
    "\n",
    "    def __hash__(self):\n",
    "        return hash(self.tuple)\n",
    "\n",
    "    def __eq__(self, other):\n",
    "        return self.tuple == other.tuple\n",
    "\n",
    "    def __str__(self):\n",
    "        n, e, d, o = self.tuple\n",
    "        return '[%d] %s -> %s.%s' % (o, n, e[:d], e[d:])"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 3,
   "metadata": {
    "collapsed": true
   },
   "outputs": [],
   "source": [
    "class Grammar:\n",
    "\n",
    "    def __init__(self, *rules):\n",
    "        self.rules = tuple(self._parse(rule) for rule in rules)\n",
    "\n",
    "    def _parse(self, rule):\n",
    "        return tuple(rule.replace(' ', '').split('::='))\n",
    "        \n",
    "    @property\n",
    "    def start(self):\n",
    "        return next(self['^'])\n",
    "\n",
    "    def __getitem__(self, nonterminal):\n",
    "        yield from [rule for rule in self.rules if rule[0] == nonterminal]"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "## grammar: arithmetic expression"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 4,
   "metadata": {
    "collapsed": false
   },
   "outputs": [],
   "source": [
    "grammar = Grammar(\n",
    "    '^ ::= E',\n",
    "    'E ::= E + T',\n",
    "    'E ::= E - T',\n",
    "    'E ::= T',\n",
    "    'T ::= T * F',\n",
    "    'T ::= T / F',\n",
    "    'T ::= F',\n",
    "    'F ::= ( E )',\n",
    "    'F ::= - F',\n",
    "    'F ::= x',\n",
    "    'F ::= y',\n",
    "    'F ::= z',\n",
    ")"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 5,
   "metadata": {
    "collapsed": false
   },
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "(0) \".x-x*(y+z)\" \n",
      "\t [0] E -> .T\n",
      "\t [0] F -> .(E)\n",
      "\t [0] E -> .E-T\n",
      "\t [0] E -> .E+T\n",
      "\t [0] F -> .x\n",
      "\t [0] F -> .z\n",
      "\t [0] F -> .-F\n",
      "\t [0] T -> .T*F\n",
      "\t [0] ^ -> .E\n",
      "\t [0] T -> .F\n",
      "\t [0] T -> .T/F\n",
      "\t [0] F -> .y\n",
      "(1) \"x.-x*(y+z)\" ACCEPTS\n",
      "\t [0] E -> T.\n",
      "\t [0] E -> E.+T\n",
      "\t [0] F -> x.\n",
      "\t [0] T -> F.\n",
      "\t [0] T -> T./F\n",
      "\t [0] T -> T.*F\n",
      "\t [0] ^ -> E.\n",
      "\t [0] E -> E.-T\n",
      "(2) \"x-.x*(y+z)\" \n",
      "\t [2] F -> .-F\n",
      "\t [2] T -> .T*F\n",
      "\t [2] T -> .F\n",
      "\t [2] T -> .T/F\n",
      "\t [2] F -> .y\n",
      "\t [2] F -> .(E)\n",
      "\t [0] E -> E-.T\n",
      "\t [2] F -> .x\n",
      "\t [2] F -> .z\n",
      "(3) \"x-x.*(y+z)\" ACCEPTS\n",
      "\t [2] T -> F.\n",
      "\t [2] T -> T.*F\n",
      "\t [2] T -> T./F\n",
      "\t [0] E -> E.+T\n",
      "\t [0] E -> E-T.\n",
      "\t [0] ^ -> E.\n",
      "\t [0] E -> E.-T\n",
      "\t [2] F -> x.\n",
      "(4) \"x-x*.(y+z)\" \n",
      "\t [4] F -> .y\n",
      "\t [4] F -> .x\n",
      "\t [4] F -> .-F\n",
      "\t [4] F -> .z\n",
      "\t [2] T -> T*.F\n",
      "\t [4] F -> .(E)\n",
      "(5) \"x-x*(.y+z)\" \n",
      "\t [5] E -> .T\n",
      "\t [5] F -> .(E)\n",
      "\t [5] F -> .y\n",
      "\t [5] E -> .E+T\n",
      "\t [4] F -> (.E)\n",
      "\t [5] T -> .T/F\n",
      "\t [5] F -> .x\n",
      "\t [5] T -> .F\n",
      "\t [5] E -> .E-T\n",
      "\t [5] F -> .-F\n",
      "\t [5] F -> .z\n",
      "\t [5] T -> .T*F\n",
      "(6) \"x-x*(y.+z)\" \n",
      "\t [5] T -> T./F\n",
      "\t [5] E -> T.\n",
      "\t [5] E -> E.+T\n",
      "\t [5] E -> E.-T\n",
      "\t [5] T -> T.*F\n",
      "\t [5] F -> y.\n",
      "\t [5] T -> F.\n",
      "\t [4] F -> (E.)\n",
      "(7) \"x-x*(y+.z)\" \n",
      "\t [7] T -> .F\n",
      "\t [7] F -> .-F\n",
      "\t [7] T -> .T*F\n",
      "\t [7] F -> .z\n",
      "\t [7] F -> .(E)\n",
      "\t [7] F -> .y\n",
      "\t [5] E -> E+.T\n",
      "\t [7] T -> .T/F\n",
      "\t [7] F -> .x\n",
      "(8) \"x-x*(y+z.)\" \n",
      "\t [7] T -> T.*F\n",
      "\t [5] E -> E.+T\n",
      "\t [7] T -> F.\n",
      "\t [5] E -> E.-T\n",
      "\t [7] T -> T./F\n",
      "\t [7] F -> z.\n",
      "\t [4] F -> (E.)\n",
      "\t [5] E -> E+T.\n",
      "(9) \"x-x*(y+z).\" ACCEPTS\n",
      "\t [4] F -> (E).\n",
      "\t [2] T -> T.*F\n",
      "\t [2] T -> T./F\n",
      "\t [0] E -> E.+T\n",
      "\t [0] E -> E-T.\n",
      "\t [0] ^ -> E.\n",
      "\t [0] E -> E.-T\n",
      "\t [2] T -> T*F.\n"
     ]
    }
   ],
   "source": [
    "EarleyParser(grammar).parse('x-x*(y+z)')"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 6,
   "metadata": {
    "collapsed": false
   },
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "(0) \".x-(y/x+y/z)/y*-z\" \n",
      "\t [0] E -> .T\n",
      "\t [0] F -> .(E)\n",
      "\t [0] E -> .E-T\n",
      "\t [0] E -> .E+T\n",
      "\t [0] F -> .x\n",
      "\t [0] F -> .z\n",
      "\t [0] F -> .-F\n",
      "\t [0] T -> .T*F\n",
      "\t [0] ^ -> .E\n",
      "\t [0] T -> .F\n",
      "\t [0] T -> .T/F\n",
      "\t [0] F -> .y\n",
      "(1) \"x.-(y/x+y/z)/y*-z\" ACCEPTS\n",
      "\t [0] E -> T.\n",
      "\t [0] E -> E.+T\n",
      "\t [0] F -> x.\n",
      "\t [0] T -> F.\n",
      "\t [0] T -> T./F\n",
      "\t [0] T -> T.*F\n",
      "\t [0] ^ -> E.\n",
      "\t [0] E -> E.-T\n",
      "(2) \"x-.(y/x+y/z)/y*-z\" \n",
      "\t [2] F -> .-F\n",
      "\t [2] T -> .T*F\n",
      "\t [2] T -> .F\n",
      "\t [2] T -> .T/F\n",
      "\t [2] F -> .y\n",
      "\t [2] F -> .(E)\n",
      "\t [0] E -> E-.T\n",
      "\t [2] F -> .x\n",
      "\t [2] F -> .z\n",
      "(3) \"x-(.y/x+y/z)/y*-z\" \n",
      "\t [3] T -> .T/F\n",
      "\t [3] F -> .x\n",
      "\t [3] F -> .z\n",
      "\t [3] F -> .(E)\n",
      "\t [3] E -> .E-T\n",
      "\t [3] F -> .-F\n",
      "\t [3] T -> .T*F\n",
      "\t [3] E -> .E+T\n",
      "\t [2] F -> (.E)\n",
      "\t [3] F -> .y\n",
      "\t [3] E -> .T\n",
      "\t [3] T -> .F\n",
      "(4) \"x-(y./x+y/z)/y*-z\" \n",
      "\t [3] F -> y.\n",
      "\t [3] T -> F.\n",
      "\t [3] E -> T.\n",
      "\t [3] E -> E.+T\n",
      "\t [2] F -> (E.)\n",
      "\t [3] T -> T./F\n",
      "\t [3] E -> E.-T\n",
      "\t [3] T -> T.*F\n",
      "(5) \"x-(y/.x+y/z)/y*-z\" \n",
      "\t [5] F -> .(E)\n",
      "\t [3] T -> T/.F\n",
      "\t [5] F -> .y\n",
      "\t [5] F -> .x\n",
      "\t [5] F -> .-F\n",
      "\t [5] F -> .z\n",
      "(6) \"x-(y/x.+y/z)/y*-z\" \n",
      "\t [5] F -> x.\n",
      "\t [2] F -> (E.)\n",
      "\t [3] E -> T.\n",
      "\t [3] E -> E.+T\n",
      "\t [3] T -> T./F\n",
      "\t [3] T -> T/F.\n",
      "\t [3] E -> E.-T\n",
      "\t [3] T -> T.*F\n",
      "(7) \"x-(y/x+.y/z)/y*-z\" \n",
      "\t [7] T -> .F\n",
      "\t [7] F -> .-F\n",
      "\t [7] T -> .T*F\n",
      "\t [7] F -> .z\n",
      "\t [3] E -> E+.T\n",
      "\t [7] F -> .(E)\n",
      "\t [7] F -> .y\n",
      "\t [7] T -> .T/F\n",
      "\t [7] F -> .x\n",
      "(8) \"x-(y/x+y./z)/y*-z\" \n",
      "\t [7] T -> T.*F\n",
      "\t [3] E -> E+T.\n",
      "\t [7] F -> y.\n",
      "\t [7] T -> F.\n",
      "\t [2] F -> (E.)\n",
      "\t [3] E -> E.+T\n",
      "\t [7] T -> T./F\n",
      "\t [3] E -> E.-T\n",
      "(9) \"x-(y/x+y/.z)/y*-z\" \n",
      "\t [9] F -> .(E)\n",
      "\t [7] T -> T/.F\n",
      "\t [9] F -> .z\n",
      "\t [9] F -> .-F\n",
      "\t [9] F -> .x\n",
      "\t [9] F -> .y\n",
      "(10) \"x-(y/x+y/z.)/y*-z\" \n",
      "\t [7] T -> T.*F\n",
      "\t [3] E -> E+T.\n",
      "\t [2] F -> (E.)\n",
      "\t [3] E -> E.+T\n",
      "\t [9] F -> z.\n",
      "\t [7] T -> T./F\n",
      "\t [3] E -> E.-T\n",
      "\t [7] T -> T/F.\n",
      "(11) \"x-(y/x+y/z)./y*-z\" ACCEPTS\n",
      "\t [2] T -> F.\n",
      "\t [2] T -> T.*F\n",
      "\t [2] T -> T./F\n",
      "\t [0] E -> E.+T\n",
      "\t [2] F -> (E).\n",
      "\t [0] E -> E-T.\n",
      "\t [0] ^ -> E.\n",
      "\t [0] E -> E.-T\n",
      "(12) \"x-(y/x+y/z)/.y*-z\" \n",
      "\t [12] F -> .-F\n",
      "\t [12] F -> .z\n",
      "\t [12] F -> .x\n",
      "\t [2] T -> T/.F\n",
      "\t [12] F -> .(E)\n",
      "\t [12] F -> .y\n",
      "(13) \"x-(y/x+y/z)/y.*-z\" ACCEPTS\n",
      "\t [12] F -> y.\n",
      "\t [2] T -> T./F\n",
      "\t [0] E -> E.+T\n",
      "\t [2] T -> T.*F\n",
      "\t [2] T -> T/F.\n",
      "\t [0] E -> E-T.\n",
      "\t [0] ^ -> E.\n",
      "\t [0] E -> E.-T\n",
      "(14) \"x-(y/x+y/z)/y*.-z\" \n",
      "\t [14] F -> .(E)\n",
      "\t [14] F -> .y\n",
      "\t [14] F -> .-F\n",
      "\t [14] F -> .z\n",
      "\t [2] T -> T*.F\n",
      "\t [14] F -> .x\n",
      "(15) \"x-(y/x+y/z)/y*-.z\" \n",
      "\t [14] F -> -.F\n",
      "\t [15] F -> .z\n",
      "\t [15] F -> .x\n",
      "\t [15] F -> .(E)\n",
      "\t [15] F -> .y\n",
      "\t [15] F -> .-F\n",
      "(16) \"x-(y/x+y/z)/y*-z.\" ACCEPTS\n",
      "\t [2] T -> T.*F\n",
      "\t [2] T -> T./F\n",
      "\t [0] E -> E.+T\n",
      "\t [0] E -> E.-T\n",
      "\t [0] E -> E-T.\n",
      "\t [0] ^ -> E.\n",
      "\t [15] F -> z.\n",
      "\t [14] F -> -F.\n",
      "\t [2] T -> T*F.\n"
     ]
    }
   ],
   "source": [
    "EarleyParser(grammar).parse('x-(y/x+y/z)/y*-z')"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "## grammar: parentheses"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 7,
   "metadata": {
    "collapsed": true
   },
   "outputs": [],
   "source": [
    "grammar = Grammar(\n",
    "    '^ ::= P',\n",
    "    'P ::= ( )',\n",
    "    'P ::= ( P )',\n",
    "    'P ::= P ( )',\n",
    "    'P ::= P ( P )',\n",
    ")"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 8,
   "metadata": {
    "collapsed": false
   },
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "(0) \".()(()())()\" \n",
      "\t [0] ^ -> .P\n",
      "\t [0] P -> .P(P)\n",
      "\t [0] P -> .()\n",
      "\t [0] P -> .P()\n",
      "\t [0] P -> .(P)\n",
      "(1) \"(.)(()())()\" \n",
      "\t [0] P -> (.P)\n",
      "\t [1] P -> .(P)\n",
      "\t [1] P -> .()\n",
      "\t [0] P -> (.)\n",
      "\t [1] P -> .P()\n",
      "\t [1] P -> .P(P)\n",
      "(2) \"().(()())()\" ACCEPTS\n",
      "\t [0] P -> P.(P)\n",
      "\t [0] P -> ().\n",
      "\t [0] P -> P.()\n",
      "\t [0] ^ -> P.\n",
      "(3) \"()(.()())()\" \n",
      "\t [3] P -> .P()\n",
      "\t [3] P -> .P(P)\n",
      "\t [0] P -> P(.)\n",
      "\t [3] P -> .(P)\n",
      "\t [3] P -> .()\n",
      "\t [0] P -> P(.P)\n",
      "(4) \"()((.)())()\" \n",
      "\t [4] P -> .(P)\n",
      "\t [3] P -> (.)\n",
      "\t [3] P -> (.P)\n",
      "\t [4] P -> .P()\n",
      "\t [4] P -> .P(P)\n",
      "\t [4] P -> .()\n",
      "(5) \"()(().())()\" \n",
      "\t [3] P -> P.(P)\n",
      "\t [0] P -> P(P.)\n",
      "\t [3] P -> P.()\n",
      "\t [3] P -> ().\n",
      "(6) \"()(()(.))()\" \n",
      "\t [6] P -> .P()\n",
      "\t [6] P -> .()\n",
      "\t [6] P -> .P(P)\n",
      "\t [6] P -> .(P)\n",
      "\t [3] P -> P(.P)\n",
      "\t [3] P -> P(.)\n",
      "(7) \"()(()().)()\" \n",
      "\t [3] P -> P.(P)\n",
      "\t [0] P -> P(P.)\n",
      "\t [3] P -> P.()\n",
      "\t [3] P -> P().\n",
      "(8) \"()(()()).()\" ACCEPTS\n",
      "\t [0] P -> P(P).\n",
      "\t [0] P -> P.(P)\n",
      "\t [0] P -> P.()\n",
      "\t [0] ^ -> P.\n",
      "(9) \"()(()())(.)\" \n",
      "\t [9] P -> .P(P)\n",
      "\t [9] P -> .()\n",
      "\t [9] P -> .P()\n",
      "\t [0] P -> P(.)\n",
      "\t [9] P -> .(P)\n",
      "\t [0] P -> P(.P)\n",
      "(10) \"()(()())().\" ACCEPTS\n",
      "\t [0] P -> P.(P)\n",
      "\t [0] P -> P().\n",
      "\t [0] P -> P.()\n",
      "\t [0] ^ -> P.\n"
     ]
    }
   ],
   "source": [
    "EarleyParser(grammar).parse('()(()())()')"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {
    "collapsed": true
   },
   "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.0"
  }
 },
 "nbformat": 4,
 "nbformat_minor": 2
}