pegbook_chap5.ipynb

{
 "cells": [
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "# 第５章 計算機を作る\n",
    "\n"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "## 5.1.2 スタックマシン"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 1,
   "metadata": {},
   "outputs": [
    {
     "data": {
      "text/plain": [
       "15"
      ]
     },
     "execution_count": 1,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "def calc(expression: str):\n",
    "    # 空白で分割して字句にする \n",
    "    tokens = expression.split() \n",
    "    stack = []\n",
    "    for token in tokens:\n",
    "        if token.isdigit():\n",
    "            # 数値はスタックに push する \n",
    "            stack.append(int(token)) \n",
    "            continue\n",
    "        # 数値でないなら，演算子として処理する \n",
    "        x = stack.pop()\n",
    "        y = stack.pop()\n",
    "        if token == '+':\n",
    "            stack.append(x+y) \n",
    "        elif token == '*':\n",
    "            stack.append(x*y)\n",
    "    return stack.pop()\n",
    "\n",
    "calc('1 2 + 2 3 + *')\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 2,
   "metadata": {},
   "outputs": [],
   "source": [
    "# !pip install pegtree\n",
    "import pegtree as pg\n",
    "from pegtree.colab import peg, pegtree, example"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "構文木を表示するためには、graphviz があらかじめインストールされている必要がある。"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 3,
   "metadata": {},
   "outputs": [
    {
     "data": {
      "text/html": [
       "<b>Expr</b> 1+2+3<span style=\"background-color:#FFCACA;\"></span>"
      ],
      "text/plain": [
       "<IPython.core.display.HTML object>"
      ]
     },
     "metadata": {},
     "output_type": "display_data"
    },
    {
     "data": {
      "image/svg+xml": "<svg xmlns=\"http://www.w3.org/2000/svg\" xmlns:xlink=\"http://www.w3.org/1999/xlink\" width=\"206pt\" height=\"202pt\" viewBox=\"0.00 0.00 206.00 202.00\">\n<g id=\"graph0\" class=\"graph\" transform=\"scale(1 1) rotate(0) translate(4 198)\">\n<title>tree</title>\n<polygon fill=\"white\" stroke=\"transparent\" points=\"-4,4 -4,-198 202,-198 202,4 -4,4\"/>\n<!-- n1 -->\n<g id=\"node1\" class=\"node\">\n<title>n1</title>\n<ellipse fill=\"none\" stroke=\"black\" cx=\"99\" cy=\"-176\" rx=\"27\" ry=\"18\"/>\n<text text-anchor=\"middle\" x=\"99\" y=\"-172.9\" font-family=\"Meiryo UI\" font-size=\"12.00\">#</text>\n</g>\n<!-- n2 -->\n<g id=\"node2\" class=\"node\">\n<title>n2</title>\n<ellipse fill=\"none\" stroke=\"black\" cx=\"27\" cy=\"-91\" rx=\"27\" ry=\"18\"/>\n<text text-anchor=\"middle\" x=\"27\" y=\"-87.9\" font-family=\"Meiryo UI\" font-size=\"12.00\">#Int</text>\n</g>\n<!-- n1&#45;&gt;n2 -->\n<g id=\"edge2\" class=\"edge\">\n<title>n1-&gt;n2</title>\n<path fill=\"none\" stroke=\"black\" d=\"M86.13,-160.16C75.14,-147.49 59.16,-129.08 46.59,-114.58\"/>\n<polygon fill=\"black\" stroke=\"black\" points=\"49.2,-112.25 40,-106.99 43.91,-116.84 49.2,-112.25\"/>\n<text text-anchor=\"middle\" x=\"71.5\" y=\"-130.4\" font-family=\"Times,serif\" font-size=\"12.00\">0</text>\n</g>\n<!-- n3 -->\n<g id=\"node4\" class=\"node\">\n<title>n3</title>\n<ellipse fill=\"none\" stroke=\"black\" cx=\"99\" cy=\"-91\" rx=\"27\" ry=\"18\"/>\n<text text-anchor=\"middle\" x=\"99\" y=\"-87.9\" font-family=\"Meiryo UI\" font-size=\"12.00\">#Int</text>\n</g>\n<!-- n1&#45;&gt;n3 -->\n<g id=\"edge4\" class=\"edge\">\n<title>n1-&gt;n3</title>\n<path fill=\"none\" stroke=\"black\" d=\"M99,-157.8C99,-146.67 99,-131.94 99,-119.24\"/>\n<polygon fill=\"black\" stroke=\"black\" points=\"102.5,-119.18 99,-109.18 95.5,-119.18 102.5,-119.18\"/>\n<text text-anchor=\"middle\" x=\"102.5\" y=\"-130.4\" font-family=\"Times,serif\" font-size=\"12.00\">1</text>\n</g>\n<!-- n4 -->\n<g id=\"node6\" class=\"node\">\n<title>n4</title>\n<ellipse fill=\"none\" stroke=\"black\" cx=\"171\" cy=\"-91\" rx=\"27\" ry=\"18\"/>\n<text text-anchor=\"middle\" x=\"171\" y=\"-87.9\" font-family=\"Meiryo UI\" font-size=\"12.00\">#Int</text>\n</g>\n<!-- n1&#45;&gt;n4 -->\n<g id=\"edge6\" class=\"edge\">\n<title>n1-&gt;n4</title>\n<path fill=\"none\" stroke=\"black\" d=\"M111.87,-160.16C122.86,-147.49 138.84,-129.08 151.41,-114.58\"/>\n<polygon fill=\"black\" stroke=\"black\" points=\"154.09,-116.84 158,-106.99 148.8,-112.25 154.09,-116.84\"/>\n<text text-anchor=\"middle\" x=\"142.5\" y=\"-130.4\" font-family=\"Times,serif\" font-size=\"12.00\">2</text>\n</g>\n<!-- c2 -->\n<g id=\"node3\" class=\"node\">\n<title>c2</title>\n<polygon fill=\"none\" stroke=\"black\" points=\"54,-36 0,-36 0,0 54,0 54,-36\"/>\n<text text-anchor=\"middle\" x=\"27\" y=\"-14.9\" font-family=\"monospace\" font-size=\"12.00\" fill=\"blue\">'1'</text>\n</g>\n<!-- n2&#45;&gt;c2 -->\n<g id=\"edge1\" class=\"edge\">\n<title>n2-&gt;c2</title>\n<path fill=\"none\" stroke=\"black\" d=\"M27,-72.81C27,-64.79 27,-55.05 27,-46.07\"/>\n<polygon fill=\"black\" stroke=\"black\" points=\"30.5,-46.03 27,-36.03 23.5,-46.03 30.5,-46.03\"/>\n</g>\n<!-- c3 -->\n<g id=\"node5\" class=\"node\">\n<title>c3</title>\n<polygon fill=\"none\" stroke=\"black\" points=\"126,-36 72,-36 72,0 126,0 126,-36\"/>\n<text text-anchor=\"middle\" x=\"99\" y=\"-14.9\" font-family=\"monospace\" font-size=\"12.00\" fill=\"blue\">'2'</text>\n</g>\n<!-- n3&#45;&gt;c3 -->\n<g id=\"edge3\" class=\"edge\">\n<title>n3-&gt;c3</title>\n<path fill=\"none\" stroke=\"black\" d=\"M99,-72.81C99,-64.79 99,-55.05 99,-46.07\"/>\n<polygon fill=\"black\" stroke=\"black\" points=\"102.5,-46.03 99,-36.03 95.5,-46.03 102.5,-46.03\"/>\n</g>\n<!-- c4 -->\n<g id=\"node7\" class=\"node\">\n<title>c4</title>\n<polygon fill=\"none\" stroke=\"black\" points=\"198,-36 144,-36 144,0 198,0 198,-36\"/>\n<text text-anchor=\"middle\" x=\"171\" y=\"-14.9\" font-family=\"monospace\" font-size=\"12.00\" fill=\"blue\">'3'</text>\n</g>\n<!-- n4&#45;&gt;c4 -->\n<g id=\"edge5\" class=\"edge\">\n<title>n4-&gt;c4</title>\n<path fill=\"none\" stroke=\"black\" d=\"M171,-72.81C171,-64.79 171,-55.05 171,-46.07\"/>\n<polygon fill=\"black\" stroke=\"black\" points=\"174.5,-46.03 171,-36.03 167.5,-46.03 174.5,-46.03\"/>\n</g>\n</g>\n</svg>",
      "text/plain": [
       "<IPython.core.display.SVG object>"
      ]
     },
     "metadata": {},
     "output_type": "display_data"
    }
   ],
   "source": [
    "%%peg\n",
    "Expr = Prod (\"+\" Prod)*\n",
    "Prod = Value (\"*\" Value)*\n",
    "Value = { [0-9]+ #Int } _\n",
    "\n",
    "example Expr 1+2+3"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 4,
   "metadata": {},
   "outputs": [
    {
     "data": {
      "text/html": [
       "<b>Expr</b> 1+2+3<span style=\"background-color:#FFCACA;\"></span>"
      ],
      "text/plain": [
       "<IPython.core.display.HTML object>"
      ]
     },
     "metadata": {},
     "output_type": "display_data"
    },
    {
     "data": {
      "image/svg+xml": "<svg xmlns=\"http://www.w3.org/2000/svg\" xmlns:xlink=\"http://www.w3.org/1999/xlink\" width=\"206pt\" height=\"287pt\" viewBox=\"0.00 0.00 206.00 287.00\">\n<g id=\"graph0\" class=\"graph\" transform=\"scale(1 1) rotate(0) translate(4 283)\">\n<title>tree</title>\n<polygon fill=\"white\" stroke=\"transparent\" points=\"-4,4 -4,-283 202,-283 202,4 -4,4\"/>\n<!-- n1 -->\n<g id=\"node1\" class=\"node\">\n<title>n1</title>\n<ellipse fill=\"none\" stroke=\"black\" cx=\"99\" cy=\"-261\" rx=\"27.9\" ry=\"18\"/>\n<text text-anchor=\"middle\" x=\"99\" y=\"-257.9\" font-family=\"Meiryo UI\" font-size=\"12.00\">#Add</text>\n</g>\n<!-- n2 -->\n<g id=\"node2\" class=\"node\">\n<title>n2</title>\n<ellipse fill=\"none\" stroke=\"black\" cx=\"27\" cy=\"-176\" rx=\"27\" ry=\"18\"/>\n<text text-anchor=\"middle\" x=\"27\" y=\"-172.9\" font-family=\"Meiryo UI\" font-size=\"12.00\">#Mul</text>\n</g>\n<!-- n1&#45;&gt;n2 -->\n<g id=\"edge3\" class=\"edge\">\n<title>n1-&gt;n2</title>\n<path fill=\"none\" stroke=\"black\" d=\"M85.79,-244.78C74.87,-232.18 59.18,-214.09 46.76,-199.77\"/>\n<polygon fill=\"black\" stroke=\"black\" points=\"49.08,-197.11 39.88,-191.85 43.79,-201.7 49.08,-197.11\"/>\n<text text-anchor=\"middle\" x=\"71.5\" y=\"-215.4\" font-family=\"Times,serif\" font-size=\"12.00\">0</text>\n</g>\n<!-- n4 -->\n<g id=\"node5\" class=\"node\">\n<title>n4</title>\n<ellipse fill=\"none\" stroke=\"black\" cx=\"99\" cy=\"-176\" rx=\"27\" ry=\"18\"/>\n<text text-anchor=\"middle\" x=\"99\" y=\"-172.9\" font-family=\"Meiryo UI\" font-size=\"12.00\">#Mul</text>\n</g>\n<!-- n1&#45;&gt;n4 -->\n<g id=\"edge6\" class=\"edge\">\n<title>n1-&gt;n4</title>\n<path fill=\"none\" stroke=\"black\" d=\"M99,-242.8C99,-231.67 99,-216.94 99,-204.24\"/>\n<polygon fill=\"black\" stroke=\"black\" points=\"102.5,-204.18 99,-194.18 95.5,-204.18 102.5,-204.18\"/>\n<text text-anchor=\"middle\" x=\"102.5\" y=\"-215.4\" font-family=\"Times,serif\" font-size=\"12.00\">1</text>\n</g>\n<!-- n6 -->\n<g id=\"node8\" class=\"node\">\n<title>n6</title>\n<ellipse fill=\"none\" stroke=\"black\" cx=\"171\" cy=\"-176\" rx=\"27\" ry=\"18\"/>\n<text text-anchor=\"middle\" x=\"171\" y=\"-172.9\" font-family=\"Meiryo UI\" font-size=\"12.00\">#Mul</text>\n</g>\n<!-- n1&#45;&gt;n6 -->\n<g id=\"edge9\" class=\"edge\">\n<title>n1-&gt;n6</title>\n<path fill=\"none\" stroke=\"black\" d=\"M112.21,-244.78C123.13,-232.18 138.82,-214.09 151.24,-199.77\"/>\n<polygon fill=\"black\" stroke=\"black\" points=\"154.21,-201.7 158.12,-191.85 148.92,-197.11 154.21,-201.7\"/>\n<text text-anchor=\"middle\" x=\"142.5\" y=\"-215.4\" font-family=\"Times,serif\" font-size=\"12.00\">2</text>\n</g>\n<!-- n3 -->\n<g id=\"node3\" class=\"node\">\n<title>n3</title>\n<ellipse fill=\"none\" stroke=\"black\" cx=\"27\" cy=\"-91\" rx=\"27\" ry=\"18\"/>\n<text text-anchor=\"middle\" x=\"27\" y=\"-87.9\" font-family=\"Meiryo UI\" font-size=\"12.00\">#Int</text>\n</g>\n<!-- n2&#45;&gt;n3 -->\n<g id=\"edge2\" class=\"edge\">\n<title>n2-&gt;n3</title>\n<path fill=\"none\" stroke=\"black\" d=\"M27,-157.8C27,-146.67 27,-131.94 27,-119.24\"/>\n<polygon fill=\"black\" stroke=\"black\" points=\"30.5,-119.18 27,-109.18 23.5,-119.18 30.5,-119.18\"/>\n<text text-anchor=\"middle\" x=\"30.5\" y=\"-130.4\" font-family=\"Times,serif\" font-size=\"12.00\">0</text>\n</g>\n<!-- c3 -->\n<g id=\"node4\" class=\"node\">\n<title>c3</title>\n<polygon fill=\"none\" stroke=\"black\" points=\"54,-36 0,-36 0,0 54,0 54,-36\"/>\n<text text-anchor=\"middle\" x=\"27\" y=\"-14.9\" font-family=\"monospace\" font-size=\"12.00\" fill=\"blue\">'1'</text>\n</g>\n<!-- n3&#45;&gt;c3 -->\n<g id=\"edge1\" class=\"edge\">\n<title>n3-&gt;c3</title>\n<path fill=\"none\" stroke=\"black\" d=\"M27,-72.81C27,-64.79 27,-55.05 27,-46.07\"/>\n<polygon fill=\"black\" stroke=\"black\" points=\"30.5,-46.03 27,-36.03 23.5,-46.03 30.5,-46.03\"/>\n</g>\n<!-- n5 -->\n<g id=\"node6\" class=\"node\">\n<title>n5</title>\n<ellipse fill=\"none\" stroke=\"black\" cx=\"99\" cy=\"-91\" rx=\"27\" ry=\"18\"/>\n<text text-anchor=\"middle\" x=\"99\" y=\"-87.9\" font-family=\"Meiryo UI\" font-size=\"12.00\">#Int</text>\n</g>\n<!-- n4&#45;&gt;n5 -->\n<g id=\"edge5\" class=\"edge\">\n<title>n4-&gt;n5</title>\n<path fill=\"none\" stroke=\"black\" d=\"M99,-157.8C99,-146.67 99,-131.94 99,-119.24\"/>\n<polygon fill=\"black\" stroke=\"black\" points=\"102.5,-119.18 99,-109.18 95.5,-119.18 102.5,-119.18\"/>\n<text text-anchor=\"middle\" x=\"102.5\" y=\"-130.4\" font-family=\"Times,serif\" font-size=\"12.00\">0</text>\n</g>\n<!-- c5 -->\n<g id=\"node7\" class=\"node\">\n<title>c5</title>\n<polygon fill=\"none\" stroke=\"black\" points=\"126,-36 72,-36 72,0 126,0 126,-36\"/>\n<text text-anchor=\"middle\" x=\"99\" y=\"-14.9\" font-family=\"monospace\" font-size=\"12.00\" fill=\"blue\">'2'</text>\n</g>\n<!-- n5&#45;&gt;c5 -->\n<g id=\"edge4\" class=\"edge\">\n<title>n5-&gt;c5</title>\n<path fill=\"none\" stroke=\"black\" d=\"M99,-72.81C99,-64.79 99,-55.05 99,-46.07\"/>\n<polygon fill=\"black\" stroke=\"black\" points=\"102.5,-46.03 99,-36.03 95.5,-46.03 102.5,-46.03\"/>\n</g>\n<!-- n7 -->\n<g id=\"node9\" class=\"node\">\n<title>n7</title>\n<ellipse fill=\"none\" stroke=\"black\" cx=\"171\" cy=\"-91\" rx=\"27\" ry=\"18\"/>\n<text text-anchor=\"middle\" x=\"171\" y=\"-87.9\" font-family=\"Meiryo UI\" font-size=\"12.00\">#Int</text>\n</g>\n<!-- n6&#45;&gt;n7 -->\n<g id=\"edge8\" class=\"edge\">\n<title>n6-&gt;n7</title>\n<path fill=\"none\" stroke=\"black\" d=\"M171,-157.8C171,-146.67 171,-131.94 171,-119.24\"/>\n<polygon fill=\"black\" stroke=\"black\" points=\"174.5,-119.18 171,-109.18 167.5,-119.18 174.5,-119.18\"/>\n<text text-anchor=\"middle\" x=\"174.5\" y=\"-130.4\" font-family=\"Times,serif\" font-size=\"12.00\">0</text>\n</g>\n<!-- c7 -->\n<g id=\"node10\" class=\"node\">\n<title>c7</title>\n<polygon fill=\"none\" stroke=\"black\" points=\"198,-36 144,-36 144,0 198,0 198,-36\"/>\n<text text-anchor=\"middle\" x=\"171\" y=\"-14.9\" font-family=\"monospace\" font-size=\"12.00\" fill=\"blue\">'3'</text>\n</g>\n<!-- n7&#45;&gt;c7 -->\n<g id=\"edge7\" class=\"edge\">\n<title>n7-&gt;c7</title>\n<path fill=\"none\" stroke=\"black\" d=\"M171,-72.81C171,-64.79 171,-55.05 171,-46.07\"/>\n<polygon fill=\"black\" stroke=\"black\" points=\"174.5,-46.03 171,-36.03 167.5,-46.03 174.5,-46.03\"/>\n</g>\n</g>\n</svg>",
      "text/plain": [
       "<IPython.core.display.SVG object>"
      ]
     },
     "metadata": {},
     "output_type": "display_data"
    }
   ],
   "source": [
    "%%peg\n",
    "\n",
    "Expr = { Prod (\"+\" Prod)* #Add }\n",
    "Prod = { Value (\"*\" Value)* #Mul }\n",
    "Value = { [0-9]+ #Int } _\n",
    "\n",
    "example Expr 1+2+3"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 6,
   "metadata": {},
   "outputs": [
    {
     "data": {
      "text/html": [
       "<b>Expr</b> 1+2+3<span style=\"background-color:#FFCACA;\"></span>"
      ],
      "text/plain": [
       "<IPython.core.display.HTML object>"
      ]
     },
     "metadata": {},
     "output_type": "display_data"
    },
    {
     "data": {
      "image/svg+xml": "<svg xmlns=\"http://www.w3.org/2000/svg\" xmlns:xlink=\"http://www.w3.org/1999/xlink\" width=\"206pt\" height=\"287pt\" viewBox=\"0.00 0.00 206.00 287.00\">\n<g id=\"graph0\" class=\"graph\" transform=\"scale(1 1) rotate(0) translate(4 283)\">\n<title>tree</title>\n<polygon fill=\"white\" stroke=\"transparent\" points=\"-4,4 -4,-283 202,-283 202,4 -4,4\"/>\n<!-- n1 -->\n<g id=\"node1\" class=\"node\">\n<title>n1</title>\n<ellipse fill=\"none\" stroke=\"black\" cx=\"134\" cy=\"-261\" rx=\"27.9\" ry=\"18\"/>\n<text text-anchor=\"middle\" x=\"134\" y=\"-257.9\" font-family=\"Meiryo UI\" font-size=\"12.00\">#Add</text>\n</g>\n<!-- n2 -->\n<g id=\"node2\" class=\"node\">\n<title>n2</title>\n<ellipse fill=\"none\" stroke=\"black\" cx=\"98\" cy=\"-176\" rx=\"27.9\" ry=\"18\"/>\n<text text-anchor=\"middle\" x=\"98\" y=\"-172.9\" font-family=\"Meiryo UI\" font-size=\"12.00\">#Add</text>\n</g>\n<!-- n1&#45;&gt;n2 -->\n<g id=\"edge5\" class=\"edge\">\n<title>n1-&gt;n2</title>\n<path fill=\"none\" stroke=\"black\" d=\"M126.89,-243.6C121.89,-232.08 115.1,-216.43 109.36,-203.19\"/>\n<polygon fill=\"black\" stroke=\"black\" points=\"112.41,-201.43 105.22,-193.65 105.99,-204.22 112.41,-201.43\"/>\n<text text-anchor=\"middle\" x=\"122.5\" y=\"-215.4\" font-family=\"Times,serif\" font-size=\"12.00\">0</text>\n</g>\n<!-- n5 -->\n<g id=\"node7\" class=\"node\">\n<title>n5</title>\n<ellipse fill=\"none\" stroke=\"black\" cx=\"171\" cy=\"-176\" rx=\"27\" ry=\"18\"/>\n<text text-anchor=\"middle\" x=\"171\" y=\"-172.9\" font-family=\"Meiryo UI\" font-size=\"12.00\">#Int</text>\n</g>\n<!-- n1&#45;&gt;n5 -->\n<g id=\"edge7\" class=\"edge\">\n<title>n1-&gt;n5</title>\n<path fill=\"none\" stroke=\"black\" d=\"M141.31,-243.6C146.53,-231.89 153.65,-215.91 159.61,-202.54\"/>\n<polygon fill=\"black\" stroke=\"black\" points=\"162.83,-203.92 163.71,-193.36 156.44,-201.07 162.83,-203.92\"/>\n<text text-anchor=\"middle\" x=\"158.5\" y=\"-215.4\" font-family=\"Times,serif\" font-size=\"12.00\">1</text>\n</g>\n<!-- n3 -->\n<g id=\"node3\" class=\"node\">\n<title>n3</title>\n<ellipse fill=\"none\" stroke=\"black\" cx=\"27\" cy=\"-91\" rx=\"27\" ry=\"18\"/>\n<text text-anchor=\"middle\" x=\"27\" y=\"-87.9\" font-family=\"Meiryo UI\" font-size=\"12.00\">#Int</text>\n</g>\n<!-- n2&#45;&gt;n3 -->\n<g id=\"edge2\" class=\"edge\">\n<title>n2-&gt;n3</title>\n<path fill=\"none\" stroke=\"black\" d=\"M84.98,-159.78C74.27,-147.26 58.92,-129.32 46.71,-115.04\"/>\n<polygon fill=\"black\" stroke=\"black\" points=\"49.1,-112.45 39.94,-107.13 43.78,-117 49.1,-112.45\"/>\n<text text-anchor=\"middle\" x=\"70.5\" y=\"-130.4\" font-family=\"Times,serif\" font-size=\"12.00\">0</text>\n</g>\n<!-- n4 -->\n<g id=\"node5\" class=\"node\">\n<title>n4</title>\n<ellipse fill=\"none\" stroke=\"black\" cx=\"99\" cy=\"-91\" rx=\"27\" ry=\"18\"/>\n<text text-anchor=\"middle\" x=\"99\" y=\"-87.9\" font-family=\"Meiryo UI\" font-size=\"12.00\">#Int</text>\n</g>\n<!-- n2&#45;&gt;n4 -->\n<g id=\"edge4\" class=\"edge\">\n<title>n2-&gt;n4</title>\n<path fill=\"none\" stroke=\"black\" d=\"M98.21,-157.8C98.34,-146.67 98.52,-131.94 98.67,-119.24\"/>\n<polygon fill=\"black\" stroke=\"black\" points=\"102.17,-119.22 98.79,-109.18 95.17,-119.13 102.17,-119.22\"/>\n<text text-anchor=\"middle\" x=\"102.5\" y=\"-130.4\" font-family=\"Times,serif\" font-size=\"12.00\">1</text>\n</g>\n<!-- c3 -->\n<g id=\"node4\" class=\"node\">\n<title>c3</title>\n<polygon fill=\"none\" stroke=\"black\" points=\"54,-36 0,-36 0,0 54,0 54,-36\"/>\n<text text-anchor=\"middle\" x=\"27\" y=\"-14.9\" font-family=\"monospace\" font-size=\"12.00\" fill=\"blue\">'1'</text>\n</g>\n<!-- n3&#45;&gt;c3 -->\n<g id=\"edge1\" class=\"edge\">\n<title>n3-&gt;c3</title>\n<path fill=\"none\" stroke=\"black\" d=\"M27,-72.81C27,-64.79 27,-55.05 27,-46.07\"/>\n<polygon fill=\"black\" stroke=\"black\" points=\"30.5,-46.03 27,-36.03 23.5,-46.03 30.5,-46.03\"/>\n</g>\n<!-- c4 -->\n<g id=\"node6\" class=\"node\">\n<title>c4</title>\n<polygon fill=\"none\" stroke=\"black\" points=\"126,-36 72,-36 72,0 126,0 126,-36\"/>\n<text text-anchor=\"middle\" x=\"99\" y=\"-14.9\" font-family=\"monospace\" font-size=\"12.00\" fill=\"blue\">'2'</text>\n</g>\n<!-- n4&#45;&gt;c4 -->\n<g id=\"edge3\" class=\"edge\">\n<title>n4-&gt;c4</title>\n<path fill=\"none\" stroke=\"black\" d=\"M99,-72.81C99,-64.79 99,-55.05 99,-46.07\"/>\n<polygon fill=\"black\" stroke=\"black\" points=\"102.5,-46.03 99,-36.03 95.5,-46.03 102.5,-46.03\"/>\n</g>\n<!-- c5 -->\n<g id=\"node8\" class=\"node\">\n<title>c5</title>\n<polygon fill=\"none\" stroke=\"black\" points=\"198,-109 144,-109 144,-73 198,-73 198,-109\"/>\n<text text-anchor=\"middle\" x=\"171\" y=\"-87.9\" font-family=\"monospace\" font-size=\"12.00\" fill=\"blue\">'3'</text>\n</g>\n<!-- n5&#45;&gt;c5 -->\n<g id=\"edge6\" class=\"edge\">\n<title>n5-&gt;c5</title>\n<path fill=\"none\" stroke=\"black\" d=\"M171,-157.8C171,-146.67 171,-131.94 171,-119.24\"/>\n<polygon fill=\"black\" stroke=\"black\" points=\"174.5,-119.18 171,-109.18 167.5,-119.18 174.5,-119.18\"/>\n</g>\n</g>\n</svg>",
      "text/plain": [
       "<IPython.core.display.SVG object>"
      ]
     },
     "metadata": {},
     "output_type": "display_data"
    }
   ],
   "source": [
    "%%peg\n",
    "\n",
    "Expr = Prod {^ \"+\" Prod #Add }*\n",
    "Prod = Value {^ \"*\" Value #Mul }*\n",
    "Value = { [0-9]+ #Int } _\n",
    "\n",
    "example Expr 1+2+3"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 10,
   "metadata": {},
   "outputs": [
    {
     "data": {
      "text/html": [
       "<b>Expr</b> 1+(2+3)<span style=\"background-color:#FFCACA;\"></span>"
      ],
      "text/plain": [
       "<IPython.core.display.HTML object>"
      ]
     },
     "metadata": {},
     "output_type": "display_data"
    },
    {
     "data": {
      "image/svg+xml": "<svg xmlns=\"http://www.w3.org/2000/svg\" xmlns:xlink=\"http://www.w3.org/1999/xlink\" width=\"206pt\" height=\"287pt\" viewBox=\"0.00 0.00 206.00 287.00\">\n<g id=\"graph0\" class=\"graph\" transform=\"scale(1 1) rotate(0) translate(4 283)\">\n<title>tree</title>\n<polygon fill=\"white\" stroke=\"transparent\" points=\"-4,4 -4,-283 202,-283 202,4 -4,4\"/>\n<!-- n1 -->\n<g id=\"node1\" class=\"node\">\n<title>n1</title>\n<ellipse fill=\"none\" stroke=\"black\" cx=\"63\" cy=\"-261\" rx=\"27.9\" ry=\"18\"/>\n<text text-anchor=\"middle\" x=\"63\" y=\"-257.9\" font-family=\"Meiryo UI\" font-size=\"12.00\">#Add</text>\n</g>\n<!-- n2 -->\n<g id=\"node2\" class=\"node\">\n<title>n2</title>\n<ellipse fill=\"none\" stroke=\"black\" cx=\"27\" cy=\"-176\" rx=\"27\" ry=\"18\"/>\n<text text-anchor=\"middle\" x=\"27\" y=\"-172.9\" font-family=\"Meiryo UI\" font-size=\"12.00\">#Int</text>\n</g>\n<!-- n1&#45;&gt;n2 -->\n<g id=\"edge2\" class=\"edge\">\n<title>n1-&gt;n2</title>\n<path fill=\"none\" stroke=\"black\" d=\"M55.89,-243.6C50.89,-232.08 44.1,-216.43 38.36,-203.19\"/>\n<polygon fill=\"black\" stroke=\"black\" points=\"41.41,-201.43 34.22,-193.65 34.99,-204.22 41.41,-201.43\"/>\n<text text-anchor=\"middle\" x=\"51.5\" y=\"-215.4\" font-family=\"Times,serif\" font-size=\"12.00\">0</text>\n</g>\n<!-- n3 -->\n<g id=\"node4\" class=\"node\">\n<title>n3</title>\n<ellipse fill=\"none\" stroke=\"black\" cx=\"100\" cy=\"-176\" rx=\"27.9\" ry=\"18\"/>\n<text text-anchor=\"middle\" x=\"100\" y=\"-172.9\" font-family=\"Meiryo UI\" font-size=\"12.00\">#Add</text>\n</g>\n<!-- n1&#45;&gt;n3 -->\n<g id=\"edge7\" class=\"edge\">\n<title>n1-&gt;n3</title>\n<path fill=\"none\" stroke=\"black\" d=\"M70.31,-243.6C75.5,-231.97 82.56,-216.12 88.5,-202.8\"/>\n<polygon fill=\"black\" stroke=\"black\" points=\"91.7,-204.21 92.58,-193.65 85.31,-201.36 91.7,-204.21\"/>\n<text text-anchor=\"middle\" x=\"87.5\" y=\"-215.4\" font-family=\"Times,serif\" font-size=\"12.00\">1</text>\n</g>\n<!-- c2 -->\n<g id=\"node3\" class=\"node\">\n<title>c2</title>\n<polygon fill=\"none\" stroke=\"black\" points=\"54,-109 0,-109 0,-73 54,-73 54,-109\"/>\n<text text-anchor=\"middle\" x=\"27\" y=\"-87.9\" font-family=\"monospace\" font-size=\"12.00\" fill=\"blue\">'1'</text>\n</g>\n<!-- n2&#45;&gt;c2 -->\n<g id=\"edge1\" class=\"edge\">\n<title>n2-&gt;c2</title>\n<path fill=\"none\" stroke=\"black\" d=\"M27,-157.8C27,-146.67 27,-131.94 27,-119.24\"/>\n<polygon fill=\"black\" stroke=\"black\" points=\"30.5,-119.18 27,-109.18 23.5,-119.18 30.5,-119.18\"/>\n</g>\n<!-- n4 -->\n<g id=\"node5\" class=\"node\">\n<title>n4</title>\n<ellipse fill=\"none\" stroke=\"black\" cx=\"99\" cy=\"-91\" rx=\"27\" ry=\"18\"/>\n<text text-anchor=\"middle\" x=\"99\" y=\"-87.9\" font-family=\"Meiryo UI\" font-size=\"12.00\">#Int</text>\n</g>\n<!-- n3&#45;&gt;n4 -->\n<g id=\"edge4\" class=\"edge\">\n<title>n3-&gt;n4</title>\n<path fill=\"none\" stroke=\"black\" d=\"M99.79,-157.8C99.66,-146.67 99.48,-131.94 99.33,-119.24\"/>\n<polygon fill=\"black\" stroke=\"black\" points=\"102.83,-119.13 99.21,-109.18 95.83,-119.22 102.83,-119.13\"/>\n<text text-anchor=\"middle\" x=\"103.5\" y=\"-130.4\" font-family=\"Times,serif\" font-size=\"12.00\">0</text>\n</g>\n<!-- n5 -->\n<g id=\"node7\" class=\"node\">\n<title>n5</title>\n<ellipse fill=\"none\" stroke=\"black\" cx=\"171\" cy=\"-91\" rx=\"27\" ry=\"18\"/>\n<text text-anchor=\"middle\" x=\"171\" y=\"-87.9\" font-family=\"Meiryo UI\" font-size=\"12.00\">#Int</text>\n</g>\n<!-- n3&#45;&gt;n5 -->\n<g id=\"edge6\" class=\"edge\">\n<title>n3-&gt;n5</title>\n<path fill=\"none\" stroke=\"black\" d=\"M113.02,-159.78C123.73,-147.26 139.08,-129.32 151.29,-115.04\"/>\n<polygon fill=\"black\" stroke=\"black\" points=\"154.22,-117 158.06,-107.13 148.9,-112.45 154.22,-117\"/>\n<text text-anchor=\"middle\" x=\"143.5\" y=\"-130.4\" font-family=\"Times,serif\" font-size=\"12.00\">1</text>\n</g>\n<!-- c4 -->\n<g id=\"node6\" class=\"node\">\n<title>c4</title>\n<polygon fill=\"none\" stroke=\"black\" points=\"126,-36 72,-36 72,0 126,0 126,-36\"/>\n<text text-anchor=\"middle\" x=\"99\" y=\"-14.9\" font-family=\"monospace\" font-size=\"12.00\" fill=\"blue\">'2'</text>\n</g>\n<!-- n4&#45;&gt;c4 -->\n<g id=\"edge3\" class=\"edge\">\n<title>n4-&gt;c4</title>\n<path fill=\"none\" stroke=\"black\" d=\"M99,-72.81C99,-64.79 99,-55.05 99,-46.07\"/>\n<polygon fill=\"black\" stroke=\"black\" points=\"102.5,-46.03 99,-36.03 95.5,-46.03 102.5,-46.03\"/>\n</g>\n<!-- c5 -->\n<g id=\"node8\" class=\"node\">\n<title>c5</title>\n<polygon fill=\"none\" stroke=\"black\" points=\"198,-36 144,-36 144,0 198,0 198,-36\"/>\n<text text-anchor=\"middle\" x=\"171\" y=\"-14.9\" font-family=\"monospace\" font-size=\"12.00\" fill=\"blue\">'3'</text>\n</g>\n<!-- n5&#45;&gt;c5 -->\n<g id=\"edge5\" class=\"edge\">\n<title>n5-&gt;c5</title>\n<path fill=\"none\" stroke=\"black\" d=\"M171,-72.81C171,-64.79 171,-55.05 171,-46.07\"/>\n<polygon fill=\"black\" stroke=\"black\" points=\"174.5,-46.03 171,-36.03 167.5,-46.03 174.5,-46.03\"/>\n</g>\n</g>\n</svg>",
      "text/plain": [
       "<IPython.core.display.SVG object>"
      ]
     },
     "metadata": {},
     "output_type": "display_data"
    }
   ],
   "source": [
    "%%peg\n",
    "\n",
    "Expr = Prod {^ \"+\" Prod #Add }* \n",
    "Prod = Value {^ \"*\" Value #Mul }* \n",
    "Value = \"(\" Expr \")\" / Int\n",
    "Int = { [0-9]+ #Int} _\n",
    "\n",
    "example Expr 1+(2+3)"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "## PegTree によるパーザ生成"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 12,
   "metadata": {},
   "outputs": [
    {
     "data": {
      "text/html": [
       "<b>Expr</b> 1+2*3<span style=\"background-color:#FFCACA;\"></span>"
      ],
      "text/plain": [
       "<IPython.core.display.HTML object>"
      ]
     },
     "metadata": {},
     "output_type": "display_data"
    },
    {
     "data": {
      "image/svg+xml": "<svg xmlns=\"http://www.w3.org/2000/svg\" xmlns:xlink=\"http://www.w3.org/1999/xlink\" width=\"206pt\" height=\"287pt\" viewBox=\"0.00 0.00 206.00 287.00\">\n<g id=\"graph0\" class=\"graph\" transform=\"scale(1 1) rotate(0) translate(4 283)\">\n<title>tree</title>\n<polygon fill=\"white\" stroke=\"transparent\" points=\"-4,4 -4,-283 202,-283 202,4 -4,4\"/>\n<!-- n1 -->\n<g id=\"node1\" class=\"node\">\n<title>n1</title>\n<ellipse fill=\"none\" stroke=\"black\" cx=\"63\" cy=\"-261\" rx=\"27.9\" ry=\"18\"/>\n<text text-anchor=\"middle\" x=\"63\" y=\"-257.9\" font-family=\"Meiryo UI\" font-size=\"12.00\">#Add</text>\n</g>\n<!-- n2 -->\n<g id=\"node2\" class=\"node\">\n<title>n2</title>\n<ellipse fill=\"none\" stroke=\"black\" cx=\"27\" cy=\"-176\" rx=\"27\" ry=\"18\"/>\n<text text-anchor=\"middle\" x=\"27\" y=\"-172.9\" font-family=\"Meiryo UI\" font-size=\"12.00\">#Int</text>\n</g>\n<!-- n1&#45;&gt;n2 -->\n<g id=\"edge2\" class=\"edge\">\n<title>n1-&gt;n2</title>\n<path fill=\"none\" stroke=\"black\" d=\"M55.89,-243.6C50.89,-232.08 44.1,-216.43 38.36,-203.19\"/>\n<polygon fill=\"black\" stroke=\"black\" points=\"41.41,-201.43 34.22,-193.65 34.99,-204.22 41.41,-201.43\"/>\n<text text-anchor=\"middle\" x=\"51.5\" y=\"-215.4\" font-family=\"Times,serif\" font-size=\"12.00\">0</text>\n</g>\n<!-- n3 -->\n<g id=\"node4\" class=\"node\">\n<title>n3</title>\n<ellipse fill=\"none\" stroke=\"black\" cx=\"99\" cy=\"-176\" rx=\"27\" ry=\"18\"/>\n<text text-anchor=\"middle\" x=\"99\" y=\"-172.9\" font-family=\"Meiryo UI\" font-size=\"12.00\">#Mul</text>\n</g>\n<!-- n1&#45;&gt;n3 -->\n<g id=\"edge7\" class=\"edge\">\n<title>n1-&gt;n3</title>\n<path fill=\"none\" stroke=\"black\" d=\"M70.11,-243.6C75.11,-232.08 81.9,-216.43 87.64,-203.19\"/>\n<polygon fill=\"black\" stroke=\"black\" points=\"91.01,-204.22 91.78,-193.65 84.59,-201.43 91.01,-204.22\"/>\n<text text-anchor=\"middle\" x=\"86.5\" y=\"-215.4\" font-family=\"Times,serif\" font-size=\"12.00\">1</text>\n</g>\n<!-- c2 -->\n<g id=\"node3\" class=\"node\">\n<title>c2</title>\n<polygon fill=\"none\" stroke=\"black\" points=\"54,-109 0,-109 0,-73 54,-73 54,-109\"/>\n<text text-anchor=\"middle\" x=\"27\" y=\"-87.9\" font-family=\"monospace\" font-size=\"12.00\" fill=\"blue\">'1'</text>\n</g>\n<!-- n2&#45;&gt;c2 -->\n<g id=\"edge1\" class=\"edge\">\n<title>n2-&gt;c2</title>\n<path fill=\"none\" stroke=\"black\" d=\"M27,-157.8C27,-146.67 27,-131.94 27,-119.24\"/>\n<polygon fill=\"black\" stroke=\"black\" points=\"30.5,-119.18 27,-109.18 23.5,-119.18 30.5,-119.18\"/>\n</g>\n<!-- n4 -->\n<g id=\"node5\" class=\"node\">\n<title>n4</title>\n<ellipse fill=\"none\" stroke=\"black\" cx=\"99\" cy=\"-91\" rx=\"27\" ry=\"18\"/>\n<text text-anchor=\"middle\" x=\"99\" y=\"-87.9\" font-family=\"Meiryo UI\" font-size=\"12.00\">#Int</text>\n</g>\n<!-- n3&#45;&gt;n4 -->\n<g id=\"edge4\" class=\"edge\">\n<title>n3-&gt;n4</title>\n<path fill=\"none\" stroke=\"black\" d=\"M99,-157.8C99,-146.67 99,-131.94 99,-119.24\"/>\n<polygon fill=\"black\" stroke=\"black\" points=\"102.5,-119.18 99,-109.18 95.5,-119.18 102.5,-119.18\"/>\n<text text-anchor=\"middle\" x=\"102.5\" y=\"-130.4\" font-family=\"Times,serif\" font-size=\"12.00\">0</text>\n</g>\n<!-- n5 -->\n<g id=\"node7\" class=\"node\">\n<title>n5</title>\n<ellipse fill=\"none\" stroke=\"black\" cx=\"171\" cy=\"-91\" rx=\"27\" ry=\"18\"/>\n<text text-anchor=\"middle\" x=\"171\" y=\"-87.9\" font-family=\"Meiryo UI\" font-size=\"12.00\">#Int</text>\n</g>\n<!-- n3&#45;&gt;n5 -->\n<g id=\"edge6\" class=\"edge\">\n<title>n3-&gt;n5</title>\n<path fill=\"none\" stroke=\"black\" d=\"M111.87,-160.16C122.86,-147.49 138.84,-129.08 151.41,-114.58\"/>\n<polygon fill=\"black\" stroke=\"black\" points=\"154.09,-116.84 158,-106.99 148.8,-112.25 154.09,-116.84\"/>\n<text text-anchor=\"middle\" x=\"142.5\" y=\"-130.4\" font-family=\"Times,serif\" font-size=\"12.00\">1</text>\n</g>\n<!-- c4 -->\n<g id=\"node6\" class=\"node\">\n<title>c4</title>\n<polygon fill=\"none\" stroke=\"black\" points=\"126,-36 72,-36 72,0 126,0 126,-36\"/>\n<text text-anchor=\"middle\" x=\"99\" y=\"-14.9\" font-family=\"monospace\" font-size=\"12.00\" fill=\"blue\">'2'</text>\n</g>\n<!-- n4&#45;&gt;c4 -->\n<g id=\"edge3\" class=\"edge\">\n<title>n4-&gt;c4</title>\n<path fill=\"none\" stroke=\"black\" d=\"M99,-72.81C99,-64.79 99,-55.05 99,-46.07\"/>\n<polygon fill=\"black\" stroke=\"black\" points=\"102.5,-46.03 99,-36.03 95.5,-46.03 102.5,-46.03\"/>\n</g>\n<!-- c5 -->\n<g id=\"node8\" class=\"node\">\n<title>c5</title>\n<polygon fill=\"none\" stroke=\"black\" points=\"198,-36 144,-36 144,0 198,0 198,-36\"/>\n<text text-anchor=\"middle\" x=\"171\" y=\"-14.9\" font-family=\"monospace\" font-size=\"12.00\" fill=\"blue\">'3'</text>\n</g>\n<!-- n5&#45;&gt;c5 -->\n<g id=\"edge5\" class=\"edge\">\n<title>n5-&gt;c5</title>\n<path fill=\"none\" stroke=\"black\" d=\"M171,-72.81C171,-64.79 171,-55.05 171,-46.07\"/>\n<polygon fill=\"black\" stroke=\"black\" points=\"174.5,-46.03 171,-36.03 167.5,-46.03 174.5,-46.03\"/>\n</g>\n</g>\n</svg>",
      "text/plain": [
       "<IPython.core.display.SVG object>"
      ]
     },
     "metadata": {},
     "output_type": "display_data"
    },
    {
     "data": {
      "text/html": [
       "<b>Expr</b> (1+2)*3<span style=\"background-color:#FFCACA;\"></span>"
      ],
      "text/plain": [
       "<IPython.core.display.HTML object>"
      ]
     },
     "metadata": {},
     "output_type": "display_data"
    },
    {
     "data": {
      "image/svg+xml": "<svg xmlns=\"http://www.w3.org/2000/svg\" xmlns:xlink=\"http://www.w3.org/1999/xlink\" width=\"206pt\" height=\"287pt\" viewBox=\"0.00 0.00 206.00 287.00\">\n<g id=\"graph0\" class=\"graph\" transform=\"scale(1 1) rotate(0) translate(4 283)\">\n<title>tree</title>\n<polygon fill=\"white\" stroke=\"transparent\" points=\"-4,4 -4,-283 202,-283 202,4 -4,4\"/>\n<!-- n1 -->\n<g id=\"node1\" class=\"node\">\n<title>n1</title>\n<ellipse fill=\"none\" stroke=\"black\" cx=\"134\" cy=\"-261\" rx=\"27\" ry=\"18\"/>\n<text text-anchor=\"middle\" x=\"134\" y=\"-257.9\" font-family=\"Meiryo UI\" font-size=\"12.00\">#Mul</text>\n</g>\n<!-- n2 -->\n<g id=\"node2\" class=\"node\">\n<title>n2</title>\n<ellipse fill=\"none\" stroke=\"black\" cx=\"98\" cy=\"-176\" rx=\"27.9\" ry=\"18\"/>\n<text text-anchor=\"middle\" x=\"98\" y=\"-172.9\" font-family=\"Meiryo UI\" font-size=\"12.00\">#Add</text>\n</g>\n<!-- n1&#45;&gt;n2 -->\n<g id=\"edge5\" class=\"edge\">\n<title>n1-&gt;n2</title>\n<path fill=\"none\" stroke=\"black\" d=\"M126.89,-243.6C121.89,-232.08 115.1,-216.43 109.36,-203.19\"/>\n<polygon fill=\"black\" stroke=\"black\" points=\"112.41,-201.43 105.22,-193.65 105.99,-204.22 112.41,-201.43\"/>\n<text text-anchor=\"middle\" x=\"122.5\" y=\"-215.4\" font-family=\"Times,serif\" font-size=\"12.00\">0</text>\n</g>\n<!-- n5 -->\n<g id=\"node7\" class=\"node\">\n<title>n5</title>\n<ellipse fill=\"none\" stroke=\"black\" cx=\"171\" cy=\"-176\" rx=\"27\" ry=\"18\"/>\n<text text-anchor=\"middle\" x=\"171\" y=\"-172.9\" font-family=\"Meiryo UI\" font-size=\"12.00\">#Int</text>\n</g>\n<!-- n1&#45;&gt;n5 -->\n<g id=\"edge7\" class=\"edge\">\n<title>n1-&gt;n5</title>\n<path fill=\"none\" stroke=\"black\" d=\"M141.31,-243.6C146.53,-231.89 153.65,-215.91 159.61,-202.54\"/>\n<polygon fill=\"black\" stroke=\"black\" points=\"162.83,-203.92 163.71,-193.36 156.44,-201.07 162.83,-203.92\"/>\n<text text-anchor=\"middle\" x=\"158.5\" y=\"-215.4\" font-family=\"Times,serif\" font-size=\"12.00\">1</text>\n</g>\n<!-- n3 -->\n<g id=\"node3\" class=\"node\">\n<title>n3</title>\n<ellipse fill=\"none\" stroke=\"black\" cx=\"27\" cy=\"-91\" rx=\"27\" ry=\"18\"/>\n<text text-anchor=\"middle\" x=\"27\" y=\"-87.9\" font-family=\"Meiryo UI\" font-size=\"12.00\">#Int</text>\n</g>\n<!-- n2&#45;&gt;n3 -->\n<g id=\"edge2\" class=\"edge\">\n<title>n2-&gt;n3</title>\n<path fill=\"none\" stroke=\"black\" d=\"M84.98,-159.78C74.27,-147.26 58.92,-129.32 46.71,-115.04\"/>\n<polygon fill=\"black\" stroke=\"black\" points=\"49.1,-112.45 39.94,-107.13 43.78,-117 49.1,-112.45\"/>\n<text text-anchor=\"middle\" x=\"70.5\" y=\"-130.4\" font-family=\"Times,serif\" font-size=\"12.00\">0</text>\n</g>\n<!-- n4 -->\n<g id=\"node5\" class=\"node\">\n<title>n4</title>\n<ellipse fill=\"none\" stroke=\"black\" cx=\"99\" cy=\"-91\" rx=\"27\" ry=\"18\"/>\n<text text-anchor=\"middle\" x=\"99\" y=\"-87.9\" font-family=\"Meiryo UI\" font-size=\"12.00\">#Int</text>\n</g>\n<!-- n2&#45;&gt;n4 -->\n<g id=\"edge4\" class=\"edge\">\n<title>n2-&gt;n4</title>\n<path fill=\"none\" stroke=\"black\" d=\"M98.21,-157.8C98.34,-146.67 98.52,-131.94 98.67,-119.24\"/>\n<polygon fill=\"black\" stroke=\"black\" points=\"102.17,-119.22 98.79,-109.18 95.17,-119.13 102.17,-119.22\"/>\n<text text-anchor=\"middle\" x=\"102.5\" y=\"-130.4\" font-family=\"Times,serif\" font-size=\"12.00\">1</text>\n</g>\n<!-- c3 -->\n<g id=\"node4\" class=\"node\">\n<title>c3</title>\n<polygon fill=\"none\" stroke=\"black\" points=\"54,-36 0,-36 0,0 54,0 54,-36\"/>\n<text text-anchor=\"middle\" x=\"27\" y=\"-14.9\" font-family=\"monospace\" font-size=\"12.00\" fill=\"blue\">'1'</text>\n</g>\n<!-- n3&#45;&gt;c3 -->\n<g id=\"edge1\" class=\"edge\">\n<title>n3-&gt;c3</title>\n<path fill=\"none\" stroke=\"black\" d=\"M27,-72.81C27,-64.79 27,-55.05 27,-46.07\"/>\n<polygon fill=\"black\" stroke=\"black\" points=\"30.5,-46.03 27,-36.03 23.5,-46.03 30.5,-46.03\"/>\n</g>\n<!-- c4 -->\n<g id=\"node6\" class=\"node\">\n<title>c4</title>\n<polygon fill=\"none\" stroke=\"black\" points=\"126,-36 72,-36 72,0 126,0 126,-36\"/>\n<text text-anchor=\"middle\" x=\"99\" y=\"-14.9\" font-family=\"monospace\" font-size=\"12.00\" fill=\"blue\">'2'</text>\n</g>\n<!-- n4&#45;&gt;c4 -->\n<g id=\"edge3\" class=\"edge\">\n<title>n4-&gt;c4</title>\n<path fill=\"none\" stroke=\"black\" d=\"M99,-72.81C99,-64.79 99,-55.05 99,-46.07\"/>\n<polygon fill=\"black\" stroke=\"black\" points=\"102.5,-46.03 99,-36.03 95.5,-46.03 102.5,-46.03\"/>\n</g>\n<!-- c5 -->\n<g id=\"node8\" class=\"node\">\n<title>c5</title>\n<polygon fill=\"none\" stroke=\"black\" points=\"198,-109 144,-109 144,-73 198,-73 198,-109\"/>\n<text text-anchor=\"middle\" x=\"171\" y=\"-87.9\" font-family=\"monospace\" font-size=\"12.00\" fill=\"blue\">'3'</text>\n</g>\n<!-- n5&#45;&gt;c5 -->\n<g id=\"edge6\" class=\"edge\">\n<title>n5-&gt;c5</title>\n<path fill=\"none\" stroke=\"black\" d=\"M171,-157.8C171,-146.67 171,-131.94 171,-119.24\"/>\n<polygon fill=\"black\" stroke=\"black\" points=\"174.5,-119.18 171,-109.18 167.5,-119.18 174.5,-119.18\"/>\n</g>\n</g>\n</svg>",
      "text/plain": [
       "<IPython.core.display.SVG object>"
      ]
     },
     "metadata": {},
     "output_type": "display_data"
    },
    {
     "data": {
      "text/html": [
       "<b>Expr</b> 1*2+3<span style=\"background-color:#FFCACA;\"></span>"
      ],
      "text/plain": [
       "<IPython.core.display.HTML object>"
      ]
     },
     "metadata": {},
     "output_type": "display_data"
    },
    {
     "data": {
      "image/svg+xml": "<svg xmlns=\"http://www.w3.org/2000/svg\" xmlns:xlink=\"http://www.w3.org/1999/xlink\" width=\"206pt\" height=\"287pt\" viewBox=\"0.00 0.00 206.00 287.00\">\n<g id=\"graph0\" class=\"graph\" transform=\"scale(1 1) rotate(0) translate(4 283)\">\n<title>tree</title>\n<polygon fill=\"white\" stroke=\"transparent\" points=\"-4,4 -4,-283 202,-283 202,4 -4,4\"/>\n<!-- n1 -->\n<g id=\"node1\" class=\"node\">\n<title>n1</title>\n<ellipse fill=\"none\" stroke=\"black\" cx=\"135\" cy=\"-261\" rx=\"27.9\" ry=\"18\"/>\n<text text-anchor=\"middle\" x=\"135\" y=\"-257.9\" font-family=\"Meiryo UI\" font-size=\"12.00\">#Add</text>\n</g>\n<!-- n2 -->\n<g id=\"node2\" class=\"node\">\n<title>n2</title>\n<ellipse fill=\"none\" stroke=\"black\" cx=\"99\" cy=\"-176\" rx=\"27\" ry=\"18\"/>\n<text text-anchor=\"middle\" x=\"99\" y=\"-172.9\" font-family=\"Meiryo UI\" font-size=\"12.00\">#Mul</text>\n</g>\n<!-- n1&#45;&gt;n2 -->\n<g id=\"edge5\" class=\"edge\">\n<title>n1-&gt;n2</title>\n<path fill=\"none\" stroke=\"black\" d=\"M127.89,-243.6C122.89,-232.08 116.1,-216.43 110.36,-203.19\"/>\n<polygon fill=\"black\" stroke=\"black\" points=\"113.41,-201.43 106.22,-193.65 106.99,-204.22 113.41,-201.43\"/>\n<text text-anchor=\"middle\" x=\"122.5\" y=\"-215.4\" font-family=\"Times,serif\" font-size=\"12.00\">0</text>\n</g>\n<!-- n5 -->\n<g id=\"node7\" class=\"node\">\n<title>n5</title>\n<ellipse fill=\"none\" stroke=\"black\" cx=\"171\" cy=\"-176\" rx=\"27\" ry=\"18\"/>\n<text text-anchor=\"middle\" x=\"171\" y=\"-172.9\" font-family=\"Meiryo UI\" font-size=\"12.00\">#Int</text>\n</g>\n<!-- n1&#45;&gt;n5 -->\n<g id=\"edge7\" class=\"edge\">\n<title>n1-&gt;n5</title>\n<path fill=\"none\" stroke=\"black\" d=\"M142.11,-243.6C147.11,-232.08 153.9,-216.43 159.64,-203.19\"/>\n<polygon fill=\"black\" stroke=\"black\" points=\"163.01,-204.22 163.78,-193.65 156.59,-201.43 163.01,-204.22\"/>\n<text text-anchor=\"middle\" x=\"158.5\" y=\"-215.4\" font-family=\"Times,serif\" font-size=\"12.00\">1</text>\n</g>\n<!-- n3 -->\n<g id=\"node3\" class=\"node\">\n<title>n3</title>\n<ellipse fill=\"none\" stroke=\"black\" cx=\"27\" cy=\"-91\" rx=\"27\" ry=\"18\"/>\n<text text-anchor=\"middle\" x=\"27\" y=\"-87.9\" font-family=\"Meiryo UI\" font-size=\"12.00\">#Int</text>\n</g>\n<!-- n2&#45;&gt;n3 -->\n<g id=\"edge2\" class=\"edge\">\n<title>n2-&gt;n3</title>\n<path fill=\"none\" stroke=\"black\" d=\"M86.13,-160.16C75.14,-147.49 59.16,-129.08 46.59,-114.58\"/>\n<polygon fill=\"black\" stroke=\"black\" points=\"49.2,-112.25 40,-106.99 43.91,-116.84 49.2,-112.25\"/>\n<text text-anchor=\"middle\" x=\"71.5\" y=\"-130.4\" font-family=\"Times,serif\" font-size=\"12.00\">0</text>\n</g>\n<!-- n4 -->\n<g id=\"node5\" class=\"node\">\n<title>n4</title>\n<ellipse fill=\"none\" stroke=\"black\" cx=\"99\" cy=\"-91\" rx=\"27\" ry=\"18\"/>\n<text text-anchor=\"middle\" x=\"99\" y=\"-87.9\" font-family=\"Meiryo UI\" font-size=\"12.00\">#Int</text>\n</g>\n<!-- n2&#45;&gt;n4 -->\n<g id=\"edge4\" class=\"edge\">\n<title>n2-&gt;n4</title>\n<path fill=\"none\" stroke=\"black\" d=\"M99,-157.8C99,-146.67 99,-131.94 99,-119.24\"/>\n<polygon fill=\"black\" stroke=\"black\" points=\"102.5,-119.18 99,-109.18 95.5,-119.18 102.5,-119.18\"/>\n<text text-anchor=\"middle\" x=\"102.5\" y=\"-130.4\" font-family=\"Times,serif\" font-size=\"12.00\">1</text>\n</g>\n<!-- c3 -->\n<g id=\"node4\" class=\"node\">\n<title>c3</title>\n<polygon fill=\"none\" stroke=\"black\" points=\"54,-36 0,-36 0,0 54,0 54,-36\"/>\n<text text-anchor=\"middle\" x=\"27\" y=\"-14.9\" font-family=\"monospace\" font-size=\"12.00\" fill=\"blue\">'1'</text>\n</g>\n<!-- n3&#45;&gt;c3 -->\n<g id=\"edge1\" class=\"edge\">\n<title>n3-&gt;c3</title>\n<path fill=\"none\" stroke=\"black\" d=\"M27,-72.81C27,-64.79 27,-55.05 27,-46.07\"/>\n<polygon fill=\"black\" stroke=\"black\" points=\"30.5,-46.03 27,-36.03 23.5,-46.03 30.5,-46.03\"/>\n</g>\n<!-- c4 -->\n<g id=\"node6\" class=\"node\">\n<title>c4</title>\n<polygon fill=\"none\" stroke=\"black\" points=\"126,-36 72,-36 72,0 126,0 126,-36\"/>\n<text text-anchor=\"middle\" x=\"99\" y=\"-14.9\" font-family=\"monospace\" font-size=\"12.00\" fill=\"blue\">'2'</text>\n</g>\n<!-- n4&#45;&gt;c4 -->\n<g id=\"edge3\" class=\"edge\">\n<title>n4-&gt;c4</title>\n<path fill=\"none\" stroke=\"black\" d=\"M99,-72.81C99,-64.79 99,-55.05 99,-46.07\"/>\n<polygon fill=\"black\" stroke=\"black\" points=\"102.5,-46.03 99,-36.03 95.5,-46.03 102.5,-46.03\"/>\n</g>\n<!-- c5 -->\n<g id=\"node8\" class=\"node\">\n<title>c5</title>\n<polygon fill=\"none\" stroke=\"black\" points=\"198,-109 144,-109 144,-73 198,-73 198,-109\"/>\n<text text-anchor=\"middle\" x=\"171\" y=\"-87.9\" font-family=\"monospace\" font-size=\"12.00\" fill=\"blue\">'3'</text>\n</g>\n<!-- n5&#45;&gt;c5 -->\n<g id=\"edge6\" class=\"edge\">\n<title>n5-&gt;c5</title>\n<path fill=\"none\" stroke=\"black\" d=\"M171,-157.8C171,-146.67 171,-131.94 171,-119.24\"/>\n<polygon fill=\"black\" stroke=\"black\" points=\"174.5,-119.18 171,-109.18 167.5,-119.18 174.5,-119.18\"/>\n</g>\n</g>\n</svg>",
      "text/plain": [
       "<IPython.core.display.SVG object>"
      ]
     },
     "metadata": {},
     "output_type": "display_data"
    },
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "wrote calc.pegtree\n"
     ]
    }
   ],
   "source": [
    "%%peg calc.pegtree\n",
    "\n",
    "Start = Expr EOF // 未消費文字を構文エラーに\n",
    "Expr = Prod ({^ \"+\" Prod #Add } / {^ \"-\" Prod #Sub } )*\n",
    "Prod = Value ({^ \"*\" Value #Mul  } / {^ \"/\" Value #Div  } )* \n",
    "Value = { [0-9]+ #Int} _ / \"(\" Expr \")\"\n",
    "example Expr 1+2*3\n",
    "example Expr (1+2)*3\n",
    "example Expr 1*2+3"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "## PegTree 文法のロード"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 13,
   "metadata": {},
   "outputs": [],
   "source": [
    "peg = pg.grammar('calc.pegtree')"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 17,
   "metadata": {},
   "outputs": [],
   "source": [
    "GRAMMAR = '''\n",
    "Start = Expr EOF\n",
    "Expr = Prod ({^ \"+\" Prod #Add } / {^ \"-\" Prod #Sub } )*\n",
    "Prod = Value ({^ \"*\" Value #Mul  } / {^ \"/\" Value #Div  } )* \n",
    "Value = { [0-9]+ #Int} _ / \"(\" Expr \")\"\n",
    "'''\n",
    "peg = pg.grammar(GRAMMAR)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 15,
   "metadata": {},
   "outputs": [
    {
     "data": {
      "text/plain": [
       "Prod ({ ^ \"+\" Prod #Add } / { ^ \"-\" Prod #Sub })*"
      ]
     },
     "execution_count": 15,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "peg['Expr']"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "## 5.3.2 パーザの生成"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 18,
   "metadata": {},
   "outputs": [],
   "source": [
    "parser = pg.generate(peg)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 19,
   "metadata": {},
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "[#Add [#Int '1'][#Int '2']]\n"
     ]
    }
   ],
   "source": [
    "tree = parser('1+2') \n",
    "print(repr(tree))"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 20,
   "metadata": {},
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "Syntax Error ((unknown source):1:1+1)\n",
      "3@14\n",
      " ^  \n"
     ]
    }
   ],
   "source": [
    "tree = parser('3@14') \n",
    "print(repr(tree))"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "## 構文木とVisitor パターン"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 21,
   "metadata": {},
   "outputs": [],
   "source": [
    "peg = pg.grammar('calc.pegtree') \n",
    "parser = pg.generate(peg)\n",
    "tree = parser('1+2*3')"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 22,
   "metadata": {},
   "outputs": [
    {
     "data": {
      "text/plain": [
       "'Add'"
      ]
     },
     "execution_count": 22,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "tree.getTag()"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 23,
   "metadata": {},
   "outputs": [
    {
     "data": {
      "text/plain": [
       "2"
      ]
     },
     "execution_count": 23,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "len(tree)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 24,
   "metadata": {},
   "outputs": [
    {
     "data": {
      "text/plain": [
       "'Int'"
      ]
     },
     "execution_count": 24,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "left = tree[0]\n",
    "left.getTag()"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 25,
   "metadata": {},
   "outputs": [
    {
     "data": {
      "text/plain": [
       "'1'"
      ]
     },
     "execution_count": 25,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "left = tree[0]\n",
    "str(left)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 26,
   "metadata": {},
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "7\n"
     ]
    }
   ],
   "source": [
    "def calc(tree):\n",
    "    tag = tree.getTag() \n",
    "    if tag == 'Add':\n",
    "        t0 = tree[0]\n",
    "        t1 = tree[1]\n",
    "        return calc(t0) + calc(t1)\n",
    "    if tag == 'Mul': \n",
    "        t0 = tree[0] \n",
    "        t1 = tree[1]\n",
    "        return calc(t0) * calc(t1) \n",
    "    if tag == 'Int':\n",
    "        token = tree.getToken()\n",
    "        return int(token)\n",
    "    print(f'TODO: {tag}') # 未実装のタグの報告 \n",
    "    return 0\n",
    "\n",
    "tree = parser('1+2*3') \n",
    "print(calc(tree))"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "## Visitor パターン"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 29,
   "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} method') \n",
    "        return None"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 34,
   "metadata": {},
   "outputs": [],
   "source": [
    "class Calc(Visitor): # Visitor の継承 \n",
    "    \n",
    "    def __init__(self, parser):\n",
    "        self.parser = parser\n",
    "    \n",
    "    def eval(self, source):\n",
    "        tree = self.parser(source)\n",
    "        return self.visit(tree)\n",
    "    \n",
    "    def acceptInt(self, tree):\n",
    "        token = tree.getToken()\n",
    "        return int(token)\n",
    "    \n",
    "    def acceptAdd(self, tree):\n",
    "        t0 = tree.get(0)\n",
    "        t1 = tree.get(1)\n",
    "        v0 = self.visit(t0)\n",
    "        v1 = self.visit(t1)\n",
    "        return  v0 + v1\n",
    "    \n",
    "    def acceptMul(self, tree):\n",
    "        t0 = tree.get(0)\n",
    "        t1 = tree.get(1)\n",
    "        v0 = self.visit(t0)\n",
    "        v1 = self.visit(t1)\n",
    "        return v0 * v1\n",
    "    \n",
    "    def accepterr(self, tree):\n",
    "        print(repr(tree))\n",
    "        raise SyntaxError()"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 35,
   "metadata": {},
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "7\n",
      "9\n",
      "5\n"
     ]
    }
   ],
   "source": [
    "calc = Calc(parser)\n",
    "print(calc.eval(\"1+2*3\"))\n",
    "print(calc.eval(\"(1+2)*3\"))\n",
    "print(calc.eval(\"1*2+3\"))"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 36,
   "metadata": {},
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "Syntax Error ((unknown source):1:1+1)\n",
      "1@2\n",
      " ^ \n"
     ]
    },
    {
     "ename": "SyntaxError",
     "evalue": "None (<string>)",
     "output_type": "error",
     "traceback": [
      "Traceback \u001b[0;36m(most recent call last)\u001b[0m:\n",
      "  File \u001b[1;32m\"/usr/local/lib/python3.9/site-packages/IPython/core/interactiveshell.py\"\u001b[0m, line \u001b[1;32m3444\u001b[0m, in \u001b[1;35mrun_code\u001b[0m\n    exec(code_obj, self.user_global_ns, self.user_ns)\n",
      "  File \u001b[1;32m\"/var/folders/c3/b3wn97_d6_1f_41g5g627qbh0000gn/T/ipykernel_83465/811203430.py\"\u001b[0m, line \u001b[1;32m1\u001b[0m, in \u001b[1;35m<module>\u001b[0m\n    calc.eval('1@2')\n",
      "  File \u001b[1;32m\"/var/folders/c3/b3wn97_d6_1f_41g5g627qbh0000gn/T/ipykernel_83465/2508912536.py\"\u001b[0m, line \u001b[1;32m8\u001b[0m, in \u001b[1;35meval\u001b[0m\n    return self.visit(tree)\n",
      "  File \u001b[1;32m\"/var/folders/c3/b3wn97_d6_1f_41g5g627qbh0000gn/T/ipykernel_83465/2341210225.py\"\u001b[0m, line \u001b[1;32m8\u001b[0m, in \u001b[1;35mvisit\u001b[0m\n    return acceptMethod(tree)\n",
      "\u001b[0;36m  File \u001b[0;32m\"/var/folders/c3/b3wn97_d6_1f_41g5g627qbh0000gn/T/ipykernel_83465/2508912536.py\"\u001b[0;36m, line \u001b[0;32m30\u001b[0;36m, in \u001b[0;35maccepterr\u001b[0;36m\u001b[0m\n\u001b[0;31m    raise SyntaxError()\u001b[0m\n",
      "\u001b[0;36m  File \u001b[0;32m\"<string>\"\u001b[0;36m, line \u001b[0;32munknown\u001b[0m\n\u001b[0;31mSyntaxError\u001b[0m\n"
     ]
    }
   ],
   "source": [
    "calc.eval('1@2')"
   ]
  }
 ],
 "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
}