pegbook_chap6.ipynb

{
 "cells": [
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "# 第６章 スモール言語を作る"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 7,
   "metadata": {},
   "outputs": [
    {
     "ename": "ImportError",
     "evalue": "cannot import name 'pegtree' from 'pegtree' (/usr/local/lib/python3.9/site-packages/pegtree/__init__.py)",
     "output_type": "error",
     "traceback": [
      "\u001b[0;31m---------------------------------------------------------------------------\u001b[0m",
      "\u001b[0;31mImportError\u001b[0m                               Traceback (most recent call last)",
      "\u001b[0;32m/var/folders/c3/b3wn97_d6_1f_41g5g627qbh0000gn/T/ipykernel_76630/916179213.py\u001b[0m in \u001b[0;36m<module>\u001b[0;34m\u001b[0m\n\u001b[1;32m      1\u001b[0m \u001b[0;31m# !pip install pegtree\u001b[0m\u001b[0;34m\u001b[0m\u001b[0;34m\u001b[0m\u001b[0m\n\u001b[1;32m      2\u001b[0m \u001b[0;32mimport\u001b[0m \u001b[0mpegtree\u001b[0m \u001b[0;32mas\u001b[0m \u001b[0mpg\u001b[0m\u001b[0;34m\u001b[0m\u001b[0;34m\u001b[0m\u001b[0m\n\u001b[0;32m----> 3\u001b[0;31m \u001b[0;32mfrom\u001b[0m \u001b[0mpegtree\u001b[0m \u001b[0;32mimport\u001b[0m \u001b[0mpegtree\u001b[0m\u001b[0;34m\u001b[0m\u001b[0;34m\u001b[0m\u001b[0m\n\u001b[0m",
      "\u001b[0;31mImportError\u001b[0m: cannot import name 'pegtree' from 'pegtree' (/usr/local/lib/python3.9/site-packages/pegtree/__init__.py)"
     ]
    }
   ],
   "source": [
    "# !pip install pegtree\n",
    "import pegtree as pg\n",
    "from pegtree.colab import peg, pegtree, example"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 6,
   "metadata": {},
   "outputs": [
    {
     "name": "stderr",
     "output_type": "stream",
     "text": [
      "UsageError: Cell magic `%%peg` not found.\n"
     ]
    }
   ],
   "source": [
    "%%peg\n",
    "\n",
    "Program = { // 開式非終端記号 Expression*\n",
    "    #Program\n",
    "} EOF\n",
    "EOF = !. // ファイル終端\n",
    "\n",
    "Expression =\n",
    "    / FuncDecl // 関数定義\n",
    "    / VarDecl // 変数定義\n",
    "    / IfExpr  // if 式\n",
    "    / Binary  // 二項演算\n"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    " import pegtree as pg\n",
    "peg = pg.grammar('chibi.pegtree') parser = pg.generate(peg)"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "## 6.2.5 パーザの生成"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 9,
   "metadata": {},
   "outputs": [],
   "source": [
    "import pegtree as pg\n",
    "peg = pg.grammar('chibi.pegtree') \n",
    "parser = pg.generate(peg)"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "## トランスコンパイラ\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 16,
   "metadata": {},
   "outputs": [],
   "source": [
    "class Visitor(object):\n",
    "    def visit(self, tree):\n",
    "        tag = tree.getTag()\n",
    "        name = f'accept{tag}'\n",
    "        if hasattr(self, name): # accept メソッドがあるか調べる\n",
    "            # メソッド名からメソッドを得る \n",
    "            acceptMethod = getattr(self, name) \n",
    "            return acceptMethod(tree)\n",
    "        print(f'TODO: accept{tag}') \n",
    "        return None\n",
    "\n",
    "class Compiler(Visitor): # Visitor クラスの継承 \n",
    "    def __init__(self):\n",
    "        self.buffers = []\n",
    "        peg = pg.grammar('chibi.pegtree') \n",
    "        self.parser = pg.generate(peg)\n",
    "\n",
    "    def compile(self, source):\n",
    "        tree = self.parser(source) # 構文木に交換\n",
    "        self.buffers = [] # バッファの初期化\n",
    "        self.visit(tree)\n",
    "        return ''.join(self.buffers) # バッファを連結してソースコードにまとめる\n",
    "\n",
    "    def push(self, s): # コード片をバッファに追加\n",
    "        self.buffers.append(s)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 17,
   "metadata": {},
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "TODO: acceptProgram\n",
      "\n"
     ]
    }
   ],
   "source": [
    "c = Compiler()\n",
    "code = c.compile('1+2*3') \n",
    "print(code)"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "### 各ノードのコード変換\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 26,
   "metadata": {},
   "outputs": [],
   "source": [
    "BUILTIN_FUNCTIONS = { \n",
    "    'print': 'console.log'\n",
    "}\n",
    "\n",
    "class Compiler(Visitor): # Visitor クラスの継承 \n",
    "    def __init__(self):\n",
    "        self.buffers = []\n",
    "        peg = pg.grammar('chibi.pegtree') \n",
    "        self.parser = pg.generate(peg)\n",
    "\n",
    "    def compile(self, source):\n",
    "        tree = self.parser(source) # 構文木に交換\n",
    "        self.buffers = [] # バッファの初期化\n",
    "        self.visit(tree)\n",
    "        return ''.join(self.buffers) # バッファを連結してソースコードにまとめる\n",
    "\n",
    "    def push(self, s): # コード片をバッファに追加\n",
    "        self.buffers.append(s)\n",
    "\n",
    "    def acceptProgram(self, tree):\n",
    "        for child in tree: # 子ノードのリスト\n",
    "            self.visit(child) # 子ノードの変換 \n",
    "            self.push('\\n') # 改行をバッファに追加\n",
    "\n",
    "    def acceptInt(self, tree):\n",
    "        v = tree.getToken()\n",
    "        self.push(v)\n",
    "\n",
    "    def acceptName(self, tree):\n",
    "        name = tree.getToken()\n",
    "        self.push(name)\n",
    "\n",
    "    def acceptAdd(self, tree): \n",
    "        self.push('(')\n",
    "        self.visit(tree[0]) \n",
    "        self.push('+') \n",
    "        self.visit(tree[1]) \n",
    "        self.push(')')\n",
    "\n",
    "    def acceptEq(self, tree): \n",
    "        self.push('(')\n",
    "        self.visit(tree[0]) \n",
    "        self.push('===') \n",
    "        self.visit(tree[1]) \n",
    "        self.push(') ? 1 : 0')\n",
    "\n",
    "    def acceptFuncApp(self, tree):\n",
    "        f = tree.getToken(0)\n",
    "        self.push(BUILTIN_FUNCTIONS.get(f, f)) \n",
    "        self.push('(')\n",
    "        self.visit(tree[1])\n",
    "        self.push(')')\n",
    "    \n",
    "    def accepterr(self, tree):\n",
    "        print(repr(tree))\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 27,
   "metadata": {},
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "Syntax Error ((unknown source):2:-1+0)\n",
      "\n",
      "\n",
      "\n"
     ]
    }
   ],
   "source": [
    "c = Compiler()\n",
    "code = c.compile('''\n",
    "f(x) = x+1\n",
    "print(x)\n",
    "''')\n",
    "print(code)"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "## インタプリタ\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 28,
   "metadata": {},
   "outputs": [],
   "source": [
    "class Interpreter(Visitor):\n",
    "    def __init__(self):\n",
    "        self.env = {} # 空の環境を用意する \n",
    "        peg = pg.grammar('chibi.pegtree') \n",
    "        self.parser = pg.generate(peg)\n",
    "    \n",
    "    def eval(self, source):\n",
    "        tree = self.parser(source)\n",
    "        return self.visit(tree)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 29,
   "metadata": {},
   "outputs": [
    {
     "ename": "KeyboardInterrupt",
     "evalue": "Interrupted by user",
     "output_type": "error",
     "traceback": [
      "\u001b[0;31m---------------------------------------------------------------------------\u001b[0m",
      "\u001b[0;31mKeyboardInterrupt\u001b[0m                         Traceback (most recent call last)",
      "\u001b[0;32m/var/folders/c3/b3wn97_d6_1f_41g5g627qbh0000gn/T/ipykernel_76630/4020553082.py\u001b[0m in \u001b[0;36m<module>\u001b[0;34m\u001b[0m\n\u001b[1;32m      1\u001b[0m \u001b[0mchibi\u001b[0m \u001b[0;34m=\u001b[0m \u001b[0mInterpreter\u001b[0m\u001b[0;34m(\u001b[0m\u001b[0;34m)\u001b[0m\u001b[0;34m\u001b[0m\u001b[0;34m\u001b[0m\u001b[0m\n\u001b[0;32m----> 2\u001b[0;31m \u001b[0msource\u001b[0m \u001b[0;34m=\u001b[0m \u001b[0minput\u001b[0m\u001b[0;34m(\u001b[0m\u001b[0;34m'>>> '\u001b[0m\u001b[0;34m)\u001b[0m\u001b[0;34m\u001b[0m\u001b[0;34m\u001b[0m\u001b[0m\n\u001b[0m\u001b[1;32m      3\u001b[0m \u001b[0;32mwhile\u001b[0m \u001b[0msource\u001b[0m \u001b[0;34m!=\u001b[0m \u001b[0;34m''\u001b[0m\u001b[0;34m:\u001b[0m\u001b[0;34m\u001b[0m\u001b[0;34m\u001b[0m\u001b[0m\n\u001b[1;32m      4\u001b[0m     \u001b[0mresult\u001b[0m \u001b[0;34m=\u001b[0m \u001b[0mchibi\u001b[0m\u001b[0;34m.\u001b[0m\u001b[0meval\u001b[0m\u001b[0;34m(\u001b[0m\u001b[0msource\u001b[0m\u001b[0;34m)\u001b[0m\u001b[0;34m\u001b[0m\u001b[0;34m\u001b[0m\u001b[0m\n\u001b[1;32m      5\u001b[0m     \u001b[0mprint\u001b[0m\u001b[0;34m(\u001b[0m\u001b[0mresult\u001b[0m\u001b[0;34m)\u001b[0m\u001b[0;34m\u001b[0m\u001b[0;34m\u001b[0m\u001b[0m\n",
      "\u001b[0;32m/usr/local/lib/python3.9/site-packages/ipykernel/kernelbase.py\u001b[0m in \u001b[0;36mraw_input\u001b[0;34m(self, prompt)\u001b[0m\n\u001b[1;32m   1005\u001b[0m                 \u001b[0;34m\"raw_input was called, but this frontend does not support input requests.\"\u001b[0m\u001b[0;34m\u001b[0m\u001b[0;34m\u001b[0m\u001b[0m\n\u001b[1;32m   1006\u001b[0m             )\n\u001b[0;32m-> 1007\u001b[0;31m         return self._input_request(\n\u001b[0m\u001b[1;32m   1008\u001b[0m             \u001b[0mstr\u001b[0m\u001b[0;34m(\u001b[0m\u001b[0mprompt\u001b[0m\u001b[0;34m)\u001b[0m\u001b[0;34m,\u001b[0m\u001b[0;34m\u001b[0m\u001b[0;34m\u001b[0m\u001b[0m\n\u001b[1;32m   1009\u001b[0m             \u001b[0mself\u001b[0m\u001b[0;34m.\u001b[0m\u001b[0m_parent_ident\u001b[0m\u001b[0;34m[\u001b[0m\u001b[0;34m\"shell\"\u001b[0m\u001b[0;34m]\u001b[0m\u001b[0;34m,\u001b[0m\u001b[0;34m\u001b[0m\u001b[0;34m\u001b[0m\u001b[0m\n",
      "\u001b[0;32m/usr/local/lib/python3.9/site-packages/ipykernel/kernelbase.py\u001b[0m in \u001b[0;36m_input_request\u001b[0;34m(self, prompt, ident, parent, password)\u001b[0m\n\u001b[1;32m   1050\u001b[0m             \u001b[0;32mexcept\u001b[0m \u001b[0mKeyboardInterrupt\u001b[0m\u001b[0;34m:\u001b[0m\u001b[0;34m\u001b[0m\u001b[0;34m\u001b[0m\u001b[0m\n\u001b[1;32m   1051\u001b[0m                 \u001b[0;31m# re-raise KeyboardInterrupt, to truncate traceback\u001b[0m\u001b[0;34m\u001b[0m\u001b[0;34m\u001b[0m\u001b[0m\n\u001b[0;32m-> 1052\u001b[0;31m                 \u001b[0;32mraise\u001b[0m \u001b[0mKeyboardInterrupt\u001b[0m\u001b[0;34m(\u001b[0m\u001b[0;34m\"Interrupted by user\"\u001b[0m\u001b[0;34m)\u001b[0m \u001b[0;32mfrom\u001b[0m \u001b[0;32mNone\u001b[0m\u001b[0;34m\u001b[0m\u001b[0;34m\u001b[0m\u001b[0m\n\u001b[0m\u001b[1;32m   1053\u001b[0m             \u001b[0;32mexcept\u001b[0m \u001b[0mException\u001b[0m\u001b[0;34m:\u001b[0m\u001b[0;34m\u001b[0m\u001b[0;34m\u001b[0m\u001b[0m\n\u001b[1;32m   1054\u001b[0m                 \u001b[0mself\u001b[0m\u001b[0;34m.\u001b[0m\u001b[0mlog\u001b[0m\u001b[0;34m.\u001b[0m\u001b[0mwarning\u001b[0m\u001b[0;34m(\u001b[0m\u001b[0;34m\"Invalid Message:\"\u001b[0m\u001b[0;34m,\u001b[0m \u001b[0mexc_info\u001b[0m\u001b[0;34m=\u001b[0m\u001b[0;32mTrue\u001b[0m\u001b[0;34m)\u001b[0m\u001b[0;34m\u001b[0m\u001b[0;34m\u001b[0m\u001b[0m\n",
      "\u001b[0;31mKeyboardInterrupt\u001b[0m: Interrupted by user"
     ]
    }
   ],
   "source": [
    "chibi = Interpreter() \n",
    "source = input('>>> ') \n",
    "while source != '':\n",
    "    result = chibi.eval(source) \n",
    "    print(result)\n",
    "source = input('>>> ')"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 30,
   "metadata": {},
   "outputs": [],
   "source": [
    "class Interpreter(Visitor):\n",
    "    def __init__(self):\n",
    "        self.env = {} # 空の環境を用意する \n",
    "        peg = pg.grammar('chibi.pegtree') \n",
    "        self.parser = pg.generate(peg)\n",
    "    \n",
    "    def eval(self, source):\n",
    "        tree = self.parser(source)\n",
    "        return self.visit(tree)\n",
    "\n",
    "    def acceptProgram(self, tree):\n",
    "        result = None\n",
    "        for child in tree:\n",
    "            result = self.visit(child)\n",
    "        return result\n",
    "    \n",
    "    def acceptInt(self, tree):\n",
    "        token = tree.getToken()\n",
    "        return int(token)\n",
    "\n",
    "    def acceptAdd(self, tree):\n",
    "        v0 = self.visit(tree[0])\n",
    "        v1 = self.visit(tree[1])\n",
    "        return v0 + v1\n",
    "\n",
    "    def acceptEq(self, tree):\n",
    "        v0 = self.visit(tree[0])\n",
    "        v1 = self.visit(tree[1])\n",
    "        return 1 if v0 == v1 else 0\n",
    "\n",
    "    def acceptIfExpr(self, tree):\n",
    "        v0 = self.visit(tree[0])\n",
    "        if v0 != 0:\n",
    "            return self.visit(tree[1])\n",
    "        else:\n",
    "            return self.visit(tree[2])\n",
    "\n",
    "    def acceptVarDecl(self, tree):\n",
    "        v = self.visit(tree[1])\n",
    "        x = str(tree[0])\n",
    "        self.env[x] = v\n",
    "        return v\n",
    "    \n",
    "    def acceptName(self, t):\n",
    "        x = t.getToken()\n",
    "        if x in self.env:\n",
    "            return self.env[x]\n",
    "        else:\n",
    "            raise NameError(x)\n",
    "\n",
    "    def acceptFuncDecl(self, tree):\n",
    "        f = tree.getToken(0)\n",
    "        x = tree.getToken(1)\n",
    "        e = tree.get(2)\n",
    "        self.env[f] = (x, e)\n",
    "        return self.env[f]\n",
    "\n",
    "    def acceptFuncApp(self, tree):\n",
    "        f = tree.getToken(0) # 関数名を得る\n",
    "        v = self.visit(tree[1]) # 引数を先に評価\n",
    "        x, e = self.env[f] # 関数名から引数名と関数式を取り出す \n",
    "        self.env[x] = v # 環境xをvにする\n",
    "        v = self.visit(e) # 関数式を評価\n",
    "        return v"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 32,
   "metadata": {},
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "TODO: accepterr\n",
      "None\n"
     ]
    }
   ],
   "source": [
    "source = '''\n",
    "fib(n) = if n < 3 then 1 else fib(n-1)+fib(n-2) \n",
    "fib(4)\n",
    "'''\n",
    "c = Interpreter()\n",
    "print(c.eval(source))"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": []
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": []
  }
 ],
 "metadata": {
  "interpreter": {
   "hash": "aee8b7b246df8f9039afb4144a1f6fd8d2ca17a180786b69acc140d282b71a49"
  },
  "kernelspec": {
   "display_name": "Python 3.9.7 64-bit",
   "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.9.7"
  },
  "orig_nbformat": 4
 },
 "nbformat": 4,
 "nbformat_minor": 2
}