Lab 3 - Parsers (Solutions).ipynb

{
 "cells": [
  {
   "cell_type": "markdown",
   "id": "34c355d7",
   "metadata": {
    "kernel": "SoS"
   },
   "source": [
    "# Lab 3\n",
    "\n",
    "- It is recommended to **go through this file with a partner**. \n",
    "- Ensure to **ask** if anything is not clear - first your partner, then a lab helper.\n",
    "- You want to first go through the accompanying code of the lectures."
   ]
  },
  {
   "cell_type": "markdown",
   "id": "2da844ce",
   "metadata": {
    "kernel": "SoS"
   },
   "source": [
    "In this lab, you will write a full parser for ``SIMP``. \n",
    "\n",
    "**HINT:** As it's easy to get stuck here, the solutions are already available in the repository."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 2,
   "id": "517392be",
   "metadata": {
    "kernel": "Python 3 (ipykernel)",
    "vscode": {
     "languageId": "ocaml"
    }
   },
   "outputs": [],
   "source": [
    "from jupyterquiz import display_quiz\n",
    "\n",
    "question_path=\"./\""
   ]
  },
  {
   "cell_type": "markdown",
   "id": "522be80e",
   "metadata": {
    "kernel": "SoS"
   },
   "source": [
    "Here is a grammar for``SIMP``. \n",
    "(This one has a slightly different definition for declarations compared to the grammar you saw in the lecture.)\n",
    "\n",
    "```\n",
    "program ::=  [declarations] commands \n",
    "declarations ::= declaration; | declaration; declarations \n",
    "declaration ::= VAR identifier\n",
    "\n",
    "commands ::= command | command; commands\n",
    "command ::= identifier := exp | IF condexp THEN command | IF condexp THEN command ELSE command | WHILE condexp DO command | BEGIN program END | INPUT identifier | PRINT exp \n",
    "\n",
    "comp := = | != | <= | < | >= | >\n",
    "condexp := exp comp exp \n",
    "exp  ::= identifier | number | exp + exp | exp – exp | exp * exp | exp / exp | - exp \n",
    "```"
   ]
  },
  {
   "cell_type": "markdown",
   "id": "5442293e",
   "metadata": {
    "kernel": "Python 3 (ipykernel)"
   },
   "source": [
    "Recall abstract syntax and tokens for ``SIMP``:"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 3,
   "id": "3505bb74",
   "metadata": {
    "kernel": "OCaml 4.13",
    "vscode": {
     "languageId": "ocaml"
    }
   },
   "outputs": [
    {
     "data": {
      "text/plain": [
       "exception SyntaxError of string\n"
      ]
     },
     "execution_count": 3,
     "metadata": {},
     "output_type": "execute_result"
    },
    {
     "data": {
      "text/plain": [
       "type op = Plus | Minus | Mult | Div\n"
      ]
     },
     "execution_count": 3,
     "metadata": {},
     "output_type": "execute_result"
    },
    {
     "data": {
      "text/plain": [
       "type exp = Id of string | Numb of int | Op of exp * op * exp | Neg of exp\n"
      ]
     },
     "execution_count": 3,
     "metadata": {},
     "output_type": "execute_result"
    },
    {
     "data": {
      "text/plain": [
       "type cond = Eq | Neq | Lte | Lt | Gte | Gt\n"
      ]
     },
     "execution_count": 3,
     "metadata": {},
     "output_type": "execute_result"
    },
    {
     "data": {
      "text/plain": [
       "type condexp = Cop of exp * cond * exp\n"
      ]
     },
     "execution_count": 3,
     "metadata": {},
     "output_type": "execute_result"
    },
    {
     "data": {
      "text/plain": [
       "type cmd =\n",
       "    Asgn of string * exp\n",
       "  | Ite of condexp * cmd * cmd\n",
       "  | If of condexp * cmd\n",
       "  | While of condexp * cmd\n",
       "  | Begin of program\n",
       "  | Input of string\n",
       "  | Print of exp\n",
       "and program = Program of string list * cmd list\n"
      ]
     },
     "execution_count": 3,
     "metadata": {},
     "output_type": "execute_result"
    },
    {
     "data": {
      "text/plain": [
       "type token =\n",
       "    SEMI\n",
       "  | VAR\n",
       "  | ASGN\n",
       "  | IF\n",
       "  | THEN\n",
       "  | ELSE\n",
       "  | WHILE\n",
       "  | DO\n",
       "  | BEGIN\n",
       "  | END\n",
       "  | INPUT\n",
       "  | PRINT\n",
       "  | EQ\n",
       "  | NEQ\n",
       "  | LTE\n",
       "  | LT\n",
       "  | GTE\n",
       "  | GT\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": 3,
     "metadata": {},
     "output_type": "execute_result"
    },
    {
     "data": {
      "text/plain": [
       "val parse_token : token -> token list -> token list = <fun>\n"
      ]
     },
     "execution_count": 3,
     "metadata": {},
     "output_type": "execute_result"
    },
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "2023-03-13T21:39:36  STDOUT>> Findlib has been successfully loaded. Additional directives:\n",
      "2023-03-13T21:39:36  STDOUT>>   #require \"package\";;      to load a package\n",
      "2023-03-13T21:39:36  STDOUT>>   #list;;                   to list the available packages\n",
      "2023-03-13T21:39:36  STDOUT>>   #camlp4o;;                to load camlp4 (standard syntax)\n",
      "2023-03-13T21:39:36  STDOUT>>   #camlp4r;;                to load camlp4 (revised syntax)\n",
      "2023-03-13T21:39:36  STDOUT>>   #predicates \"p,q,...\";;   to set these predicates\n",
      "2023-03-13T21:39:36  STDOUT>>   Topfind.reset();;         to force that packages will be reloaded\n",
      "2023-03-13T21:39:36  STDOUT>>   #thread;;                 to enable threads\n",
      "2023-03-13T21:39:36  STDOUT>> \n"
     ]
    }
   ],
   "source": [
    "(* Abstract syntax, tokens and helper functions *)\n",
    "\n",
    "exception SyntaxError of string\n",
    "\n",
    "type op = Plus | Minus | Mult | Div \n",
    "\n",
    "type exp = Id of string | Numb of int | Op of exp * op * exp | Neg of exp\n",
    "\n",
    "type cond = Eq | Neq | Lte | Lt | Gte | Gt \n",
    "type condexp = Cop of exp * cond * exp\n",
    "                                          \n",
    "type cmd = Asgn of string * exp \n",
    "         | Ite of condexp * cmd * cmd | If of condexp * cmd \n",
    "         | While of condexp * cmd\n",
    "         | Begin of program \n",
    "         | Input of string\n",
    "         | Print of exp \n",
    "         \n",
    "and program = Program of string list * cmd list\n",
    "\n",
    "type token = SEMI | VAR | ASGN | IF | THEN | ELSE\n",
    "            | WHILE | DO | BEGIN | END | INPUT | PRINT\n",
    "            | EQ | NEQ | LTE | LT | GTE | GT \n",
    "            | ID of string | INT of int\n",
    "            | PLUS  | MINUS | STAR | SLASH \n",
    "            | LBRA | RBRA \n",
    "            | EOF\n",
    "\n",
    "let parse_token (x : token) (xs : token list) = match xs with \n",
    "| y :: ys -> if (x == y) then ys else raise (SyntaxError \"Token expected.\")\n",
    "| _ -> raise (SyntaxError \"Token expected.\") "
   ]
  },
  {
   "cell_type": "markdown",
   "id": "69ded459",
   "metadata": {
    "kernel": "Python 3 (ipykernel)"
   },
   "source": [
    "## 1. LL(1) "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 4,
   "id": "871ee8af",
   "metadata": {
    "kernel": "Python 3 (ipykernel)",
    "vscode": {
     "languageId": "ocaml"
    }
   },
   "outputs": [
    {
     "data": {
      "text/html": [
       "<div id=\"rGiYjbhXRAOm\" data-shufflequestions=\"False\"\n",
       "               data-shuffleanswers=\"True\"\n",
       "               data-preserveresponses=\"false\"\n",
       "               data-numquestions=\"1000000\"> <style>:root {\n",
       "    --medium-slate-blue: #6f78ffff;\n",
       "    --orange-pantone: #f75c03ff;\n",
       "    --russian-violet: #392061ff;\n",
       "    --maximum-yellow-red: #ffc857ff;\n",
       "    --viridian-green: #119da4ff;\n",
       "    --incorrect-red: #c80202;\n",
       "    --correct-green: #009113;\n",
       "}\n",
       "\n",
       ".Quiz {\n",
       "    max-width: 600px;\n",
       "    margin-top: 15px;\n",
       "    margin-left: auto;\n",
       "    margin-right: auto;\n",
       "    margin-bottom: 15px;\n",
       "    padding-bottom: 4px;\n",
       "    padding-top: 4px;\n",
       "    line-height: 1.1;\n",
       "    font-size: 16pt;\n",
       "}\n",
       "\n",
       ".QuizCode {\n",
       "    font-size: 14pt;\n",
       "    margin-top: 10px;\n",
       "    margin-left: 20px;\n",
       "    margin-right: 20px;\n",
       "}\n",
       "\n",
       ".QuizCode>pre {\n",
       "    padding: 4px;\n",
       "}\n",
       "\n",
       ".Answer {\n",
       "    margin: 10px 0;\n",
       "    display: grid;\n",
       "    grid-template-columns: auto auto;\n",
       "    grid-gap: 10px;\n",
       "}\n",
       "\n",
       ".Feedback {\n",
       "    font-size: 16pt;\n",
       "    text-align: center;\n",
       "    min-height: 2em;\n",
       "}\n",
       "\n",
       ".Input {\n",
       "    align: left;\n",
       "    font-size: 20pt;\n",
       "}\n",
       "\n",
       ".Input-text {\n",
       "    display: block;\n",
       "    margin: 10px;\n",
       "    color: inherit;\n",
       "    width: 140px;\n",
       "    background-color: #c0c0c0;\n",
       "    color: #fff;\n",
       "    padding: 5px;\n",
       "    padding-left: 10px;\n",
       "    font-family: inherit;\n",
       "    font-size: 20px;\n",
       "    font-weight: inherit;\n",
       "    line-height: 20pt;\n",
       "    border: none;\n",
       "    border-radius: 0.2rem;\n",
       "    transition: box-shadow 0.1s);\n",
       "}\n",
       "\n",
       ".Input-text:focus {\n",
       "    outline: none;\n",
       "    background-color: #c0c0c0;\n",
       "    box-shadow: 0.6rem 0.8rem 1.4rem -0.5rem #999999;\n",
       "}\n",
       "\n",
       ".MCButton {\n",
       "    background: #fafafa;\n",
       "    border: 1px solid #eee;\n",
       "    border-radius: 10px;\n",
       "    padding: 10px;\n",
       "    font-size: 16px;\n",
       "    cursor: pointer;\n",
       "    text-align: center;\n",
       "}\n",
       "\n",
       ".MCButton p {\n",
       "    color: inherit;\n",
       "}\n",
       "\n",
       ".MultipleChoiceQn {\n",
       "    padding: 10px;\n",
       "    background: var(--medium-slate-blue);\n",
       "    color: #fafafa;\n",
       "    border-radius: 10px;\n",
       "}\n",
       "\n",
       ".ManyChoiceQn {\n",
       "    padding: 10px;\n",
       "    background: var(--orange-pantone);\n",
       "    color: #fafafa;\n",
       "    border-radius: 10px;\n",
       "}\n",
       "\n",
       ".NumericQn {\n",
       "    padding: 10px;\n",
       "    background: var(--russian-violet);\n",
       "    color: #fafafa;\n",
       "    border-radius: 10px;\n",
       "}\n",
       "\n",
       ".NumericQn p {\n",
       "    color: inherit;\n",
       "}\n",
       "\n",
       ".InpLabel {\n",
       "    line-height: 34px;\n",
       "    float: left;\n",
       "    margin-right: 10px;\n",
       "    color: #101010;\n",
       "    font-size: 15pt;\n",
       "}\n",
       "\n",
       ".incorrect {\n",
       "    color: var(--incorrect-red);\n",
       "}\n",
       "\n",
       ".correct {\n",
       "    color: var(--correct-green);\n",
       "}\n",
       "\n",
       ".correctButton {\n",
       "    /*\n",
       "    background: var(--correct-green);\n",
       "   */\n",
       "    animation: correct-anim 0.6s ease;\n",
       "    animation-fill-mode: forwards;\n",
       "    color: #fafafa;\n",
       "    box-shadow: inset 0px 0px 5px #555555;\n",
       "    outline: none;\n",
       "}\n",
       "\n",
       ".incorrectButton {\n",
       "    animation: incorrect-anim 0.8s ease;\n",
       "    animation-fill-mode: forwards;\n",
       "    color: #fafafa;\n",
       "    box-shadow: inset 0px 0px 5px #555555;\n",
       "    outline: none;\n",
       "}\n",
       "\n",
       "@keyframes incorrect-anim {\n",
       "    100% {\n",
       "        background-color: var(--incorrect-red);\n",
       "    }\n",
       "}\n",
       "\n",
       "@keyframes correct-anim {\n",
       "    100% {\n",
       "        background-color: var(--correct-green);\n",
       "    }\n",
       "}</style>"
      ],
      "text/plain": [
       "<IPython.core.display.HTML object>"
      ]
     },
     "metadata": {},
     "output_type": "display_data"
    },
    {
     "data": {
      "application/javascript": "var questionsrGiYjbhXRAOm=[\n    {\n        \"question\": \"Which of the following syntactic categories are LL(1)?\",\n        \"type\": \"many_choice\",\n        \"answers\": [\n            {\n                \"answer\": \"program\",\n                \"correct\": true,\n                \"feedback\": \"Correct.\"\n            },\n                        {\n                \"answer\": \"declarations\",\n                \"correct\": false,\n                \"feedback\": \"No - compute the FIRST sets!\"\n            },\n                {\n                \"answer\": \"declaration\",\n                \"correct\": true,\n                \"feedback\": \"Correct.\"\n            },\n                                    {\n                \"answer\": \"commands\",\n                \"correct\": false,\n                \"feedback\": \"No - compute the FIRST sets!\"\n            },\n                                                {\n                \"answer\": \"command\",\n                \"correct\": false,\n                \"feedback\": \"No - compute the FIRST sets!\"\n            },\n                            {\n                \"answer\": \"comp\",\n                \"correct\": true,\n                \"feedback\": \"Correct.\"\n            },\n                            {\n                \"answer\": \"condexp\",\n                \"correct\": true,\n                \"feedback\": \"Correct.\"\n            }\n            \n        ]\n    }\n];\n    // Make a random ID\nfunction makeid(length) {\n    var result = [];\n    var characters = 'ABCDEFGHIJKLMNOPQRSTUVWXYZabcdefghijklmnopqrstuvwxyz';\n    var charactersLength = characters.length;\n    for (var i = 0; i < length; i++) {\n        result.push(characters.charAt(Math.floor(Math.random() * charactersLength)));\n    }\n    return result.join('');\n}\n\n// Choose a random subset of an array. Can also be used to shuffle the array\nfunction getRandomSubarray(arr, size) {\n    var shuffled = arr.slice(0), i = arr.length, temp, index;\n    while (i--) {\n        index = Math.floor((i + 1) * Math.random());\n        temp = shuffled[index];\n        shuffled[index] = shuffled[i];\n        shuffled[i] = temp;\n    }\n    return shuffled.slice(0, size);\n}\n\nfunction printResponses(responsesContainer) {\n    var responses=JSON.parse(responsesContainer.dataset.responses);\n    var stringResponses='<B>IMPORTANT!</B>To preserve this answer sequence for submission, when you have finalized your answers: <ol> <li> Copy the text in this cell below \"Answer String\"</li> <li> Double click on the cell directly below the Answer String, labeled \"Replace Me\"</li> <li> Select the whole \"Replace Me\" text</li> <li> Paste in your answer string and press shift-Enter.</li><li>Save the notebook using the save icon or File->Save Notebook menu item</li></ul><br><br><br><b>Answer String:</b><br> ';\n    console.log(responses);\n    responses.forEach((response, index) => {\n        if (response) {\n            console.log(index + ': ' + response);\n            stringResponses+= index + ': ' + response +\"<BR>\";\n        }\n    });\n    responsesContainer.innerHTML=stringResponses;\n}\nfunction check_mc() {\n    var id = this.id.split('-')[0];\n    //var response = this.id.split('-')[1];\n    //console.log(response);\n    //console.log(\"In check_mc(), id=\"+id);\n    //console.log(event.srcElement.id)           \n    //console.log(event.srcElement.dataset.correct)   \n    //console.log(event.srcElement.dataset.feedback)\n\n    var label = event.srcElement;\n    //console.log(label, label.nodeName);\n    var depth = 0;\n    while ((label.nodeName != \"LABEL\") && (depth < 20)) {\n        label = label.parentElement;\n        console.log(depth, label);\n        depth++;\n    }\n\n\n\n    var answers = label.parentElement.children;\n\n    //console.log(answers);\n\n\n    // Split behavior based on multiple choice vs many choice:\n    var fb = document.getElementById(\"fb\" + id);\n\n\n\n\n    if (fb.dataset.numcorrect == 1) {\n        // What follows is for the saved responses stuff\n        var outerContainer = fb.parentElement.parentElement;\n        var responsesContainer = document.getElementById(\"responses\" + outerContainer.id);\n        if (responsesContainer) {\n            //console.log(responsesContainer);\n            var response = label.firstChild.innerText;\n            if (label.querySelector(\".QuizCode\")){\n                response+= label.querySelector(\".QuizCode\").firstChild.innerText;\n            }\n            console.log(response);\n            //console.log(document.getElementById(\"quizWrap\"+id));\n            var qnum = document.getElementById(\"quizWrap\"+id).dataset.qnum;\n            console.log(\"Question \" + qnum);\n            //console.log(id, \", got numcorrect=\",fb.dataset.numcorrect);\n            var responses=JSON.parse(responsesContainer.dataset.responses);\n            console.log(responses);\n            responses[qnum]= response;\n            responsesContainer.setAttribute('data-responses', JSON.stringify(responses));\n            printResponses(responsesContainer);\n        }\n        // End code to preserve responses\n        \n        for (var i = 0; i < answers.length; i++) {\n            var child = answers[i];\n            //console.log(child);\n            child.className = \"MCButton\";\n        }\n\n\n\n        if (label.dataset.correct == \"true\") {\n            // console.log(\"Correct action\");\n            if (\"feedback\" in label.dataset) {\n                fb.textContent = jaxify(label.dataset.feedback);\n            } else {\n                fb.textContent = \"Correct!\";\n            }\n            label.classList.add(\"correctButton\");\n\n            fb.className = \"Feedback\";\n            fb.classList.add(\"correct\");\n\n        } else {\n            if (\"feedback\" in label.dataset) {\n                fb.textContent = jaxify(label.dataset.feedback);\n            } else {\n                fb.textContent = \"Incorrect -- try again.\";\n            }\n            //console.log(\"Error action\");\n            label.classList.add(\"incorrectButton\");\n            fb.className = \"Feedback\";\n            fb.classList.add(\"incorrect\");\n        }\n    }\n    else {\n        var reset = false;\n        var feedback;\n         if (label.dataset.correct == \"true\") {\n            if (\"feedback\" in label.dataset) {\n                feedback = jaxify(label.dataset.feedback);\n            } else {\n                feedback = \"Correct!\";\n            }\n            if (label.dataset.answered <= 0) {\n                if (fb.dataset.answeredcorrect < 0) {\n                    fb.dataset.answeredcorrect = 1;\n                    reset = true;\n                } else {\n                    fb.dataset.answeredcorrect++;\n                }\n                if (reset) {\n                    for (var i = 0; i < answers.length; i++) {\n                        var child = answers[i];\n                        child.className = \"MCButton\";\n                        child.dataset.answered = 0;\n                    }\n                }\n                label.classList.add(\"correctButton\");\n                label.dataset.answered = 1;\n                fb.className = \"Feedback\";\n                fb.classList.add(\"correct\");\n\n            }\n        } else {\n            if (\"feedback\" in label.dataset) {\n                feedback = jaxify(label.dataset.feedback);\n            } else {\n                feedback = \"Incorrect -- try again.\";\n            }\n            if (fb.dataset.answeredcorrect > 0) {\n                fb.dataset.answeredcorrect = -1;\n                reset = true;\n            } else {\n                fb.dataset.answeredcorrect--;\n            }\n\n            if (reset) {\n                for (var i = 0; i < answers.length; i++) {\n                    var child = answers[i];\n                    child.className = \"MCButton\";\n                    child.dataset.answered = 0;\n                }\n            }\n            label.classList.add(\"incorrectButton\");\n            fb.className = \"Feedback\";\n            fb.classList.add(\"incorrect\");\n        }\n        // What follows is for the saved responses stuff\n        var outerContainer = fb.parentElement.parentElement;\n        var responsesContainer = document.getElementById(\"responses\" + outerContainer.id);\n        if (responsesContainer) {\n            //console.log(responsesContainer);\n            var response = label.firstChild.innerText;\n            if (label.querySelector(\".QuizCode\")){\n                response+= label.querySelector(\".QuizCode\").firstChild.innerText;\n            }\n            console.log(response);\n            //console.log(document.getElementById(\"quizWrap\"+id));\n            var qnum = document.getElementById(\"quizWrap\"+id).dataset.qnum;\n            console.log(\"Question \" + qnum);\n            //console.log(id, \", got numcorrect=\",fb.dataset.numcorrect);\n            var responses=JSON.parse(responsesContainer.dataset.responses);\n            if (label.dataset.correct == \"true\") {\n                if (typeof(responses[qnum]) == \"object\"){\n                    if (!responses[qnum].includes(response))\n                        responses[qnum].push(response);\n                } else{\n                    responses[qnum]= [ response ];\n                }\n            } else {\n                responses[qnum]= response;\n            }\n            console.log(responses);\n            responsesContainer.setAttribute('data-responses', JSON.stringify(responses));\n            printResponses(responsesContainer);\n        }\n        // End save responses stuff\n\n\n\n        var numcorrect = fb.dataset.numcorrect;\n        var answeredcorrect = fb.dataset.answeredcorrect;\n        if (answeredcorrect >= 0) {\n            fb.textContent = feedback + \" [\" + answeredcorrect + \"/\" + numcorrect + \"]\";\n        } else {\n            fb.textContent = feedback + \" [\" + 0 + \"/\" + numcorrect + \"]\";\n        }\n\n\n    }\n\n    if (typeof MathJax != 'undefined') {\n        var version = MathJax.version;\n        console.log('MathJax version', version);\n        if (version[0] == \"2\") {\n            MathJax.Hub.Queue([\"Typeset\", MathJax.Hub]);\n        } else if (version[0] == \"3\") {\n            MathJax.typeset([fb]);\n        }\n    } else {\n        console.log('MathJax not detected');\n    }\n\n}\n\nfunction make_mc(qa, shuffle_answers, outerqDiv, qDiv, aDiv, id) {\n    var shuffled;\n    if (shuffle_answers == \"True\") {\n        //console.log(shuffle_answers+\" read as true\");\n        shuffled = getRandomSubarray(qa.answers, qa.answers.length);\n    } else {\n        //console.log(shuffle_answers+\" read as false\");\n        shuffled = qa.answers;\n    }\n\n\n    var num_correct = 0;\n\n\n\n    shuffled.forEach((item, index, ans_array) => {\n        //console.log(answer);\n\n        // Make input element\n        var inp = document.createElement(\"input\");\n        inp.type = \"radio\";\n        inp.id = \"quizo\" + id + index;\n        inp.style = \"display:none;\";\n        aDiv.append(inp);\n\n        //Make label for input element\n        var lab = document.createElement(\"label\");\n        lab.className = \"MCButton\";\n        lab.id = id + '-' + index;\n        lab.onclick = check_mc;\n        var aSpan = document.createElement('span');\n        aSpan.classsName = \"\";\n        //qDiv.id=\"quizQn\"+id+index;\n        if (\"answer\" in item) {\n            aSpan.innerHTML = jaxify(item.answer);\n            //aSpan.innerHTML=item.answer;\n        }\n        lab.append(aSpan);\n\n        // Create div for code inside question\n        var codeSpan;\n        if (\"code\" in item) {\n            codeSpan = document.createElement('span');\n            codeSpan.id = \"code\" + id + index;\n            codeSpan.className = \"QuizCode\";\n            var codePre = document.createElement('pre');\n            codeSpan.append(codePre);\n            var codeCode = document.createElement('code');\n            codePre.append(codeCode);\n            codeCode.innerHTML = item.code;\n            lab.append(codeSpan);\n            //console.log(codeSpan);\n        }\n\n        //lab.textContent=item.answer;\n\n        // Set the data attributes for the answer\n        lab.setAttribute('data-correct', item.correct);\n        if (item.correct) {\n            num_correct++;\n        }\n        if (\"feedback\" in item) {\n            lab.setAttribute('data-feedback', item.feedback);\n        }\n        lab.setAttribute('data-answered', 0);\n\n        aDiv.append(lab);\n\n    });\n\n    if (num_correct > 1) {\n        outerqDiv.className = \"ManyChoiceQn\";\n    } else {\n        outerqDiv.className = \"MultipleChoiceQn\";\n    }\n\n    return num_correct;\n\n}\nfunction check_numeric(ths, event) {\n\n    if (event.keyCode === 13) {\n        ths.blur();\n\n        var id = ths.id.split('-')[0];\n\n        var submission = ths.value;\n        if (submission.indexOf('/') != -1) {\n            var sub_parts = submission.split('/');\n            //console.log(sub_parts);\n            submission = sub_parts[0] / sub_parts[1];\n        }\n        //console.log(\"Reader entered\", submission);\n\n        if (\"precision\" in ths.dataset) {\n            var precision = ths.dataset.precision;\n            // console.log(\"1:\", submission)\n            submission = Math.round((1 * submission + Number.EPSILON) * 10 ** precision) / 10 ** precision;\n            // console.log(\"Rounded to \", submission, \" precision=\", precision  );\n        }\n\n\n        //console.log(\"In check_numeric(), id=\"+id);\n        //console.log(event.srcElement.id)           \n        //console.log(event.srcElement.dataset.feedback)\n\n        var fb = document.getElementById(\"fb\" + id);\n        fb.style.display = \"none\";\n        fb.textContent = \"Incorrect -- try again.\";\n\n        var answers = JSON.parse(ths.dataset.answers);\n        //console.log(answers);\n\n        var defaultFB = \"\";\n        var correct;\n        var done = false;\n        answers.every(answer => {\n            //console.log(answer.type);\n\n            correct = false;\n            // if (answer.type==\"value\"){\n            if ('value' in answer) {\n                if (submission == answer.value) {\n                    fb.textContent = jaxify(answer.feedback);\n                    correct = answer.correct;\n                    //console.log(answer.correct);\n                    done = true;\n                }\n                // } else if (answer.type==\"range\") {\n            } else if ('range' in answer) {\n                //console.log(answer.range);\n                if ((submission >= answer.range[0]) && (submission < answer.range[1])) {\n                    fb.textContent = jaxify(answer.feedback);\n                    correct = answer.correct;\n                    //console.log(answer.correct);\n                    done = true;\n                }\n            } else if (answer.type == \"default\") {\n                defaultFB = answer.feedback;\n            }\n            if (done) {\n                return false; // Break out of loop if this has been marked correct\n            } else {\n                return true; // Keep looking for case that includes this as a correct answer\n            }\n        });\n\n        if ((!done) && (defaultFB != \"\")) {\n            fb.innerHTML = jaxify(defaultFB);\n            //console.log(\"Default feedback\", defaultFB);\n        }\n\n        fb.style.display = \"block\";\n        if (correct) {\n            ths.className = \"Input-text\";\n            ths.classList.add(\"correctButton\");\n            fb.className = \"Feedback\";\n            fb.classList.add(\"correct\");\n        } else {\n            ths.className = \"Input-text\";\n            ths.classList.add(\"incorrectButton\");\n            fb.className = \"Feedback\";\n            fb.classList.add(\"incorrect\");\n        }\n\n        // What follows is for the saved responses stuff\n        var outerContainer = fb.parentElement.parentElement;\n        var responsesContainer = document.getElementById(\"responses\" + outerContainer.id);\n        if (responsesContainer) {\n            console.log(submission);\n            var qnum = document.getElementById(\"quizWrap\"+id).dataset.qnum;\n            //console.log(\"Question \" + qnum);\n            //console.log(id, \", got numcorrect=\",fb.dataset.numcorrect);\n            var responses=JSON.parse(responsesContainer.dataset.responses);\n            console.log(responses);\n            if (submission == ths.value){\n                responses[qnum]= submission;\n            } else {\n                responses[qnum]= ths.value + \"(\" + submission +\")\";\n            }\n            responsesContainer.setAttribute('data-responses', JSON.stringify(responses));\n            printResponses(responsesContainer);\n        }\n        // End code to preserve responses\n\n        if (typeof MathJax != 'undefined') {\n            var version = MathJax.version;\n            console.log('MathJax version', version);\n            if (version[0] == \"2\") {\n                MathJax.Hub.Queue([\"Typeset\", MathJax.Hub]);\n            } else if (version[0] == \"3\") {\n                MathJax.typeset([fb]);\n            }\n        } else {\n            console.log('MathJax not detected');\n        }\n        return false;\n    }\n\n}\n\nfunction isValid(el, charC) {\n    //console.log(\"Input char: \", charC);\n    if (charC == 46) {\n        if (el.value.indexOf('.') === -1) {\n            return true;\n        } else if (el.value.indexOf('/') != -1) {\n            var parts = el.value.split('/');\n            if (parts[1].indexOf('.') === -1) {\n                return true;\n            }\n        }\n        else {\n            return false;\n        }\n    } else if (charC == 47) {\n        if (el.value.indexOf('/') === -1) {\n            if ((el.value != \"\") && (el.value != \".\")) {\n                return true;\n            } else {\n                return false;\n            }\n        } else {\n            return false;\n        }\n    } else if (charC == 45) {\n        var edex = el.value.indexOf('e');\n        if (edex == -1) {\n            edex = el.value.indexOf('E');\n        }\n\n        if (el.value == \"\") {\n            return true;\n        } else if (edex == (el.value.length - 1)) { // If just after e or E\n            return true;\n        } else {\n            return false;\n        }\n    } else if (charC == 101) { // \"e\"\n        if ((el.value.indexOf('e') === -1) && (el.value.indexOf('E') === -1) && (el.value.indexOf('/') == -1)) {\n            // Prev symbol must be digit or decimal point:\n            if (el.value.slice(-1).search(/\\d/) >= 0) {\n                return true;\n            } else if (el.value.slice(-1).search(/\\./) >= 0) {\n                return true;\n            } else {\n                return false;\n            }\n        } else {\n            return false;\n        }\n    } else {\n        if (charC > 31 && (charC < 48 || charC > 57))\n            return false;\n    }\n    return true;\n}\n\nfunction numeric_keypress(evnt) {\n    var charC = (evnt.which) ? evnt.which : evnt.keyCode;\n\n    if (charC == 13) {\n        check_numeric(this, evnt);\n    } else {\n        return isValid(this, charC);\n    }\n}\n\n\n\n\n\nfunction make_numeric(qa, outerqDiv, qDiv, aDiv, id) {\n\n\n\n    //console.log(answer);\n\n\n    outerqDiv.className = \"NumericQn\";\n    aDiv.style.display = 'block';\n\n    var lab = document.createElement(\"label\");\n    lab.className = \"InpLabel\";\n    lab.textContent = \"Type numeric answer here:\";\n    aDiv.append(lab);\n\n    var inp = document.createElement(\"input\");\n    inp.type = \"text\";\n    //inp.id=\"input-\"+id;\n    inp.id = id + \"-0\";\n    inp.className = \"Input-text\";\n    inp.setAttribute('data-answers', JSON.stringify(qa.answers));\n    if (\"precision\" in qa) {\n        inp.setAttribute('data-precision', qa.precision);\n    }\n    aDiv.append(inp);\n    //console.log(inp);\n\n    //inp.addEventListener(\"keypress\", check_numeric);\n    //inp.addEventListener(\"keypress\", numeric_keypress);\n    /*\n    inp.addEventListener(\"keypress\", function(event) {\n        return numeric_keypress(this, event);\n    }\n                        );\n                        */\n    //inp.onkeypress=\"return numeric_keypress(this, event)\";\n    inp.onkeypress = numeric_keypress;\n    inp.onpaste = event => false;\n\n    inp.addEventListener(\"focus\", function (event) {\n        this.value = \"\";\n        return false;\n    }\n    );\n\n\n}\nfunction jaxify(string) {\n    var mystring = string;\n\n    var count = 0;\n    var loc = mystring.search(/([^\\\\]|^)(\\$)/);\n\n    var count2 = 0;\n    var loc2 = mystring.search(/([^\\\\]|^)(\\$\\$)/);\n\n    //console.log(loc);\n\n    while ((loc >= 0) || (loc2 >= 0)) {\n\n        /* Have to replace all the double $$ first with current implementation */\n        if (loc2 >= 0) {\n            if (count2 % 2 == 0) {\n                mystring = mystring.replace(/([^\\\\]|^)(\\$\\$)/, \"$1\\\\[\");\n            } else {\n                mystring = mystring.replace(/([^\\\\]|^)(\\$\\$)/, \"$1\\\\]\");\n            }\n            count2++;\n        } else {\n            if (count % 2 == 0) {\n                mystring = mystring.replace(/([^\\\\]|^)(\\$)/, \"$1\\\\(\");\n            } else {\n                mystring = mystring.replace(/([^\\\\]|^)(\\$)/, \"$1\\\\)\");\n            }\n            count++;\n        }\n        loc = mystring.search(/([^\\\\]|^)(\\$)/);\n        loc2 = mystring.search(/([^\\\\]|^)(\\$\\$)/);\n        //console.log(mystring,\", loc:\",loc,\", loc2:\",loc2);\n    }\n\n    //console.log(mystring);\n    return mystring;\n}\n\n\nfunction show_questions(json, mydiv) {\n    console.log('show_questions');\n    //var mydiv=document.getElementById(myid);\n    var shuffle_questions = mydiv.dataset.shufflequestions;\n    var num_questions = mydiv.dataset.numquestions;\n    var shuffle_answers = mydiv.dataset.shuffleanswers;\n\n    if (num_questions > json.length) {\n        num_questions = json.length;\n    }\n\n    var questions;\n    if ((num_questions < json.length) || (shuffle_questions == \"True\")) {\n        //console.log(num_questions+\",\"+json.length);\n        questions = getRandomSubarray(json, num_questions);\n    } else {\n        questions = json;\n    }\n\n    //console.log(\"SQ: \"+shuffle_questions+\", NQ: \" + num_questions + \", SA: \", shuffle_answers);\n\n    // Iterate over questions\n    questions.forEach((qa, index, array) => {\n        //console.log(qa.question); \n\n        var id = makeid(8);\n        //console.log(id);\n\n\n        // Create Div to contain question and answers\n        var iDiv = document.createElement('div');\n        //iDiv.id = 'quizWrap' + id + index;\n        iDiv.id = 'quizWrap' + id;\n        iDiv.className = 'Quiz';\n        iDiv.setAttribute('data-qnum', index);\n        mydiv.appendChild(iDiv);\n        // iDiv.innerHTML=qa.question;\n\n        var outerqDiv = document.createElement('div');\n        outerqDiv.id = \"OuterquizQn\" + id + index;\n\n        iDiv.append(outerqDiv);\n\n        // Create div to contain question part\n        var qDiv = document.createElement('div');\n        qDiv.id = \"quizQn\" + id + index;\n        //qDiv.textContent=qa.question;\n        qDiv.innerHTML = jaxify(qa.question);\n\n        outerqDiv.append(qDiv);\n\n        // Create div for code inside question\n        var codeDiv;\n        if (\"code\" in qa) {\n            codeDiv = document.createElement('div');\n            codeDiv.id = \"code\" + id + index;\n            codeDiv.className = \"QuizCode\";\n            var codePre = document.createElement('pre');\n            codeDiv.append(codePre);\n            var codeCode = document.createElement('code');\n            codePre.append(codeCode);\n            codeCode.innerHTML = qa.code;\n            outerqDiv.append(codeDiv);\n            //console.log(codeDiv);\n        }\n\n\n        // Create div to contain answer part\n        var aDiv = document.createElement('div');\n        aDiv.id = \"quizAns\" + id + index;\n        aDiv.className = 'Answer';\n        iDiv.append(aDiv);\n\n        //console.log(qa.type);\n\n        var num_correct;\n        if (qa.type == \"multiple_choice\") {\n            num_correct = make_mc(qa, shuffle_answers, outerqDiv, qDiv, aDiv, id);\n        } else if (qa.type == \"many_choice\") {\n            num_correct = make_mc(qa, shuffle_answers, outerqDiv, qDiv, aDiv, id);\n        } else if (qa.type == \"numeric\") {\n            //console.log(\"numeric\");\n            make_numeric(qa, outerqDiv, qDiv, aDiv, id);\n        }\n\n\n        //Make div for feedback\n        var fb = document.createElement(\"div\");\n        fb.id = \"fb\" + id;\n        //fb.style=\"font-size: 20px;text-align:center;\";\n        fb.className = \"Feedback\";\n        fb.setAttribute(\"data-answeredcorrect\", 0);\n        fb.setAttribute(\"data-numcorrect\", num_correct);\n        iDiv.append(fb);\n\n\n    });\n    var preserveResponses = mydiv.dataset.preserveresponses;\n    console.log(preserveResponses);\n    console.log(preserveResponses == \"true\");\n    if (preserveResponses == \"true\") {\n        console.log(preserveResponses);\n        // Create Div to contain record of answers\n        var iDiv = document.createElement('div');\n        iDiv.id = 'responses' + mydiv.id;\n        iDiv.className = 'JCResponses';\n        // Create a place to store responses as an empty array\n        iDiv.setAttribute('data-responses', '[]');\n\n        // Dummy Text\n        iDiv.innerHTML=\"<b>Select your answers and then follow the directions that will appear here.</b>\"\n        //iDiv.className = 'Quiz';\n        mydiv.appendChild(iDiv);\n    }\n//console.log(\"At end of show_questions\");\n    if (typeof MathJax != 'undefined') {\n        console.log(\"MathJax version\", MathJax.version);\n        var version = MathJax.version;\n        setTimeout(function(){\n            var version = MathJax.version;\n            console.log('After sleep, MathJax version', version);\n            if (version[0] == \"2\") {\n                MathJax.Hub.Queue([\"Typeset\", MathJax.Hub]);\n            } else if (version[0] == \"3\") {\n                MathJax.typeset([mydiv]);\n            }\n        }, 500);\nif (typeof version == 'undefined') {\n        } else\n        {\n            if (version[0] == \"2\") {\n                MathJax.Hub.Queue([\"Typeset\", MathJax.Hub]);\n            } else if (version[0] == \"3\") {\n                MathJax.typeset([mydiv]);\n            } else {\n                console.log(\"MathJax not found\");\n            }\n        }\n    }\n    return false;\n}\n\n        {\n        show_questions(questionsrGiYjbhXRAOm,  rGiYjbhXRAOm);\n        }\n        ",
      "text/plain": [
       "<IPython.core.display.Javascript object>"
      ]
     },
     "metadata": {},
     "output_type": "display_data"
    }
   ],
   "source": [
    "display_quiz(question_path+\"questions31.json\")"
   ]
  },
  {
   "cell_type": "markdown",
   "id": "b55b1b1a",
   "metadata": {
    "kernel": "Python 3 (ipykernel)"
   },
   "source": [
    "## 2. Extend Expressions by Unary Negation \n",
    "\n",
    "1. Make ``exp`` LL(1) by building in precedence, and associativity, and eliminating left-recursion.\n",
    "\n",
    "Take care: Compared to the lecture, expressions can contain a factor, i.e. \n",
    "```\n",
    "[MINUS; ID \"x\"]\n",
    "```\n",
    "is a valid token sequence for expressions.\n",
    "\n",
    "All operators are right-associative. Multiplication/division bind stronger than addition/subtraction bind stronger than negation.\n",
    "E.g. - 2 * 3 + 5  binds as ((-2) * 3)  + 5."
   ]
  },
  {
   "cell_type": "markdown",
   "id": "9b5f6525",
   "metadata": {
    "kernel": "Python 3 (ipykernel)"
   },
   "source": [
    "(* SOLUTION *)\n",
    "```\n",
    "exp ::= term [{+|-} exp]\n",
    "term ::= factor [{*|/} term]\n",
    "factor ::= [-] base\n",
    "base ::= identifier | number | (exp)\n",
    "```"
   ]
  },
  {
   "cell_type": "markdown",
   "id": "65039c86",
   "metadata": {
    "kernel": "Python 3 (ipykernel)"
   },
   "source": [
    "2. Below is the previous definition of an expression parser without negation. Extend it with the new unary negation operation. You'll need a new category (see a)."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "id": "4f56ba42",
   "metadata": {
    "kernel": "OCaml 4.13",
    "vscode": {
     "languageId": "ocaml"
    }
   },
   "outputs": [],
   "source": [
    "let rec parse_exp (xs : token list) : exp * token list = let \n",
    "  (e1, xs') = parse_term xs in \n",
    "  match xs' with \n",
    "  | PLUS :: xs'' -> let \n",
    "      (e2, xs''') = parse_exp xs'' \n",
    "      in (Op (e1, Plus, e2), xs''')\n",
    "  | MINUS :: xs'' -> let \n",
    "      (e2, xs''') = parse_exp xs'' \n",
    "      in (Op (e1, Minus, e2), xs''')\n",
    "  | _ -> (e1, xs') \n",
    "           \n",
    "and parse_term (xs : token list) : exp * token list = let \n",
    "  (e1, xs') = parse_base xs in \n",
    "  match xs' with \n",
    "  | STAR :: xs'' -> let \n",
    "    (e2, xs''') = parse_term xs''\n",
    "      in (Op (e1, Mult, e2), xs''') \n",
    "  | SLASH :: xs'' -> let \n",
    "    (e2, xs''') = parse_term xs''\n",
    "      in (Op (e1, Div, e2), xs''')    \n",
    "  | _ -> (e1, xs')\n",
    "  \n",
    "and parse_base (xs : token list) : exp * token list = match xs with \n",
    "  | ID x :: xs' -> (Id x, xs')\n",
    "  | INT x :: xs' -> (Numb x , xs')\n",
    "  | LBRA :: xs' -> (let \n",
    "        (e, xs'') = parse_exp xs' in let\n",
    "         xs''' = parse_token RBRA xs''\n",
    "      in (e, xs'''))\n",
    "  | _ -> raise (SyntaxError \"Expected ID, INT or LBRA.\") "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "id": "70eb90c7",
   "metadata": {
    "kernel": "OCaml 4.13",
    "vscode": {
     "languageId": "ocaml"
    }
   },
   "outputs": [],
   "source": [
    "(* SOLUTION *)\n",
    "\n",
    "let rec parse_exp (xs : token list) : exp * token list = let \n",
    "  (e1, xs') = parse_term xs in \n",
    "  match xs' with \n",
    "  | PLUS :: xs'' -> let \n",
    "      (e2, xs''') = parse_exp xs'' \n",
    "      in (Op (e1, Plus, e2), xs''')\n",
    "  | MINUS :: xs'' -> let \n",
    "      (e2, xs''') = parse_exp xs'' \n",
    "      in (Op (e1, Minus, e2), xs''')\n",
    "  | _ -> (e1, xs') \n",
    "           \n",
    "and parse_term (xs : token list) : exp * token list = let \n",
    "  (e1, xs') = parse_factor xs in \n",
    "  match xs' with \n",
    "  | STAR :: xs'' -> let \n",
    "    (e2, xs''') = parse_term xs''\n",
    "      in (Op (e1, Mult, e2), xs''') \n",
    "  | SLASH :: xs'' -> let \n",
    "    (e2, xs''') = parse_term xs''\n",
    "      in (Op (e1, Div, e2), xs''')    \n",
    "  | _ -> (e1, xs')\n",
    "  \n",
    "and parse_factor (xs : token list) : exp * token list = match xs with \n",
    "  | MINUS :: xs' -> let (e, xs'') = parse_base xs' in \n",
    "                    (Neg e, xs'')\n",
    "  | _ -> parse_base xs\n",
    "  \n",
    "and parse_base (xs : token list) : exp * token list = match xs with \n",
    "  | ID x :: xs' -> (Id x, xs')\n",
    "  | INT x :: xs' -> (Numb x , xs')\n",
    "  | LBRA :: xs' -> (let \n",
    "        (e, xs'') = parse_exp xs' in let\n",
    "         xs''' = parse_token RBRA xs''\n",
    "      in (e, xs'''))\n",
    "  | _ -> raise (SyntaxError \"Expected ID, INT or LBRA.\") "
   ]
  },
  {
   "cell_type": "markdown",
   "id": "f07bb94b",
   "metadata": {
    "kernel": "Python 3 (ipykernel)"
   },
   "source": [
    "3. Test the parser with one token list that should be accepted and one token list that should not be accepted."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "id": "0f48088f",
   "metadata": {
    "kernel": "OCaml 4.13",
    "vscode": {
     "languageId": "ocaml"
    }
   },
   "outputs": [],
   "source": []
  },
  {
   "cell_type": "markdown",
   "id": "8111a627",
   "metadata": {
    "kernel": "Python 3 (ipykernel)"
   },
   "source": [
    "4. Explain why [MINUS; INT 3] is a valid ``exp``-sentence using your implementation of a parser."
   ]
  },
  {
   "cell_type": "markdown",
   "id": "c150d314",
   "metadata": {
    "kernel": "OCaml 4.13"
   },
   "source": [
    "(* SOLUTION *)\n",
    "\n",
    "```\n",
    "parse_exp [MINUS; INT 3] \n",
    "1. parse_term [MINUS; INT 3], then match on the remaining list according to parse_exp in 2.\n",
    "1.1 parse_factor [MINUS; INT 3], then match on the remaining list according to parse_term in 1.2\n",
    "1.1.1 parse_base [INT 3], then return the negation of the yielded expression/remaining list of tokens. \n",
    "1.1.1.1 We get Numb 3 and the empty list. Go to 1.1.2.\n",
    "1.1.2 We return Neg (Numb 3) and the empty list. Go back to 1.2. \n",
    "1.2 As the remaining list of tokens is empty, we match with the last case and just return Neg (Numb 3) and the empty list. \n",
    "2. As the remaining list of tokens is empty, we match with the last case and just return Neg (Numb 3) and the empty list. \n",
    " \n",
    "```"
   ]
  },
  {
   "cell_type": "markdown",
   "id": "774cced6",
   "metadata": {
    "kernel": "Python 3 (ipykernel)"
   },
   "source": [
    "## 3. Conditional Expressions \n",
    "\n",
    "Extend the parser with conditional expressions by completing the following code. \n",
    "\n",
    "Test the parser with one token list that should be accepted and one token list that should not be accepted."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "id": "4c66494c",
   "metadata": {
    "kernel": "OCaml 4.13",
    "vscode": {
     "languageId": "ocaml"
    }
   },
   "outputs": [],
   "source": [
    "let parse_comp (ts : token list) : cond * token list = \n",
    "    raise (SyntaxError \"TODO: IMPLEMENT\")\n",
    "    \n",
    "let parse_cond (ts : token list) : condexp * token list = \n",
    "   raise (SyntaxError \"TODO: IMPLEMENT\")"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "id": "549e3657",
   "metadata": {
    "kernel": "OCaml 4.13",
    "vscode": {
     "languageId": "ocaml"
    }
   },
   "outputs": [],
   "source": [
    "(* SOLUTION *)\n",
    "\n",
    "let parse_comp (ts : token list) : cond * token list = match ts with \n",
    "    | LT :: ts' -> (Lt, ts')\n",
    "    | LTE :: ts' -> (Lte, ts')\n",
    "    | EQ :: ts' -> (Eq, ts')\n",
    "    | NEQ :: ts' ->  (Neq, ts')\n",
    "    | GT :: ts' -> (Gt, ts')\n",
    "    | GTE :: ts' -> (Gte, ts')\n",
    "    | _ -> raise (SyntaxError \"Comparison token expected.\")\n",
    "    \n",
    "let parse_cond (ts : token list) : condexp * token list = let \n",
    "        (e1, ts') = parse_exp ts in let\n",
    "        (c, ts'') = parse_comp ts' in let \n",
    "        (e2, ts''') = parse_exp ts'' in \n",
    "        (Cop (e1, c, e2), ts''')  "
   ]
  },
  {
   "cell_type": "markdown",
   "id": "0d62a90e",
   "metadata": {
    "kernel": "OCaml 4.13"
   },
   "source": [
    "## 4. Abstract Syntax to Concrete Syntax \n",
    "\n",
    "Change the grammar such that the remaining parts are LL(1)."
   ]
  },
  {
   "cell_type": "markdown",
   "id": "525c1202",
   "metadata": {
    "kernel": "OCaml 4.13"
   },
   "source": [
    "(* SOLUTION *)\n",
    "\n",
    "```\n",
    "program ::=  [declarations] commands \n",
    "declarations ::= declaration; [declarations] \n",
    "declaration ::= VAR identifier\n",
    "\n",
    "commands ::= command[; commands]\n",
    "command ::= identifier := exp | IF condexp THEN command [ELSE command] | WHILE condexp DO command | BEGIN program END | INPUT identifier | PRINT exp \n",
    " \n",
    "comp := = | != | <= | < | >= | >\n",
    "condexp := exp comp exp \n",
    "\n",
    "exp ::= term [{+|-} exp]\n",
    "term ::= factor [{*|/} term]\n",
    "factor ::= [-] base\n",
    "base ::= identifier | number | (exp)\n",
    "```"
   ]
  },
  {
   "cell_type": "markdown",
   "id": "3266cbad",
   "metadata": {
    "kernel": "OCaml 4.13"
   },
   "source": [
    "## 5. Full Parser \n",
    "\n",
    "Below you see a partial definition of the full parser for ``SIMP``. \n",
    "The parts which you have seen in the lecture have been filled in. \n",
    "\n",
    "a) Ensure you understand the return types of all functions.\n",
    "\n",
    "b) Why do parse_program/parse_while/parse_if/parse_command/parse_commands have to be declared mutually recursive? \n",
    "\n",
    "c) Explain why ``[VAR; SEMI]`` is not a valid ``declaration``- sentence given the implementation of the parser. \n",
    "\n",
    "d) Complete the definition of a parser. \n",
    "\n",
    "e) Test the parser with one token list that should be accepted and one token list that should not be accepted."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "id": "83503d1f",
   "metadata": {
    "kernel": "OCaml 4.13",
    "vscode": {
     "languageId": "ocaml"
    }
   },
   "outputs": [],
   "source": [
    "let parse_declaration (ts : token list) : string * token list = match ts with \n",
    "  | VAR :: ID x :: ts' -> (x, ts')\n",
    "  | _ ->  raise (SyntaxError \"Declaration expected.\")\n",
    "\n",
    "let rec parse_declarations (ts : token list) : string list * token list = let \n",
    "  (dcl, ts') = parse_declaration ts in let \n",
    "  ts'' = parse_token SEMI ts' in \n",
    "  match ts'' with \n",
    "  | VAR :: _ -> (let (dcls, ts''') = parse_declarations ts'' in \n",
    "                  (dcl :: dcls, ts''')\n",
    "                  )\n",
    "  | _ -> ([dcl], ts'')\n",
    "\n",
    "\n",
    "let parse_assign x ts = \n",
    "    raise (SyntaxError \"TODO: IMPLEMENT\")\n",
    "\n",
    "let parse_input ts =\n",
    "    raise (SyntaxError \"TODO: IMPLEMENT\")\n",
    "\n",
    "let parse_print ts = \n",
    "     raise (SyntaxError \"TODO: IMPLEMENT\")\n",
    "\n",
    "let rec parse_program (ts : token list) : program * token list = match ts with \n",
    "    | VAR :: _ -> let \n",
    "                  (dcls, ts') = parse_declarations ts in let \n",
    "                  (cs, ts'') = parse_commands ts' in \n",
    "                  (Program (dcls, cs), ts'')\n",
    "    | _ -> let \n",
    "          (cs, ts'') = parse_commands ts in \n",
    "          (Program ([], cs), ts'')\n",
    "\n",
    "and parse_commands (ts : token list) : cmd list * token list = let \n",
    "    (c, ts') = parse_command ts in \n",
    "    match ts' with \n",
    "    | SEMI :: ts'' -> let \n",
    "                      (cs, ts''') = parse_commands ts''\n",
    "                      in (c :: cs, ts''')\n",
    "    | _ -> ([c], ts')\n",
    "\n",
    "and parse_command (ts : token list) : cmd * token list = match ts with \n",
    "  | ID x :: ts' -> parse_assign x ts'\n",
    "  | INPUT :: ts' -> parse_input ts'\n",
    "  | PRINT :: ts' -> parse_print ts'\n",
    "  | IF :: ts' -> parse_if ts'\n",
    "  | WHILE :: ts' -> parse_while ts'\n",
    "  | BEGIN :: ts' -> parse_block ts'\n",
    "  | _ -> raise (SyntaxError \"Command expected.\")\n",
    "    \n",
    "and parse_if (ts : token list) : cmd * token list = let \n",
    "    (b, ts') = parse_cond ts in let \n",
    "    ts'' = parse_token THEN ts' in let\n",
    "    (c1, ts''') = parse_command ts'' in \n",
    "        match ts''' with \n",
    "        | ELSE :: ts'''' -> let (c2, ts''''') = parse_command ts'''' in \n",
    "                           (Ite (b, c1, c2), ts''''')\n",
    "        | _ -> (If (b, c1), ts''')\n",
    "\n",
    "and parse_while (ts : token list) : cmd * token list = \n",
    "   raise (SyntaxError \"TODO: IMPLEMENT\")\n",
    "\n",
    "and parse_block (ts : token list) : cmd * token list =\n",
    "  raise (SyntaxError \"TODO: IMPLEMENT\")"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "id": "97c8a849",
   "metadata": {
    "kernel": "OCaml 4.13",
    "vscode": {
     "languageId": "ocaml"
    }
   },
   "outputs": [],
   "source": [
    "(* SOLUTION *)\n",
    "\n",
    "let parse_declaration (ts : token list) : string * token list = match ts with \n",
    "  | VAR :: ID x :: ts' -> (x, ts')\n",
    "  | _ ->  raise (SyntaxError \"Declaration expected.\")\n",
    "\n",
    "let rec parse_declarations (ts : token list) : string list * token list = let \n",
    "  (dcl, ts') = parse_declaration ts in let \n",
    "  ts'' = parse_token SEMI ts' in \n",
    "  match ts'' with \n",
    "  | VAR :: _ -> (let (dcls, ts''') = parse_declarations ts'' in \n",
    "                  (dcl :: dcls, ts''')\n",
    "                  )\n",
    "  | _ -> ([dcl], ts'')\n",
    "\n",
    "\n",
    "let parse_assign x ts = let \n",
    "    ts' = parse_token ASGN ts in let \n",
    "    (e, ts'') = parse_exp ts' in \n",
    "    ((Asgn (x, e)), ts'')\n",
    "\n",
    "let parse_input ts = match ts with \n",
    "    | ID x :: ts' -> (Input x, ts')\n",
    "    | _ -> raise (SyntaxError \"Identifier expected.\")\n",
    "\n",
    "let parse_print ts = let \n",
    "    (e, ts') = parse_exp ts in \n",
    "    (Print e, ts')\n",
    "\n",
    "\n",
    "let rec parse_program (ts : token list) : program * token list = match ts with \n",
    "    | VAR :: _ -> let \n",
    "                  (dcls, ts') = parse_declarations ts in let \n",
    "                  (cs, ts'') = parse_commands ts' in \n",
    "                  (Program (dcls, cs), ts'')\n",
    "    | _ -> let \n",
    "          (cs, ts'') = parse_commands ts in \n",
    "          (Program ([], cs), ts'')\n",
    "\n",
    "and parse_commands (ts : token list) : cmd list * token list = let \n",
    "    (c, ts') = parse_command ts in \n",
    "    match ts' with \n",
    "    | SEMI :: ts'' -> let \n",
    "                      (cs, ts''') = parse_commands ts''\n",
    "                      in (c :: cs, ts''')\n",
    "    | _ -> ([c], ts')\n",
    "\n",
    "and parse_command (ts : token list) : cmd * token list = match ts with \n",
    "  | ID x :: ts' -> parse_assign x ts'\n",
    "  | INPUT :: ts' -> parse_input ts'\n",
    "  | PRINT :: ts' -> parse_print ts'\n",
    "  | IF :: ts' -> parse_if ts'\n",
    "  | WHILE :: ts' -> parse_while ts'\n",
    "  | BEGIN :: ts' -> parse_block ts'\n",
    "  | _ -> raise (SyntaxError \"Command expected.\")\n",
    "    \n",
    "and parse_if (ts : token list) : cmd * token list = let \n",
    "    (b, ts') = parse_cond ts in let \n",
    "    ts'' = parse_token THEN ts' in let\n",
    "    (c1, ts''') = parse_command ts'' in \n",
    "        match ts''' with \n",
    "        | ELSE :: ts'''' -> let (c2, ts''''') = parse_command ts'''' in \n",
    "                           (Ite (b, c1, c2), ts''''')\n",
    "        | _ -> (If (b, c1), ts''')\n",
    "\n",
    "and parse_while (ts : token list) : cmd * token list = let \n",
    "    (b, ts') = parse_cond ts in let \n",
    "    ts'' = parse_token DO ts' in let \n",
    "    (c, ts''') = parse_command ts'' in \n",
    "    (While (b, c), ts''')\n",
    "\n",
    "and parse_block (ts : token list) : cmd * token list = let \n",
    "    (p, ts') = parse_program ts in let \n",
    "    ts'' = parse_token END ts' in \n",
    "    (Begin p, ts'')"
   ]
  },
  {
   "cell_type": "markdown",
   "id": "0b0ddcb8",
   "metadata": {
    "kernel": "OCaml 4.13"
   },
   "source": [
    "## 6. Challenge \n",
    "\n",
    "Change the parser of expressions so that all binary operators are **left-associative**. "
   ]
  }
 ],
 "metadata": {
  "kernelspec": {
   "display_name": "OCaml 4.13",
   "language": "OCaml",
   "name": "ocaml-jupyter-4.13"
  },
  "language_info": {
   "codemirror_mode": "sos",
   "file_extension": ".sos",
   "mimetype": "text/x-sos",
   "name": "OCaml",
   "nbconvert_exporter": "sos_notebook.converter.SoS_Exporter",
   "pygments_lexer": "sos"
  },
  "sos": {
   "kernels": [
    [
     "OCaml 4.13",
     "ocaml-jupyter-4.13",
     "OCaml",
     "",
     "text/x-ocaml"
    ],
    [
     "Python 3 (ipykernel)",
     "python3",
     "python3",
     "",
     {
      "name": "ipython",
      "version": 3
     }
    ]
   ],
   "panel": {
    "displayed": true,
    "height": 0
   },
   "version": "0.24.0"
  }
 },
 "nbformat": 4,
 "nbformat_minor": 5
}