{
 "cells": [
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "# Opérateurs\n",
    "\n",
    "Toute méthode à un argument peut être utilisée comme un opérateur infixe.\n",
    "Cette particularité de Scala permet de définir facilement des DSL utilisables directement depuis Scala.\n",
    "\n",
    "Nous illustrons cette possibilité avec une classe représentant des expressions rationnelles."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 1,
   "metadata": {
    "collapsed": false
   },
   "outputs": [
    {
     "data": {
      "text/plain": [
       "Name: Compile Error\n",
       "Message: <console>:21: error: not found: type Union\n",
       "                  def +(x: RatExpr) = new Union(this, x)\n",
       "                                          ^\n",
       "<console>:22: error: not found: type Concat\n",
       "                  def ~(x: RatExpr) = new Concat(this, x)\n",
       "                                          ^\n",
       "<console>:23: error: not found: type Star\n",
       "                  def * = new Star(this)\n",
       "                              ^\n",
       "StackTrace: "
      ]
     },
     "execution_count": 1,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "abstract class RatExpr\n",
    "{\n",
    "    def +(x: RatExpr) = new Union(this, x)\n",
    "    def ~(x: RatExpr) = new Concat(this, x)\n",
    "    def * = new Star(this)\n",
    "\n",
    "}\n",
    "\n",
    "case class Character(val c: Char) extends RatExpr\n",
    "case class Union(val lhs: RatExpr, val rhs: RatExpr) extends RatExpr\n",
    "case class Concat(val lhs: RatExpr, val rhs: RatExpr) extends RatExpr\n",
    "case class Star(val expr: RatExpr) extends RatExpr\n",
    "\n",
    "implicit def char2Expr(x: Char) = new Character(x)\n",
    "\n",
    "val a: RatExpr = 'a'\n",
    "val b: RatExpr = 'b'\n",
    "val e1: RatExpr = (a + b).*\n",
    "val e2: RatExpr = (a ~ (a + b)).*\n"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "# Packrat Parsers\n",
    "\n",
    "Scala utilise la souplesse des opérateurs en fournissant un composant permettant de construire facilement des parsers, en Scala directement. Les parsers de Scala sont, par défaut, des parsers LL, qui ne supportent donc pas la récursion gauche.\n",
    "Nous nous concentrons sur les Packrat Parsers, qui utilisent un mécanisme de mémoïzation leur permettant d'implémenter des parsers LL(*) et de gérer la récursion gauche."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 2,
   "metadata": {
    "collapsed": false
   },
   "outputs": [
    {
     "data": {
      "text/plain": [
       "Name: Compile Error\n",
       "Message: <console>:25: error: not found: type PackratParser\n",
       "    lazy val char: PackratParser[RatExpr] = \"\"\"[a-zA-Z]\"\"\".r ^^{ new Character(_) }\n",
       "                   ^\n",
       "<console>:27: error: not found: type PackratParser\n",
       "    lazy val expr: PackratParser[RatExpr] =\n",
       "                   ^\n",
       "<console>:25: error: value ^^ is not a member of scala.util.matching.Regex\n",
       "    lazy val char: PackratParser[RatExpr] = \"\"\"[a-zA-Z]\"\"\".r ^^{ new Character(_) }\n",
       "                                                             ^\n",
       "<console>:28: error: value ~ is not a member of String\n",
       "        \"(\" ~ expr ~ \")\"  ^^{ case _ ~ e ~ _ => e } |\n",
       "            ^\n",
       "<console>:36: error: not found: value parseAll\n",
       "        parseAll(phrase(expr), new PackratReader(new CharacterInputSequence(input))) match\n",
       "        ^\n",
       "<console>:38: error: not found: value Success\n",
       "            case Success(res, _) => res\n",
       "                 ^\n",
       "<console>:38: error: not found: value res\n",
       "            case Success(res, _) => res\n",
       "                                    ^\n",
       "<console>:39: error: not found: type NoSuccess\n",
       "            case f: NoSuccess => scala.sys.error(f.msg)\n",
       "                    ^\n",
       "StackTrace: "
      ]
     },
     "execution_count": 2,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "import scala.util.parsing.combinator._\n",
    "import scala.util.parsing.input.CharSequenceReader\n",
    "\n",
    "  object RatExprParser extends RegexParsers with PackratParsers\n",
    "  {\n",
    "      lazy val char: PackratParser[RatExpr] = \"\"\"[a-zA-Z]\"\"\".r ^^{ case x => new Character(x.apply(0)) }\n",
    "      // the expression between triple-quotes is a (textual) regular expression, converted to a parser (.r) thanks\n",
    "      // to a conversion provided by the trait RegexParsers\n",
    "      // the operator ^^ introduces a semantic action: a RegexParser returns a String, and we convert it to a RatExpr\n",
    "      // note that with our expression, the returned string has a single character, retrived with `apply(0)`\n",
    "\n",
    "      lazy val expr: PackratParser[RatExpr] =\n",
    "          // ~ is the concatenation operator\n",
    "          // the token returned by the \"+\" is discarded in the semantic action\n",
    "          // note that the trait Parsers (from which RegexParsers derives) provides a conversion to turn \"+\" into a Parser\n",
    "          expr ~ \"+\" ~ expr ^^{ case e1 ~ _ ~ e2 => new Union(e1, e2) } |\n",
    "          // | is the alternative operator (as in bison)\n",
    "          expr ~ \".\" ~ expr ^^{ case e1 ~ _ ~ e2 => new Concat(e1, e2) } |\n",
    "          expr ~ \"*\"        ^^{ case e ~ _ => new Star(e) } |\n",
    "          char              ^^{ case e => e } |\n",
    "          \"(\" ~ expr ~ \")\"  ^^{ case _ ~ e ~ _ => e }\n",
    "\n",
    "      // a helper function to parse a string\n",
    "      def apply(input: String): RatExpr =\n",
    "      {\n",
    "          parseAll(phrase(expr), new PackratReader(new CharSequenceReader(input))) match\n",
    "          {\n",
    "              case Success(res, _) => res\n",
    "              case f: NoSuccess => scala.sys.error(f.msg)\n",
    "          }\n",
    "      }\n",
    "  }\n",
    "\n",
    "val e: RatExpr = RatExprParser(\"(a.(a+b))*\")"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {
    "collapsed": true
   },
   "outputs": [],
   "source": []
  }
 ],
 "metadata": {
  "kernelspec": {
   "display_name": "Apache Toree - Scala",
   "language": "scala",
   "name": "apache_toree_scala"
  },
  "language_info": {
   "name": "scala",
   "version": "2.10.4"
  }
 },
 "nbformat": 4,
 "nbformat_minor": 2
}