diff options
Diffstat (limited to 'abstract-syntax-exercise.ipynb')
-rw-r--r-- | abstract-syntax-exercise.ipynb | 1657 |
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 +} |