Lecture 03 - Lexer.ipynb

{
 "cells": [
  {
   "cell_type": "markdown",
   "id": "a4a4b589",
   "metadata": {},
   "source": [
    "# Lexer"
   ]
  },
  {
   "cell_type": "markdown",
   "id": "2792ceb4",
   "metadata": {},
   "source": [
    "Today, we will learn all about the **lexing phase** of a compiler.\n",
    "\n",
    "For example,"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 1,
   "id": "13952da5",
   "metadata": {},
   "outputs": [
    {
     "data": {
      "text/plain": [
       "val source_code : string = \"x := (3 + 4) + 5\\nread y\\nx + y\"\n"
      ]
     },
     "execution_count": 1,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "let source_code : string =\n",
    "\"x := (3 + 4) + 5\n",
    "read y\n",
    "x + y\""
   ]
  },
  {
   "cell_type": "markdown",
   "id": "ccd7b9b2",
   "metadata": {},
   "source": [
    "is transformed in the list of tokens: \n",
    "\n",
    "```let phrasal_syntax : token list =\n",
    "[ID \"x\"; ASGN; LBRA; INT 3; PLUS; INT 4; RBRA; PLUS; INT 5; READ;\n",
    " ID \"y\"; ID \"x\"; PLUS; ID \"y\"]```"
   ]
  },
  {
   "cell_type": "markdown",
   "id": "ea01bf89",
   "metadata": {},
   "source": [
    "## Manual Lexers\n",
    "\n",
    "We start with expressions and their representation in abstract syntax: "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 2,
   "id": "869635ed",
   "metadata": {},
   "outputs": [
    {
     "data": {
      "text/plain": [
       "type op = Plus | Minus | Mult | Div\n"
      ]
     },
     "execution_count": 2,
     "metadata": {},
     "output_type": "execute_result"
    },
    {
     "data": {
      "text/plain": [
       "type exp = Id of string | Numb of int | Op of exp * op * exp\n"
      ]
     },
     "execution_count": 2,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "type op = Plus | Minus | Mult | Div\n",
    "type exp = Id of string | Numb of int | Op of exp * op * exp "
   ]
  },
  {
   "cell_type": "markdown",
   "id": "e960ebbc",
   "metadata": {},
   "source": [
    "We start off with a lexer for expressions without identifers or integers, the only constant is ``1`` - represented by the token ``ONE``. \n",
    "\n",
    "We represent tokens as an **algebraic datatype**.\n",
    "If you require a quick reminder you can find some good explanation here: https://cs3110.github.io/textbook/chapters/data/variants.html and here: https://cs3110.github.io/textbook/chapters/data/algebraic_data_types.html. "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 3,
   "id": "9a44498e",
   "metadata": {},
   "outputs": [
    {
     "data": {
      "text/plain": [
       "type token = ONE | PLUS | MINUS | STAR | SLASH | LBRA | RBRA | EOF\n"
      ]
     },
     "execution_count": 3,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    " type token = ONE\n",
    "           | PLUS  | MINUS | STAR | SLASH \n",
    "           | LBRA | RBRA \n",
    "           | EOF"
   ]
  },
  {
   "cell_type": "markdown",
   "id": "f2e8d8fb",
   "metadata": {},
   "source": [
    "Recall that we convert a String into a list of tokens.\n",
    "For this representation we want to look through all characters one-by-one.\n",
    "\n",
    "Below you see a function ``lex_step`` which takes a list of characters and yields the next token and the remaining list of characters. \n",
    "\n",
    "If the list of characters ``cs``... \n",
    "- is empty, we return the end-of-file symbol and the empty list. \n",
    "- is a white space character, we forget this character and go on with the remaining list of characters. \n",
    "- is '1', we return the token ``ONE`` and the remaining list of characters. \n",
    "- ... similarly for our other defined tokens. \n",
    "- If it is none of these tokens, we raise an exception."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 4,
   "id": "d4991bb6",
   "metadata": {},
   "outputs": [
    {
     "data": {
      "text/plain": [
       "exception LexError\n"
      ]
     },
     "execution_count": 4,
     "metadata": {},
     "output_type": "execute_result"
    },
    {
     "data": {
      "text/plain": [
       "val lex_step : char list -> token * char list = <fun>\n"
      ]
     },
     "execution_count": 4,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "exception LexError\n",
    "\n",
    "let rec lex_step (cs: char list) : token * char list = \n",
    "  match cs with \n",
    "  | [] -> (EOF, [])\n",
    "  | '\\t' :: cs | '\\n' :: cs | ' ' :: cs -> lex_step cs\n",
    "  | '1' :: cs -> (ONE, cs)\n",
    "  | '+' :: cs -> (PLUS, cs)\n",
    "  | '-' :: cs -> (MINUS, cs)\n",
    "  | '*' :: cs -> (STAR, cs) \n",
    "  | '/' :: cs -> (SLASH, cs)  \n",
    "  | '(' :: cs -> (LBRA, cs) \n",
    "  | ')' :: cs -> (RBRA, cs)\n",
    "  | c :: cs -> raise LexError"
   ]
  },
  {
   "cell_type": "markdown",
   "id": "f137b1f1",
   "metadata": {},
   "source": [
    "Internally strings are not lists of characaters. \n",
    "We hence have convert strings to a list of letters (``explode``) and convert a list of letters to a string (``implode``). \n",
    "Don't worry about how they are defined!"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 5,
   "id": "834409b7",
   "metadata": {},
   "outputs": [
    {
     "data": {
      "text/plain": [
       "val implode : char list -> string = <fun>\n"
      ]
     },
     "execution_count": 5,
     "metadata": {},
     "output_type": "execute_result"
    },
    {
     "data": {
      "text/plain": [
       "val explode : string -> char list = <fun>\n"
      ]
     },
     "execution_count": 5,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "let implode chars = \n",
    "  let buf = Buffer.create 16 in\n",
    "  List.iter (Buffer.add_char buf) chars;\n",
    "  Buffer.contents buf\n",
    "\n",
    "let explode s =\n",
    "  let rec exp i l =\n",
    "    if i < 0 then l else exp (i - 1) (s.[i] :: l) in\n",
    "  exp (String.length s - 1) []  "
   ]
  },
  {
   "cell_type": "markdown",
   "id": "40d89c7e",
   "metadata": {},
   "source": [
    "We can then test our above function ``lex_step``: "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 6,
   "id": "f030d5e9",
   "metadata": {},
   "outputs": [
    {
     "data": {
      "text/plain": [
       "- : token * char list = (ONE, [' '; ' '; '+'; ' '; '1'])\n"
      ]
     },
     "execution_count": 6,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "lex_step (explode \"1  + 1\")"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 7,
   "id": "2630fd25",
   "metadata": {},
   "outputs": [
    {
     "data": {
      "text/plain": [
       "- : token * char list = (LBRA, ['1'; ' '; ' '; '+'; ' '; '1'])\n"
      ]
     },
     "execution_count": 7,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "lex_step (explode \" (1  + 1\")"
   ]
  },
  {
   "cell_type": "markdown",
   "id": "90d02827",
   "metadata": {},
   "source": [
    "To define the full lexing phase we repeat reading the next token, until we get to the end of the file: "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 8,
   "id": "92b4421c",
   "metadata": {},
   "outputs": [
    {
     "data": {
      "text/plain": [
       "val lex : char list -> token list = <fun>\n"
      ]
     },
     "execution_count": 8,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "let rec lex cs = \n",
    "    match lex_step cs with \n",
    "    | (EOF, _) -> []\n",
    "    | (t, cs) -> t :: lex cs"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 9,
   "id": "6715b082",
   "metadata": {},
   "outputs": [
    {
     "data": {
      "text/plain": [
       "- : token list = [ONE; PLUS; ONE]\n"
      ]
     },
     "execution_count": 9,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "lex (explode \"1  + 1\")"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 10,
   "id": "bb864b47",
   "metadata": {},
   "outputs": [
    {
     "data": {
      "text/plain": [
       "- : token list = [LBRA; ONE; PLUS; ONE]\n"
      ]
     },
     "execution_count": 10,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "lex (explode \" (1  + 1\")"
   ]
  },
  {
   "cell_type": "markdown",
   "id": "4e51fbe8",
   "metadata": {},
   "source": [
    "## Optional: A Manual Lexer for Expressions"
   ]
  },
  {
   "cell_type": "markdown",
   "id": "48ed7459",
   "metadata": {},
   "source": [
    "(The following is optional and was not handled in the lecture.)\n",
    "\n",
    "Let's now go to full expressions and the following token type:"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 11,
   "id": "8752a547",
   "metadata": {},
   "outputs": [
    {
     "data": {
      "text/plain": [
       "type token =\n",
       "    ID of string\n",
       "  | INT of int\n",
       "  | PLUS\n",
       "  | MINUS\n",
       "  | STAR\n",
       "  | SLASH\n",
       "  | LBRA\n",
       "  | RBRA\n",
       "  | EOF\n"
      ]
     },
     "execution_count": 11,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "type token = ID of string | INT of int\n",
    "           | PLUS  | MINUS | STAR | SLASH \n",
    "           | LBRA | RBRA \n",
    "           | EOF"
   ]
  },
  {
   "cell_type": "markdown",
   "id": "3c7c958b",
   "metadata": {},
   "source": [
    "Implementing a lexer which recognizes identifers and integers requires us to implement the maximal munch rule into our lexer function. \n",
    "\n",
    "The following function ``grab`` continues reading an input, until the predicate ``f`` no longer holds:"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 12,
   "id": "8148b2dd",
   "metadata": {},
   "outputs": [
    {
     "data": {
      "text/plain": [
       "val grab : (char -> bool) -> char list -> char list * char list = <fun>\n"
      ]
     },
     "execution_count": 12,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "let rec grab (f : char -> bool) (xs : char list) : char list * char list  = match xs with \n",
    "| [] -> ([], [])\n",
    "| x :: xs' -> let (l1, l2) = grab f xs' in\n",
    "                if f x then (x :: l1, l2) else ([], xs)"
   ]
  },
  {
   "cell_type": "markdown",
   "id": "c65f37d2",
   "metadata": {},
   "source": [
    "We can moreover define functions which recognize whether a character is a digit or a character by a case distinction:"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 13,
   "id": "424c230d",
   "metadata": {},
   "outputs": [
    {
     "data": {
      "text/plain": [
       "val is_digit : char -> bool = <fun>\n"
      ]
     },
     "execution_count": 13,
     "metadata": {},
     "output_type": "execute_result"
    },
    {
     "data": {
      "text/plain": [
       "val is_char : char -> bool = <fun>\n"
      ]
     },
     "execution_count": 13,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "let is_digit digit =\n",
    "  match digit with\n",
    "    '0' .. '9' -> true\n",
    "  | _ -> false\n",
    "\n",
    "let is_char char = \n",
    "  match char with \n",
    "    'a' .. 'z' -> true \n",
    "  | 'A' .. 'Z' -> true\n",
    "  | _ -> false"
   ]
  },
  {
   "cell_type": "markdown",
   "id": "4cb8779f",
   "metadata": {},
   "source": [
    "This allows us to define functions which read an integer or an identifier:"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 14,
   "id": "0b2e4804",
   "metadata": {},
   "outputs": [
    {
     "data": {
      "text/plain": [
       "val lex_int : char list -> token * char list = <fun>\n"
      ]
     },
     "execution_count": 14,
     "metadata": {},
     "output_type": "execute_result"
    },
    {
     "data": {
      "text/plain": [
       "val lex_id : char list -> token * char list = <fun>\n"
      ]
     },
     "execution_count": 14,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "let lex_int s = let (l1, l2) = grab is_digit s in \n",
    "                (INT (int_of_string (implode l1)), l2)\n",
    "\n",
    "let lex_id s = let (l1, l2) = grab is_char s in \n",
    "                (ID (implode l1), l2)"
   ]
  },
  {
   "cell_type": "markdown",
   "id": "8a9a2ca0",
   "metadata": {},
   "source": [
    "... and hence also to define a lexer function as before:"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 15,
   "id": "cf2bc6a0",
   "metadata": {},
   "outputs": [
    {
     "data": {
      "text/plain": [
       "val lex_step : char list -> token * char list = <fun>\n"
      ]
     },
     "execution_count": 15,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "let rec lex_step s : token * char list = \n",
    "  match s with \n",
    "  | [] -> (EOF, [])\n",
    "  | '\\t' :: xs | '\\n' :: xs | ' ' :: xs -> lex_step xs\n",
    "  | '+' :: xs -> (PLUS, xs)\n",
    "  | '-' :: xs -> (MINUS, xs)\n",
    "  | '*' :: xs -> (STAR, xs) \n",
    "  | '/' :: xs -> (SLASH, xs)  \n",
    "  | '(' :: xs -> (LBRA, xs) \n",
    "  | ')' :: xs -> (RBRA, xs)\n",
    "  | c :: cs -> if is_char c \n",
    "                  then lex_id (c :: cs)\n",
    "                  else if is_digit c then lex_int (c :: cs)\n",
    "                  else raise LexError"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 16,
   "id": "de423e6f",
   "metadata": {},
   "outputs": [
    {
     "data": {
      "text/plain": [
       "val lex : char list -> token list = <fun>\n"
      ]
     },
     "execution_count": 16,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "let rec lex cs = \n",
    "    match lex_step cs with \n",
    "    | (EOF, _) -> []\n",
    "    | (t, cs) -> t :: lex cs"
   ]
  },
  {
   "cell_type": "markdown",
   "id": "0099a873",
   "metadata": {},
   "source": [
    "Let's try it out:"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 17,
   "id": "370d3934",
   "metadata": {},
   "outputs": [
    {
     "data": {
      "text/plain": [
       "- : token list = [INT 34; PLUS; ID \"abc\"]\n"
      ]
     },
     "execution_count": 17,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "lex (explode \"34 + abc\")"
   ]
  },
  {
   "cell_type": "markdown",
   "id": "ba6c4031",
   "metadata": {},
   "source": [
    "## Lexer Generator for Expressions"
   ]
  },
  {
   "cell_type": "markdown",
   "id": "69502e26",
   "metadata": {},
   "source": [
    "We show how to use the lexer generator in the Jupyter notebook.\n",
    "\n",
    "We will here use the ``ocamllex`` tool - this one is based on the ``lex`` tool. "
   ]
  },
  {
   "cell_type": "markdown",
   "id": "de7c1a37",
   "metadata": {},
   "source": [
    "We require certain functionality from Jupyter notebooks to later run ``ocamllex`` and compile files."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 18,
   "id": "fd976386",
   "metadata": {},
   "outputs": [
    {
     "name": "stderr",
     "output_type": "stream",
     "text": [
      "/home/opam/.opam/4.13/lib/base64: added to search path\n",
      "/home/opam/.opam/4.13/lib/base64/base64.cma: loaded\n",
      "/home/opam/.opam/4.13/lib/ocaml/compiler-libs: added to search path\n",
      "/home/opam/.opam/4.13/lib/ocaml/compiler-libs/ocamlcommon.cma: loaded\n",
      "/home/opam/.opam/4.13/lib/seq: added to search path\n",
      "/home/opam/.opam/4.13/lib/yojson: added to search path\n",
      "/home/opam/.opam/4.13/lib/yojson/yojson.cma: loaded\n",
      "/home/opam/.opam/4.13/lib/ppx_yojson_conv_lib: added to search path\n",
      "/home/opam/.opam/4.13/lib/ppx_yojson_conv_lib/ppx_yojson_conv_lib.cma: loaded\n",
      "/home/opam/.opam/4.13/lib/ocaml/unix.cma: loaded\n",
      "/home/opam/.opam/4.13/lib/bytes: added to search path\n",
      "/home/opam/.opam/4.13/lib/uuidm: added to search path\n",
      "/home/opam/.opam/4.13/lib/uuidm/uuidm.cma: loaded\n",
      "/home/opam/.opam/4.13/lib/jupyter: added to search path\n",
      "/home/opam/.opam/4.13/lib/jupyter/jupyter.cma: loaded\n",
      "/home/opam/.opam/4.13/lib/result: added to search path\n",
      "/home/opam/.opam/4.13/lib/result/result.cma: loaded\n",
      "/home/opam/.opam/4.13/lib/ppx_deriving/runtime: added to search path\n",
      "/home/opam/.opam/4.13/lib/ppx_deriving/runtime/ppx_deriving_runtime.cma: loaded\n",
      "/home/opam/.opam/4.13/lib/jupyter/notebook: added to search path\n",
      "/home/opam/.opam/4.13/lib/jupyter/notebook/jupyter_notebook.cma: loaded\n"
     ]
    }
   ],
   "source": [
    "#require \"jupyter.notebook\" ;;\n",
    "\n",
    "open Jupyter_notebook;;"
   ]
  },
  {
   "cell_type": "markdown",
   "id": "63b2432e",
   "metadata": {},
   "source": [
    "This is the content of the file ``exp.mll``, the input to the later lexer generator. \n",
    "See the slides for the explanation.\n",
    "\n",
    "```\n",
    "{ (* User definitions *) \n",
    "\n",
    "type token = ID of string | INT of int\n",
    "           | PLUS  | MINUS | STAR | SLASH \n",
    "           | LBRA | RBRA | EOF\n",
    "           \n",
    "exception LEX of string\n",
    "\n",
    "}\n",
    "\n",
    "(* LEX definitions - setting up regular expressions for int/white/id *) \n",
    "let int = '-'? ['0'-'9'] ['0'-'9']*\n",
    "let white = [' ' '\\t' '\\n']+\n",
    "let id = ['a'-'z' 'A'-'Z' '_'] ['a'-'z' 'A'-'Z' '0'-'9' '_']*\n",
    "\n",
    "(* Rules *) \n",
    "rule token = parse\n",
    "    | white          { token lexbuf }\n",
    "    | int            { INT (int_of_string (Lexing.lexeme lexbuf)) }\n",
    "    | id             { ID (Lexing.lexeme lexbuf) }\n",
    "    | '+'            { PLUS }\n",
    "    | '-'            { MINUS }\n",
    "    | '*'            { STAR }\n",
    "    | '/'            { SLASH }\n",
    "    | '('            { LBRA }\n",
    "    | ')'            { RBRA }\n",
    "    | eof            { EOF }\n",
    "    | _ { raise (LEX (\"Unexpected char: \" ^ Lexing.lexeme lexbuf)) } \n",
    "    \n",
    "    \n",
    "(* User functions *)   \n",
    "```"
   ]
  },
  {
   "cell_type": "markdown",
   "id": "1bcd3f00",
   "metadata": {},
   "source": [
    "The first command calls the lexer generator on the input file ``exp.mll`` and saves the output to ``exp.ml``.\n",
    "\n",
    "The second command compiles the output file into ``exp.cmi``, a compiled interface file which includes e.g. type information of functions or variables and ``exp.cmo``, a bytecode object file (think of .class files in Java).\n",
    "\n",
    "(You don't need to know about these processes, we will always give you the corresponding code.)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 19,
   "id": "25637252",
   "metadata": {
    "scrolled": true
   },
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "12 states, 417 transitions, table size 1740 bytes\n"
     ]
    },
    {
     "data": {
      "text/plain": [
       "- : Jupyter_notebook.Process.t =\n",
       "{Jupyter_notebook.Process.exit_status = Unix.WEXITED 0; stdout = None;\n",
       " stderr = None}\n"
      ]
     },
     "execution_count": 19,
     "metadata": {},
     "output_type": "execute_result"
    },
    {
     "data": {
      "text/plain": [
       "- : Jupyter_notebook.Process.t =\n",
       "{Jupyter_notebook.Process.exit_status = Unix.WEXITED 0; stdout = None;\n",
       " stderr = None}\n"
      ]
     },
     "execution_count": 19,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "Process.sh \"ocamllex exp.mll\";;\n",
    "Process.sh \"ocamlc -c exp.ml\";;"
   ]
  },
  {
   "cell_type": "markdown",
   "id": "14504174",
   "metadata": {},
   "source": [
    "You can see the result in the file ``exp.ml``.\n",
    "(It is strongly recommend to look yourself!)"
   ]
  },
  {
   "cell_type": "markdown",
   "id": "a69c5827",
   "metadata": {},
   "source": [
    "The ``#load`` command allows to include the functions in the compiled file."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 20,
   "id": "7ca0f9a2",
   "metadata": {},
   "outputs": [],
   "source": [
    "#load \"exp.cmo\""
   ]
  },
  {
   "cell_type": "markdown",
   "id": "c3773e71",
   "metadata": {},
   "source": [
    "All functions we use from this file will have to be prefixed by ``Exp.`` (the name of the file capitalized). \n",
    "\n",
    "E.g., we can check the type of the function ``token``: "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 21,
   "id": "f79137ca",
   "metadata": {},
   "outputs": [
    {
     "data": {
      "text/plain": [
       "- : Lexing.lexbuf -> Exp.token = <fun>\n"
      ]
     },
     "execution_count": 21,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "Exp.token"
   ]
  },
  {
   "cell_type": "markdown",
   "id": "5bca7434",
   "metadata": {},
   "source": [
    "So the function ``Exp.token`` expects a buffer (something of type ``Lexing.lexbuf``) and then returns the next token. \n",
    "\n",
    "The library contains a function ``Lexing.from_string`` which converts a string into a buffer. \n",
    "\n",
    "In principle, we can now use the function ``Exp.token`` to get the next element of the buffer:"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 22,
   "id": "24c332f8",
   "metadata": {},
   "outputs": [
    {
     "data": {
      "text/plain": [
       "val buf : Lexing.lexbuf =\n",
       "  {Lexing.refill_buff = <fun>; lex_buffer = Bytes.of_string \"3 + 5\";\n",
       "   lex_buffer_len = 5; lex_abs_pos = 0; lex_start_pos = 0; lex_curr_pos = 0;\n",
       "   lex_last_pos = 0; lex_last_action = 0; lex_eof_reached = true;\n",
       "   lex_mem = [||];\n",
       "   lex_start_p =\n",
       "    {Lexing.pos_fname = \"\"; pos_lnum = 1; pos_bol = 0; pos_cnum = 0};\n",
       "   lex_curr_p =\n",
       "    {Lexing.pos_fname = \"\"; pos_lnum = 1; pos_bol = 0; pos_cnum = 0}}\n"
      ]
     },
     "execution_count": 22,
     "metadata": {},
     "output_type": "execute_result"
    },
    {
     "data": {
      "text/plain": [
       "- : Exp.token = Exp.INT 3\n"
      ]
     },
     "execution_count": 22,
     "metadata": {},
     "output_type": "execute_result"
    },
    {
     "data": {
      "text/plain": [
       "- : Exp.token = Exp.PLUS\n"
      ]
     },
     "execution_count": 22,
     "metadata": {},
     "output_type": "execute_result"
    },
    {
     "data": {
      "text/plain": [
       "- : Exp.token = Exp.INT 5\n"
      ]
     },
     "execution_count": 22,
     "metadata": {},
     "output_type": "execute_result"
    },
    {
     "data": {
      "text/plain": [
       "- : Exp.token = Exp.EOF\n"
      ]
     },
     "execution_count": 22,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "let buf = Lexing.from_string \"3 + 5\";; \n",
    "\n",
    "Exp.token buf;;\n",
    "\n",
    "Exp.token buf;;\n",
    "\n",
    "Exp.token buf;;\n",
    "\n",
    "Exp.token buf"
   ]
  },
  {
   "cell_type": "markdown",
   "id": "47b1a7c0",
   "metadata": {},
   "source": [
    "We could use the definition of a buffer but to make things clearer, we will work with lists. \n",
    "\n",
    "We can convert the stream of tokens into lists by the following function ``stream_to_list``, which takes one-by-one the next element of the buffer (``Exp.token buffer``) and makes a case analysis whether \n",
    "- this element is the end-of-file symbol ``EOF`` - we can return the empty list. \n",
    "- this element is another token - then remember this token t, and put it to the beginning of the list and run the function recursively on the remaining buffer."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 23,
   "id": "c63e51a1",
   "metadata": {},
   "outputs": [
    {
     "data": {
      "text/plain": [
       "val stream_to_list : Lexing.lexbuf -> Exp.token list = <fun>\n"
      ]
     },
     "execution_count": 23,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "let rec stream_to_list buffer = \n",
    "    match Exp.token buffer with \n",
    "    | EOF -> []\n",
    "    | t -> t :: stream_to_list buffer"
   ]
  },
  {
   "cell_type": "markdown",
   "id": "37c79e71",
   "metadata": {},
   "source": [
    "See below for an example of getting the corresponding list:"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 24,
   "id": "1350bc4a",
   "metadata": {},
   "outputs": [
    {
     "data": {
      "text/plain": [
       "val res : Exp.token list = [Exp.INT 3; Exp.PLUS; Exp.INT 5]\n"
      ]
     },
     "execution_count": 24,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "let res = stream_to_list (Lexing.from_string \"3 + 5\")"
   ]
  },
  {
   "cell_type": "markdown",
   "id": "4a776bfc",
   "metadata": {},
   "source": [
    "Try it out with your own example: "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 25,
   "id": "15707490",
   "metadata": {},
   "outputs": [],
   "source": [
    "(* TODO *)"
   ]
  }
 ],
 "metadata": {
  "kernelspec": {
   "display_name": "OCaml 4.13",
   "language": "OCaml",
   "name": "ocaml-jupyter-4.13"
  },
  "language_info": {
   "codemirror_mode": "text/x-ocaml",
   "file_extension": ".ml",
   "mimetype": "text/x-ocaml",
   "name": "OCaml",
   "nbconverter_exporter": null,
   "pygments_lexer": "OCaml",
   "version": "4.13.1"
  }
 },
 "nbformat": 4,
 "nbformat_minor": 5
}