notebooks/1_RegularExpressions.ipynb

{
 "cells": [
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "# Regular Expressions"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    ">*\"Let’s say you have a problem, and you decide to solve it with regular expressions. Well, now you have two problems\"*"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "## Regular Expressions\n",
    "\n",
    "Regular expressions (a.k.a. **REs**, **regexes**, **regexpses**, **regex patterns**) are a tiny, specialized **programming language** used to parse and manipulate text.\n",
    "\n",
    "Regular expressions are available in:\n",
    "\n",
    "\n",
    "- applications involving text processing, e.g text editors and IDEs (e.g. emacs, vi, Notepad++);\n",
    "\n",
    "\n",
    "- the Unix command line (see `sed`, `grep`, `awk`);\n",
    "\n",
    "\n",
    "- those programming language that natively support them (e.g. Perl, Ruby, Tcl);\n",
    "\n",
    "\n",
    "- those programming language that support them through extension libraries (e.g. C, C++, Python)."
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Basically, a regex is **a pattern describing a portion of text**, that is typically used to:\n",
    "\n",
    "\n",
    "- check **if** a string has a given form\n",
    "\n",
    "\n",
    "- find **a** text portion that satisfies a given search criterion\n",
    "\n",
    "\n",
    "- find **all** the text portions that satisfy a given search criterion\n",
    "\n",
    "\n",
    "The ultimate goal being either to inspect a portion of text or to modify it in various possible ways (e.g. string replacement, tokenization etc.)"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Usually, search patterns can be paraphrased into natural languages as something like:\n",
    "\n",
    "- *\"non-digits sequences where the second character is upper-case\"*\n",
    "\n",
    "\n",
    "- *\"everything preceding a question mark\"*\n",
    "\n",
    "\n",
    "- *\"all those words that starts with a digit\"*"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "## Regular Expressions in Python"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    ">### Some Literature:\n",
    ">\n",
    "> - **[Sections 3.4 - 3.8](http://www.nltk.org/book/ch03.html#sec-regular-expressions-word-patterns)** of: S. Bird, S., E. Klein & W. Loper (2009). Natural Language Processing with Python, O'Reilly\n",
    ">\n",
    ">\n",
    "> - [**Regular Expression HOWTO**](https://docs.python.org/2/howto/regex.html): a gentle tutorial\n",
    ">\n",
    "> \n",
    "> - [**the official documentation**](https://docs.python.org/2/library/re.html) for the `re` module\n",
    ">\n",
    ">\n",
    "> - [**PyMOTW post**](https://pymotw.com/2/re/index.html) on the `re` module"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 1,
   "metadata": {},
   "outputs": [],
   "source": [
    "## Notebook settings \n",
    "\n",
    "# multiple lines of output per cell\n",
    "from IPython.core.interactiveshell import InteractiveShell\n",
    "InteractiveShell.ast_node_interactivity = \"all\""
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {
    "collapsed": true
   },
   "source": [
    "There are multiple regex implementations, each sharing a core syntax but with different extensions or advanced features, i.e. each has a different **flavor**. \n",
    "\n",
    "Python provides support for regex in the `re` module, whose syntax is based on the one used in Perl regex, plus some Python-specific enhancements."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 2,
   "metadata": {},
   "outputs": [],
   "source": [
    "import re"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "In the most simplistic form, the use of regular expressions in Python is a three step process:\n",
    "\n",
    "\n",
    "- a pattern is defined through a regex in string format;\n",
    "\n",
    "\n",
    "- the regex is compiled into a pattern object by means of the `re.compile()` method (note that this step is often implicitly performed by most of the top-level `re` methods we'll use);\n",
    "\n",
    "\n",
    "- the appropriate pattern object methods are used in accordance with our purposes (e.g. do we want to look for all thee matches or only one? do we want the match to start from the first character? do we want to modify the matching string?)"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "For instance, the `re.findall()` function is a top-level method that find all substrings where the regex matches, and returns them as a list. When used according to the following syntax:\n",
    "\n",
    "\n",
    "```python\n",
    "re.findall(\"pattern_string\", target_string, **Kwargs)\n",
    "```\n",
    "\n",
    "it creates a pattern object by calling the `re.compile()` method on the `pattern_string` and looks for all the matched in the \"target_string\"."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 3,
   "metadata": {},
   "outputs": [
    {
     "data": {
      "text/plain": [
       "['is', 'is']"
      ]
     },
     "execution_count": 3,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "# let's look for all the occurrence of the bigram \"is\" in the string: \"this is a string\"\n",
    "re.findall(r\"is\", \"this is a string\")"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "**NOTE**. The following alternative syntax can be used for most top-level methods:\n",
    "\n",
    "```python\n",
    "pattern_re = re.compile(\"pattern_string\")\n",
    "pattern_re.method(target_string)\n",
    "```\n",
    "\n",
    "(This may be useful if you don't want to compile the same regex each time your applying a given method, or when you want to apply several methods on the same pattern objects)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 4,
   "metadata": {},
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "['is', 'is']\n"
     ]
    }
   ],
   "source": [
    "# the same as the previous code cell\n",
    "pattern_re = re.compile(r\"is\")\n",
    "print(pattern_re.findall(\"this is a string\"))"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "> **Suggestion**\n",
    ">\n",
    "> An educational tool that can be used to consolidate your understanding of regular expression is the nltk **`re_show(pattern, string)`** module, which annotates the `string` in every place where the `pattern` is matched. Try it:"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 5,
   "metadata": {},
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "th{is} {is} a string\n"
     ]
    }
   ],
   "source": [
    "import nltk\n",
    "nltk.re_show(r\"is\", \"this is a string\")"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "## Regex: Syntax & Semantics"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "A pattern consists of:\n",
    "\n",
    "- **Atoms**: units specifying what we're looking for and where\n",
    "\n",
    "\n",
    "- **Operators** combining atoms into complex expressions"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "### Atoms\n",
    "\n",
    "- Single Characters\n",
    "\n",
    "\n",
    "- Dot\n",
    "\n",
    "\n",
    "- Class\n",
    "\n",
    "\n",
    "- Anchor"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "**Ordinary Characters** simply match themselves exactly. "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 6,
   "metadata": {},
   "outputs": [
    {
     "data": {
      "text/plain": [
       "['t']"
      ]
     },
     "execution_count": 6,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "re.findall(r\"t\", \"This is a string\")"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "By default, regex are **case-sensitive**, but you can use the `re.I` (short for `re.IGNORECASE`) compilation flag "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 7,
   "metadata": {},
   "outputs": [
    {
     "data": {
      "text/plain": [
       "['T', 't']"
      ]
     },
     "execution_count": 7,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "re.findall(r\"t\", \"This is a string\", re.I)"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "A **dot** matches any single character, except the new line character \"`\\n`\""
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 8,
   "metadata": {},
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "['t', 'h', 'i', 's', 'i', 's', 'a', 's', 't', 'r', 'i', 'n', 'g']\n"
     ]
    }
   ],
   "source": [
    "print(re.findall(r\".\", \"this\\nis\\na\\nstring\"))"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "... but if you want the dot to match also the new line character, use the `re.S` (short for `re.DOTALL`) flag "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 9,
   "metadata": {},
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "['t', 'h', 'i', 's', '\\n', 'i', 's', '\\n', 'a', '\\n', 's', 't', 'r', 'i', 'n', 'g']\n"
     ]
    }
   ],
   "source": [
    "print(re.findall(r\".\", \"this\\nis\\na\\nstring\", re.S))"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "**Classes** define sets of characters, **any one of which** may match **one of the characters** in our string. \n",
    "\n",
    "The set of characters of interest in enclosed in `[`square brackets`]`"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 10,
   "metadata": {},
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "['i', 's', 'i', 's', 's', 'i']\n"
     ]
    }
   ],
   "source": [
    "# let's look for \"i\" OR \"s\"\n",
    "print(re.findall(r\"[is]\", \"this is a string\"))"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "A **range** is indicated by a dash `-`:"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 11,
   "metadata": {},
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "['d', 'e', 'e', 'a']\n"
     ]
    }
   ],
   "source": [
    "# let's look for any of the following letters: \"a\", \"b\", \"c\", \"d\", \"e\"\n",
    "print(re.findall(r\"[a-e]\", \"this is definitively a string\"))"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "When used in the definition of a class, `^` is an **exclusion operator**. It means \"all but this set of characters\":"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 12,
   "metadata": {},
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "['t', 'h', 's', ' ', 's', ' ', 'd', 'f', 'n', 't', 'v', 'l', 'y', ' ', ' ', 's', 't', 'r', 'n', 'g']\n"
     ]
    }
   ],
   "source": [
    "# let's look for any character other than a vowel\n",
    "print(re.findall(r\"[^aeiou]\", \"this is definitively a string\"))"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Some classes are associated with a special notation:\n",
    "\n",
    "- `\\d`: any decimal digit; this is equivalent to the class `[0-9]`\n",
    "\n",
    "\n",
    "- `\\D`: any non-digit character; this is equivalent to the class `[^0-9]`\n",
    "\n",
    "\n",
    "- `\\s`: any whitespace character; this is equivalent to the class `[ \\t\\n\\r\\f\\v]`\n",
    "\n",
    "\n",
    "- `\\S`: any non-whitespace character; this is equivalent to the class `[^ \\t\\n\\r\\f\\v]`\n",
    "\n",
    "\n",
    "- `\\w`: any alphanumeric character; this is equivalent to the class `[a-zA-Z0-9_]`\n",
    "\n",
    "\n",
    "- `\\W`: any non-alphanumeric character; this is equivalent to the class `[^a-zA-Z0-9_]`"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 13,
   "metadata": {},
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "['t', 'h', 'i', 's', 'i', 's', 'd', 'e', 'f', 'i', 'n', 'i', 't', 'i', 'v', 'e', 'l', 'y', 'a', 's', 't', 'r', 'i', 'n', 'g']\n"
     ]
    }
   ],
   "source": [
    "# let's look for any character but the whitespaces\n",
    "print(re.findall(r\"\\S\", \"this is definitively a string\"))"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "**Tab**, **newlines** and **returns** can be matched also by using the special characters `\\t`, `\\n` and `\\r`"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 14,
   "metadata": {},
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "['\\n', '\\n', '\\n']\n"
     ]
    }
   ],
   "source": [
    "print(re.findall(r\"\\n\", \"this\\nis\\na\\nstring\", re.S))"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "** A Note about the escape character \"`\\`\"**: The escape character is used to mark:\n",
    "\n",
    "\n",
    "- a special use of a normal character (e.g. the `\\d` class above)\n",
    "\n",
    "\n",
    "- the literal use of meta-characters (i.e. `\".\", \"^\", \"$\", \"*\", \"+\", \"?\", \"{\", \"[\", \"]\", \"\\\", \"|\", \"(\", \")\"`)..."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 15,
   "metadata": {},
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "['.', '.', '.']\n"
     ]
    }
   ],
   "source": [
    "# let's look for any dot in our string\n",
    "print(re.findall(r\"\\.\", \"this.is.a.string\"))"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 16,
   "metadata": {},
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "['[', ']']\n"
     ]
    }
   ],
   "source": [
    "# let's look for square brackets in our string\n",
    "from IPython.core.interactiveshell import InteractiveShell\n",
    "InteractiveShell.ast_node_interactivity = \"all\"\n",
    "print(re.findall(r\"[\\[\\]]\", \"[this] is a string\"))"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "The use of the backslash as an escape characters may [conflict](https://docs.python.org/2/howto/regex.html#the-backslash-plague) with the Python use of the same character for the same purpose. \n",
    "\n",
    "The solution is to use the so-called **raw string notation** for regular expressions: by prepending `r` to our string (as we're doing in this notes) we signal the Python interpreter that backslashes should be not handled in any special way:"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 17,
   "metadata": {},
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "\\s\n"
     ]
    }
   ],
   "source": [
    "# let's look for the sequence \"\\s\" by using the REGULAR string notation\n",
    "print(re.findall(\"\\\\\\s\", \"\\section\")[0])"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 18,
   "metadata": {},
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "\\s\n"
     ]
    }
   ],
   "source": [
    "# let's look for the sequence \"\\s\" by using the RAW string notation\n",
    "print(re.findall(r\"\\\\s\", \"\\section\")[0])"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "**Anchors** are special characters that specify where (in which position of the target string) a given pattern should appear. As such, they **are not matched** to the text:\n",
    "\n",
    "- `^`: beginning of the line, it is used to match the pattern that follows when at the beginning of the lines\n",
    "\n",
    "\n",
    "- `$`: end of the line, it is used to match the preceding pattern at the end of the lines\n",
    "\n",
    "\n",
    "- `b`: word boundaries, i.e. every whitespace or non-alphanumeric character (underscore excluded)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 19,
   "metadata": {},
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "['s']\n"
     ]
    }
   ],
   "source": [
    "# let's look for the character \"s\" at the beginning of a line\n",
    "print(re.findall(r\"^s\", \"satisfaction\"))"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 20,
   "metadata": {},
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "['a']\n"
     ]
    }
   ],
   "source": [
    "# let's look for the character \"a\" at the end of a line\n",
    "print(re.findall(r\"a$\", \"gianluca\"))"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 21,
   "metadata": {},
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "['s', 's']\n"
     ]
    }
   ],
   "source": [
    "# let's look for the character \"s\" when at the end of a word\n",
    "print(re.findall(r\"s\\b\", \"this isn't a matter of strings\"))"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "**A Note about flags**: multiple flags can be concatenate by using the \"`|`\" symbol, in the following way:. "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 22,
   "metadata": {},
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "['Th', 'tr']\n"
     ]
    }
   ],
   "source": [
    "print(re.findall(r\"t.\", \"This\\nis\\na\\nstring\", re.S|re.I))"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "See the [official tutorial](https://docs.python.org/2/howto/regex.html#compilation-flags) for more info on the available compilation flags."
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "### Operators\n",
    "\n",
    "- Sequence\n",
    "\n",
    "\n",
    "- Alternation\n",
    "\n",
    "\n",
    "- Repetition\n",
    "\n",
    "\n",
    "- Groups"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "When a regex is composed by a **sequence** of atoms, it is implied that these are connected by a void sequence operator."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 23,
   "metadata": {},
   "outputs": [
    {
     "data": {
      "text/plain": [
       "['th']"
      ]
     },
     "execution_count": 23,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "# matches the pattern \"th\"\n",
    "re.findall(r\"th\", \"this is a string\")"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 24,
   "metadata": {},
   "outputs": [
    {
     "data": {
      "text/plain": [
       "['thi', 'tri']"
      ]
     },
     "execution_count": 24,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "# matches the pattern \"t\" + any character + \"i\"\n",
    "re.findall(r\"t.i\", \"this is a string\")"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 25,
   "metadata": {},
   "outputs": [
    {
     "data": {
      "text/plain": [
       "['38', '45']"
      ]
     },
     "execution_count": 25,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "# matches any number between 30 and 49\n",
    "re.findall(r\"[34][0-9]\", \"Nick is 29, Jason is 38 and Nick is 45\")"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "The **alternation** operator \"`|`\" is used to concatenate two or more alternative strings"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 26,
   "metadata": {},
   "outputs": [
    {
     "data": {
      "text/plain": [
       "['thi', 'tri']"
      ]
     },
     "execution_count": 26,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "# matches the patterns \"thi\" or \"tri\"\n",
    "re.findall(r\"thi|tri\", \"this is a string\")"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {
    "collapsed": true
   },
   "source": [
    "**Repetition** operators are used to specify that the atom or expression immediately before may be repeated.\n",
    "\n",
    "| Operator      |    Behavior  |\n",
    "|:-------------:|:-------------|\n",
    "| \\*\t        | Zero or more of previous atom |\n",
    "| +\t            | One or more of previous atom |\n",
    "| ?             | Zero or one of the previous atom (i.e. optional) |\n",
    "| {n}           | Exactly *n* repeats where *n* is a non-negative integer |\n",
    "| {n,}          | At least *n* repeats |\n",
    "| {,n}          | No more than *n* repeats |\n",
    "| {m,n}         | At least *m* and no more than *n* repeats |"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 27,
   "metadata": {},
   "outputs": [
    {
     "data": {
      "text/plain": [
       "['bo', 'b', 'b', 'bo']"
      ]
     },
     "execution_count": 27,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "# matches a \"b\" followed by 0 or 1 \"o\"s\n",
    "re.findall(r\"bo?\", \"bob is the abboooot\")"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 28,
   "metadata": {},
   "outputs": [
    {
     "data": {
      "text/plain": [
       "['bo', 'boooo']"
      ]
     },
     "execution_count": 28,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "# matches a \"b\" followed by 1 or more \"o\"s\n",
    "re.findall(r\"bo+\", \"bob is the abboooot\")"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 29,
   "metadata": {},
   "outputs": [
    {
     "data": {
      "text/plain": [
       "['bo', 'b', 'b', 'boooo']"
      ]
     },
     "execution_count": 29,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "# matches a \"b\" followed by 0 or more \"o\"s\n",
    "re.findall(r\"bo*\", \"bob is the abboooot\")"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 30,
   "metadata": {},
   "outputs": [
    {
     "data": {
      "text/plain": [
       "['bo', 'boooo']"
      ]
     },
     "execution_count": 30,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "# matches a \"b\" followed by 1 to 4 \"o\"s\n",
    "re.findall(r\"bo{1,4}\", \"bob is the abboooot\")"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 31,
   "metadata": {},
   "outputs": [
    {
     "data": {
      "text/plain": [
       "['boo']"
      ]
     },
     "execution_count": 31,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "# matches a \"b\" followed by 2 \"o\"s\n",
    "re.findall(r\"bo{2}\", \"bob is the abboooot\")"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 32,
   "metadata": {},
   "outputs": [
    {
     "data": {
      "text/plain": [
       "['boooo']"
      ]
     },
     "execution_count": 32,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "# matches a \"b\" followed by at least 2 \"o\"s\n",
    "re.findall(r\"bo{2,}\", \"bob is the abboooot\")"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "##### Multipliers in Python are greedy: they match the LONGEST possible string.\n",
    "\n",
    "By appending a question mark to the multipliers (i.e. using the mutipliers `*?`, `+?`, `??`, `{m,n}?`) we can force the multipliers to match **as LITTLE text as possible** (i.e. they become **lazy**)."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 33,
   "metadata": {},
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "greedy:\t['bo', 'b', 'b', 'bo']\n",
      "lazy:\t['b', 'b', 'b', 'b']\n"
     ]
    }
   ],
   "source": [
    "print (\"greedy:\\t\" + str(re.findall(r\"bo?\", \"bob is the abboooot\")))\n",
    "print (\"lazy:\\t\" + str(re.findall(r\"bo??\", \"bob is the abboooot\")))"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 34,
   "metadata": {},
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "greedy:\t['bo', 'boooo']\n",
      "lazy:\t['bo', 'bo']\n"
     ]
    }
   ],
   "source": [
    "print (\"greedy:\\t\" + str(re.findall(r\"bo+\", \"bob is the abboooot\")))\n",
    "print (\"lazy:\\t\" + str(re.findall(r\"bo+?\", \"bob is the abboooot\")))"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 35,
   "metadata": {},
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "greedy:\t['bo', 'b', 'b', 'boooo']\n",
      "lazy:\t['b', 'b', 'b', 'b']\n"
     ]
    }
   ],
   "source": [
    "print (\"greedy:\\t\" + str(re.findall(r\"bo*\", \"bob is the abboooot\")))\n",
    "print (\"lazy:\\t\" + str(re.findall(r\"bo*?\", \"bob is the abboooot\")))"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 36,
   "metadata": {},
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "greedy:\t['bo', 'boooo']\n",
      "lazy:\t['bo', 'bo']\n"
     ]
    }
   ],
   "source": [
    "print (\"greedy:\\t\" + str(re.findall(r\"bo{1,4}\", \"bob is the abboooot\")))\n",
    "print (\"lazy:\\t\" + str(re.findall(r\"bo{1,4}?\", \"bob is the abboooot\")))"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Operators apply also to **sequences of atoms**, and their scope is delimited by `(` round brackets `)` "
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "**NOTE**: due to its implementation, the `re.findall()` function may return counterintuitive results when dealing with groups. \n",
    "\n",
    "(TEST IT: try the following regexes `(a|b)+` and `((?:ab)+)\\1`, and compare the results with the examples below)"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "We will resort to **`re.finditer()`**, whose syntax is identical to `re.findall()` but that returns *a sequence of match object instances* as an iterator.\n",
    "\n",
    "**Match object instances** are the results of a verification of a regex on a string (if not match is found, `None` is returned). They have several methods and attributes, the most important of which are:\n",
    "\n",
    "| Method / Attribute |    Purpose  |\n",
    "|:------------------:|:-------------|\n",
    "| group()\t         | Return the string matched by the regex |\n",
    "| start()\t         | Return the starting position of the match |\n",
    "| end()              | Return the ending position of the match |\n",
    "| span()             | Return a tuple containing the (start, end) of the match |"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 37,
   "metadata": {},
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "ab\n",
      "abb\n"
     ]
    }
   ],
   "source": [
    "# matches \"a\" followed by 1 or more \"b\"s\n",
    "matches = re.finditer(r\"ab+\", \"bob is the ababboooot\")\n",
    "for m in matches:\n",
    "    print (m.group())"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 38,
   "metadata": {},
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "abab\n"
     ]
    }
   ],
   "source": [
    "# matches one or more \"ab\" sequences\n",
    "matches = re.finditer(r\"(ab)+\", \"bob is the ababboooot\")\n",
    "for m in matches:\n",
    "    print (m.group())"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 39,
   "metadata": {},
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "b\n",
      "b\n",
      "ababb\n"
     ]
    }
   ],
   "source": [
    "# matches any sequence composed by at least 1 of the following characters \"a\" or \"b\"\n",
    "matches = re.finditer(r\"(a|b)+\", \"bob is the ababboooot\")\n",
    "for m in matches:\n",
    "    print (m.group())"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Depending on whether the enclosed sequence of characters should be **memorized** or not, groups can be divided into:\n",
    "\n",
    "\n",
    "- **Capturing** groups save the enclosed string into a temporary variable whose value can be referred to using the notation `\\NUMBER`, where number points at the position of the group in the regex. For instance: `\\1` denotes the leftmost group of characters, `\\2` the one following the leftmost and so forth. Capturing groups are marked by `(` round brackets `)`, that is by the notation we've adopted so far.\n",
    "\n",
    "\n",
    "- **Non capturing** groups do not memorize the enclosed sequence of atoms. These groups are marked by the `(?: ... )` syntax.\n",
    "\n",
    "\n",
    "(Capturing groups can also be **named**, a [topic](https://docs.python.org/2/howto/regex.html#non-capturing-and-named-groups) that we leave to the interested student)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 40,
   "metadata": {},
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "abcab\n",
      "ababcab\n",
      "ababcab\n"
     ]
    }
   ],
   "source": [
    "# matches sequences composed by: one or more \"ab\" sequences followed by a \"c\" plus one \"ab\" sequence\n",
    "matches = re.finditer(r\"(ab)+c\\1\", \"abcab ababcab ababcabab\")\n",
    "for m in matches:\n",
    "    print (m.group())"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 41,
   "metadata": {},
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "abcab\n",
      "abcab\n",
      "ababcabab\n"
     ]
    }
   ],
   "source": [
    "# matches sequences composed by: one or more \"ab\" sequences followed by a \"c\" plus the same \"ab\" sequence preceding \"c\"\n",
    "matches = re.finditer(r\"((?:ab)+)c\\1\", \"abcab ababcab ababcabab\")\n",
    "for m in matches:\n",
    "    print (m.group())"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 42,
   "metadata": {},
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "abba\n",
      "abba\n",
      "abbbba\n",
      "aabbaa\n"
     ]
    }
   ],
   "source": [
    "# matches one or more \"a\"s followed by one or more \"b\"s  plus the repetition of the preceding pattern reversed\n",
    "matches = re.finditer(r\"(a+)(b+)\\2\\1\", \"abba abbaa abbba abbbba aabbaa\")\n",
    "for m in matches:\n",
    "    print (m.group())"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Groups info (i.e. start and ending position, matching subgroup) can be retrieved also by passing their index to the `group()`, `start()`, `end()` and `span()` methods, by adopting the following convention:\n",
    "\n",
    "\n",
    "- **Group 0** is always present; it’s the whole regex (i.e the default method of any match object method):"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 43,
   "metadata": {},
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "abba abba\n",
      "abba abba\n",
      "abbbba abbbba\n",
      "aabbaa aabbaa\n"
     ]
    }
   ],
   "source": [
    "matches = re.finditer(r\"(a+)(b+)\\2\\1\", \"abba abbaa abbba abbbba aabbaa\")\n",
    "for m in matches:\n",
    "    print (m.group(), m.group(0))"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {
    "collapsed": true
   },
   "source": [
    "- **Subgroups** are numbered from 1 upward: to determine the number, just count the opening parenthesis characters, going **from left to right**."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 44,
   "metadata": {},
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "('abba', 'a', 'b')\n",
      "('abba', 'a', 'b')\n",
      "('abbbba', 'a', 'bb')\n",
      "('aabbaa', 'aa', 'b')\n"
     ]
    }
   ],
   "source": [
    "matches = re.finditer(r\"(a+)(b+)\\2\\1\", \"abba abbaa abbba abbbba aabbaa\")\n",
    "for m in matches:\n",
    "    print (m.group(0, 1, 2))"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 45,
   "metadata": {},
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "('abcbabc', 'ab', 'b', 'c')\n",
      "('abbcbbabbc', 'abb', 'bb', 'c')\n",
      "('aabbcbbaabbc', 'aabb', 'bb', 'c')\n"
     ]
    }
   ],
   "source": [
    "# nested groups: group 2 includes group 1\n",
    "matches = re.finditer(r\"(a+(b+))(c+)\\2\\1\\3\", \"abcbabc abbcbbabbc aabbcbbaabbc\")\n",
    "for m in matches:\n",
    "    print (m.group(0, 1, 2, 3))"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "The `.groups()` method returns a tuple containing the strings for all the subgroups, **from 1 upwards** (i.e. there's no 0 position)."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 46,
   "metadata": {},
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "('ab',)\n",
      "('ab',)\n",
      "('ab',)\n"
     ]
    }
   ],
   "source": [
    "matches = re.finditer(r\"(ab)+c\\1\", \"abcab ababcab ababcabab\")\n",
    "for m in matches:\n",
    "    print (m.groups())"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {
    "collapsed": true
   },
   "source": [
    "## Main uses for Python Regexes:"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 47,
   "metadata": {},
   "outputs": [],
   "source": [
    "# the data we'll work with\n",
    "\n",
    "taxi_services = \"\"\"Amsterdam (North Holland): 020 677 7777\n",
    "The Hague (South Holland): 070 383 0830\n",
    "Rotterdam (South Holland): 010 462 6333\n",
    "Utrecht (Utrecht): 030 230 0400\"\"\"\n",
    "\n",
    "pattern = r'([\\w ]+) \\(([\\w ]+)\\): ([\\d ]+)'\n",
    "regex = re.compile(pattern)"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {
    "collapsed": true
   },
   "source": [
    "### 1. Match / Find (just one match)\n",
    "\n",
    "- `re.search(pattern,string)`: look for the first location where the regex pattern produces a match, and return a MatchObject instance (return `None` if no matches)\n",
    "\n",
    "- `re.match(pattern,string)`: return a MatchObject instance only if the regex patterns produces a match at the beginning of the string"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 48,
   "metadata": {},
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "*** Is there a Match? ***\n",
      "Yes\n"
     ]
    }
   ],
   "source": [
    "# Task 1: Is there a match?\n",
    "print(\"*** Is there a Match? ***\")\n",
    "if regex.search(taxi_services):\n",
    "    print (\"Yes\")\n",
    "else:\n",
    "    print (\"No\")"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 49,
   "metadata": {},
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "*** First Match ***\n",
      "Overall match:  Amsterdam (North Holland): 020 677 7777\n",
      "Group 1 :  Amsterdam\n",
      "Group 2 :  North Holland\n",
      "Group 3 :  020 677 7777\n"
     ]
    }
   ],
   "source": [
    "# Task 2: What is the first match?\n",
    "print(\"*** First Match ***\")\n",
    "match = regex.search(taxi_services)\n",
    "if match:\n",
    "    print(\"Overall match: \", match.group(0))\n",
    "    print(\"Group 1 : \", match.group(1))\n",
    "    print(\"Group 2 : \", match.group(2))\n",
    "    print(\"Group 3 : \", match.group(3))"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {
    "collapsed": true
   },
   "source": [
    "### 2. Match / Find (multiple matches)\n",
    "\n",
    "- `re.findall(pattern,string)`: return all non-overlapping matches of pattern in string, as a list of strings\n",
    "\n",
    "- `re.finditer(pattern,string)`: return an iterator yielding MatchObject instances"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 50,
   "metadata": {},
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "*** Number of Matches ***\n",
      "4\n"
     ]
    }
   ],
   "source": [
    "# Task 3: How many matches are there?\n",
    "print(\"*** Number of Matches ***\")\n",
    "matches = regex.findall(taxi_services)\n",
    "print(len(matches))"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 51,
   "metadata": {},
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "*** All Matches ***\n",
      "\n",
      "------ Method 1: finditer ------\n",
      "\n",
      "--- Start of Match ---\n",
      "Overall match:  Amsterdam (North Holland): 020 677 7777\n",
      "Group 1 :  Amsterdam\n",
      "Group 2 :  North Holland\n",
      "Group 3 :  020 677 7777\n",
      "--- End of Match---\n",
      "\n",
      "--- Start of Match ---\n",
      "Overall match:  The Hague (South Holland): 070 383 0830\n",
      "Group 1 :  The Hague\n",
      "Group 2 :  South Holland\n",
      "Group 3 :  070 383 0830\n",
      "--- End of Match---\n",
      "\n",
      "--- Start of Match ---\n",
      "Overall match:  Rotterdam (South Holland): 010 462 6333\n",
      "Group 1 :  Rotterdam\n",
      "Group 2 :  South Holland\n",
      "Group 3 :  010 462 6333\n",
      "--- End of Match---\n",
      "\n",
      "--- Start of Match ---\n",
      "Overall match:  Utrecht (Utrecht): 030 230 0400\n",
      "Group 1 :  Utrecht\n",
      "Group 2 :  Utrecht\n",
      "Group 3 :  030 230 0400\n",
      "--- End of Match---\n",
      "\n"
     ]
    }
   ],
   "source": [
    "# Task 4: What are all the matches?\n",
    "print(\"*** All Matches ***\\n\")\n",
    "print(\"------ Method 1: finditer ------\\n\")\n",
    "for match in regex.finditer(taxi_services):\n",
    "    print (\"--- Start of Match ---\")\n",
    "    print(\"Overall match: \", match.group(0))\n",
    "    print(\"Group 1 : \", match.group(1))\n",
    "    print(\"Group 2 : \", match.group(2))\n",
    "    print(\"Group 3 : \", match.group(3))\n",
    "    print (\"--- End of Match---\\n\")"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 52,
   "metadata": {},
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "------ Method 2: findall ------\n",
      "\n",
      "--- Start of Match ---\n",
      "Overall Match:  Amsterdam (North Holland): 020 677 7777\n",
      "Group 1:  Amsterdam\n",
      "Group 2:  North Holland\n",
      "Group 3:  020 677 7777\n",
      "--- End of Match---\n",
      "\n",
      "--- Start of Match ---\n",
      "Overall Match:  The Hague (South Holland): 070 383 0830\n",
      "Group 1:  The Hague\n",
      "Group 2:  South Holland\n",
      "Group 3:  070 383 0830\n",
      "--- End of Match---\n",
      "\n",
      "--- Start of Match ---\n",
      "Overall Match:  Rotterdam (South Holland): 010 462 6333\n",
      "Group 1:  Rotterdam\n",
      "Group 2:  South Holland\n",
      "Group 3:  010 462 6333\n",
      "--- End of Match---\n",
      "\n",
      "--- Start of Match ---\n",
      "Overall Match:  Utrecht (Utrecht): 030 230 0400\n",
      "Group 1:  Utrecht\n",
      "Group 2:  Utrecht\n",
      "Group 3:  030 230 0400\n",
      "--- End of Match---\n",
      "\n"
     ]
    }
   ],
   "source": [
    "print(\"------ Method 2: findall ------\\n\")\n",
    "# if there are capture groups, findall doesn't return the overall match\n",
    "# a simple workaround is warp the whole pattern in a group\n",
    "\n",
    "wrappedregex = re.compile(\"\".join([\"(\", pattern, \")\"]))\n",
    "\n",
    "for match in wrappedregex.findall(taxi_services):\n",
    "    print (\"--- Start of Match ---\")\n",
    "    print (\"Overall Match: \",match[0])\n",
    "    print (\"Group 1: \",match[1])\n",
    "    print (\"Group 2: \",match[2])\n",
    "    print (\"Group 3: \",match[3])\n",
    "    print (\"--- End of Match---\\n\")"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {
    "collapsed": true
   },
   "source": [
    "### 3. Search and Replace\n",
    "\n",
    "- `re.sub(pattern, repl, string)`: return the string obtained by replacing the leftmost non-overlapping occurrences of `pattern` in `string` by the replacement `repl` (If the pattern isn’t found, `string` is returned unchanged)\n",
    "\n",
    "    * Note that you can use backreferences in `repl`: e.g. \\6 is replaced with the substring matched by group 6 in the pattern"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 53,
   "metadata": {},
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "*** Replacements ***\n",
      "Let's reverse the groups\n",
      "020 677 7777: Amsterdam (North Holland)\n",
      "070 383 0830: The Hague (South Holland)\n",
      "010 462 6333: Rotterdam (South Holland)\n",
      "030 230 0400: Utrecht (Utrecht)\n"
     ]
    }
   ],
   "source": [
    "# Task 5: Replace the matches\n",
    "\n",
    "print(\"*** Replacements ***\")\n",
    "print(\"Let's reverse the groups\")\n",
    "print (regex.sub(r'\\3: \\1 (\\2)', taxi_services))"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {
    "collapsed": true
   },
   "source": [
    "### 4. Split\n",
    "\n",
    "- `re.split(pattern, string, maxsplit=0)`: split `string` by the occurrences of `pattern` for a maximum of `maxsplit > 0` times. \n",
    "\n",
    "    * If capturing parentheses are used in pattern, then the text of all groups in the pattern are also returned as part of the resulting list."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 54,
   "metadata": {},
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "*** Splits ***\n",
      "Amsterdam (North Holland)\n",
      " 020 677 7777\n",
      "The Hague (South Holland)\n",
      " 070 383 0830\n",
      "Rotterdam (South Holland)\n",
      " 010 462 6333\n",
      "Utrecht (Utrecht)\n",
      " 030 230 0400\n"
     ]
    }
   ],
   "source": [
    "# Task 6: Split\n",
    "# Let's split at colons or newline characters\n",
    "\n",
    "print(\"*** Splits ***\")\n",
    "\n",
    "for split in re.split(r\"[:\\n]\", taxi_services):\n",
    "    print (split)"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {
    "collapsed": true
   },
   "source": [
    "### Quiz. \n",
    "\n",
    "How would you remove the whitespaces at the beginning of each phone number string?"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 55,
   "metadata": {},
   "outputs": [],
   "source": [
    "# your code here"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {
    "collapsed": true
   },
   "source": [
    "---"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {
    "collapsed": true
   },
   "source": [
    "## Your Turn"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "### Exercise 1.\n",
    "\n",
    "Solve the following exercise (from [NLTK CH 3.12](http://www.nltk.org/book/ch03.html#exercises): Exercises 6)\n",
    "\n",
    "Describe the class of strings matched by the following regular expressions and test them by using any appropriate function from the `re` module:\n",
    "\n",
    "- `[a-zA-Z]+`\n",
    "\n",
    "\n",
    "- `[A-Z][a-z]*`\n",
    "\n",
    "\n",
    "- `p[aeiou]{,2}t`\n",
    "\n",
    "\n",
    "- `\\d+(\\.\\d+)?`\n",
    "\n",
    "\n",
    "- `([^aeiou][aeiou][^aeiou])*`\n",
    "\n",
    "\n",
    "- `\\w+|[^\\w\\s]+`"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 56,
   "metadata": {},
   "outputs": [],
   "source": [
    "# your code here"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "### Exercise 2 (advanced, but helps with assignment 1).\n",
    "\n",
    "Implement the tokenizer described in [NLTK CH 3.7](http://www.nltk.org/book/ch03.html#regular-expressions-for-tokenizing-text) by using the appropriate method from the `re` module.\n",
    "\n",
    "\n",
    "- Test it on the raw text of the Wall Street Journal corpus, available in the `nltk.corpus.treebank_raw.raw()` method.\n",
    "\n",
    "\n",
    "- Explain how this tokenizer works by decomposing the regex pattern into smaller units (e.g. `([A-Z]\\.)+`) and reporting WSJ examples of character sequences caught by each subpattern.\n",
    "\n",
    "\n",
    "- List at least two linguistic phenomena that this tokenizer cannot handle properly."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 57,
   "metadata": {},
   "outputs": [],
   "source": [
    "# your code here"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "### Exercise 3 (advanced, see J&M, ch. 2).\n",
    "\n",
    "Let me introduce you to [ELIZA](https://en.wikipedia.org/wiki/ELIZA), a (simulation of a) Rogerian psychotherapist.\n",
    "\n",
    "Eliza is implemented by using a pattern matching and substitution methodology that gave users an illusion of understanding. It is a simple program that recognizes phrases like \"You are X\" and outputs questions or request of the form \"What makes you think I am X?\".\n",
    "\n",
    "Can you write a code that uses the `raw_input()` method and regular expressions to allow a user to recreate the following psychotherapy session?"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "```\n",
    "User: Men are all alike.\n",
    "\n",
    "ELIZA: IN WHAT WAY\n",
    "\n",
    "User: They're always bugging us about something or other.\n",
    "\n",
    "ELIZA: CAN YOU THINK OF A SPECIFIC EXAMPLE\n",
    "\n",
    "User: Well, my boyfriend made me come here.\n",
    "\n",
    "ELIZA: YOUR BOYFRIEND MADE YOU COME HERE\n",
    "\n",
    "User: He says I'm depressed much of the time.\n",
    "\n",
    "ELIZA: I AM SORRY TO HEAR YOU ARE DEPRESSED\n",
    "\n",
    "User: You are like my father in some ways.\n",
    "\n",
    "ELIZA: WHAT RESEMBLANCE DO YOU SEE\n",
    "\n",
    "User: You are not very aggressive but I think you don't want me to notice that.\n",
    "\n",
    "ELIZA: WHAT MAKES YOU THINK I AM NOT VERY AGGRESSIVE\n",
    "\n",
    "User: You don't argue with me.\n",
    "\n",
    "ELIZA: WHY DO YOU THINK I DON'T ARGUE WITH YOU\n",
    "\n",
    "User: You are afraid of me.\n",
    "\n",
    "ELIZA: DOES IT PLEASE YOU TO BELIEVE I AM AFRAID OF YOU\n",
    "```"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 58,
   "metadata": {},
   "outputs": [],
   "source": [
    "# your code here"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "---"
   ]
  }
 ],
 "metadata": {
  "kernelspec": {
   "display_name": "Python 3",
   "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.8.5"
  },
  "toc": {
   "base_numbering": 1,
   "nav_menu": {},
   "number_sections": true,
   "sideBar": true,
   "skip_h1_title": false,
   "title_cell": "Table of Contents",
   "title_sidebar": "Contents",
   "toc_cell": false,
   "toc_position": {},
   "toc_section_display": true,
   "toc_window_display": true
  }
 },
 "nbformat": 4,
 "nbformat_minor": 2
}