parsing.ipynb

{
 "metadata": {
  "name": ""
 },
 "nbformat": 3,
 "nbformat_minor": 0,
 "worksheets": [
  {
   "cells": [
    {
     "cell_type": "heading",
     "level": 1,
     "metadata": {},
     "source": [
      "Parsing"
     ]
    },
    {
     "cell_type": "markdown",
     "metadata": {},
     "source": [
      "The `parser` takes a series of tokens from the lexical analysis stage and converts them into instances of the AST nodes in the `astnodes` module."
     ]
    },
    {
     "cell_type": "heading",
     "level": 2,
     "metadata": {},
     "source": [
      "Token stack"
     ]
    },
    {
     "cell_type": "markdown",
     "metadata": {},
     "source": [
      "The token stack allows individual tokens to be popped off the stack and the top-most token to be 'peeked'. It also allows saving positions for later restoration."
     ]
    },
    {
     "cell_type": "code",
     "collapsed": false,
     "input": [
      "import collections"
     ],
     "language": "python",
     "metadata": {},
     "outputs": [],
     "prompt_number": 25
    },
    {
     "cell_type": "code",
     "collapsed": false,
     "input": [
      "class ParseError(Exception):\n",
      "    def __init__(self, message, *tokens):\n",
      "        self.message = message\n",
      "        self.tokens = tokens\n",
      "    \n",
      "    def __str__(self):\n",
      "        if len(self.tokens) == 0:\n",
      "            return self.message\n",
      "        return '{0}-{1}: {2}'.format(self.tokens[0].slice.start, self.tokens[-1].slice.stop-1, self.message)"
     ],
     "language": "python",
     "metadata": {},
     "outputs": [],
     "prompt_number": 26
    },
    {
     "cell_type": "code",
     "collapsed": false,
     "input": [
      "class TokenStack(object):\n",
      "    def __init__(self, tokens):\n",
      "        self._tokens = list(tokens)\n",
      "        self._cursor = 0\n",
      "        self._cursor_stack = []\n",
      "    \n",
      "    def peek(self):\n",
      "        return self._tokens[self._cursor]\n",
      "    \n",
      "    def pop(self):\n",
      "        rv = self.peek()\n",
      "        self._cursor += 1\n",
      "        return rv\n",
      "    \n",
      "    def push_cursor(self):\n",
      "        self._cursor_stack.append(self._cursor)\n",
      "    \n",
      "    def pop_cursor(self):\n",
      "        self._cursor = self._cursor_stack.pop()"
     ],
     "language": "python",
     "metadata": {},
     "outputs": [],
     "prompt_number": 27
    },
    {
     "cell_type": "heading",
     "level": 2,
     "metadata": {},
     "source": [
      "Expression parsing"
     ]
    },
    {
     "cell_type": "code",
     "collapsed": false,
     "input": [
      "class ParseBase(object):\n",
      "    def __init__(self, token_stack):\n",
      "        self.token_stack = token_stack\n",
      "        self.node = self.parse()\n",
      "    \n",
      "    def parse(self):\n",
      "        raise NotImplementedError()\n",
      "    \n",
      "    def pop_expecting(self, type_):\n",
      "        next_token = self.token_stack.pop()\n",
      "        if next_token.type is not type_:\n",
      "            raise ParseError('Unexpected token; was expecting {0}, got {1}'.format(type_, next_token.type), next_token)\n",
      "        return next_token"
     ],
     "language": "python",
     "metadata": {},
     "outputs": [],
     "prompt_number": 28
    },
    {
     "cell_type": "code",
     "collapsed": false,
     "input": [
      "from lexing import TokenType"
     ],
     "language": "python",
     "metadata": {},
     "outputs": [],
     "prompt_number": 29
    },
    {
     "cell_type": "code",
     "collapsed": false,
     "input": [
      "import astnodes"
     ],
     "language": "python",
     "metadata": {},
     "outputs": [],
     "prompt_number": 30
    },
    {
     "cell_type": "code",
     "collapsed": false,
     "input": [
      "class IntegerLiteralExpression(ParseBase):\n",
      "    def parse(self):\n",
      "        int_token = self.pop_expecting(TokenType.integer)\n",
      "        return astnodes.IntegerLiteral(int_token.value)"
     ],
     "language": "python",
     "metadata": {},
     "outputs": [],
     "prompt_number": 31
    },
    {
     "cell_type": "code",
     "collapsed": false,
     "input": [
      "from lexing import lex"
     ],
     "language": "python",
     "metadata": {},
     "outputs": [],
     "prompt_number": 32
    },
    {
     "cell_type": "code",
     "collapsed": false,
     "input": [
      "IntegerLiteralExpression(TokenStack(lex('5'))).node"
     ],
     "language": "python",
     "metadata": {},
     "outputs": [
      {
       "metadata": {},
       "output_type": "pyout",
       "prompt_number": 33,
       "text": [
        "IntegerLiteral(value=5)"
       ]
      }
     ],
     "prompt_number": 33
    },
    {
     "cell_type": "code",
     "collapsed": false,
     "input": [
      "class UnaryOpExpression(ParseBase):\n",
      "    def parse(self):\n",
      "        op_token = self.token_stack.pop()\n",
      "        if op_token.type not in [TokenType.plus, TokenType.minus]:\n",
      "            raise ParseError('Expected unary operator, got {0}'.format(op_token.type), op_token)\n",
      "        rhs_node = Expression(self.token_stack).node\n",
      "        return astnodes.UnaryOpExpression(op_token.value, rhs_node)"
     ],
     "language": "python",
     "metadata": {},
     "outputs": [],
     "prompt_number": 34
    },
    {
     "cell_type": "code",
     "collapsed": false,
     "input": [
      "Expression = IntegerLiteralExpression"
     ],
     "language": "python",
     "metadata": {},
     "outputs": [],
     "prompt_number": 35
    },
    {
     "cell_type": "code",
     "collapsed": false,
     "input": [
      "UnaryOpExpression(TokenStack(lex('-5'))).node"
     ],
     "language": "python",
     "metadata": {},
     "outputs": [
      {
       "metadata": {},
       "output_type": "pyout",
       "prompt_number": 36,
       "text": [
        "UnaryOpExpression(op='-', rhs=IntegerLiteral(value=5))"
       ]
      }
     ],
     "prompt_number": 36
    },
    {
     "cell_type": "code",
     "collapsed": false,
     "input": [
      "class BracketedExpression(ParseBase):\n",
      "    def parse(self):\n",
      "        self.pop_expecting(TokenType.left_paren)\n",
      "        expr_node = Expression(self.token_stack).node\n",
      "        self.pop_expecting(TokenType.right_paren)\n",
      "        return expr_node"
     ],
     "language": "python",
     "metadata": {},
     "outputs": [],
     "prompt_number": 37
    },
    {
     "cell_type": "code",
     "collapsed": false,
     "input": [
      "BracketedExpression(TokenStack(lex('(5)'))).node"
     ],
     "language": "python",
     "metadata": {},
     "outputs": [
      {
       "metadata": {},
       "output_type": "pyout",
       "prompt_number": 38,
       "text": [
        "IntegerLiteral(value=5)"
       ]
      }
     ],
     "prompt_number": 38
    },
    {
     "cell_type": "code",
     "collapsed": false,
     "input": [
      "class PrimaryExpression(ParseBase):\n",
      "    def try_to_parse(self, parser):\n",
      "        \"\"\"Return a tuple node, success indicating the parsed AST node and whether parsing succeeded.\"\"\"\n",
      "        try:\n",
      "            self.token_stack.push_cursor()\n",
      "            return parser(self.token_stack).node, True\n",
      "        except ParseError as err:\n",
      "            # print 'ttp', err\n",
      "            self.token_stack.pop_cursor()\n",
      "            return None, False\n",
      "        \n",
      "    def parse(self):\n",
      "        # print 'prim expr parse'\n",
      "        rv, ok = self.try_to_parse(IntegerLiteralExpression)\n",
      "        # print rv,ok\n",
      "        if ok:\n",
      "            return rv\n",
      "        \n",
      "        # print 'try unary op'\n",
      "        rv, ok = self.try_to_parse(UnaryOpExpression)\n",
      "        if ok:\n",
      "            return rv\n",
      "        \n",
      "        rv, ok = self.try_to_parse(BracketedExpression)\n",
      "        if ok:\n",
      "            return rv\n",
      "        \n",
      "        raise ParseError(\n",
      "                'Expected integer, unary operator or bracket. Got {0}'.format(self.token_stack.peek().type),\n",
      "                self.token_stack.peek())"
     ],
     "language": "python",
     "metadata": {},
     "outputs": [],
     "prompt_number": 39
    },
    {
     "cell_type": "code",
     "collapsed": false,
     "input": [
      "Expression = PrimaryExpression"
     ],
     "language": "python",
     "metadata": {},
     "outputs": [],
     "prompt_number": 40
    },
    {
     "cell_type": "code",
     "collapsed": false,
     "input": [
      "Expression(TokenStack(lex('-(+5)'))).node"
     ],
     "language": "python",
     "metadata": {},
     "outputs": [
      {
       "metadata": {},
       "output_type": "pyout",
       "prompt_number": 41,
       "text": [
        "UnaryOpExpression(op='-', rhs=UnaryOpExpression(op='+', rhs=IntegerLiteral(value=5)))"
       ]
      }
     ],
     "prompt_number": 41
    },
    {
     "cell_type": "heading",
     "level": 2,
     "metadata": {},
     "source": [
      "Binary Operators"
     ]
    },
    {
     "cell_type": "code",
     "collapsed": false,
     "input": [
      "class BinaryOpExpression(ParseBase):\n",
      "    _op_precedence = {\n",
      "        '+': 20, '-': 20,\n",
      "        '*': 30, '/': 30,\n",
      "    }\n",
      "    \n",
      "    def parse(self):\n",
      "        primary = PrimaryExpression(self.token_stack).node\n",
      "        return self.parse_expression_(primary, 0)\n",
      "    \n",
      "    def parse_expression_(self, lhs, min_precedence):\n",
      "        while self.next_is_binary_() and self.precedence_() >= min_precedence:\n",
      "            op_token = self.token_stack.pop()\n",
      "            rhs = PrimaryExpression(self.token_stack).node\n",
      "            while self.next_is_binary_() and self.precedence_() > self.precedence_(op_token):\n",
      "                rhs = self.parse_expression_(rhs, self.precedence_())\n",
      "            lhs = astnodes.BinaryOpExpression(lhs, op_token.value, rhs)\n",
      "        return lhs\n",
      "    \n",
      "    def next_is_binary_(self):\n",
      "        try:\n",
      "            next_token = self.token_stack.peek()\n",
      "        except IndexError:\n",
      "            return False\n",
      "        return next_token.value in BinaryOpExpression._op_precedence\n",
      "    \n",
      "    def precedence_(self, token = None):\n",
      "        token = token or self.token_stack.peek()\n",
      "        return BinaryOpExpression._op_precedence[token.value]"
     ],
     "language": "python",
     "metadata": {},
     "outputs": [],
     "prompt_number": 42
    },
    {
     "cell_type": "code",
     "collapsed": false,
     "input": [
      "Expression = BinaryOpExpression"
     ],
     "language": "python",
     "metadata": {},
     "outputs": [],
     "prompt_number": 43
    },
    {
     "cell_type": "code",
     "collapsed": false,
     "input": [
      "import json"
     ],
     "language": "python",
     "metadata": {},
     "outputs": [],
     "prompt_number": 44
    },
    {
     "cell_type": "code",
     "collapsed": false,
     "input": [
      "if __name__ == \"__main__\":\n",
      "    print json.dumps(Expression(TokenStack(lex('4*5+3*(2+1)'))).node.to_dict(), indent=2)"
     ],
     "language": "python",
     "metadata": {},
     "outputs": [
      {
       "output_type": "stream",
       "stream": "stdout",
       "text": [
        "{\n",
        "  \"lhs\": {\n",
        "    \"lhs\": {\n",
        "      \"type\": \"IntegerLiteral\", \n",
        "      \"value\": 4\n",
        "    }, \n",
        "    \"rhs\": {\n",
        "      \"type\": \"IntegerLiteral\", \n",
        "      \"value\": 5\n",
        "    }, \n",
        "    \"type\": \"BinaryOpExpression\", \n",
        "    \"op\": \"*\"\n",
        "  }, \n",
        "  \"rhs\": {\n",
        "    \"lhs\": {\n",
        "      \"type\": \"IntegerLiteral\", \n",
        "      \"value\": 3\n",
        "    }, \n",
        "    \"rhs\": {\n",
        "      \"lhs\": {\n",
        "        \"type\": \"IntegerLiteral\", \n",
        "        \"value\": 2\n",
        "      }, \n",
        "      \"rhs\": {\n",
        "        \"type\": \"IntegerLiteral\", \n",
        "        \"value\": 1\n",
        "      }, \n",
        "      \"type\": \"BinaryOpExpression\", \n",
        "      \"op\": \"+\"\n",
        "    }, \n",
        "    \"type\": \"BinaryOpExpression\", \n",
        "    \"op\": \"*\"\n",
        "  }, \n",
        "  \"type\": \"BinaryOpExpression\", \n",
        "  \"op\": \"+\"\n",
        "}\n"
       ]
      }
     ],
     "prompt_number": 48
    },
    {
     "cell_type": "code",
     "collapsed": false,
     "input": [],
     "language": "python",
     "metadata": {},
     "outputs": [],
     "prompt_number": 45
    }
   ],
   "metadata": {}
  }
 ]
}