talks/2015-05-12-pyparsing/PyParsing.ipynb

{
 "metadata": {
  "name": "",
  "signature": "sha256:db8ebe59256a9e77701800059b9ceba1e6e694d2658c23f2b0126235ede11261"
 },
 "nbformat": 3,
 "nbformat_minor": 0,
 "worksheets": [
  {
   "cells": [
    {
     "cell_type": "heading",
     "level": 1,
     "metadata": {},
     "source": [
      "PyParsing"
     ]
    },
    {
     "cell_type": "markdown",
     "metadata": {},
     "source": [
      "*By [Martin Geisler][1]. Originally used for a talk at the [Zurich Python User Group][2]. Notebook available on [GitHub][3].*\n",
      "\n",
      "[1]: http://geisler.net/\n",
      "[2]: http://www.meetup.com/pyzurich/events/219713718/\n",
      "[3]: https://github.com/mgeisler/pyparsing-talk"
     ]
    },
    {
     "cell_type": "markdown",
     "metadata": {},
     "source": [
      "PyParsing aims at making it super easy to define small and simple grammars. They won't be the fastest parsers around, but they will be easy to build, maintain and reason about."
     ]
    },
    {
     "cell_type": "markdown",
     "metadata": {},
     "source": [
      "Some useful pages:\n",
      "* PyParsing homepage: http://pyparsing.wikispaces.com/\n",
      "* API documentation: http://pyparsing.wikispaces.com/"
     ]
    },
    {
     "cell_type": "markdown",
     "metadata": {},
     "source": [
      "Why would you want to use such a library -- when do you need a parser?\n",
      "\n",
      "* Do you have a search form? Let your users enter a query, complete with Boolean operators such as\n",
      "\n",
      "        name == 'Martin' and (zipcode == 8000 or city == 'Zurich')\n",
      "     \n",
      "     Now translate this into SQL, without introducing opportunities for arbitrary SQL-injection!\n",
      "\n",
      "* Need to read data from an old system? Write a parser for the data and robustly transform it into a more modern format such as JSON!"
     ]
    },
    {
     "cell_type": "heading",
     "level": 2,
     "metadata": {},
     "source": [
      "What about using Regular Expressions?"
     ]
    },
    {
     "cell_type": "markdown",
     "metadata": {},
     "source": [
      "You can parse a lot of things with regular expressions. Let us make a function that formats a phone number nicely:"
     ]
    },
    {
     "cell_type": "code",
     "collapsed": false,
     "input": [
      "import re\n",
      "def format_phone_number(number):\n",
      "    regex = re.compile(r'(?:\\+41\\s*|0)(\\d{2})\\s*(\\d{3})\\s*(\\d{2})\\s*(\\d{2})')\n",
      "    match = regex.match(number)\n",
      "    if match:\n",
      "        return '+41 %s %s %s %s' % match.groups()"
     ],
     "language": "python",
     "metadata": {},
     "outputs": [],
     "prompt_number": 45
    },
    {
     "cell_type": "code",
     "collapsed": false,
     "input": [
      "format_phone_number('078 123 45 46')"
     ],
     "language": "python",
     "metadata": {},
     "outputs": [
      {
       "metadata": {},
       "output_type": "pyout",
       "prompt_number": 46,
       "text": [
        "'+41 78 123 45 46'"
       ]
      }
     ],
     "prompt_number": 46
    },
    {
     "cell_type": "code",
     "collapsed": false,
     "input": [
      "format_phone_number('+41 78 123 45 46')"
     ],
     "language": "python",
     "metadata": {},
     "outputs": [
      {
       "metadata": {},
       "output_type": "pyout",
       "prompt_number": 47,
       "text": [
        "'+41 78 123 45 46'"
       ]
      }
     ],
     "prompt_number": 47
    },
    {
     "cell_type": "code",
     "collapsed": false,
     "input": [
      "format_phone_number('+41 781234546')"
     ],
     "language": "python",
     "metadata": {},
     "outputs": [
      {
       "metadata": {},
       "output_type": "pyout",
       "prompt_number": 48,
       "text": [
        "'+41 78 123 45 46'"
       ]
      }
     ],
     "prompt_number": 48
    },
    {
     "cell_type": "heading",
     "level": 2,
     "metadata": {},
     "source": [
      "Limitations of Regular Expressions"
     ]
    },
    {
     "cell_type": "markdown",
     "metadata": {},
     "source": [
      "Without getting too much into the theory, we can say that regular expressions can be implemented using a state machine. This state machine has a finite amount of memory and this limits the kinds of patterns it can recognize. Here is a simple state machine:"
     ]
    },
    {
     "cell_type": "code",
     "collapsed": false,
     "input": [
      "from IPython.display import SVG\n",
      "SVG(filename='DFAexample.svg')"
     ],
     "language": "python",
     "metadata": {},
     "outputs": [
      {
       "metadata": {},
       "output_type": "pyout",
       "prompt_number": 49,
       "svg": [
        "<svg height=\"299.34848\" id=\"svg2\" inkscape:output_extension=\"org.inkscape.output.svg.inkscape\" inkscape:version=\"0.45.1\" sodipodi:docbase=\"c:\\temp\" sodipodi:docname=\"DFAexample.svg\" sodipodi:version=\"0.32\" version=\"1.0\" width=\"500.10916\" xmlns=\"http://www.w3.org/2000/svg\" xmlns:cc=\"http://web.resource.org/cc/\" xmlns:dc=\"http://purl.org/dc/elements/1.1/\" xmlns:inkscape=\"http://www.inkscape.org/namespaces/inkscape\" xmlns:rdf=\"http://www.w3.org/1999/02/22-rdf-syntax-ns#\" xmlns:sodipodi=\"http://sodipodi.sourceforge.net/DTD/sodipodi-0.dtd\" xmlns:svg=\"http://www.w3.org/2000/svg\">\n",
        "  <metadata id=\"metadata7\">\n",
        "    <rdf:RDF>\n",
        "      <cc:Work rdf:about=\"\">\n",
        "        <dc:format>image/svg+xml</dc:format>\n",
        "        <dc:type rdf:resource=\"http://purl.org/dc/dcmitype/StillImage\"/>\n",
        "      </cc:Work>\n",
        "    </rdf:RDF>\n",
        "  </metadata>\n",
        "  <defs id=\"defs5\"/>\n",
        "  <sodipodi:namedview bordercolor=\"#666666\" borderopacity=\"1.0\" gridtolerance=\"10.0\" guidetolerance=\"10.0\" height=\"120px\" id=\"base\" inkscape:current-layer=\"svg2\" inkscape:cx=\"466.5123\" inkscape:cy=\"139.43848\" inkscape:pageopacity=\"0.0\" inkscape:pageshadow=\"2\" inkscape:window-height=\"1031\" inkscape:window-width=\"1920\" inkscape:window-x=\"0\" inkscape:window-y=\"22\" inkscape:zoom=\"1.3876971\" objecttolerance=\"10.0\" pagecolor=\"#ffffff\" width=\"200px\"/>\n",
        "  <path d=\"M 42.007371 77.355034 A 32.444717 35.347668 0 1 1  -22.882064,77.355034 A 32.444717 35.347668 0 1 1  42.007371 77.355034 z\" id=\"path2764\" sodipodi:cx=\"9.5626535\" sodipodi:cy=\"77.355034\" sodipodi:rx=\"32.444717\" sodipodi:ry=\"35.347668\" sodipodi:type=\"arc\" style=\"fill:#ffffff;fill-opacity:1;fill-rule:nonzero;stroke:#000000;stroke-width:1;stroke-miterlimit:4;stroke-dasharray:none;stroke-opacity:1\" transform=\"matrix(1.8887994,0,0,1.7336817,132.08161,28.28968)\"/>\n",
        "  <path d=\"M 42.007371 77.355034 A 32.444717 35.347668 0 1 1  -22.882064,77.355034 A 32.444717 35.347668 0 1 1  42.007371 77.355034 z\" id=\"path1873\" sodipodi:cx=\"9.5626535\" sodipodi:cy=\"77.355034\" sodipodi:rx=\"32.444717\" sodipodi:ry=\"35.347668\" sodipodi:type=\"arc\" style=\"fill:none;fill-opacity:1;fill-rule:nonzero;stroke:#000000;stroke-width:1;stroke-miterlimit:4;stroke-dasharray:none;stroke-opacity:1\" transform=\"matrix(1.5110395,0,0,1.3869453,135.69399,55.11148)\"/>\n",
        "  <path d=\"M 42.007371 77.355034 A 32.444717 35.347668 0 1 1  -22.882064,77.355034 A 32.444717 35.347668 0 1 1  42.007371 77.355034 z\" id=\"path2762\" sodipodi:cx=\"9.5626535\" sodipodi:cy=\"77.355034\" sodipodi:rx=\"32.444717\" sodipodi:ry=\"35.347668\" sodipodi:type=\"arc\" style=\"opacity:1;color:#000000;fill:#ffffff;fill-opacity:1;fill-rule:nonzero;stroke:#000000;stroke-width:1;stroke-linecap:butt;stroke-linejoin:miter;marker:none;marker-start:none;marker-mid:none;marker-end:none;stroke-miterlimit:4;stroke-dasharray:none;stroke-dashoffset:0;stroke-opacity:1;visibility:visible;display:inline;overflow:visible\" transform=\"matrix(1.8887994,0,0,1.7336817,405.70174,28.28968)\"/>\n",
        "  <path d=\"M 431.16898,150.52132 L 431.16898,153.87113 C 429.8653,153.24766 428.63533,152.78289 427.47908,152.47679 C 426.32279,152.17074 425.2062,152.0177 424.12928,152.01768 C 422.25881,152.0177 420.81348,152.38046 419.79322,153.10594 C 418.78431,153.83147 418.27985,154.86305 418.27988,156.20069 C 418.27985,157.32297 418.61426,158.17318 419.28312,158.7513 C 419.96326,159.31812 421.24423,159.77723 423.12604,160.12863 L 425.20053,160.55373 C 427.76245,161.0412 429.64991,161.90274 430.8629,163.13836 C 432.08717,164.36266 432.69931,166.00639 432.69933,168.06954 C 432.69931,170.52947 431.87178,172.39425 430.21673,173.66389 C 428.57299,174.93353 426.15842,175.56834 422.97299,175.56834 C 421.77137,175.56834 420.49038,175.43231 419.13007,175.16024 C 417.78107,174.88818 416.38108,174.48575 414.93007,173.95296 L 414.93007,170.4161 C 416.32439,171.1983 417.69038,171.78777 419.02805,172.18453 C 420.36568,172.5813 421.68068,172.77967 422.97299,172.77967 C 424.93412,172.77967 426.44749,172.39425 427.51309,171.62339 C 428.57866,170.85255 429.11145,169.75295 429.11148,168.3246 C 429.11145,167.07764 428.72603,166.10274 427.95518,165.3999 C 427.19567,164.69707 425.94303,164.16995 424.19729,163.81852 L 422.10579,163.41042 C 419.54383,162.90031 417.69038,162.10112 416.54545,161.01284 C 415.4005,159.9246 414.82804,158.41124 414.82804,156.47275 C 414.82804,154.22823 415.61589,152.45981 417.19161,151.16748 C 418.77864,149.87519 420.96083,149.22904 423.73818,149.22901 C 424.92845,149.22904 426.1414,149.33673 427.37705,149.55209 C 428.61267,149.7675 429.87664,150.09058 431.16898,150.52132\" id=\"text2766\" style=\"font-size:14px;font-style:normal;font-weight:normal;fill:#000000;fill-opacity:1;stroke:none;stroke-width:1px;stroke-linecap:butt;stroke-linejoin:miter;stroke-opacity:1;font-family:Bitstream Vera Sans\"/>\n",
        "  <path d=\"M 157.54882,150.52134 L 157.54882,153.87114 C 156.24516,153.24768 155.0152,152.78291 153.85894,152.47681 C 152.70264,152.17076 151.58604,152.01772 150.50913,152.0177 C 148.63867,152.01772 147.19332,152.38048 146.17308,153.10596 C 145.16417,153.83149 144.65972,154.86307 144.65973,156.20071 C 144.65972,157.32299 144.99413,158.1732 145.66296,158.75132 C 146.34312,159.31814 147.6241,159.77725 149.50589,160.12865 L 151.58039,160.55375 C 154.14232,161.04122 156.02977,161.90276 157.24275,163.13837 C 158.46702,164.36268 159.07917,166.00641 159.07919,168.06956 C 159.07917,170.52949 158.25164,172.39427 156.59659,173.66391 C 154.95285,174.93354 152.53827,175.56836 149.35285,175.56836 C 148.15122,175.56836 146.87025,175.43233 145.50993,175.16026 C 144.16093,174.8882 142.76093,174.48577 141.30991,173.95297 L 141.30991,170.41612 C 142.70424,171.19831 144.07024,171.78779 145.4079,172.18455 C 146.74555,172.58131 148.06053,172.77969 149.35285,172.77969 C 151.31397,172.77969 152.82734,172.39427 153.89294,171.62341 C 154.95851,170.85257 155.49131,169.75297 155.49133,168.32462 C 155.49131,167.07766 155.10588,166.10276 154.33505,165.39992 C 153.57552,164.69709 152.32289,164.16996 150.57715,163.81854 L 148.48564,163.41044 C 145.92369,162.90033 144.07024,162.10114 142.9253,161.01286 C 141.78036,159.92462 141.20789,158.41125 141.20789,156.47277 C 141.20789,154.22825 141.99575,152.45983 143.57146,151.16749 C 145.1585,149.87521 147.34069,149.22905 150.11804,149.22903 C 151.30831,149.22905 152.52126,149.33675 153.75691,149.55211 C 154.99253,149.76752 156.25649,150.09059 157.54882,150.52134\" id=\"text2770\" style=\"font-size:14px;font-style:normal;font-weight:normal;fill:#000000;fill-opacity:1;stroke:none;stroke-width:1px;stroke-linecap:butt;stroke-linejoin:miter;stroke-opacity:1;font-family:Bitstream Vera Sans\"/>\n",
        "  <path d=\"M 417.70779,28.37844 L 422.51754,28.37844 L 422.51754,11.77759 L 417.28512,12.82699 L 417.28512,10.1452 L 422.48838,9.0957997 L 425.43251,9.0957997 L 425.43251,28.37844 L 430.24225,28.37844 L 430.24225,30.85617 L 417.70779,30.85617 L 417.70779,28.37844\" id=\"text2804\" style=\"font-size:12px;font-style:normal;font-weight:normal;fill:#000000;fill-opacity:1;stroke:none;stroke-width:1px;stroke-linecap:butt;stroke-linejoin:miter;stroke-opacity:1;font-family:Bitstream Vera Sans\"/>\n",
        "  <path d=\"M 286.95361,269.06945 C 285.4378,269.06945 284.29611,269.81765 283.52851,271.31398 C 282.77061,272.80063 282.39164,275.04031 282.39167,278.03302 C 282.39164,281.01603 282.77061,283.25571 283.52851,284.75206 C 284.29611,286.23871 285.4378,286.98204 286.95361,286.98204 C 288.47912,286.98204 289.62081,286.23871 290.37871,284.75206 C 291.14631,283.25571 291.53013,281.01603 291.53013,278.03302 C 291.53013,275.04031 291.14631,272.80063 290.37871,271.31398 C 289.62081,269.81765 288.47912,269.06945 286.95361,269.06945 M 286.95361,266.73746 C 289.39246,266.73749 291.2532,267.70429 292.5358,269.63786 C 293.82811,271.56178 294.47426,274.36017 294.47428,278.03302 C 294.47426,281.6962 293.82811,284.49458 292.5358,286.42819 C 291.2532,288.35208 289.39246,289.31403 286.95361,289.31403 C 284.51473,289.31403 282.64914,288.35208 281.35683,286.42819 C 280.07423,284.49458 279.43294,281.6962 279.43294,278.03302 C 279.43294,274.36017 280.07423,271.56178 281.35683,269.63786 C 282.64914,267.70429 284.51473,266.73749 286.95361,266.73746\" id=\"text2808\" style=\"font-size:12px;font-style:normal;font-weight:normal;fill:#000000;fill-opacity:1;stroke:none;stroke-width:1px;stroke-linecap:butt;stroke-linejoin:miter;stroke-opacity:1;font-family:Bitstream Vera Sans\"/>\n",
        "  <path d=\"M 186.22784,67.4251 C 181.09706,48.27679 161.3392,36.91069 142.21428,42.0352 C 123.08937,47.1597 111.73548,66.86217 116.86625,86.010481 L 112.83171,87.091539 L 120.52693,94.944775 L 123.26456,84.296062 L 119.23002,85.37712 C 114.45034,67.53914 124.99399,49.21373 142.85538,44.42778 C 160.71677,39.64184 179.08441,50.22049 183.86408,68.05847 C 186.2539,76.97746 184.79444,86.023257 180.50487,93.43755 C 180.50487,93.43755 182.61276,94.681574 182.61276,94.681574 C 187.21896,86.716902 188.79322,76.99926 186.22784,67.4251 z \" id=\"path2812\" sodipodi:nodetypes=\"cscccccssccc\" style=\"fill:#000000;fill-opacity:1;fill-rule:nonzero;stroke:none;stroke-width:1;stroke-miterlimit:4;stroke-opacity:1\"/>\n",
        "  <path d=\"M 387.6794,67.42511 C 392.81017,48.27679 412.56803,36.91069 431.69293,42.0352 C 450.81786,47.1597 462.17172,66.86217 457.04097,86.010489 L 461.0755,87.091539 L 453.38031,94.944775 L 450.64267,84.29607 L 454.67719,85.377128 C 459.45689,67.53914 448.91324,49.21373 431.05184,44.42778 C 413.19047,39.64184 394.82282,50.22049 390.04318,68.05847 C 387.65331,76.97747 389.11278,86.023265 393.40237,93.437559 C 393.40237,93.437559 391.29447,94.681574 391.29447,94.681574 C 386.68825,86.71691 385.11402,76.99926 387.6794,67.42511 z \" id=\"path2819\" sodipodi:nodetypes=\"cscccccssccc\" style=\"fill:#000000;fill-opacity:1;fill-rule:nonzero;stroke:none;stroke-width:1;stroke-miterlimit:4;stroke-opacity:1\"/>\n",
        "  <path d=\"M 286.95361,37.81291 C 285.4378,37.81294 284.29611,38.56112 283.52851,40.05746 C 282.77061,41.54411 282.39164,43.7838 282.39167,46.7765 C 282.39164,49.75951 282.77061,51.99919 283.52851,53.49554 C 284.29611,54.98219 285.4378,55.72551 286.95361,55.72551 C 288.47912,55.72551 289.62081,54.98219 290.37871,53.49554 C 291.14631,51.99919 291.53013,49.75951 291.53013,46.7765 C 291.53013,43.7838 291.14631,41.54411 290.37871,40.05746 C 289.62081,38.56112 288.47912,37.81294 286.95361,37.81291 M 286.95361,35.48093 C 289.39246,35.48095 291.2532,36.44775 292.5358,38.38134 C 293.82811,40.30525 294.47426,43.10363 294.47428,46.7765 C 294.47426,50.43968 293.82811,53.23805 292.5358,55.17166 C 291.2532,57.09556 289.39246,58.0575 286.95361,58.0575 C 284.51473,58.0575 282.64914,57.09556 281.35683,55.17166 C 280.07423,53.23805 279.43294,50.43968 279.43294,46.7765 C 279.43294,43.10363 280.07423,40.30525 281.35683,38.38134 C 282.64914,36.44775 284.51473,35.48095 286.95361,35.48093\" id=\"text2821\" style=\"font-size:12px;font-style:normal;font-weight:normal;fill:#000000;fill-opacity:1;stroke:none;stroke-width:1px;stroke-linecap:butt;stroke-linejoin:miter;stroke-opacity:1;font-family:Bitstream Vera Sans\"/>\n",
        "  <path d=\"M 144.08765,28.37845 L 148.89739,28.37845 L 148.89739,11.7776 L 143.66498,12.82699 L 143.66498,10.1452 L 148.86823,9.0957997 L 151.81237,9.0957997 L 151.81237,28.37845 L 156.6221,28.37845 L 156.6221,30.85618 L 144.08765,30.85618 L 144.08765,28.37845\" id=\"text2825\" style=\"font-size:12px;font-style:normal;font-weight:normal;fill:#000000;fill-opacity:1;stroke:none;stroke-width:1px;stroke-linecap:butt;stroke-linejoin:miter;stroke-opacity:1;font-family:Bitstream Vera Sans\"/>\n",
        "  <path d=\"M 374.01454,103.52541 C 351.28316,80.794033 319.0444,68.00732 287.93996,68.00732 C 256.8355,68.00731 224.65149,80.939204 201.9225,103.66821 L 197.87611,99.509795 L 197.44043,109.54447 L 208.37136,109.78098 L 203.76481,105.51053 C 226.4954,82.779928 257.63226,70.1858 288.20032,70.18579 C 318.76836,70.18578 349.42841,82.551419 372.20843,105.33147 C 372.20843,105.33147 374.01454,103.52541 374.01454,103.52541 z \" id=\"path2849\" inkscape:transform-center-x=\"-20.320853\" inkscape:transform-center-y=\"-19.30594\" sodipodi:nodetypes=\"cscccccscc\" style=\"fill:#000000;fill-opacity:1;fill-rule:nonzero;stroke:none;stroke-width:0.07586141;stroke-miterlimit:4;stroke-opacity:1\"/>\n",
        "  <path d=\"M 199.89267,221.26959 C 222.62405,244.00095 254.8628,256.78764 285.96726,256.78767 C 317.07175,256.78767 349.25573,243.85578 371.98473,221.12678 L 375.72619,224.83144 L 375.90499,216.01717 L 366.31212,215.51018 L 370.1424,219.28445 C 347.41183,242.01504 316.27496,254.60918 285.70689,254.60918 C 255.13883,254.6092 224.47881,242.24356 201.69876,219.4635 C 201.69876,219.4635 199.89267,221.26959 199.89267,221.26959 z \" id=\"path3744\" inkscape:transform-center-x=\"20.320846\" inkscape:transform-center-y=\"19.305937\" sodipodi:nodetypes=\"cscccccscc\" style=\"fill:#000000;fill-opacity:1;fill-rule:nonzero;stroke:none;stroke-width:0.07586141;stroke-miterlimit:4;stroke-opacity:1\"/>\n",
        "  <path d=\"M 159.36097,188.42345 L 162.56746,188.42345 L 162.56746,177.35622 L 159.07919,178.05582 L 159.07919,176.26796 L 162.54802,175.56836 L 164.51078,175.56836 L 164.51078,188.42345 L 167.71727,188.42345 L 167.71727,190.07528 L 159.36097,190.07528 L 159.36097,188.42345\" id=\"text3808\" style=\"font-size:8px;font-style:normal;font-weight:normal;fill:#000000;fill-opacity:1;stroke:none;stroke-width:1px;stroke-linecap:butt;stroke-linejoin:miter;stroke-opacity:1;font-family:Bitstream Vera Sans\"/>\n",
        "  <path d=\"M 435.06047,188.68578 L 441.91071,188.68578 L 441.91071,190.33761 L 432.69933,190.33761 L 432.69933,188.68578 C 433.44428,187.91493 434.45804,186.88173 435.74064,185.58618 C 437.0297,184.28416 437.83941,183.44529 438.16979,183.06958 C 438.79813,182.36351 439.23537,181.76756 439.48153,181.28172 C 439.73415,180.78942 439.86047,180.30683 439.86049,179.83394 C 439.86047,179.0631 439.58841,178.43476 439.04428,177.94892 C 438.50662,177.4631 437.80379,177.22018 436.93579,177.22017 C 436.3204,177.22018 435.66938,177.32706 434.98274,177.54082 C 434.30257,177.7546 433.57382,178.07848 432.79649,178.51248 L 432.79649,176.53029 C 433.58679,176.21289 434.32526,175.97322 435.01189,175.81126 C 435.69853,175.64933 436.32687,175.56836 436.89691,175.56834 C 438.39974,175.56836 439.59811,175.94407 440.49206,176.69547 C 441.38598,177.4469 441.83295,178.45095 441.83297,179.70762 C 441.83295,180.30359 441.71959,180.87039 441.49289,181.40803 C 441.27262,181.93922 440.86776,182.56756 440.27832,183.29306 C 440.11635,183.48092 439.60138,184.02505 438.73335,184.92545 C 437.86533,185.81938 436.64103,187.07283 435.06047,188.68578\" id=\"text3812\" style=\"font-size:8px;font-style:normal;font-weight:normal;fill:#000000;fill-opacity:1;stroke:none;stroke-width:1px;stroke-linecap:butt;stroke-linejoin:miter;stroke-opacity:1;font-family:Bitstream Vera Sans\"/>\n",
        "  <path d=\"M 21.064808,160.97085 L 64.70197,160.97085 L 64.70197,157.1215 L 74.102939,162.39868 L 64.70197,167.67587 L 64.70197,163.8265 L 21.064808,163.8265 L 21.064808,160.97085 z \" id=\"rect2826\" sodipodi:nodetypes=\"cccccccc\" style=\"color:#000000;fill:#000000;fill-opacity:1;fill-rule:nonzero;stroke:none;stroke-width:0.72748214;stroke-linecap:butt;stroke-linejoin:miter;marker:none;marker-start:none;marker-mid:none;marker-end:none;stroke-miterlimit:4;stroke-dashoffset:0;stroke-opacity:1;visibility:visible;display:inline;overflow:visible\"/>\n",
        "</svg>"
       ],
       "text": [
        "<IPython.core.display.SVG at 0x7ff6c2e556d0>"
       ]
      }
     ],
     "prompt_number": 49
    },
    {
     "cell_type": "markdown",
     "metadata": {},
     "source": [
      "This machine accepts strings with an even number of zeros. As a regular expression, this is $1^* \\bigl( 0 (1^*) 0 (1^*) \\bigr)^*$."
     ]
    },
    {
     "cell_type": "markdown",
     "metadata": {},
     "source": [
      "There is a one-to-one correspondance between regular expression and finite automatons. The limited memory means that a regular expression cannot handle languages with arbitrary nesting. Things you cannot parse correctly with regular expressions:\n",
      "\n",
      "* math expressions\n",
      "* JSON, XML, HTML, SQL,\n",
      "* programming languages in general\n",
      "\n",
      "For anything that contains nesting you need a more powerful parser."
     ]
    },
    {
     "cell_type": "heading",
     "level": 2,
     "metadata": {},
     "source": [
      "About bad Input to Regular Expression Engines"
     ]
    },
    {
     "cell_type": "markdown",
     "metadata": {},
     "source": [
      "The above is not strictly true for several regular expression engines used today (including the re module in Pyhon and engines using the PCRE library from Perl). These engines allow you to refer back to an earlier group in your pattern. An example would be matching strings surrounded by single- or double-quotes where you want to refer back to the opening quote:"
     ]
    },
    {
     "cell_type": "code",
     "collapsed": false,
     "input": [
      "import re\n",
      "regex = re.compile(r'''([\"'])(.*?)\\1''')\n",
      "regex.findall('''aaa 'bbb' \"ccc\" ddd''')"
     ],
     "language": "python",
     "metadata": {},
     "outputs": [
      {
       "metadata": {},
       "output_type": "pyout",
       "prompt_number": 50,
       "text": [
        "[(\"'\", 'bbb'), ('\"', 'ccc')]"
       ]
      }
     ],
     "prompt_number": 50
    },
    {
     "cell_type": "markdown",
     "metadata": {},
     "source": [
      "This functionality makes the engines much more powerful than \"classic\" regular expressions. The power comes with a cost, however, since the engines aren't implemented with DFAs as described above. Instead they use back-tracking and this can make them use exponential (instead of linear) time to match a pattern:"
     ]
    },
    {
     "cell_type": "code",
     "collapsed": false,
     "input": [
      "def bad_case(re, n):\n",
      "    bad_re = 'a?' * n + 'a' * n\n",
      "    bad_input = 'a' * n\n",
      "    re.match(bad_re, bad_input)"
     ],
     "language": "python",
     "metadata": {},
     "outputs": [],
     "prompt_number": 51
    },
    {
     "cell_type": "code",
     "collapsed": false,
     "input": [
      "%timeit bad_case(re, 15)\n",
      "%timeit bad_case(re, 16)\n",
      "%timeit bad_case(re, 17)\n",
      "%timeit bad_case(re, 18)"
     ],
     "language": "python",
     "metadata": {},
     "outputs": [
      {
       "output_type": "stream",
       "stream": "stdout",
       "text": [
        "1000 loops, best of 3: 1.67 ms per loop\n",
        "100 loops, best of 3: 3.3 ms per loop"
       ]
      },
      {
       "output_type": "stream",
       "stream": "stdout",
       "text": [
        "\n",
        "100 loops, best of 3: 6.36 ms per loop"
       ]
      },
      {
       "output_type": "stream",
       "stream": "stdout",
       "text": [
        "\n",
        "100 loops, best of 3: 13 ms per loop"
       ]
      },
      {
       "output_type": "stream",
       "stream": "stdout",
       "text": [
        "\n"
       ]
      }
     ],
     "prompt_number": 52
    },
    {
     "cell_type": "markdown",
     "metadata": {},
     "source": [
      "If you will be working with untrusted regular expressions, you should take a look at the [re2][1] module. Compared to the normal re module, re2 gives you performance linear in the length of the regular expression you're matching:\n",
      "\n",
      "[1]: https://pypi.python.org/pypi/re2/"
     ]
    },
    {
     "cell_type": "code",
     "collapsed": false,
     "input": [
      "import re2\n",
      "%timeit bad_case(re2, 15)\n",
      "%timeit bad_case(re2, 16)\n",
      "%timeit bad_case(re2, 17)\n",
      "%timeit bad_case(re2, 18)"
     ],
     "language": "python",
     "metadata": {},
     "outputs": [
      {
       "output_type": "stream",
       "stream": "stdout",
       "text": [
        "100000 loops, best of 3: 2.05 \u00b5s per loop\n",
        "100000 loops, best of 3: 2.01 \u00b5s per loop"
       ]
      },
      {
       "output_type": "stream",
       "stream": "stdout",
       "text": [
        "\n",
        "100000 loops, best of 3: 2 \u00b5s per loop"
       ]
      },
      {
       "output_type": "stream",
       "stream": "stdout",
       "text": [
        "\n",
        "100000 loops, best of 3: 2.04 \u00b5s per loop"
       ]
      },
      {
       "output_type": "stream",
       "stream": "stdout",
       "text": [
        "\n"
       ]
      }
     ],
     "prompt_number": 53
    },
    {
     "cell_type": "heading",
     "level": 2,
     "metadata": {},
     "source": [
      "Simple PyParsing Parsers"
     ]
    },
    {
     "cell_type": "markdown",
     "metadata": {},
     "source": [
      "One of the simplest parsers will only parse a single word:"
     ]
    },
    {
     "cell_type": "code",
     "collapsed": true,
     "input": [
      "from pyparsing import Word\n",
      "abcd = Word('abcd')\n",
      "abcd.parseString('aa bb')"
     ],
     "language": "python",
     "metadata": {},
     "outputs": [
      {
       "metadata": {},
       "output_type": "pyout",
       "prompt_number": 54,
       "text": [
        "(['aa'], {})"
       ]
      }
     ],
     "prompt_number": 54
    },
    {
     "cell_type": "markdown",
     "metadata": {},
     "source": [
      "The parse result contain the prefix that was parsed. The argument to `Word` determines the characters recognized. Parsing something that cannot be recognized results in an exception:"
     ]
    },
    {
     "cell_type": "code",
     "collapsed": false,
     "input": [
      "from pyparsing import ParseException\n",
      "import sys\n",
      "\n",
      "try:\n",
      "    abcd.parseString('foo')\n",
      "except ParseException, e:\n",
      "    print >> sys.stderr, e"
     ],
     "language": "python",
     "metadata": {},
     "outputs": [
      {
       "output_type": "stream",
       "stream": "stderr",
       "text": [
        "Expected W:(abcd) (at char 0), (line:1, col:1)\n"
       ]
      }
     ],
     "prompt_number": 55
    },
    {
     "cell_type": "markdown",
     "metadata": {},
     "source": [
      "PyParsing comes with useful constants for quickly declarings alphanumeric words:"
     ]
    },
    {
     "cell_type": "code",
     "collapsed": false,
     "input": [
      "from pyparsing import alphas\n",
      "a_word = Word(alphas)\n",
      "a_word.parseString('foo bar')"
     ],
     "language": "python",
     "metadata": {},
     "outputs": [
      {
       "metadata": {},
       "output_type": "pyout",
       "prompt_number": 56,
       "text": [
        "(['foo'], {})"
       ]
      }
     ],
     "prompt_number": 56
    },
    {
     "cell_type": "markdown",
     "metadata": {},
     "source": [
      " We can also require the entire string to be parsed:"
     ]
    },
    {
     "cell_type": "code",
     "collapsed": false,
     "input": [
      "try:\n",
      "    a_word.parseString('aa bb', parseAll=True)\n",
      "except ParseException, e:\n",
      "    print >> sys.stderr, e"
     ],
     "language": "python",
     "metadata": {},
     "outputs": [
      {
       "output_type": "stream",
       "stream": "stderr",
       "text": [
        "Expected end of text (at char 3), (line:1, col:4)\n"
       ]
      }
     ],
     "prompt_number": 57
    },
    {
     "cell_type": "markdown",
     "metadata": {},
     "source": [
      "Small parsers can be combined into larger parsers:"
     ]
    },
    {
     "cell_type": "code",
     "collapsed": true,
     "input": [
      "two_words = a_word + a_word\n",
      "two_words.parseString('aa bb', parseAll=True)"
     ],
     "language": "python",
     "metadata": {},
     "outputs": [
      {
       "metadata": {},
       "output_type": "pyout",
       "prompt_number": 58,
       "text": [
        "(['aa', 'bb'], {})"
       ]
      }
     ],
     "prompt_number": 58
    },
    {
     "cell_type": "markdown",
     "metadata": {},
     "source": [
      "You can also match literals:"
     ]
    },
    {
     "cell_type": "code",
     "collapsed": false,
     "input": [
      "from pyparsing import Literal\n",
      "assignment = a_word + Literal('=') + a_word\n",
      "assignment.parseString('foo = testing')"
     ],
     "language": "python",
     "metadata": {},
     "outputs": [
      {
       "metadata": {},
       "output_type": "pyout",
       "prompt_number": 59,
       "text": [
        "(['foo', '=', 'testing'], {})"
       ]
      }
     ],
     "prompt_number": 59
    },
    {
     "cell_type": "markdown",
     "metadata": {},
     "source": [
      "Thanks to operator overloading, you can often just write the string literal as a normal string:"
     ]
    },
    {
     "cell_type": "code",
     "collapsed": false,
     "input": [
      "assignment = a_word + '=' + a_word\n",
      "assignment.parseString('foo = testing')"
     ],
     "language": "python",
     "metadata": {},
     "outputs": [
      {
       "metadata": {},
       "output_type": "pyout",
       "prompt_number": 60,
       "text": [
        "(['foo', '=', 'testing'], {})"
       ]
      }
     ],
     "prompt_number": 60
    },
    {
     "cell_type": "markdown",
     "metadata": {},
     "source": [
      "It is easy to suppress parts of the parser. This will still match the part, but it is no longer part of the result:"
     ]
    },
    {
     "cell_type": "code",
     "collapsed": false,
     "input": [
      "from pyparsing import Suppress\n",
      "assignment = a_word + Suppress('=') + a_word\n",
      "assignment.parseString('foo = testing')"
     ],
     "language": "python",
     "metadata": {},
     "outputs": [
      {
       "metadata": {},
       "output_type": "pyout",
       "prompt_number": 61,
       "text": [
        "(['foo', 'testing'], {})"
       ]
      }
     ],
     "prompt_number": 61
    },
    {
     "cell_type": "heading",
     "level": 2,
     "metadata": {},
     "source": [
      "Parse Result"
     ]
    },
    {
     "cell_type": "markdown",
     "metadata": {},
     "source": [
      "The result of `parseString` is a `ParseResult`, which behaves like a list:"
     ]
    },
    {
     "cell_type": "code",
     "collapsed": false,
     "input": [
      "result = assignment.parseString('foo = testing')\n",
      "result[0], result[1]"
     ],
     "language": "python",
     "metadata": {},
     "outputs": [
      {
       "metadata": {},
       "output_type": "pyout",
       "prompt_number": 62,
       "text": [
        "('foo', 'testing')"
       ]
      }
     ],
     "prompt_number": 62
    },
    {
     "cell_type": "markdown",
     "metadata": {},
     "source": [
      "You can also get a real `list` back if you like:"
     ]
    },
    {
     "cell_type": "code",
     "collapsed": false,
     "input": [
      "result.asList()"
     ],
     "language": "python",
     "metadata": {},
     "outputs": [
      {
       "metadata": {},
       "output_type": "pyout",
       "prompt_number": 63,
       "text": [
        "['foo', 'testing']"
       ]
      }
     ],
     "prompt_number": 63
    },
    {
     "cell_type": "markdown",
     "metadata": {},
     "source": [
      "If you associate names with different sub-parts of the parser, you can use the `asDict` method to get data out:"
     ]
    },
    {
     "cell_type": "code",
     "collapsed": false,
     "input": [
      "name = a_word('first') + a_word('last')\n",
      "result = name.parseString('Martin Geisler')\n",
      "result.asDict()"
     ],
     "language": "python",
     "metadata": {},
     "outputs": [
      {
       "metadata": {},
       "output_type": "pyout",
       "prompt_number": 64,
       "text": [
        "{'first': 'Martin', 'last': 'Geisler'}"
       ]
      }
     ],
     "prompt_number": 64
    },
    {
     "cell_type": "markdown",
     "metadata": {},
     "source": [
      "You can also access the data directly as fields on the result:"
     ]
    },
    {
     "cell_type": "code",
     "collapsed": false,
     "input": [
      "result.first, result.last"
     ],
     "language": "python",
     "metadata": {},
     "outputs": [
      {
       "metadata": {},
       "output_type": "pyout",
       "prompt_number": 65,
       "text": [
        "('Martin', 'Geisler')"
       ]
      }
     ],
     "prompt_number": 65
    },
    {
     "cell_type": "heading",
     "level": 2,
     "metadata": {},
     "source": [
      "Parsing Phone Numbers Again"
     ]
    },
    {
     "cell_type": "markdown",
     "metadata": {},
     "source": [
      "We can now parse a phone number again:"
     ]
    },
    {
     "cell_type": "code",
     "collapsed": false,
     "input": [
      "from pyparsing import nums, Literal\n",
      "prefix = Literal('+41') | Literal('0')\n",
      "carrier = Word(nums, exact=2)\n",
      "area = Word(nums, exact=3)\n",
      "subscriber = Word(nums, exact=2) + Word(nums, exact=2)\n",
      "\n",
      "phone_number = prefix.suppress() + carrier + area + subscriber"
     ],
     "language": "python",
     "metadata": {},
     "outputs": [],
     "prompt_number": 66
    },
    {
     "cell_type": "markdown",
     "metadata": {},
     "source": [
      "We can now use the parser:"
     ]
    },
    {
     "cell_type": "code",
     "collapsed": false,
     "input": [
      "phone_number.parseString('+41 78 123 4567').asList()"
     ],
     "language": "python",
     "metadata": {},
     "outputs": [
      {
       "metadata": {},
       "output_type": "pyout",
       "prompt_number": 67,
       "text": [
        "['78', '123', '45', '67']"
       ]
      }
     ],
     "prompt_number": 67
    },
    {
     "cell_type": "code",
     "collapsed": false,
     "input": [
      "phone_number.parseString('0781234567').asList()"
     ],
     "language": "python",
     "metadata": {},
     "outputs": [
      {
       "metadata": {},
       "output_type": "pyout",
       "prompt_number": 68,
       "text": [
        "['78', '123', '45', '67']"
       ]
      }
     ],
     "prompt_number": 68
    },
    {
     "cell_type": "markdown",
     "metadata": {},
     "source": [
      "This is not more or less robust than using a regular expression. However, you might be able to get better error messages out of PyParsing since it will tell you where in the string it first detects a parse error."
     ]
    },
    {
     "cell_type": "heading",
     "level": 2,
     "metadata": {},
     "source": [
      "Repetition"
     ]
    },
    {
     "cell_type": "markdown",
     "metadata": {},
     "source": [
      "It is easy to match a parser zero or more times:"
     ]
    },
    {
     "cell_type": "code",
     "collapsed": false,
     "input": [
      "from pyparsing import ZeroOrMore, Keyword\n",
      "\n",
      "operator = Keyword('+') | Keyword('-') | Keyword('*')\n",
      "identifier = Word(alphas)\n",
      "number = Word(nums)\n",
      "operand = identifier | number\n",
      "\n",
      "expr = operand('first') + ZeroOrMore(operator + operand('last'))\n",
      "\n",
      "expr.parseString('10 + x - 30 * y + z', parseAll=True).asDict()"
     ],
     "language": "python",
     "metadata": {},
     "outputs": [
      {
       "metadata": {},
       "output_type": "pyout",
       "prompt_number": 69,
       "text": [
        "{'first': '10', 'last': 'z'}"
       ]
      }
     ],
     "prompt_number": 69
    },
    {
     "cell_type": "heading",
     "level": 2,
     "metadata": {},
     "source": [
      "Recursion"
     ]
    },
    {
     "cell_type": "markdown",
     "metadata": {},
     "source": [
      "Parsers can refer to other parsers, which makes the construction of the overall parser modular and easy to test. Parsers can also refer to themselves, thereby creating a *recursive* parser. This occurs naturally when parsing nested expressions -- precisely the kind of expressions that cannot be parsed by a regular expression.\n",
      "\n",
      "Since parsers are Python variables, we cannot do\n",
      "\n",
      "    parser = something + parser\n",
      "    \n",
      "directly since `parser` would be undefined. To get around this, we need to use the `Forward` class:"
     ]
    },
    {
     "cell_type": "code",
     "collapsed": false,
     "input": [
      "from pyparsing import Forward\n",
      "\n",
      "parser = Forward()\n",
      "parser << (Literal('x') | (Literal('[') + parser + Literal(']')))"
     ],
     "language": "python",
     "metadata": {},
     "outputs": [
      {
       "metadata": {},
       "output_type": "pyout",
       "prompt_number": 70,
       "text": [
        "Forward: {\"x\" | {{\"[\" ...} \"]\"}}"
       ]
      }
     ],
     "prompt_number": 70
    },
    {
     "cell_type": "markdown",
     "metadata": {},
     "source": [
      "This parser will parse a correctly bracketed `x`, with arbitrarily many brackets:"
     ]
    },
    {
     "cell_type": "code",
     "collapsed": false,
     "input": [
      "parser.parseString('x').asList()"
     ],
     "language": "python",
     "metadata": {},
     "outputs": [
      {
       "metadata": {},
       "output_type": "pyout",
       "prompt_number": 71,
       "text": [
        "['x']"
       ]
      }
     ],
     "prompt_number": 71
    },
    {
     "cell_type": "code",
     "collapsed": false,
     "input": [
      "parser.parseString('[[[[x]]]]').asList()"
     ],
     "language": "python",
     "metadata": {},
     "outputs": [
      {
       "metadata": {},
       "output_type": "pyout",
       "prompt_number": 72,
       "text": [
        "['[', '[', '[', '[', 'x', ']', ']', ']', ']']"
       ]
      }
     ],
     "prompt_number": 72
    },
    {
     "cell_type": "markdown",
     "metadata": {},
     "source": [
      "Bad nesting causes an error:"
     ]
    },
    {
     "cell_type": "code",
     "collapsed": false,
     "input": [
      "try:\n",
      "    parser.parseString('[[x]').asList()\n",
      "except ParseException, e:\n",
      "    print >> sys.stderr, e"
     ],
     "language": "python",
     "metadata": {},
     "outputs": [
      {
       "output_type": "stream",
       "stream": "stderr",
       "text": [
        "Expected \"]\" (at char 4), (line:1, col:5)\n"
       ]
      }
     ],
     "prompt_number": 73
    },
    {
     "cell_type": "markdown",
     "metadata": {},
     "source": [
      "Be very careful with the precedence of `<<` compared to other operators such as `|` and `+`. This does not do what we want:"
     ]
    },
    {
     "cell_type": "code",
     "collapsed": false,
     "input": [
      "bad = Forward()\n",
      "bad << Literal('x') | (Literal('[') + bad + Literal(']'))\n",
      "try:\n",
      "    bad.parseString('[x]')\n",
      "except ParseException, e:\n",
      "    print >> sys.stderr, e"
     ],
     "language": "python",
     "metadata": {},
     "outputs": [
      {
       "output_type": "stream",
       "stream": "stderr",
       "text": [
        "Expected \"x\" (at char 0), (line:1, col:1)\n"
       ]
      }
     ],
     "prompt_number": 74
    },
    {
     "cell_type": "markdown",
     "metadata": {},
     "source": [
      "What happened here is that we add `Literal('x')` to `bad`, and *then* evaluate the `|` alternative operator. The result of the alternative is thrown away. See the [Python reference][1] for the operator precedences.\n",
      "\n",
      "[1]: https://docs.python.org/2/reference/expressions.html#operator-precedence"
     ]
    },
    {
     "cell_type": "heading",
     "level": 2,
     "metadata": {},
     "source": [
      "Ambigious Parsers and Left Recursion"
     ]
    },
    {
     "cell_type": "markdown",
     "metadata": {},
     "source": [
      "Since PyParsing builds a recursive descent parser behind the scenes, you must be careful about *left recursion* in your parsers. The above parser is non-ambigious, which means that there is exactly one production that match at any given time while parsing. It can thus be implemented without backtracking. An *ambigious* parser is a parser where there are multiple production rules that can apply.\n",
      "\n",
      "Ambigious parsers need more care:"
     ]
    },
    {
     "cell_type": "code",
     "collapsed": false,
     "input": [
      "name = Word(alphas)\n",
      "bad = Forward()\n",
      "bad << (name | (name + '.' + bad))\n",
      "bad.parseString('foo.bar.baz').asList()"
     ],
     "language": "python",
     "metadata": {},
     "outputs": [
      {
       "metadata": {},
       "output_type": "pyout",
       "prompt_number": 75,
       "text": [
        "['foo']"
       ]
      }
     ],
     "prompt_number": 75
    },
    {
     "cell_type": "markdown",
     "metadata": {},
     "source": [
      "This parser is bad because the `|` alternative operator eagerly uses the first parser that matches. In other words, it does not try the `name + '.' + bad` branch when it sees that `name` matches. To correctly parse this, we need to use the `^` operator which tries both parsers and uses the one that matched the longest string:"
     ]
    },
    {
     "cell_type": "code",
     "collapsed": false,
     "input": [
      "good = Forward()\n",
      "good << (name ^ (name + Suppress('.') + good))\n",
      "\n",
      "good.parseString('foo.bar.baz').asList()"
     ],
     "language": "python",
     "metadata": {},
     "outputs": [
      {
       "metadata": {},
       "output_type": "pyout",
       "prompt_number": 76,
       "text": [
        "['foo', 'bar', 'baz']"
       ]
      }
     ],
     "prompt_number": 76
    },
    {
     "cell_type": "markdown",
     "metadata": {},
     "source": [
      "We can encounter another problem with ambigious parsers: left recursion. This occurs when the recursive descent parser used behind the scenes keep trying the same branch:"
     ]
    },
    {
     "cell_type": "code",
     "collapsed": false,
     "input": [
      "bad = Forward()\n",
      "bad << ((bad + '.' + name) ^ name)\n",
      "\n",
      "try:\n",
      "    bad.parseString('foo.bar.baz')\n",
      "except RuntimeError, e:\n",
      "    print >> sys.stderr, e"
     ],
     "language": "python",
     "metadata": {},
     "outputs": [
      {
       "output_type": "stream",
       "stream": "stderr",
       "text": [
        "maximum recursion depth exceeded\n"
       ]
      }
     ],
     "prompt_number": 77
    },
    {
     "cell_type": "markdown",
     "metadata": {},
     "source": [
      "The problem is not simple the ordering of parsers around the `^` operator:"
     ]
    },
    {
     "cell_type": "code",
     "collapsed": false,
     "input": [
      "bad = Forward()\n",
      "bad << (name ^ (bad + '.' + name))\n",
      "\n",
      "try:\n",
      "    print bad.parseString('foo.bar.baz', parseAll=True)\n",
      "except RuntimeError, e:\n",
      "    print >> sys.stderr, e"
     ],
     "language": "python",
     "metadata": {},
     "outputs": [
      {
       "output_type": "stream",
       "stream": "stderr",
       "text": [
        "maximum recursion depth exceeded\n"
       ]
      }
     ],
     "prompt_number": 78
    },
    {
     "cell_type": "markdown",
     "metadata": {},
     "source": [
      "For such a parser, the only option is to refactor it into a right recursive parser as above.\n",
      "\n",
      "Don't forget the `ZeroOrMore` helper, which allows you to simply write:"
     ]
    },
    {
     "cell_type": "code",
     "collapsed": false,
     "input": [
      "better = name + ZeroOrMore(Suppress('.') + name)\n",
      "better.parseString('foo.bar.baz').asList()"
     ],
     "language": "python",
     "metadata": {},
     "outputs": [
      {
       "metadata": {},
       "output_type": "pyout",
       "prompt_number": 79,
       "text": [
        "['foo', 'bar', 'baz']"
       ]
      }
     ],
     "prompt_number": 79
    },
    {
     "cell_type": "heading",
     "level": 2,
     "metadata": {},
     "source": [
      "Parsing Boolean Expressions"
     ]
    },
    {
     "cell_type": "markdown",
     "metadata": {},
     "source": [
      "We should now be able to make a parser and evaluator for a simple language of Boolean expressions. We will have\n",
      "\n",
      "* Comparison operators: `==` and `!=`\n",
      "* Logical operators: `and` and `or`\n",
      "* Variables: unquoted strings such as `name`\n",
      "* Values: duoble-quoted strings and integers"
     ]
    },
    {
     "cell_type": "code",
     "collapsed": false,
     "input": [
      "from pyparsing import QuotedString, Group\n",
      "\n",
      "variable = Word(alphas)\n",
      "integer = Word(nums)\n",
      "string = QuotedString(quoteChar='\"')\n",
      "value = variable | integer | string\n",
      "\n",
      "comp_op = Literal('==') | Literal('!=')\n",
      "bool_op = Keyword('and') | Keyword('or')\n",
      "\n",
      "comp = Group(value + comp_op + value)\n",
      "\n",
      "bool_expr = comp + ZeroOrMore(bool_op + comp)\n",
      "\n",
      "bool_expr.parseString(\n",
      "  'name == \"Peter\" and zipcode == 8000 or zipcode == 8004').asList()"
     ],
     "language": "python",
     "metadata": {},
     "outputs": [
      {
       "metadata": {},
       "output_type": "pyout",
       "prompt_number": 80,
       "text": [
        "[['name', '==', 'Peter'],\n",
        " 'and',\n",
        " ['zipcode', '==', '8000'],\n",
        " 'or',\n",
        " ['zipcode', '==', '8004']]"
       ]
      }
     ],
     "prompt_number": 80
    },
    {
     "cell_type": "markdown",
     "metadata": {},
     "source": [
      "This parses the input, but fails to add much structure. In particular, there's no operator precedence implemented -- we only get a flat list with `and` and `or` back. To get more structure, we will refactor the grammar so that `X or Y` is parsed before `X and Y`. That makes `and` bind tighter than `or`:"
     ]
    },
    {
     "cell_type": "code",
     "collapsed": false,
     "input": [
      "bool_and = Group(comp + ZeroOrMore(Keyword('and') + comp))\n",
      "bool_or = Group(bool_and + ZeroOrMore(Keyword('or') + bool_and))\n",
      "bool_expr = bool_or\n",
      "\n",
      "bool_expr.parseString('name == \"Peter\" and zipcode == 8000 or zipcode == 8004').asList()"
     ],
     "language": "python",
     "metadata": {},
     "outputs": [
      {
       "metadata": {},
       "output_type": "pyout",
       "prompt_number": 81,
       "text": [
        "[[[['name', '==', 'Peter'], 'and', ['zipcode', '==', '8000']],\n",
        "  'or',\n",
        "  [['zipcode', '==', '8004']]]]"
       ]
      }
     ],
     "prompt_number": 81
    },
    {
     "cell_type": "markdown",
     "metadata": {},
     "source": [
      "To actually evaluate the expression, we will add parse actions:"
     ]
    },
    {
     "cell_type": "code",
     "collapsed": false,
     "input": [
      "integer.setParseAction(lambda toks: lambda env: int(toks[0]))\n",
      "\n",
      "result = integer.parseString('123').asList()\n",
      "func = result[0]\n",
      "func({})"
     ],
     "language": "python",
     "metadata": {},
     "outputs": [
      {
       "metadata": {},
       "output_type": "pyout",
       "prompt_number": 82,
       "text": [
        "123"
       ]
      }
     ],
     "prompt_number": 82
    },
    {
     "cell_type": "markdown",
     "metadata": {},
     "source": [
      "What we did here was to define a parse action that is a function that given an environment (a mapping of variable names to values) will return a value. Here the environment is ignored and we return the fixed integer that was parsed from the string. We need to do the same thing for strings:"
     ]
    },
    {
     "cell_type": "code",
     "collapsed": false,
     "input": [
      "string.setParseAction(lambda toks: lambda env: toks[0])\n",
      "result = string.parseString('\"foo bar\"').asList()\n",
      "func = result[0]\n",
      "func({})"
     ],
     "language": "python",
     "metadata": {},
     "outputs": [
      {
       "metadata": {},
       "output_type": "pyout",
       "prompt_number": 83,
       "text": [
        "'foo bar'"
       ]
      }
     ],
     "prompt_number": 83
    },
    {
     "cell_type": "markdown",
     "metadata": {},
     "source": [
      "The parse action for `variable` actually uses the environment to lookup the value for the variable:"
     ]
    },
    {
     "cell_type": "code",
     "collapsed": false,
     "input": [
      "variable.setParseAction(lambda toks: lambda env: env.get(toks[0]))\n",
      "\n",
      "result = variable.parseString('foo').asList()\n",
      "func = result[0]\n",
      "func({'foo': 'a value'})"
     ],
     "language": "python",
     "metadata": {},
     "outputs": [
      {
       "metadata": {},
       "output_type": "pyout",
       "prompt_number": 84,
       "text": [
        "'a value'"
       ]
      }
     ],
     "prompt_number": 84
    },
    {
     "cell_type": "markdown",
     "metadata": {},
     "source": [
      "The `comp` parse action require us to use the environment we're given to evaluate the nested expressions first. When that is done, we can compare them and return the result:"
     ]
    },
    {
     "cell_type": "code",
     "collapsed": false,
     "input": [
      "def compAction(toks):\n",
      "    def action(env):\n",
      "        left = toks[0](env)\n",
      "        comp = toks[1]\n",
      "        right = toks[2](env)\n",
      "        if comp == '==':\n",
      "            return left == right\n",
      "        else:\n",
      "            return left != right\n",
      "    return action\n",
      "\n",
      "comp = value + comp_op + value\n",
      "comp.setParseAction(compAction)\n",
      "\n",
      "result = comp.parseString('foo == \"hi\"').asList()\n",
      "func = result[0]\n",
      "func({'foo': 'hi'}), func({'foo': 'not hi'})"
     ],
     "language": "python",
     "metadata": {},
     "outputs": [
      {
       "metadata": {},
       "output_type": "pyout",
       "prompt_number": 85,
       "text": [
        "(True, False)"
       ]
      }
     ],
     "prompt_number": 85
    },
    {
     "cell_type": "markdown",
     "metadata": {},
     "source": [
      "The `bool_and` parser works similarly. A small wringle here is that we can have arbitrarily many tokens in our list since our `bool_and` parser isn't just binary, it collects all expressions on the same level:"
     ]
    },
    {
     "cell_type": "code",
     "collapsed": false,
     "input": [
      "bool_and = comp + ZeroOrMore(Keyword('and').suppress() + comp)\n",
      "bool_and.setParseAction(lambda toks: lambda env: all(tok(env) for tok in toks))\n",
      "\n",
      "result = bool_and.parseString('x == 10 and y == 20 and z == 30').asList()\n",
      "func = result[0]\n",
      "func({'x': 10, 'y': 20, 'z': 30}), func({'x': 10, 'y': 25, 'z': 30})"
     ],
     "language": "python",
     "metadata": {},
     "outputs": [
      {
       "metadata": {},
       "output_type": "pyout",
       "prompt_number": 86,
       "text": [
        "(True, False)"
       ]
      }
     ],
     "prompt_number": 86
    },
    {
     "cell_type": "code",
     "collapsed": false,
     "input": [
      "bool_or = bool_and + ZeroOrMore(Keyword('or').suppress() + bool_and)\n",
      "bool_or.setParseAction(lambda toks: lambda env: any(tok(env) for tok in toks))\n",
      "\n",
      "result = bool_or.parseString('x == 10 or y == 20 or z == 30').asList()\n",
      "func = result[0]\n",
      "func({'x': 10, 'y': 20, 'z': 30}), func({'x': 15, 'y': 25, 'z': 35})"
     ],
     "language": "python",
     "metadata": {},
     "outputs": [
      {
       "metadata": {},
       "output_type": "pyout",
       "prompt_number": 87,
       "text": [
        "(True, False)"
       ]
      }
     ],
     "prompt_number": 87
    },
    {
     "cell_type": "markdown",
     "metadata": {},
     "source": [
      "Finally, we can redefine `bool_expr` and write a little convenience function to evaluate an expression with a certain environment:"
     ]
    },
    {
     "cell_type": "code",
     "collapsed": false,
     "input": [
      "bool_expr = bool_or\n",
      "\n",
      "def evaluate(expr, env):\n",
      "    result = bool_expr.parseString(expr)\n",
      "    func = result[0]\n",
      "    return func(env)\n",
      "\n",
      "# Find people names Peter in 8000, or anybody in 8004\n",
      "evaluate('name == \"Peter\" and zipcode == 8000 or zipcode == 8004',\n",
      "         {'name': 'Martin', 'zipcode': 8004})"
     ],
     "language": "python",
     "metadata": {},
     "outputs": [
      {
       "metadata": {},
       "output_type": "pyout",
       "prompt_number": 88,
       "text": [
        "True"
       ]
      }
     ],
     "prompt_number": 88
    },
    {
     "cell_type": "markdown",
     "metadata": {},
     "source": [
      "PyParsing actually has a `operatorPrecedence` helper function that will allow you to construct a parser similar to the above. The parser will construct a parse tree and you'll have to write an interpreter for it. That's not at all a bad idea -- it would allow you to do things like short-circuit Boolean logic, for example."
     ]
    },
    {
     "cell_type": "heading",
     "level": 2,
     "metadata": {},
     "source": [
      "Conclusion"
     ]
    },
    {
     "cell_type": "markdown",
     "metadata": {},
     "source": [
      "PyParsing makes it easy to construct parsers in an incremental fashion. The parsers constructed won't be the fastest parsers possible, but they will often end up being easy to understand and maintain."
     ]
    }
   ],
   "metadata": {}
  }
 ]
}