pegbook_chap10.ipynb

{
 "cells": [
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "# パーザコンビネータ"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "## ラムダ式"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 1,
   "metadata": {},
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "1\n"
     ]
    }
   ],
   "source": [
    " def succ(x):\n",
    "    return x+1\n",
    "\n",
    "print(succ(0)) # 1 と表示される"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 2,
   "metadata": {},
   "outputs": [
    {
     "data": {
      "text/plain": [
       "function"
      ]
     },
     "execution_count": 2,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "#  succ の型を調べる\n",
    "type(succ)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 3,
   "metadata": {},
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "1\n"
     ]
    }
   ],
   "source": [
    "# succ を f に代入\n",
    "f = succ\n",
    "print(f(0))"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 4,
   "metadata": {},
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "1\n"
     ]
    }
   ],
   "source": [
    "# ラムダ式による関数定義\n",
    "succ = lambda x : x + 1\n",
    "print(succ(0))"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "## 高階関数"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 5,
   "metadata": {},
   "outputs": [],
   "source": [
    "def map(f, xs) :\n",
    "    mapped = []\n",
    "    for x in xs:\n",
    "        mapped.append(f(x))\n",
    "    return mapped"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 6,
   "metadata": {},
   "outputs": [
    {
     "data": {
      "text/plain": [
       "[2, 3, 4]"
      ]
     },
     "execution_count": 6,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    " # 関数名による map \n",
    " map(succ, [1,2,3])"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 7,
   "metadata": {},
   "outputs": [
    {
     "data": {
      "text/plain": [
       "[2, 4, 6]"
      ]
     },
     "execution_count": 7,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "# ラムダ式による map\n",
    "map(lambda x: x * 2, [1,2,3])"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "## クロージャ"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 8,
   "metadata": {},
   "outputs": [],
   "source": [
    "def counter():\n",
    "    x=0 #ローカル変数\n",
    "    def f() :\n",
    "        nonlocal x\n",
    "        x=x+1\n",
    "        return x\n",
    "    return f # 定義された関数を返す"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 9,
   "metadata": {},
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "1\n",
      "2\n",
      "3\n"
     ]
    }
   ],
   "source": [
    "# クロージャの実行例\n",
    "c = counter()\n",
    "print(c())\n",
    "print(c())\n",
    "print(c())"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "## パーサコンビネーター"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 10,
   "metadata": {},
   "outputs": [],
   "source": [
    "def pAny():\n",
    "    def match(x):\n",
    "        if len(x) > 0:\n",
    "            y = x[1:]\n",
    "            return y\n",
    "        return None\n",
    "    return match"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 11,
   "metadata": {},
   "outputs": [
    {
     "data": {
      "text/plain": [
       "'b'"
      ]
     },
     "execution_count": 11,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "dot = pAny() # パーザ関数を dot とする\n",
    "dot('ab')"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 13,
   "metadata": {},
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "None\n"
     ]
    }
   ],
   "source": [
    "print(dot(''))"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 14,
   "metadata": {},
   "outputs": [],
   "source": [
    "def pChar(text):\n",
    "    def match(x):\n",
    "        if x.startswith(text):\n",
    "            return x[len(text):]\n",
    "        return None\n",
    "    return match"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 15,
   "metadata": {},
   "outputs": [
    {
     "data": {
      "text/plain": [
       "'b'"
      ]
     },
     "execution_count": 15,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "#解析表現'a'で入力\"ab\"をマッチ \n",
    "a = pChar('a')\n",
    "a('ab')"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 18,
   "metadata": {},
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "None\n"
     ]
    }
   ],
   "source": [
    "#解析表現'b'で入力\"ab\"をマッチ \n",
    "b = pChar('b')\n",
    "print(b('ab'))"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 19,
   "metadata": {},
   "outputs": [],
   "source": [
    "def pRange(cs):\n",
    "    def match(x):\n",
    "        if len(x) >= 1 and x[0] in cs:\n",
    "            y = x[1:]\n",
    "            return y\n",
    "        return None\n",
    "    return match"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 20,
   "metadata": {},
   "outputs": [
    {
     "data": {
      "text/plain": [
       "'b'"
      ]
     },
     "execution_count": 20,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "abc = pRange('abc')\n",
    "abc('ab')"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 21,
   "metadata": {},
   "outputs": [],
   "source": [
    "def pNot(e):\n",
    "    # e が文字列のとき， pChar(e) に変換\n",
    "    e = pChar(e) if isinstance(e, str) else e\n",
    "    def match(x):\n",
    "        if not e(x):\n",
    "            return x\n",
    "        return None\n",
    "    return match\n",
    " "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 22,
   "metadata": {},
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "None\n"
     ]
    }
   ],
   "source": [
    " #!'a'で入力\"ab\"をマッチ \n",
    " not_a = pNot(pChar('a')) \n",
    " print(not_a('ab'))"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 25,
   "metadata": {},
   "outputs": [],
   "source": [
    "def pMany(e):\n",
    "    # e が文字列のとき， pChar(e) に変換\n",
    "    e = pChar(e) if isinstance(e, str) else e\n",
    "    def match(x):\n",
    "        y = e(x)\n",
    "        while y != None:\n",
    "            x = y\n",
    "            y = e(x)\n",
    "        return x\n",
    "    return match"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 26,
   "metadata": {},
   "outputs": [
    {
     "data": {
      "text/plain": [
       "'bb'"
      ]
     },
     "execution_count": 26,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "# 'a'*で入力\"aaaabb\"をマッチ\n",
    "many_a = pMany(pChar('a')) \n",
    "many_a('aaaabb')"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 27,
   "metadata": {},
   "outputs": [],
   "source": [
    "def pSeq(e1, e2):\n",
    "    e1 = pChar(e1) if isinstance(e1, str) else e1\n",
    "    e2 = pChar(e2) if isinstance(e2, str) else e2\n",
    "    def match(x):\n",
    "        y = e1(x)\n",
    "        if y == None:\n",
    "            return None\n",
    "        return e2(y)\n",
    "    return match"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 28,
   "metadata": {},
   "outputs": [
    {
     "data": {
      "text/plain": [
       "''"
      ]
     },
     "execution_count": 28,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "#  'a' 'b'で入力\"ab\"をマッチ\n",
    "ab = pSeq('a', 'b') \n",
    "ab('ab')"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 29,
   "metadata": {},
   "outputs": [],
   "source": [
    "def pSeq(*es):\n",
    "    # 文字列'a'はpChar('a')に変換する\n",
    "    es = [pChar(e) if isinstance(e, str) else e for e in es]\n",
    "\n",
    "    if len(es) == 1: # 要素が一つならそのまま \n",
    "        return es[0]\n",
    "    \n",
    "    def match(x):\n",
    "        for e in es:\n",
    "            x = e(x)\n",
    "            if x is None:\n",
    "                return None\n",
    "        return x\n",
    "    return match"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 30,
   "metadata": {},
   "outputs": [
    {
     "data": {
      "text/plain": [
       "<function __main__.pSeq.<locals>.match(x)>"
      ]
     },
     "execution_count": 30,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "# 'a' 'a'* 'b'\n",
    "pSeq('a', pMany('a'), 'b')\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 31,
   "metadata": {},
   "outputs": [],
   "source": [
    "def pOre(e1, e2):\n",
    "    e1 = pChar(e1) if isinstance(e1, str) else e1\n",
    "    e2 = pChar(e2) if isinstance(e2, str) else e2\n",
    "    def match(x):\n",
    "        y = e1(x)\n",
    "        if y != None:\n",
    "            return y\n",
    "        return e2(x)\n",
    "    return match"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 32,
   "metadata": {},
   "outputs": [
    {
     "data": {
      "text/plain": [
       "'b'"
      ]
     },
     "execution_count": 32,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "# 'a' / 'c'で入力\"ab\"をマッチ\n",
    "a_or_b = pOre('a', 'b') \n",
    "a_or_b('ab')"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 33,
   "metadata": {},
   "outputs": [],
   "source": [
    "def pRef(peg, name):\n",
    "    if name in peg: # すでにパーザ関数が定義済みなら\n",
    "        return peg[name] # そのまま定義済み関数を返す \n",
    "    def match(x):\n",
    "        e = peg[name]\n",
    "        return e(x)\n",
    "    return match"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 34,
   "metadata": {},
   "outputs": [
    {
     "data": {
      "text/plain": [
       "'bb'"
      ]
     },
     "execution_count": 34,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "peg = {}\n",
    "peg['A'] = pOre(pSeq('a', pRef(peg, 'A')), '')\n",
    "peg['A']('aaaabb')"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "## 10.3 パーザコンビネータとPEG文法"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 35,
   "metadata": {},
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "\n",
      "a\n",
      "\n",
      "aaa\n",
      "aa\n"
     ]
    }
   ],
   "source": [
    "peg = {}\n",
    "peg[\"A\"] = pOre(pSeq('a', pRef(peg, 'A'), 'a'), 'a') \n",
    "print(peg['A']('a'))\n",
    "print(peg['A']('aa'))\n",
    "print(peg['A']('aaa')) \n",
    "print(peg['A']('aaaa')) \n",
    "print(peg['A']('aaaaa'))"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 38,
   "metadata": {},
   "outputs": [
    {
     "data": {
      "text/plain": [
       "''"
      ]
     },
     "execution_count": 38,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "peg = {}\n",
    "peg['EXPR'] = pSeq(pRef(peg, 'PROD'), pMany(pSeq('+', pRef(peg, 'PROD')))) \n",
    "peg['PROD'] = pSeq(pRef(peg, 'TERM'), pMany(pSeq('*', pRef(peg, 'TERM'))))\n",
    "peg['TERM'] = pSeq(pRef(peg, 'DIGIT'), pMany(pRef(peg, 'DIGIT'))) \n",
    "peg['DIGIT'] = pRange('0123456789')\n",
    "\n",
    "peg['EXPR']('1+2*3')"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "## 12.2 メモ化\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 39,
   "metadata": {},
   "outputs": [],
   "source": [
    "def pRef(peg, A):\n",
    "    def match(x):\n",
    "        o = peg[A](x)\n",
    "        return o\n",
    "    return match"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "# メモあり\n",
    "\n",
    "M = {}\n",
    "def pRef(peg, A):\n",
    "    def match(x):\n",
    "        if (A, x) in M:\n",
    "            return M[(A, x)]\n",
    "        o = peg[A](x)\n",
    "        M[(A, x)] = o\n",
    "        return o\n",
    "    return match\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 40,
   "metadata": {},
   "outputs": [
    {
     "data": {
      "text/plain": [
       "'bb'"
      ]
     },
     "execution_count": 40,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "peg = {}\n",
    "peg['A'] = pOre(pSeq('a', pRef(peg, 'A')), '')\n",
    "peg['A']('aaaabb')"
   ]
  }
 ],
 "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
}