aboutsummaryrefslogtreecommitdiff
path: root/abstract-syntax-exercise.ipynb
diff options
context:
space:
mode:
Diffstat (limited to 'abstract-syntax-exercise.ipynb')
-rw-r--r--abstract-syntax-exercise.ipynb1657
1 files changed, 1657 insertions, 0 deletions
diff --git a/abstract-syntax-exercise.ipynb b/abstract-syntax-exercise.ipynb
new file mode 100644
index 0000000..c8a5be3
--- /dev/null
+++ b/abstract-syntax-exercise.ipynb
@@ -0,0 +1,1657 @@
+{
+ "cells": [
+ {
+ "cell_type": "markdown",
+ "id": "25085ca3",
+ "metadata": {},
+ "source": [
+ "Before you turn this problem in, make sure everything runs as expected. First, **restart the kernel** (in the menubar, select Kernel $\\rightarrow$ Restart) and then **run all cells** (in the menubar, select Cell $\\rightarrow$ Run All).\n",
+ "\n",
+ "Make sure you fill in any place that says `???`, `YOUR CODE HERE`, \"???\", \"YOUR ANSWER HERE\", as well as your name and collaborators below:"
+ ]
+ },
+ {
+ "cell_type": "code",
+ "execution_count": 19,
+ "id": "746e58f4",
+ "metadata": {},
+ "outputs": [
+ {
+ "data": {
+ "text/plain": [
+ "\u001b[36mNAME\u001b[39m: \u001b[32mString\u001b[39m = \u001b[32m\"Jack Sangdahl\"\u001b[39m\n",
+ "\u001b[36mCOLLABORATORS\u001b[39m: \u001b[32mString\u001b[39m = \u001b[32m\"N/A\"\u001b[39m"
+ ]
+ },
+ "execution_count": 19,
+ "metadata": {},
+ "output_type": "execute_result"
+ }
+ ],
+ "source": [
+ "val NAME = \"Jack Sangdahl\"\n",
+ "val COLLABORATORS = \"N/A\""
+ ]
+ },
+ {
+ "cell_type": "markdown",
+ "id": "bdb1d285",
+ "metadata": {},
+ "source": [
+ "---"
+ ]
+ },
+ {
+ "cell_type": "markdown",
+ "id": "7428aa62-a2f8-45d6-a04d-568bbec79950",
+ "metadata": {},
+ "source": [
+ "# Exercise: Syntax\n",
+ "\n",
+ "<!-- 3 Expressions -->\n",
+ "\n",
+ "<!-- 4 Binding and Scope -->\n",
+ "\n",
+ "<!-- 8 Recursion -->\n",
+ "\n",
+ "<!-- 9 Inductive Data Types -->\n",
+ "\n",
+ "<!-- 11 Concrete Syntax -->\n",
+ "\n",
+ "<!-- 12 Abstract Syntax and Parsing -->\n",
+ "\n",
+ "<!-- 13 Exercise: Syntax -->\n",
+ "\n",
+ "<!-- 14 Static Scoping -->\n",
+ "\n",
+ "### Learning Goals\n",
+ "\n",
+ "The primary learning goals of this assignment are to build intuition for\n",
+ "the following:\n",
+ "\n",
+ "- working with abstract syntax trees;\n",
+ "- how grammars are used to specify the syntax of programming\n",
+ " languages; and\n",
+ "- the distinction between concrete and abstract syntax.\n",
+ "\n",
+ "### Instructions\n",
+ "\n",
+ "This assignment asks you to write Scala code. There are restrictions\n",
+ "associated with how you can solve these problems. Please pay careful\n",
+ "heed to those. If you are unsure, ask the course staff.\n",
+ "\n",
+ "Note that `???` indicates that there is a missing function or code\n",
+ "fragment that needs to be filled in. Make sure that you remove the `???`\n",
+ "and replace it with the answer.\n",
+ "\n",
+ "Use the test cases provided to test your implementations. You are also\n",
+ "encouraged to write your own test cases to help debug your work.\n",
+ "However, please delete any extra cells you may have created lest they\n",
+ "break an autograder.\n",
+ "\n",
+ "### Imports"
+ ]
+ },
+ {
+ "cell_type": "code",
+ "execution_count": 20,
+ "id": "0c85487c",
+ "metadata": {
+ "deletable": false,
+ "editable": false,
+ "nbgrader": {
+ "cell_type": "code",
+ "checksum": "afc1ca0eb6ddf4e8f942a9b59b4d2e8e",
+ "grade": false,
+ "grade_id": "testing",
+ "locked": true,
+ "schema_version": 3,
+ "solution": false,
+ "task": false
+ }
+ },
+ "outputs": [
+ {
+ "data": {
+ "text/plain": [
+ "\u001b[32mimport \u001b[39m\u001b[36mRun this cell FIRST before testing.\n",
+ "import $ivy.$ , org.scalatest._, events._, flatspec._\n",
+ "\u001b[39m\n",
+ "defined \u001b[32mfunction\u001b[39m \u001b[36mreport\u001b[39m\n",
+ "defined \u001b[32mfunction\u001b[39m \u001b[36massertPassed\u001b[39m\n",
+ "defined \u001b[32mfunction\u001b[39m \u001b[36mpassed\u001b[39m\n",
+ "defined \u001b[32mfunction\u001b[39m \u001b[36mtest\u001b[39m"
+ ]
+ },
+ "execution_count": 20,
+ "metadata": {},
+ "output_type": "execute_result"
+ }
+ ],
+ "source": [
+ "// Run this cell FIRST before testing.\n",
+ "import $ivy.`org.scalatest::scalatest:3.2.19`, org.scalatest._, events._, flatspec._\n",
+ "def report(suite: Suite): Unit = suite.execute(stats = true)\n",
+ "def assertPassed(suite: Suite): Unit =\n",
+ " suite.run(None, Args(new Reporter {\n",
+ " def apply(e: Event) = e match {\n",
+ " case e @ (_: TestFailed) => assert(false, s\"${e.message} (${e.testName})\")\n",
+ " case _ => ()\n",
+ " }\n",
+ " }))\n",
+ "def passed(points: Int): Unit = {\n",
+ " require(points >=0)\n",
+ " if (points == 1) println(\"*** 🎉 Tests Passed (1 point) ***\")\n",
+ " else println(s\"*** 🎉 Tests Passed ($points points) ***\")\n",
+ "}\n",
+ "def test(suite: Suite, points: Int): Unit = {\n",
+ " report(suite)\n",
+ " assertPassed(suite)\n",
+ " passed(points)\n",
+ "}"
+ ]
+ },
+ {
+ "cell_type": "code",
+ "execution_count": 21,
+ "id": "213c5736",
+ "metadata": {
+ "deletable": false,
+ "editable": false,
+ "nbgrader": {
+ "cell_type": "code",
+ "checksum": "3a42711f30a92ef63bef70549eb85bd2",
+ "grade": false,
+ "grade_id": "parser",
+ "locked": true,
+ "schema_version": 3,
+ "solution": false,
+ "task": false
+ }
+ },
+ "outputs": [
+ {
+ "data": {
+ "text/plain": [
+ "\u001b[32mimport \u001b[39m\u001b[36m$ivy.$\u001b[39m"
+ ]
+ },
+ "execution_count": 21,
+ "metadata": {},
+ "output_type": "execute_result"
+ }
+ ],
+ "source": [
+ "// Run this cell FIRST before building your parser.\n",
+ "import $ivy.`org.scala-lang.modules::scala-parser-combinators:2.4.0`"
+ ]
+ },
+ {
+ "cell_type": "markdown",
+ "id": "7e8272a2-d82f-4888-92d0-25fd120fd768",
+ "metadata": {},
+ "source": [
+ "## Abstract Syntax Trees\n",
+ "\n",
+ "Let us consider the (abstract) syntax of a language of Boolean\n",
+ "expressions:\n",
+ "\n",
+ "$$\\begin{array}{lrrl}\n",
+ " \\text{Boolean expressions} & e& \\mathrel{::=}& x\n",
+ " \\mid\\neg e_1\n",
+ " \\mid e_1 \\wedge e_2\n",
+ " \\mid e_1 \\vee e_2 \\\\\n",
+ " \\text{variables} & x\n",
+ "\\end{array}$$\n",
+ "\n",
+ "### Defining an Inductive Data Type\n",
+ "\n",
+ "We can write explicitly the above grammar with abstract syntax tree\n",
+ "nodes:\n",
+ "\n",
+ "$$\\begin{array}{rrrl}\n",
+ "\\text{Boolean expressions $\\texttt{BExpr}$} & e& \\mathrel{::=}&\n",
+ " \\texttt{Var(} x\\texttt{)} \\\\\n",
+ " & & \\mid& \\texttt{Not(}e_1\\texttt{)} \\\\\n",
+ " & & \\mid& \\texttt{And(}e_1\\texttt{,}\\;e_2\\texttt{)} \\\\\n",
+ " & & \\mid& \\texttt{Or(}e_1\\texttt{,}\\;e_2\\texttt{)} \\\\\n",
+ "\\end{array}$$\n",
+ "\n",
+ "<span class=\"theorem-title\">**Exercise 1 (5 points)**</span> Define an\n",
+ "inductive data type `BExpr` in Scala following the above grammar. Use\n",
+ "the the names given above for the constructors, and use the Scala type\n",
+ "`String` to represent variable names.\n",
+ "\n",
+ "**Edit this cell:**"
+ ]
+ },
+ {
+ "cell_type": "code",
+ "execution_count": 22,
+ "id": "c17f7690",
+ "metadata": {
+ "deletable": false,
+ "nbgrader": {
+ "cell_type": "code",
+ "checksum": "4fa8ce605b81e3837cc6f0a5eb8c87c0",
+ "grade": false,
+ "grade_id": "bexpr_answer",
+ "locked": false,
+ "schema_version": 3,
+ "solution": true,
+ "task": false
+ }
+ },
+ "outputs": [
+ {
+ "data": {
+ "text/plain": [
+ "defined \u001b[32mtrait\u001b[39m \u001b[36mBExpr\u001b[39m\n",
+ "defined \u001b[32mclass\u001b[39m \u001b[36mVar\u001b[39m\n",
+ "defined \u001b[32mclass\u001b[39m \u001b[36mNot\u001b[39m\n",
+ "defined \u001b[32mclass\u001b[39m \u001b[36mAnd\u001b[39m\n",
+ "defined \u001b[32mclass\u001b[39m \u001b[36mOr\u001b[39m"
+ ]
+ },
+ "execution_count": 22,
+ "metadata": {},
+ "output_type": "execute_result"
+ }
+ ],
+ "source": [
+ "sealed trait BExpr\n",
+ "case class Var(x: String) extends BExpr\n",
+ "case class Not(e: BExpr) extends BExpr\n",
+ "case class And(e1: BExpr, e2: BExpr) extends BExpr\n",
+ "case class Or(e1: BExpr, e2: BExpr) extends BExpr"
+ ]
+ },
+ {
+ "cell_type": "markdown",
+ "id": "6bb509ab-c5d2-4069-b322-a4455dc8528b",
+ "metadata": {},
+ "source": [
+ "#### Tests"
+ ]
+ },
+ {
+ "cell_type": "code",
+ "execution_count": 23,
+ "id": "e0b0d389",
+ "metadata": {
+ "deletable": false,
+ "editable": false,
+ "nbgrader": {
+ "cell_type": "code",
+ "checksum": "9d5a59b48e6c646390a761b3e2129439",
+ "grade": true,
+ "grade_id": "bexpr_tests",
+ "locked": true,
+ "points": 5,
+ "schema_version": 3,
+ "solution": false,
+ "task": false
+ }
+ },
+ "outputs": [
+ {
+ "name": "stdout",
+ "output_type": "stream",
+ "text": [
+ "*** 🎉 Tests Passed (5 points) ***\n"
+ ]
+ },
+ {
+ "data": {
+ "text/plain": [
+ "\u001b[36ma\u001b[39m: \u001b[32mBExpr\u001b[39m = \u001b[33mVar\u001b[39m(x = \u001b[32m\"A\"\u001b[39m)\n",
+ "\u001b[36mb\u001b[39m: \u001b[32mBExpr\u001b[39m = \u001b[33mVar\u001b[39m(x = \u001b[32m\"B\"\u001b[39m)\n",
+ "\u001b[36mc\u001b[39m: \u001b[32mBExpr\u001b[39m = \u001b[33mVar\u001b[39m(x = \u001b[32m\"C\"\u001b[39m)\n",
+ "\u001b[36mnot_b\u001b[39m: \u001b[32mBExpr\u001b[39m = \u001b[33mNot\u001b[39m(e = \u001b[33mVar\u001b[39m(x = \u001b[32m\"B\"\u001b[39m))\n",
+ "\u001b[36mnot_a\u001b[39m: \u001b[32mBExpr\u001b[39m = \u001b[33mNot\u001b[39m(e = \u001b[33mVar\u001b[39m(x = \u001b[32m\"A\"\u001b[39m))\n",
+ "\u001b[36me1\u001b[39m: \u001b[32mBExpr\u001b[39m = \u001b[33mAnd\u001b[39m(e1 = \u001b[33mVar\u001b[39m(x = \u001b[32m\"A\"\u001b[39m), e2 = \u001b[33mNot\u001b[39m(e = \u001b[33mVar\u001b[39m(x = \u001b[32m\"B\"\u001b[39m)))\n",
+ "\u001b[36me2\u001b[39m: \u001b[32mBExpr\u001b[39m = \u001b[33mAnd\u001b[39m(e1 = \u001b[33mVar\u001b[39m(x = \u001b[32m\"B\"\u001b[39m), e2 = \u001b[33mNot\u001b[39m(e = \u001b[33mVar\u001b[39m(x = \u001b[32m\"A\"\u001b[39m)))\n",
+ "\u001b[36me3\u001b[39m: \u001b[32mBExpr\u001b[39m = \u001b[33mOr\u001b[39m(\n",
+ " e1 = \u001b[33mAnd\u001b[39m(e1 = \u001b[33mVar\u001b[39m(x = \u001b[32m\"A\"\u001b[39m), e2 = \u001b[33mNot\u001b[39m(e = \u001b[33mVar\u001b[39m(x = \u001b[32m\"B\"\u001b[39m))),\n",
+ " e2 = \u001b[33mAnd\u001b[39m(e1 = \u001b[33mVar\u001b[39m(x = \u001b[32m\"B\"\u001b[39m), e2 = \u001b[33mNot\u001b[39m(e = \u001b[33mVar\u001b[39m(x = \u001b[32m\"A\"\u001b[39m)))\n",
+ ")"
+ ]
+ },
+ "execution_count": 23,
+ "metadata": {},
+ "output_type": "execute_result"
+ }
+ ],
+ "source": [
+ "val a: BExpr = Var(\"A\")\n",
+ "val b: BExpr = Var(\"B\")\n",
+ "val c: BExpr = Var(\"C\")\n",
+ "val not_b: BExpr = Not(b)\n",
+ "val not_a: BExpr = Not(a)\n",
+ "val e1: BExpr = And(a,not_b)\n",
+ "val e2: BExpr = And(b, not_a)\n",
+ "val e3: BExpr = Or(e1,e2)\n",
+ "passed(5)"
+ ]
+ },
+ {
+ "cell_type": "markdown",
+ "id": "f1a9c60a-f0d8-4ce7-9de1-e5a9bb0a5cc0",
+ "metadata": {},
+ "source": [
+ "### Converting to Negation Normal Form\n",
+ "\n",
+ "<span class=\"theorem-title\">**Exercise 2 (10 points)**</span> Write a\n",
+ "function `nnf` to convert Boolean formulas from the above grammar to\n",
+ "their Negation Normal Form (NNF). A Boolean formula is said to be in NNF\n",
+ "iff the negation operator $\\neg$ (i.e., $\\texttt{Not}$) is only applied\n",
+ "to the variables. For example, the following formula is in NNF because\n",
+ "negation is only applied to $A$ or $B$, or both of which are variables:\n",
+ "\n",
+ "$$\n",
+ "(A \\wedge \\neg B) \\vee (B \\land \\neg A) \\;.\n",
+ "$$\n",
+ "\n",
+ "On the other hand, the following formula is not in NNF as negation is\n",
+ "applied to a complex expression:\n",
+ "\n",
+ "$$\n",
+ "\\neg(A \\vee \\neg B) \\wedge (\\neg B \\vee C) \\;.\n",
+ "$$\n",
+ "\n",
+ "The negation normal form of the above formula is as follows:\n",
+ "\n",
+ "$$\n",
+ "(\\neg A \\wedge \\neg B) \\wedge (\\neg B \\vee C) \\;.\n",
+ "$$\n",
+ "\n",
+ "**Edit this cell:**"
+ ]
+ },
+ {
+ "cell_type": "code",
+ "execution_count": 24,
+ "id": "1d442d89",
+ "metadata": {
+ "deletable": false,
+ "nbgrader": {
+ "cell_type": "code",
+ "checksum": "72a0f6bf19b244521a77d1989ad162d4",
+ "grade": false,
+ "grade_id": "nnf_answer",
+ "locked": false,
+ "schema_version": 3,
+ "solution": true,
+ "task": false
+ }
+ },
+ "outputs": [
+ {
+ "data": {
+ "text/plain": [
+ "defined \u001b[32mfunction\u001b[39m \u001b[36mnnf\u001b[39m"
+ ]
+ },
+ "execution_count": 24,
+ "metadata": {},
+ "output_type": "execute_result"
+ }
+ ],
+ "source": [
+ "def nnf(e: BExpr): BExpr = e match {\n",
+ " case Var(_) => e // variable already in nnf\n",
+ " case Not(Var(x)) => Not(Var(x)) // negated variable in nnf\n",
+ " case Not(Not(e1)) => nnf(e1) // double negation cancels out\n",
+ " case Not(And(e1, e2)) => Or(nnf(Not(e1)), nnf(Not(e2))) // apply de morgan law for and\n",
+ " case Not(Or(e1, e2)) => And(nnf(Not(e1)), nnf(Not(e2))) // apply de morgan law for or\n",
+ " case And(e1, e2) => And(nnf(e1), nnf(e2)) // recursively convert sub expression nnf\n",
+ " case Or(e1, e2) => Or(nnf(e1), nnf(e2)) // recursively convert sub expression nnf\n",
+ " case Not(e1) => Not(nnf(e1)) // handle negation in other cases\n",
+ "}"
+ ]
+ },
+ {
+ "cell_type": "markdown",
+ "id": "adb8d1a9-1114-46c5-ac33-7b5269666896",
+ "metadata": {},
+ "source": [
+ "#### Notes\n",
+ "\n",
+ "In general, a formula can be converted to NNF by applying three rules:\n",
+ "\n",
+ "Rule 1 \n",
+ "Double negation is cancelled: $\\neg(\\neg e) = e$ for any Boolean formula\n",
+ "$e$.\n",
+ "\n",
+ "Rule 2 \n",
+ "De Morgan’s Law for conjunction:\n",
+ "$\\neg(e_1 \\wedge e_2) = \\neg e_1 \\vee \\neg e_2$ for any two Boolean\n",
+ "formulas $e_1$ and $e_2$.\n",
+ "\n",
+ "Rule 3 \n",
+ "De Morgan’s Law for disjunction:\n",
+ "$\\neg(e_1 \\vee e_2) = \\neg e_1 \\wedge \\neg e_2$ for any two Boolean\n",
+ "formulas $e_1$ and $e_2$.\n",
+ "\n",
+ "The `nnf` function will have a case for each of the above rule. In\n",
+ "addition, the function will also need to handle the following cases:\n",
+ "\n",
+ "- A variable $x$ or its negation $\\neg x$ is already in NNF.\n",
+ "- An expression $e_1 \\wedge e_2$ is in NNF iff $e_1$ and $e_2$ are in\n",
+ " NNF.\n",
+ "- An expression $e_1 \\vee e_2$ is in NNF iff $e_1$ and $e_2$ are in\n",
+ " NNF.\n",
+ "- An expression $\\neg e_1$ is in NNF iff $e_1$ is in NNF and none of\n",
+ " the above 3 rules apply.\n",
+ "\n",
+ "If you handle all the 7 cases described above, then your `nnf` function\n",
+ "will likely be correct, though of course, you will want to test it.\n",
+ "\n",
+ "#### Tests"
+ ]
+ },
+ {
+ "cell_type": "code",
+ "execution_count": 25,
+ "id": "70af5768",
+ "metadata": {
+ "deletable": false,
+ "editable": false,
+ "nbgrader": {
+ "cell_type": "code",
+ "checksum": "388fcf4fd08defa19603710f164045cb",
+ "grade": true,
+ "grade_id": "nnf_tests",
+ "locked": true,
+ "points": 10,
+ "schema_version": 3,
+ "solution": false,
+ "task": false
+ }
+ },
+ "outputs": [
+ {
+ "name": "stdout",
+ "output_type": "stream",
+ "text": [
+ "\u001b[36mRun starting. Expected test count is: 7\u001b[0m\n",
+ "\u001b[32mcmd25$Helper$$anon$1:\u001b[0m\n",
+ "\u001b[32mnnf\u001b[0m\n",
+ "\u001b[32m- should Test Case 1\u001b[0m\n",
+ "\u001b[32m- should Test Case 2\u001b[0m\n",
+ "\u001b[32m- should Test Case 3\u001b[0m\n",
+ "\u001b[32m- should Test Case 4\u001b[0m\n",
+ "\u001b[32m- should Test Case 5\u001b[0m\n",
+ "\u001b[32m- should Test Case 6\u001b[0m\n",
+ "\u001b[32m- should Test Case 7\u001b[0m\n",
+ "\u001b[36mRun completed in 2 milliseconds.\u001b[0m\n",
+ "\u001b[36mTotal number of tests run: 7\u001b[0m\n",
+ "\u001b[36mSuites: completed 1, aborted 0\u001b[0m\n",
+ "\u001b[36mTests: succeeded 7, failed 0, canceled 0, ignored 0, pending 0\u001b[0m\n",
+ "\u001b[32mAll tests passed.\u001b[0m\n",
+ "*** 🎉 Tests Passed (10 points) ***\n"
+ ]
+ }
+ ],
+ "source": [
+ "test(new AnyFlatSpec {\n",
+ " val testcase1 = Var(\"A\")\n",
+ " val testcase2 = Not(Not(Var(\"B\")))\n",
+ " val testcase3 = And(Var(\"A\"), Or(Var(\"B\"), Var(\"C\")))\n",
+ " val testcase4 = Or(Var(\"A\"), And(Var(\"B\"), Var(\"C\")))\n",
+ " val testcase5 = Not(And(Var(\"A\"), Var(\"B\")))\n",
+ " val testcase6 = Not(Or(Var(\"A\"), Var(\"B\")))\n",
+ " val testcase7 = Or(And(testcase5,testcase6),testcase2)\n",
+ "\n",
+ " \"nnf\" should \"Test Case 1\" in { assertResult( Var(\"A\") ) { nnf(testcase1)} }\n",
+ " it should \"Test Case 2\" in { assertResult( Var(\"B\") ) { nnf(testcase2) } }\n",
+ " it should \"Test Case 3\" in { assertResult( And(Var(\"A\"), Or(Var(\"B\"), Var(\"C\"))) ) { nnf(testcase3) } }\n",
+ " it should \"Test Case 4\" in { assertResult( Or(Var(\"A\"), And(Var(\"B\"), Var(\"C\"))) ) { nnf(testcase4) } }\n",
+ " it should \"Test Case 5\" in { assertResult( Or(Not(Var(\"A\")), Not(Var(\"B\"))) ) { nnf(testcase5) } }\n",
+ " it should \"Test Case 6\" in { assertResult( And(Not(Var(\"A\")), Not(Var(\"B\"))) ) { nnf(testcase6) } }\n",
+ " it should \"Test Case 7\" in { assertResult( Or(And(Or(Not(Var(\"A\")), Not(Var(\"B\"))), And(Not(Var(\"A\")), Not(Var(\"B\")))), Var(\"B\")) ) { nnf(testcase7) } }\n",
+ "}, 10)"
+ ]
+ },
+ {
+ "cell_type": "markdown",
+ "id": "2e45d4e9-4d1a-474b-a3ae-115bd54edb56",
+ "metadata": {},
+ "source": [
+ "### Substitution\n",
+ "\n",
+ "<span class=\"theorem-title\">**Exercise 3 (5 points)**</span> Write a\n",
+ "function `subst` that substitutes *in* a given Boolean expression *with*\n",
+ "another expression *for* a given variable name. For example,\n",
+ "substituting in $$\n",
+ "\\neg(A \\vee B) \\wedge (\\neg B \\vee C)\n",
+ "$$ with $D$ for $B$ yields $$\n",
+ "\\neg(A \\vee D) \\wedge (\\neg D \\vee C) \\;.\n",
+ "$$\n",
+ "\n",
+ "**Edit this cell:**"
+ ]
+ },
+ {
+ "cell_type": "code",
+ "execution_count": 26,
+ "id": "e4c5dda3",
+ "metadata": {
+ "deletable": false,
+ "nbgrader": {
+ "cell_type": "code",
+ "checksum": "1f82f78050d59cbb7dd28d88085f4b63",
+ "grade": false,
+ "grade_id": "subst_answer",
+ "locked": false,
+ "schema_version": 3,
+ "solution": true,
+ "task": false
+ }
+ },
+ "outputs": [
+ {
+ "data": {
+ "text/plain": [
+ "defined \u001b[32mfunction\u001b[39m \u001b[36msubst\u001b[39m"
+ ]
+ },
+ "execution_count": 26,
+ "metadata": {},
+ "output_type": "execute_result"
+ }
+ ],
+ "source": [
+ "def subst(in_e: BExpr, with_e: BExpr, for_x: String): BExpr = in_e match {\n",
+ " case Var(x) if x == for_x => with_e // variable matches? substitute with with_e\n",
+ " case Var(x) => Var(x) // if variable does not match, leavh unchanged\n",
+ " case Not(e1) => Not(subst(e1, with_e, for_x)) // recursively apply substitution inside not\n",
+ " case And(e1, e2) => And(subst(e1, with_e, for_x), subst(e2, with_e, for_x)) // recursively apply substitution inside and\n",
+ " case Or(e1, e2) => Or(subst(e1, with_e, for_x), subst(e2, with_e, for_x)) // recursively apply substitution inside Or\n",
+ "}"
+ ]
+ },
+ {
+ "cell_type": "markdown",
+ "id": "f454f19f-fb7c-4eeb-807f-7c3e39419d67",
+ "metadata": {},
+ "source": [
+ "#### Tests"
+ ]
+ },
+ {
+ "cell_type": "code",
+ "execution_count": 27,
+ "id": "b2176f6b",
+ "metadata": {
+ "deletable": false,
+ "editable": false,
+ "nbgrader": {
+ "cell_type": "code",
+ "checksum": "95cf8b324808d901baa863057040f86a",
+ "grade": true,
+ "grade_id": "subst_tests",
+ "locked": true,
+ "points": 5,
+ "schema_version": 3,
+ "solution": false,
+ "task": false
+ }
+ },
+ "outputs": [
+ {
+ "name": "stdout",
+ "output_type": "stream",
+ "text": [
+ "\u001b[36mRun starting. Expected test count is: 5\u001b[0m\n",
+ "\u001b[32mcmd27$Helper$$anon$1:\u001b[0m\n",
+ "\u001b[32m- should Test Case 1\u001b[0m\n",
+ "\u001b[32m- should Test Case 2\u001b[0m\n",
+ "\u001b[32m- should Test Case 3\u001b[0m\n",
+ "\u001b[32m- should Test Case 4\u001b[0m\n",
+ "\u001b[32m- should Test Case 5\u001b[0m\n",
+ "\u001b[36mRun completed in 2 milliseconds.\u001b[0m\n",
+ "\u001b[36mTotal number of tests run: 5\u001b[0m\n",
+ "\u001b[36mSuites: completed 1, aborted 0\u001b[0m\n",
+ "\u001b[36mTests: succeeded 5, failed 0, canceled 0, ignored 0, pending 0\u001b[0m\n",
+ "\u001b[32mAll tests passed.\u001b[0m\n",
+ "*** 🎉 Tests Passed (5 points) ***\n"
+ ]
+ }
+ ],
+ "source": [
+ "test(new AnyFlatSpec {\n",
+ " val testcase1 = Var(\"A\")\n",
+ " val testcase2 = Not(Var(\"B\"))\n",
+ " val testcase3 = Or(Var(\"A\"), Var(\"B\"))\n",
+ " val testcase4 = And(Not(Var(\"C\")), Or(Var(\"D\"), Var(\"E\")))\n",
+ " val testcase5 = Or(And(Var(\"X\"), Var(\"Y\")), Or(Var(\"Z\"), Var(\"X\")))\n",
+ "\n",
+ " it should \"Test Case 1\" in { assertResult( Var(\"X\") ) { subst(testcase1, Var(\"X\"), \"A\") } }\n",
+ " it should \"Test Case 2\" in { assertResult( Not(Var(\"Y\")) ) { subst(testcase2, Var(\"Y\"), \"B\") } }\n",
+ " it should \"Test Case 3\" in { assertResult( Or(Var(\"C\"), Var(\"B\")) ) { subst(testcase3, Var(\"C\"), \"A\") } }\n",
+ " it should \"Test Case 4\" in { assertResult( And(Not(Var(\"C\")), Or(Var(\"D\"), Var(\"F\"))) ) { subst(testcase4, Var(\"F\"), \"E\") } }\n",
+ " it should \"Test Case 5\" in { assertResult( Or(And(Var(\"W\"), Var(\"Y\")), Or(Var(\"Z\"), Var(\"W\"))) ) { subst(testcase5, Var(\"W\"), \"X\") } }\n",
+ "}, 5)"
+ ]
+ },
+ {
+ "cell_type": "markdown",
+ "id": "258e56f0-791c-487a-9bf5-44c3f5ad5f2b",
+ "metadata": {},
+ "source": [
+ "## Concrete Syntax\n",
+ "\n",
+ "### Precedence Detective\n",
+ "\n",
+ "Consider the Scala binary expressions $$\\begin{array}{rrrl}\n",
+ " \\text{expressions} & e& \\mathrel{::=}& n\\mid\n",
+ " e_1 \\mathrel{\\texttt{-}} e_2 \\mid\n",
+ " e_1 \\mathrel{\\texttt{<<}} e_2 \\\\\n",
+ " \\text{integers} & n\n",
+ "\\end{array}$$\n",
+ "\n",
+ "<span class=\"theorem-title\">**Exercise 4 (5 points)**</span> Write Scala\n",
+ "expressions to determine if $\\texttt{-}$ has higher precedence than\n",
+ "$\\texttt{<<}$ or vice versa. To do, write an expression bound to\n",
+ "`e_no_parens` that uses no parentheses. Then, bind to `e_higher_-` the\n",
+ "expression that adds parentheses to the `e_no_parens` expression\n",
+ "corresponding to the case if $\\texttt{-}$ has higher precedence than\n",
+ "$\\texttt{<<}$, and bind to `e_higher_<<` the expression adds parentheses\n",
+ "corresponding to the other case.\n",
+ "\n",
+ "**Edit this cell:**"
+ ]
+ },
+ {
+ "cell_type": "code",
+ "execution_count": 28,
+ "id": "d8f3bfb9",
+ "metadata": {
+ "deletable": false,
+ "nbgrader": {
+ "cell_type": "code",
+ "checksum": "7390f29f3e77d88a7e7062e2075f457f",
+ "grade": false,
+ "grade_id": "detective_answer",
+ "locked": false,
+ "schema_version": 3,
+ "solution": true,
+ "task": false
+ }
+ },
+ "outputs": [
+ {
+ "data": {
+ "text/plain": [
+ "\u001b[36me_no_parens\u001b[39m: \u001b[32mInt\u001b[39m = \u001b[32m160\u001b[39m\n",
+ "\u001b[36me_higher_-\u001b[39m: \u001b[32mInt\u001b[39m = \u001b[32m160\u001b[39m\n",
+ "\u001b[36me_higher_<<\u001b[39m: \u001b[32mInt\u001b[39m = \u001b[32m-305\u001b[39m"
+ ]
+ },
+ "execution_count": 28,
+ "metadata": {},
+ "output_type": "execute_result"
+ }
+ ],
+ "source": [
+ "val e_no_parens = 15 - 10 << 5\n",
+ "\n",
+ "val e_higher_- = (15 - 10) << 5\n",
+ "\n",
+ "val e_higher_<< = 15 - (10 << 5)"
+ ]
+ },
+ {
+ "cell_type": "markdown",
+ "id": "5d01deab-3444-4389-a508-267ce2000ae1",
+ "metadata": {},
+ "source": [
+ "Make sure that you are checking for precedence and not for left or right\n",
+ "associativity.\n",
+ "\n",
+ "#### Assertions"
+ ]
+ },
+ {
+ "cell_type": "code",
+ "execution_count": 29,
+ "id": "4ea4f3fa",
+ "metadata": {
+ "deletable": false,
+ "editable": false,
+ "nbgrader": {
+ "cell_type": "code",
+ "checksum": "aca8f5794f0463134ecc5a6431a927fc",
+ "grade": true,
+ "grade_id": "detective_tests",
+ "locked": true,
+ "points": 5,
+ "schema_version": 3,
+ "solution": false,
+ "task": false
+ }
+ },
+ "outputs": [
+ {
+ "name": "stdout",
+ "output_type": "stream",
+ "text": [
+ "*** 🎉 Tests Passed (5 points) ***\n"
+ ]
+ }
+ ],
+ "source": [
+ "assert(e_no_parens == e_higher_- || e_no_parens == e_higher_<<)\n",
+ "assert(e_higher_- != e_higher_<<)\n",
+ "passed(5)"
+ ]
+ },
+ {
+ "cell_type": "markdown",
+ "id": "e37dcbd3-7a37-40ee-8c38-f5cf4efe04e2",
+ "metadata": {},
+ "source": [
+ "#### Explanation\n",
+ "\n",
+ "<span class=\"theorem-title\">**Exercise 5 (5 points)**</span> Explain how\n",
+ "you arrived at the relative precedence of $\\texttt{-}$ and $\\texttt{<<}$\n",
+ "based on the output that you saw in the Scala interpreter.\n",
+ "\n",
+ "**Edit this cell:**"
+ ]
+ },
+ {
+ "cell_type": "markdown",
+ "id": "9863319c-1d77-42fd-b2e7-736986916592",
+ "metadata": {
+ "deletable": false,
+ "nbgrader": {
+ "cell_type": "markdown",
+ "checksum": "14b2eda93b7713aad6035f40f587a675",
+ "grade": true,
+ "grade_id": "detective_explanation",
+ "locked": false,
+ "points": 5,
+ "schema_version": 3,
+ "solution": true,
+ "task": false
+ }
+ },
+ "source": [
+ "1. `e_no_parens`: When written without parentheses, it is up to Scala interpreter to determine precedence between subtraction and left shift.\n",
+ "2. `e_higher_-`: This expresion will have parentheses to explicitly show that subtraction has higher precedence than left shift.\n",
+ "3. `e_higher_<<`: This expression will have parentheses to explicitly show that left shift has high precedence than subtraction."
+ ]
+ },
+ {
+ "cell_type": "markdown",
+ "id": "6b00d249-372d-44df-9c44-aecd94bce0a4",
+ "metadata": {},
+ "source": [
+ "## Parse Trees\n",
+ "\n",
+ "Consider the following grammar:\n",
+ "\n",
+ "<span id=\"eq-ite-grammar\">$$\\begin{array}{rrrl}\n",
+ " \\text{expressions} & e& \\mathrel{::=}& x\\mid e\\;\\texttt{?}\\;e\\;\\texttt{:}\\;e \\\\\n",
+ " \\text{variables} & x& \\mathrel{::=}& \\texttt{a} \\mid\\texttt{b}\n",
+ "\\end{array} \\qquad(1)$$</span>\n",
+ "\n",
+ "Consider the following data type for representing parse trees:"
+ ]
+ },
+ {
+ "cell_type": "code",
+ "execution_count": 30,
+ "id": "e0ff9277",
+ "metadata": {
+ "deletable": false,
+ "editable": false,
+ "nbgrader": {
+ "cell_type": "code",
+ "checksum": "0cda8ee79fbaceb83e15d3e0117e877c",
+ "grade": false,
+ "grade_id": "parsetree_types",
+ "locked": true,
+ "schema_version": 3,
+ "solution": false,
+ "task": false
+ }
+ },
+ "outputs": [
+ {
+ "data": {
+ "text/plain": [
+ "defined \u001b[32mtrait\u001b[39m \u001b[36mParseTree\u001b[39m\n",
+ "defined \u001b[32mclass\u001b[39m \u001b[36mLeaf\u001b[39m\n",
+ "defined \u001b[32mclass\u001b[39m \u001b[36mNode\u001b[39m"
+ ]
+ },
+ "execution_count": 30,
+ "metadata": {},
+ "output_type": "execute_result"
+ }
+ ],
+ "source": [
+ "sealed trait ParseTree\n",
+ "case class Leaf(term: String) extends ParseTree\n",
+ "case class Node(nonterm: String, children: List[ParseTree]) extends ParseTree"
+ ]
+ },
+ {
+ "cell_type": "markdown",
+ "id": "9b5b444d-6085-494d-8015-cd9f56a46003",
+ "metadata": {},
+ "source": [
+ "Observe that a `ParseTree` is just an $n$-ary tree containing `String`s.\n",
+ "A `Leaf` is a terminal containing the lexemes (i.e., letters from the\n",
+ "alphabet), while a `Node` is represents a non-terminal with a `String`\n",
+ "for the name of the non-terminal a list of `children` `ParseTree`s.\n",
+ "\n",
+ "For example, the following are `ParseTree`s for this grammar\n",
+ "(<a href=\"#eq-ite-grammar\" class=\"quarto-xref\">Equation 1</a>):"
+ ]
+ },
+ {
+ "cell_type": "code",
+ "execution_count": 31,
+ "id": "aebbb3d1",
+ "metadata": {
+ "deletable": false,
+ "editable": false,
+ "nbgrader": {
+ "cell_type": "code",
+ "checksum": "bdee80feebaa951f42684815b22c642d",
+ "grade": false,
+ "grade_id": "parsetree_examples",
+ "locked": true,
+ "schema_version": 3,
+ "solution": false,
+ "task": false
+ }
+ },
+ "outputs": [
+ {
+ "data": {
+ "text/plain": [
+ "\u001b[36mp1\u001b[39m: \u001b[32mNode\u001b[39m = \u001b[33mNode\u001b[39m(nonterm = \u001b[32m\"x\"\u001b[39m, children = \u001b[33mList\u001b[39m(\u001b[33mLeaf\u001b[39m(term = \u001b[32m\"a\"\u001b[39m)))\n",
+ "\u001b[36mp2\u001b[39m: \u001b[32mNode\u001b[39m = \u001b[33mNode\u001b[39m(\n",
+ " nonterm = \u001b[32m\"e\"\u001b[39m,\n",
+ " children = \u001b[33mList\u001b[39m(\u001b[33mNode\u001b[39m(nonterm = \u001b[32m\"x\"\u001b[39m, children = \u001b[33mList\u001b[39m(\u001b[33mLeaf\u001b[39m(term = \u001b[32m\"a\"\u001b[39m))))\n",
+ ")"
+ ]
+ },
+ "execution_count": 31,
+ "metadata": {},
+ "output_type": "execute_result"
+ }
+ ],
+ "source": [
+ "val p1 = Node(\"x\", Leaf(\"a\") :: Nil)\n",
+ "val p2 = Node(\"e\", Node(\"x\", Leaf(\"a\") :: Nil) :: Nil)"
+ ]
+ },
+ {
+ "cell_type": "markdown",
+ "id": "0df2099c-8f51-4cb1-9ce3-77895f8c7d24",
+ "metadata": {},
+ "source": [
+ "We provide a function that pretty-prints a `ParseTree` for *this\n",
+ "grammar* (<a href=\"#eq-ite-grammar\" class=\"quarto-xref\">Equation 1</a>)."
+ ]
+ },
+ {
+ "cell_type": "code",
+ "execution_count": 32,
+ "id": "9c07f06e",
+ "metadata": {
+ "deletable": false,
+ "editable": false,
+ "nbgrader": {
+ "cell_type": "code",
+ "checksum": "d45ba978ac101ae4f1409cf49329b416",
+ "grade": false,
+ "grade_id": "parsetree_pretty",
+ "locked": true,
+ "schema_version": 3,
+ "solution": false,
+ "task": false
+ }
+ },
+ "outputs": [
+ {
+ "data": {
+ "text/plain": [
+ "defined \u001b[32mfunction\u001b[39m \u001b[36mpretty\u001b[39m\n",
+ "\u001b[36mres32_1\u001b[39m: \u001b[32mOption\u001b[39m[\u001b[32mString\u001b[39m] = \u001b[33mSome\u001b[39m(value = \u001b[32m\"a\"\u001b[39m)\n",
+ "\u001b[36mres32_2\u001b[39m: \u001b[32mOption\u001b[39m[\u001b[32mString\u001b[39m] = \u001b[33mSome\u001b[39m(value = \u001b[32m\"a\"\u001b[39m)"
+ ]
+ },
+ "execution_count": 32,
+ "metadata": {},
+ "output_type": "execute_result"
+ }
+ ],
+ "source": [
+ "def pretty(t: ParseTree): Option[String] = {\n",
+ " val alphabet = Set(\"a\", \"b\", \"?\", \":\")\n",
+ " t match {\n",
+ " // e ::= x\n",
+ " case Node(\"e\", (x @ Node(\"x\", _)) :: Nil) => pretty(x)\n",
+ " // e ::= e ? e : e\n",
+ " case Node(\"e\", (e1 @ Node(\"e\", _)) :: Leaf(\"?\") :: (e2 @ Node(\"e\", _)) :: Leaf(\":\") :: (e3 @ Node(\"e\", _)) :: Nil) =>\n",
+ " for { s1 <- pretty(e1); s2 <- pretty(e2); s3 <- pretty(e3) }\n",
+ " yield s\"$s1 ? $s2 : $s3\"\n",
+ " // x ::= a\n",
+ " case Node(\"x\", Leaf(\"a\") :: Nil) => Some(\"a\")\n",
+ " // x ::= b\n",
+ " case Node(\"x\", Leaf(\"b\") :: Nil) => Some(\"b\")\n",
+ " // failure\n",
+ " case _ => None\n",
+ " }\n",
+ "}\n",
+ "\n",
+ "pretty(p1)\n",
+ "pretty(p2)"
+ ]
+ },
+ {
+ "cell_type": "markdown",
+ "id": "825bfb1e-0618-42ff-8ce7-8a99ffafbe82",
+ "metadata": {},
+ "source": [
+ "Since it is possible to have `ParseTree`s that are not recognized by\n",
+ "this grammar, the `pretty` function has return type `Option[String]`.\n",
+ "Calling `pretty` on `ParseTree`s that are not in this grammar return\n",
+ "`None`:"
+ ]
+ },
+ {
+ "cell_type": "code",
+ "execution_count": 33,
+ "id": "f5778462",
+ "metadata": {
+ "deletable": false,
+ "editable": false,
+ "nbgrader": {
+ "cell_type": "code",
+ "checksum": "4e383bc90701275803c2d59457e1ffdb",
+ "grade": false,
+ "grade_id": "parsetree_pretty_none",
+ "locked": true,
+ "schema_version": 3,
+ "solution": false,
+ "task": false
+ }
+ },
+ "outputs": [
+ {
+ "data": {
+ "text/plain": [
+ "\u001b[36mres33_0\u001b[39m: \u001b[32mOption\u001b[39m[\u001b[32mString\u001b[39m] = \u001b[32mNone\u001b[39m\n",
+ "\u001b[36mres33_1\u001b[39m: \u001b[32mOption\u001b[39m[\u001b[32mString\u001b[39m] = \u001b[32mNone\u001b[39m\n",
+ "\u001b[36mres33_2\u001b[39m: \u001b[32mOption\u001b[39m[\u001b[32mString\u001b[39m] = \u001b[32mNone\u001b[39m"
+ ]
+ },
+ "execution_count": 33,
+ "metadata": {},
+ "output_type": "execute_result"
+ }
+ ],
+ "source": [
+ "pretty(Leaf(\"a\"))\n",
+ "pretty(Node(\"x\", Leaf(\"c\") :: Nil))\n",
+ "pretty(Node(\"y\", Leaf(\"a\") :: Nil))"
+ ]
+ },
+ {
+ "cell_type": "markdown",
+ "id": "f487d822-bbb6-48c4-bdd8-510cb0fbe6a3",
+ "metadata": {},
+ "source": [
+ "Note that the `pretty` function makes use of Scala’s `for`-`yield`\n",
+ "expressions, which you do not need to understand for this exercise.\n",
+ "\n",
+ "#### Exercise\n",
+ "\n",
+ "<span class=\"theorem-title\">**Exercise 6 (5 points)**</span> Give a\n",
+ "parse tree for the sentence in the grammar `a ? b : a`.\n",
+ "\n",
+ "**Edit this cell:**"
+ ]
+ },
+ {
+ "cell_type": "code",
+ "execution_count": 34,
+ "id": "e7d3515d",
+ "metadata": {
+ "deletable": false,
+ "nbgrader": {
+ "cell_type": "code",
+ "checksum": "f4a6165e9338422805ad7a5697a15209",
+ "grade": false,
+ "grade_id": "parse_tree_1_answer",
+ "locked": false,
+ "schema_version": 3,
+ "solution": true,
+ "task": false
+ }
+ },
+ "outputs": [
+ {
+ "data": {
+ "text/plain": [
+ "\u001b[36mparseTree1\u001b[39m: \u001b[32mParseTree\u001b[39m = \u001b[33mNode\u001b[39m(\n",
+ " nonterm = \u001b[32m\"e\"\u001b[39m,\n",
+ " children = \u001b[33mList\u001b[39m(\n",
+ " \u001b[33mNode\u001b[39m(\n",
+ " nonterm = \u001b[32m\"e\"\u001b[39m,\n",
+ " children = \u001b[33mList\u001b[39m(\u001b[33mNode\u001b[39m(nonterm = \u001b[32m\"x\"\u001b[39m, children = \u001b[33mList\u001b[39m(\u001b[33mLeaf\u001b[39m(term = \u001b[32m\"a\"\u001b[39m))))\n",
+ " ),\n",
+ " \u001b[33mLeaf\u001b[39m(term = \u001b[32m\"?\"\u001b[39m),\n",
+ " \u001b[33mNode\u001b[39m(\n",
+ " nonterm = \u001b[32m\"e\"\u001b[39m,\n",
+ " children = \u001b[33mList\u001b[39m(\u001b[33mNode\u001b[39m(nonterm = \u001b[32m\"x\"\u001b[39m, children = \u001b[33mList\u001b[39m(\u001b[33mLeaf\u001b[39m(term = \u001b[32m\"b\"\u001b[39m))))\n",
+ " ),\n",
+ " \u001b[33mLeaf\u001b[39m(term = \u001b[32m\":\"\u001b[39m),\n",
+ " \u001b[33mNode\u001b[39m(\n",
+ " nonterm = \u001b[32m\"e\"\u001b[39m,\n",
+ " children = \u001b[33mList\u001b[39m(\u001b[33mNode\u001b[39m(nonterm = \u001b[32m\"x\"\u001b[39m, children = \u001b[33mList\u001b[39m(\u001b[33mLeaf\u001b[39m(term = \u001b[32m\"a\"\u001b[39m))))\n",
+ " )\n",
+ " )\n",
+ ")"
+ ]
+ },
+ "execution_count": 34,
+ "metadata": {},
+ "output_type": "execute_result"
+ }
+ ],
+ "source": [
+ "val parseTree1: ParseTree =\n",
+ " Node(\"e\",\n",
+ " Node(\"e\", Node(\"x\", Leaf(\"a\") :: Nil) :: Nil)\n",
+ " :: Leaf(\"?\")\n",
+ " :: Node(\"e\", Node(\"x\", Leaf(\"b\") :: Nil) :: Nil)\n",
+ " :: Leaf(\":\")\n",
+ " :: Node(\"e\", Node(\"x\", Leaf(\"a\") :: Nil) :: Nil)\n",
+ " :: Nil\n",
+ " )"
+ ]
+ },
+ {
+ "cell_type": "markdown",
+ "id": "32bcc28b-473e-4af8-b5a4-125b3e98718c",
+ "metadata": {},
+ "source": [
+ "#### Assertion"
+ ]
+ },
+ {
+ "cell_type": "code",
+ "execution_count": 35,
+ "id": "60cc7566",
+ "metadata": {
+ "deletable": false,
+ "editable": false,
+ "nbgrader": {
+ "cell_type": "code",
+ "checksum": "235a3c106ebba2dd23cc05c34da836bf",
+ "grade": true,
+ "grade_id": "parsetree_tree_test",
+ "locked": true,
+ "points": 5,
+ "schema_version": 3,
+ "solution": false,
+ "task": false
+ }
+ },
+ "outputs": [
+ {
+ "name": "stdout",
+ "output_type": "stream",
+ "text": [
+ "*** 🎉 Tests Passed (5 points) ***\n"
+ ]
+ }
+ ],
+ "source": [
+ "assert(pretty(parseTree1) == Some(\"a ? b : a\"))\n",
+ "passed(5)"
+ ]
+ },
+ {
+ "cell_type": "markdown",
+ "id": "4127541f-87d2-49d5-8bae-045e20feac58",
+ "metadata": {},
+ "source": [
+ "#### Exercise\n",
+ "\n",
+ "<span class=\"theorem-title\">**Exercise 7 (10 points)**</span> Show that\n",
+ "this grammar\n",
+ "(<a href=\"#eq-ite-grammar\" class=\"quarto-xref\">Equation 1</a>) is\n",
+ "ambiguous by giving two parse trees for the sentence in the grammar\n",
+ "`a ? b : a ? b : a`.\n",
+ "\n",
+ "**Edit this cell:**"
+ ]
+ },
+ {
+ "cell_type": "code",
+ "execution_count": 36,
+ "id": "e0c46f00",
+ "metadata": {
+ "deletable": false,
+ "nbgrader": {
+ "cell_type": "code",
+ "checksum": "fec8c17457a1f15c9d4eb305bc5193b9",
+ "grade": false,
+ "grade_id": "parse_tree_ambiguous_answer",
+ "locked": false,
+ "schema_version": 3,
+ "solution": true,
+ "task": false
+ }
+ },
+ "outputs": [
+ {
+ "data": {
+ "text/plain": [
+ "\u001b[36mparseTree2\u001b[39m: \u001b[32mParseTree\u001b[39m = \u001b[33mNode\u001b[39m(\n",
+ " nonterm = \u001b[32m\"e\"\u001b[39m,\n",
+ " children = \u001b[33mList\u001b[39m(\n",
+ " \u001b[33mNode\u001b[39m(\n",
+ " nonterm = \u001b[32m\"e\"\u001b[39m,\n",
+ " children = \u001b[33mList\u001b[39m(\u001b[33mNode\u001b[39m(nonterm = \u001b[32m\"x\"\u001b[39m, children = \u001b[33mList\u001b[39m(\u001b[33mLeaf\u001b[39m(term = \u001b[32m\"a\"\u001b[39m))))\n",
+ " ),\n",
+ " \u001b[33mLeaf\u001b[39m(term = \u001b[32m\"?\"\u001b[39m),\n",
+ " \u001b[33mNode\u001b[39m(\n",
+ " nonterm = \u001b[32m\"e\"\u001b[39m,\n",
+ " children = \u001b[33mList\u001b[39m(\u001b[33mNode\u001b[39m(nonterm = \u001b[32m\"x\"\u001b[39m, children = \u001b[33mList\u001b[39m(\u001b[33mLeaf\u001b[39m(term = \u001b[32m\"b\"\u001b[39m))))\n",
+ " ),\n",
+ " \u001b[33mLeaf\u001b[39m(term = \u001b[32m\":\"\u001b[39m),\n",
+ " \u001b[33mNode\u001b[39m(\n",
+ " nonterm = \u001b[32m\"e\"\u001b[39m,\n",
+ " children = \u001b[33mList\u001b[39m(\n",
+ " \u001b[33mNode\u001b[39m(\n",
+ " nonterm = \u001b[32m\"e\"\u001b[39m,\n",
+ " children = \u001b[33mList\u001b[39m(\n",
+ " \u001b[33mNode\u001b[39m(nonterm = \u001b[32m\"x\"\u001b[39m, children = \u001b[33mList\u001b[39m(\u001b[33mLeaf\u001b[39m(term = \u001b[32m\"a\"\u001b[39m)))\n",
+ " )\n",
+ " ),\n",
+ " \u001b[33mLeaf\u001b[39m(term = \u001b[32m\"?\"\u001b[39m),\n",
+ " \u001b[33mNode\u001b[39m(\n",
+ " nonterm = \u001b[32m\"e\"\u001b[39m,\n",
+ " children = \u001b[33mList\u001b[39m(\n",
+ " \u001b[33mNode\u001b[39m(nonterm = \u001b[32m\"x\"\u001b[39m, children = \u001b[33mList\u001b[39m(\u001b[33mLeaf\u001b[39m(term = \u001b[32m\"b\"\u001b[39m)))\n",
+ " )\n",
+ " ),\n",
+ " \u001b[33mLeaf\u001b[39m(term = \u001b[32m\":\"\u001b[39m),\n",
+ " \u001b[33mNode\u001b[39m(\n",
+ " nonterm = \u001b[32m\"e\"\u001b[39m,\n",
+ " children = \u001b[33mList\u001b[39m(\n",
+ " \u001b[33mNode\u001b[39m(nonterm = \u001b[32m\"x\"\u001b[39m, children = \u001b[33mList\u001b[39m(\u001b[33mLeaf\u001b[39m(term = \u001b[32m\"a\"\u001b[39m)))\n",
+ " )\n",
+ " )\n",
+ " )\n",
+ " )\n",
+ " )\n",
+ ")\n",
+ "\u001b[36mparseTree3\u001b[39m: \u001b[32mParseTree\u001b[39m = \u001b[33mNode\u001b[39m(\n",
+ " nonterm = \u001b[32m\"e\"\u001b[39m,\n",
+ " children = \u001b[33mList\u001b[39m(\n",
+ " \u001b[33mNode\u001b[39m(\n",
+ " nonterm = \u001b[32m\"e\"\u001b[39m,\n",
+ " children = \u001b[33mList\u001b[39m(\n",
+ " \u001b[33mNode\u001b[39m(\n",
+ " nonterm = \u001b[32m\"e\"\u001b[39m,\n",
+ " children = \u001b[33mList\u001b[39m(\n",
+ " \u001b[33mNode\u001b[39m(nonterm = \u001b[32m\"x\"\u001b[39m, children = \u001b[33mList\u001b[39m(\u001b[33mLeaf\u001b[39m(term = \u001b[32m\"a\"\u001b[39m)))\n",
+ " )\n",
+ " ),\n",
+ " \u001b[33mLeaf\u001b[39m(term = \u001b[32m\"?\"\u001b[39m),\n",
+ " \u001b[33mNode\u001b[39m(\n",
+ " nonterm = \u001b[32m\"e\"\u001b[39m,\n",
+ " children = \u001b[33mList\u001b[39m(\n",
+ " \u001b[33mNode\u001b[39m(nonterm = \u001b[32m\"x\"\u001b[39m, children = \u001b[33mList\u001b[39m(\u001b[33mLeaf\u001b[39m(term = \u001b[32m\"b\"\u001b[39m)))\n",
+ " )\n",
+ " ),\n",
+ " \u001b[33mLeaf\u001b[39m(term = \u001b[32m\":\"\u001b[39m),\n",
+ " \u001b[33mNode\u001b[39m(\n",
+ " nonterm = \u001b[32m\"e\"\u001b[39m,\n",
+ " children = \u001b[33mList\u001b[39m(\n",
+ " \u001b[33mNode\u001b[39m(nonterm = \u001b[32m\"x\"\u001b[39m, children = \u001b[33mList\u001b[39m(\u001b[33mLeaf\u001b[39m(term = \u001b[32m\"a\"\u001b[39m)))\n",
+ " )\n",
+ " )\n",
+ " )\n",
+ " ),\n",
+ " \u001b[33mLeaf\u001b[39m(term = \u001b[32m\"?\"\u001b[39m),\n",
+ " \u001b[33mNode\u001b[39m(\n",
+ " nonterm = \u001b[32m\"e\"\u001b[39m,\n",
+ " children = \u001b[33mList\u001b[39m(\u001b[33mNode\u001b[39m(nonterm = \u001b[32m\"x\"\u001b[39m, children = \u001b[33mList\u001b[39m(\u001b[33mLeaf\u001b[39m(term = \u001b[32m\"b\"\u001b[39m))))\n",
+ " ),\n",
+ " \u001b[33mLeaf\u001b[39m(term = \u001b[32m\":\"\u001b[39m),\n",
+ " \u001b[33mNode\u001b[39m(\n",
+ " nonterm = \u001b[32m\"e\"\u001b[39m,\n",
+ " children = \u001b[33mList\u001b[39m(\u001b[33mNode\u001b[39m(nonterm = \u001b[32m\"x\"\u001b[39m, children = \u001b[33mList\u001b[39m(\u001b[33mLeaf\u001b[39m(term = \u001b[32m\"a\"\u001b[39m))))\n",
+ " )\n",
+ " )\n",
+ ")"
+ ]
+ },
+ "execution_count": 36,
+ "metadata": {},
+ "output_type": "execute_result"
+ }
+ ],
+ "source": [
+ "// a ? b : (a ? b : a)\n",
+ "val parseTree2: ParseTree =\n",
+ " Node(\"e\",\n",
+ " Node(\"e\", Node(\"x\", Leaf(\"a\") :: Nil) :: Nil)\n",
+ " :: Leaf(\"?\")\n",
+ " :: Node(\"e\", Node(\"x\", Leaf(\"b\") :: Nil) :: Nil)\n",
+ " :: Leaf(\":\")\n",
+ " :: Node(\"e\",\n",
+ " Node(\"e\", Node(\"x\", Leaf(\"a\") :: Nil) :: Nil)\n",
+ " :: Leaf(\"?\")\n",
+ " :: Node(\"e\", Node(\"x\", Leaf(\"b\") :: Nil) :: Nil)\n",
+ " :: Leaf(\":\")\n",
+ " :: Node(\"e\", Node(\"x\", Leaf(\"a\") :: Nil) :: Nil)\n",
+ " :: Nil)\n",
+ " :: Nil\n",
+ " )\n",
+ "\n",
+ "// (a ? b : a) ? b : a\n",
+ "val parseTree3: ParseTree =\n",
+ " Node(\"e\",\n",
+ " Node(\"e\",\n",
+ " Node(\"e\", Node(\"x\", Leaf(\"a\") :: Nil) :: Nil)\n",
+ " :: Leaf(\"?\")\n",
+ " :: Node(\"e\", Node(\"x\", Leaf(\"b\") :: Nil) :: Nil)\n",
+ " :: Leaf(\":\")\n",
+ " :: Node(\"e\", Node(\"x\", Leaf(\"a\") :: Nil) :: Nil)\n",
+ " :: Nil)\n",
+ " :: Leaf(\"?\")\n",
+ " :: Node(\"e\", Node(\"x\", Leaf(\"b\") :: Nil) :: Nil)\n",
+ " :: Leaf(\":\")\n",
+ " :: Node(\"e\", Node(\"x\", Leaf(\"a\") :: Nil) :: Nil)\n",
+ " :: Nil\n",
+ " )"
+ ]
+ },
+ {
+ "cell_type": "code",
+ "execution_count": 37,
+ "id": "789ba753",
+ "metadata": {},
+ "outputs": [
+ {
+ "data": {
+ "text/plain": [
+ "\u001b[36mres37_0\u001b[39m: \u001b[32mOption\u001b[39m[\u001b[32mString\u001b[39m] = \u001b[33mSome\u001b[39m(value = \u001b[32m\"a ? b : a ? b : a\"\u001b[39m)\n",
+ "\u001b[36mres37_1\u001b[39m: \u001b[32mOption\u001b[39m[\u001b[32mString\u001b[39m] = \u001b[33mSome\u001b[39m(value = \u001b[32m\"a ? b : a ? b : a\"\u001b[39m)"
+ ]
+ },
+ "execution_count": 37,
+ "metadata": {},
+ "output_type": "execute_result"
+ }
+ ],
+ "source": [
+ "pretty(parseTree2)\n",
+ "pretty(parseTree3)"
+ ]
+ },
+ {
+ "cell_type": "markdown",
+ "id": "b6096f88-0de5-4826-9599-d9c86f2b365e",
+ "metadata": {},
+ "source": [
+ "#### Assertions"
+ ]
+ },
+ {
+ "cell_type": "code",
+ "execution_count": 38,
+ "id": "72197a91",
+ "metadata": {
+ "deletable": false,
+ "editable": false,
+ "nbgrader": {
+ "cell_type": "code",
+ "checksum": "1072c2352550ba63657d754309a8a368",
+ "grade": true,
+ "grade_id": "parsetree_ambiguous_test_1",
+ "locked": true,
+ "points": 5,
+ "schema_version": 3,
+ "solution": false,
+ "task": false
+ }
+ },
+ "outputs": [
+ {
+ "name": "stdout",
+ "output_type": "stream",
+ "text": [
+ "*** 🎉 Tests Passed (5 points) ***\n"
+ ]
+ }
+ ],
+ "source": [
+ "assert(parseTree2 != parseTree3)\n",
+ "assert(pretty(parseTree2).isDefined)\n",
+ "assert(pretty(parseTree3).isDefined)\n",
+ "passed(5)"
+ ]
+ },
+ {
+ "cell_type": "code",
+ "execution_count": 39,
+ "id": "084fbb3b",
+ "metadata": {
+ "deletable": false,
+ "editable": false,
+ "nbgrader": {
+ "cell_type": "code",
+ "checksum": "1843616ac2befc8ef5c950df69e798aa",
+ "grade": true,
+ "grade_id": "parsetree_ambiguous_test_2",
+ "locked": true,
+ "points": 5,
+ "schema_version": 3,
+ "solution": false,
+ "task": false
+ }
+ },
+ "outputs": [
+ {
+ "name": "stdout",
+ "output_type": "stream",
+ "text": [
+ "*** 🎉 Tests Passed (5 points) ***\n"
+ ]
+ }
+ ],
+ "source": [
+ "assert(pretty(parseTree2) == Some(\"a ? b : a ? b : a\"))\n",
+ "assert(pretty(parseTree3) == Some(\"a ? b : a ? b : a\"))\n",
+ "passed(5)"
+ ]
+ },
+ {
+ "cell_type": "markdown",
+ "id": "558f8a4c-7af1-4eaa-bd10-99dae585dc75",
+ "metadata": {},
+ "source": [
+ "## Defining Grammars\n",
+ "\n",
+ "In this question, we define a BNF grammar for *floating-point numbers*\n",
+ "that are made up of a fraction (e.g., `5.6` or `3.123` or `-2.5`)\n",
+ "followed by an optional exponent (e.g., `E10` or `E-10`).\n",
+ "\n",
+ "More precisely for this exercise, our floating-point numbers\n",
+ "\n",
+ "- [x] must have a decimal point,\n",
+ "- [x] do not have leading zeros,\n",
+ "- [x] can have any number of trailing zeros,\n",
+ "- [x] non-zero exponents if it exists,\n",
+ "- [x] must have non-zero fraction to have an exponent, and\n",
+ "- [x] cannot have a ‘-’ in front of a zero number; also,\n",
+ "- [x] the exponent cannot have leading zeros.\n",
+ "\n",
+ "The exponent, if it exists, is the letter `E` followed by an integer.\n",
+ "For example, the following are floating-point numbers: `0.0`, `3.5E3`,\n",
+ "`3.123E30`, `-2.5E2`, `-2.5E-2`, `3.50`, and `3.01E2`.\n",
+ "\n",
+ "The following are examples of strings that are *not* floating-point\n",
+ "numbers by our definition: `0`, `-0.0`, `3.E3`, `E3`, `3.0E4.5`, and\n",
+ "`4E4`.\n",
+ "\n",
+ "For this exercise, let us assume that the tokens are characters in the\n",
+ "following alphabet $\\Sigma$:\n",
+ "\n",
+ "$\\Sigma \\stackrel{\\text{\\tiny def}}{=}\\{$ `0`, `1`, `2`, `3`, `4`, `5`,\n",
+ "`6`, `7`, `8`, `9`, `E`, `-`, `.` $\\}$\n",
+ "\n",
+ "<span class=\"theorem-title\">**Exercise 8 (10 points)**</span> Translate\n",
+ "a grammar into a parser `FloatParser.float: Parser[String]` using the\n",
+ "Scala Parsing Combinator Library that recognizes the language of\n",
+ "floating-point numbers described above. Since we do not care about the\n",
+ "correctness of the grammar, we let parse result simply be the input\n",
+ "string.\n",
+ "\n",
+ "We suggest that you first use the scratch cell below to give a grammar\n",
+ "in BNF notation. Your grammar should be completely defined using the\n",
+ "alphabet above as the terminals (i.e., it should not count on a\n",
+ "non-terminal that it does not itself define)."
+ ]
+ },
+ {
+ "cell_type": "markdown",
+ "id": "8c1ba46e-527e-4664-a32f-80e800bbfe7f",
+ "metadata": {},
+ "source": [
+ "SCRATCH CELL"
+ ]
+ },
+ {
+ "cell_type": "markdown",
+ "id": "a15d3aab-2045-4565-87bd-46ce02998967",
+ "metadata": {},
+ "source": [
+ "**Edit this cell:**"
+ ]
+ },
+ {
+ "cell_type": "code",
+ "execution_count": 40,
+ "id": "1355139a",
+ "metadata": {
+ "deletable": false,
+ "nbgrader": {
+ "cell_type": "code",
+ "checksum": "2c18dc9a164093ed57559bc0bee3e557",
+ "grade": false,
+ "grade_id": "floatparser_answer",
+ "locked": false,
+ "schema_version": 3,
+ "solution": true,
+ "task": false
+ }
+ },
+ "outputs": [
+ {
+ "data": {
+ "text/plain": [
+ "defined \u001b[32mobject\u001b[39m \u001b[36mFloatParser\u001b[39m"
+ ]
+ },
+ "execution_count": 40,
+ "metadata": {},
+ "output_type": "execute_result"
+ }
+ ],
+ "source": [
+ "object FloatParser extends scala.util.parsing.combinator.RegexParsers {\n",
+ " val concat2: String ~ String => String = { case s1 ~ s2 => s1 + s2 }\n",
+ " val concat3: String ~ String ~ String => String = { case s1 ~ s2 ~ s3 => s1 + s2 + s3 }\n",
+ " val concat4: String ~ String ~ String ~ String => String = { case s1 ~ s2 ~ s3 ~ s4 => s1 + s2 + s3 + s4 }\n",
+ " val concat5: String ~ String ~ String ~ String ~ String => String = { case s1 ~ s2 ~ s3 ~ s4 ~ s5 => s1 + s2 + s3 + s4 + s5 }\n",
+ "\n",
+ " def float: Parser[String] =\n",
+ " fraction ~ exponent ^^ concat2 |\n",
+ " sign ~ fraction ~ exponent ^^ concat3 |\n",
+ " fraction |\n",
+ " success(\"\")\n",
+ "\n",
+ " def fraction: Parser[String] =\n",
+ " anyOneToNine ~ \".\" ~ oneOrMoreDigits ^^ concat3 |\n",
+ " \"0\" ~ \".\" ~ zeroOrMoreDigits ^^ concat3\n",
+ "\n",
+ " def oneOrMoreDigits: Parser[String] =\n",
+ " digit ~ zeroOrMoreDigits ^^ concat2\n",
+ "\n",
+ " def exponent: Parser[String] =\n",
+ " \"E\" ~ sign ~ anyOneToNine ~ zeroOrMoreDigits ^^ concat4 |\n",
+ " \"E\" ~ anyOneToNine ~ zeroOrMoreDigits ^^ concat3\n",
+ " success(\"\")\n",
+ "\n",
+ " def zeroOrMoreDigits: Parser[String] =\n",
+ " digit ~ zeroOrMoreDigits ^^ concat2 |\n",
+ " success(\"\")\n",
+ "\n",
+ " def digit: Parser[String] = \"0\" | anyOneToNine\n",
+ "\n",
+ " def anyOneToNine: Parser[String] = \"1\" | \"2\" | \"3\" | \"4\" | \"5\" | \"6\" | \"7\" | \"8\" | \"9\"\n",
+ "\n",
+ " def sign: Parser[String] =\n",
+ " \"-\" |\n",
+ " success(\"\")\n",
+ "\n",
+ " def parse(str: String): Option[String] = parseAll(float, str) match {\n",
+ " case Success(str, _) => Some(str)\n",
+ " case Failure(_, _) | Error(_, _) => None\n",
+ " }\n",
+ "}"
+ ]
+ },
+ {
+ "cell_type": "markdown",
+ "id": "327ebd79-bbe0-4763-a6c4-b71a860f3a3a",
+ "metadata": {},
+ "source": [
+ "#### Notes\n",
+ "\n",
+ "- The `success[A](a: A): Parser[A]` method corresponds to an\n",
+ " $\\varepsilon$ production in BNF. It returns a parser that is\n",
+ " successful without consuming any input yielding the parse result\n",
+ " `a`. If you use it in your parser, make sure it is the *last*\n",
+ " production for the non-terminal.\n",
+ "- We provide some helper functions\n",
+ " `concat2: String ~ String => String`,\n",
+ " `concat3: String ~ String ~ String => String`, etc. that simply\n",
+ " concatenate their input strings together. These helper functions are\n",
+ " the only semantic actions you need.\n",
+ "- We have provided some basic parsers `sign`, `anyOneToNine`, `digit`,\n",
+ " `zeroOrMoreDigits` that you may use if you like.\n",
+ "- You may edit the `parse` interface function that we have provided to\n",
+ " start from a different non-terminal while you’re developing, but\n",
+ " make sure it is `float` in the end and that your starting\n",
+ " non-terminal is `float`. Alternatively, you may add additional such\n",
+ " interface functions with a different name for your testing.\n",
+ "\n",
+ "#### Tests"
+ ]
+ },
+ {
+ "cell_type": "code",
+ "execution_count": 41,
+ "id": "b1824177",
+ "metadata": {
+ "deletable": false,
+ "editable": false,
+ "nbgrader": {
+ "cell_type": "code",
+ "checksum": "66ebc679977f9e9d6d9450c594637910",
+ "grade": true,
+ "grade_id": "floatparser_tests",
+ "locked": true,
+ "points": 10,
+ "schema_version": 3,
+ "solution": false,
+ "task": false
+ }
+ },
+ "outputs": [
+ {
+ "name": "stdout",
+ "output_type": "stream",
+ "text": [
+ "\u001b[36mRun starting. Expected test count is: 13\u001b[0m\n",
+ "\u001b[32mcmd41$Helper$$anon$1:\u001b[0m\n",
+ "\u001b[32mFloatParser\u001b[0m\n",
+ "\u001b[32m- should parse 0.0\u001b[0m\n",
+ "\u001b[32m- should parse 3.5E3\u001b[0m\n",
+ "\u001b[32m- should parse 3.123E30\u001b[0m\n",
+ "\u001b[32m- should parse -2.5E2\u001b[0m\n",
+ "\u001b[32m- should parse -2.5E-2\u001b[0m\n",
+ "\u001b[32m- should parse 3.50\u001b[0m\n",
+ "\u001b[32m- should parse 3.01E2\u001b[0m\n",
+ "\u001b[32m- should fail to parse 0\u001b[0m\n",
+ "\u001b[32m- should fail to parse -0.0\u001b[0m\n",
+ "\u001b[32m- should fail to parse 3.E3\u001b[0m\n",
+ "\u001b[32m- should fail to parse E3\u001b[0m\n",
+ "\u001b[32m- should fail to parse 3.0E4.5\u001b[0m\n",
+ "\u001b[32m- should fail to parse 4E4\u001b[0m\n",
+ "\u001b[36mRun completed in 15 milliseconds.\u001b[0m\n",
+ "\u001b[36mTotal number of tests run: 13\u001b[0m\n",
+ "\u001b[36mSuites: completed 1, aborted 0\u001b[0m\n",
+ "\u001b[36mTests: succeeded 13, failed 0, canceled 0, ignored 0, pending 0\u001b[0m\n",
+ "\u001b[32mAll tests passed.\u001b[0m\n",
+ "*** 🎉 Tests Passed (10 points) ***\n"
+ ]
+ }
+ ],
+ "source": [
+ "test(new AnyFlatSpec {\n",
+ " val tests_positive = List(\n",
+ " \"0.0\",\n",
+ " \"3.5E3\",\n",
+ " \"3.123E30\",\n",
+ " \"-2.5E2\",\n",
+ " \"-2.5E-2\",\n",
+ " \"3.50\",\n",
+ " \"3.01E2\"\n",
+ " )\n",
+ "\n",
+ " behavior of \"FloatParser\"\n",
+ "\n",
+ " for (t <- tests_positive) {\n",
+ " it should s\"parse $t\" in {\n",
+ " assertResult( Some(t) ) {\n",
+ " FloatParser.parse(t)\n",
+ " }\n",
+ " }\n",
+ " }\n",
+ "\n",
+ " val tests_negative = List(\n",
+ " \"0\",\n",
+ " \"-0.0\",\n",
+ " \"3.E3\",\n",
+ " \"E3\",\n",
+ " \"3.0E4.5\",\n",
+ " \"4E4\"\n",
+ " )\n",
+ "\n",
+ " for (t <- tests_negative) {\n",
+ " it should s\"fail to parse $t\" in {\n",
+ " assertResult( None ) {\n",
+ " FloatParser.parse(t)\n",
+ " }\n",
+ " }\n",
+ " }\n",
+ "}, 10)"
+ ]
+ }
+ ],
+ "metadata": {
+ "kernelspec": {
+ "display_name": "Scala",
+ "language": "scala",
+ "name": "scala"
+ },
+ "language_info": {
+ "codemirror_mode": "text/x-scala",
+ "file_extension": ".sc",
+ "mimetype": "text/x-scala",
+ "name": "scala",
+ "nbconvert_exporter": "script",
+ "version": "2.13.14"
+ }
+ },
+ "nbformat": 4,
+ "nbformat_minor": 5
+}