{"id":6202,"date":"2026-10-16T00:55:24","date_gmt":"2026-10-16T00:55:24","guid":{"rendered":"https:\/\/danielschlegel.org\/wp\/?page_id=6202"},"modified":"2026-10-16T00:55:26","modified_gmt":"2026-10-16T00:55:26","slug":"project-3-logical-expression-simplifier","status":"publish","type":"page","link":"https:\/\/danielschlegel.org\/wp\/teaching\/csc344-fall-2026\/project-3-logical-expression-simplifier\/","title":{"rendered":"Project 3 &#8211; Logical Expression Simplifier"},"content":{"rendered":"\n<h2 class=\"wp-block-heading\">Microproject<\/h2>\n\n\n\n<p class=\"wp-block-paragraph\">Begin with the code from the <a href=\"https:\/\/danielschlegel.org\/wp\/teaching\/recursive-descent-parser-in-scala\/\">class example<\/a> on recursive descent parsers in Scala. That program implements a parser for the following grammar:<\/p>\n\n\n\n<pre>S -: E$\nE -: Terminal E2\nE2 -: + E\nE2 -: NIL\nTerminal -: Const\nTerminal -: Var  <\/pre>\n\n\n\n<p class=\"wp-block-paragraph\">It also implements evaluation for parse trees in that grammar. Modify the program to implement the following, modified grammar:<\/p>\n\n\n\n<pre>S -: E$\nE -: T E2\nE2 -: + E\nE2 -: NIL\nT -: Terminal T2\nT2 -: * T\nT2 -: NIL\nTerminal -: Const\nTerminal -: Var \n<\/pre>\n\n\n\n<p class=\"wp-block-paragraph\">Be sure the parser works as well as the evaluation component. You will need to modify the case classes, the parser, and the evaluation.<\/p>\n\n\n\n<h2 class=\"wp-block-heading\">Main Project<\/h2>\n\n\n\n<p class=\"wp-block-paragraph\">Write a Scala program which reads in logical expressions, simplifies then, and reports the result. Your program will read in logical expressions in C\/Java\/Scala format then parse them, using a recursive descent parser, into a tree representation using case classes. Only logical and (&amp;&amp;), or (||), and not (!) are supported. Parentheses may be used as part of the expressions. Precedence is captured by the below BNF-style grammar:<\/p>\n\n\n\n<pre>S := E $\nE := T '||' E | T\nT := F '&amp;&amp;' T | F\nF := '!' A | A\nA := '(' E ')' | C\nC := 'true' | 'false' | c\nc := any alphabetic character<\/pre>\n\n\n\n<p class=\"wp-block-paragraph\">The below grammar is equivalent but easier to parse since it doesn&#8217;t require looking ahead.<\/p>\n\n\n\n<pre class=\"wp-block-code\"><code>S  -&gt; E $\n\nE  -&gt; T E2\nE2 -&gt; '||' E\nE2 -&gt; NIL\n\nT  -&gt; F T2\nT2 -&gt; '&amp;&amp;' T\nT2 -&gt; NIL\n\nF  -&gt; '!' A\nF  -&gt; A\n\nA  -&gt; '(' E ')'\nA  -&gt; C\n\nC  -&gt; 'true'\nC  -&gt; 'false'\nC  -&gt; c\n\nc  -&gt; any alphabetic character<\/code><\/pre>\n\n\n\n<p class=\"wp-block-paragraph\">Once you have built the parse tree, you should simplify the given expression. Note that &#8216;and&#8217; and &#8216;or&#8217; expressions will always take two arguments, and &#8216;not&#8217; will always take one. Recursively traverse your tree to implement the following simplification rules:<\/p>\n\n\n\n<figure class=\"wp-block-table\"><table class=\"has-fixed-layout\"><thead><tr><th>Category<\/th><th>Rules<\/th><\/tr><\/thead><tbody><tr><td>Negation of constants<\/td><td><code>!true<\/code> \u21d2 <code>false<\/code>, <code>!false<\/code> \u21d2 <code>true<\/code><\/td><\/tr><tr><td>Double negation<\/td><td><code>!(!e)<\/code> \u21d2 <code>e<\/code><\/td><\/tr><tr><td>And with <code>true<\/code><\/td><td><code>true &amp;&amp; e<\/code> \u21d2 <code>e<\/code>, <code>e &amp;&amp; true<\/code> \u21d2 <code>e<\/code><\/td><\/tr><tr><td>And with <code>false<\/code><\/td><td><code>false &amp;&amp; e<\/code> \u21d2 <code>false<\/code>, <code>e &amp;&amp; false<\/code> \u21d2 <code>false<\/code><\/td><\/tr><tr><td>Or with <code>false<\/code><\/td><td><code>false || e<\/code> \u21d2 <code>e<\/code>, <code>e || false<\/code> \u21d2 <code>e<\/code><\/td><\/tr><tr><td>Or with <code>true<\/code><\/td><td><code>true || e<\/code> \u21d2 <code>true<\/code>, <code>e || true<\/code> \u21d2 <code>true<\/code><\/td><\/tr><\/tbody><\/table><\/figure>\n\n\n\n<p class=\"wp-block-paragraph\">Once the simplification has been performed, print out the resulting expression. Again, use C\/Java\/Scala form. <\/p>\n\n\n\n<p class=\"wp-block-paragraph\">Your program, when run, should ask the user for an input expression to simplify and print the output. It should continue doing so until the user terminates the program.&nbsp;<\/p>\n\n\n\n<p class=\"wp-block-paragraph\">Example run:&nbsp;<\/p>\n\n\n\n<pre>expression? (a||!b)&amp;&amp;c\nresult:&nbsp;(a||!b)&amp;&amp;c\nexpression? (a||!b)&amp;&amp;false\nresult: false\nexpression? (a||!true)&amp;&amp;c\nresult: a&amp;&amp;c\nexpression? (a||!false)&amp;&amp;c\nresult: c<\/pre>\n\n\n\n<h2 class=\"wp-block-heading\">Bootstrap<\/h2>\n\n\n\n<p class=\"wp-block-paragraph\">You are welcome to use case classes matching the grammar as we have done in class. One possible starter for those could be: <\/p>\n\n\n\n<pre class=\"wp-block-code\"><code>sealed trait Stmt\n\nfinal case class S(e: E) extends Stmt\n\nfinal case class E(left: T, right: Option&#91;E2]) extends Stmt\nfinal case class E2(right: E) extends Stmt\n\nfinal case class T(left: F, right: Option&#91;T2]) extends Stmt\nfinal case class T2(right: T) extends Stmt\n\nsealed trait F extends Stmt\nfinal case class NotF(a: A) extends F\nfinal case class AFactor(a: A) extends F\n\nsealed trait A extends Stmt\nfinal case class Parens(e: E) extends A\nfinal case class CAtom(c: C) extends A\n\nsealed trait C extends Stmt\ncase object TrueConst extends C\ncase object FalseConst extends C\nfinal case class Var(name: String) extends C<\/code><\/pre>\n\n\n\n<p class=\"wp-block-paragraph\">Other case classes could be used, but you&#8217;ll need to be prepared to defend your choice, and show how your program deals with the various cases. (This is a fun thing to explore, but only if you&#8217;re comfortable with it!)<br><br><\/p>\n","protected":false},"excerpt":{"rendered":"<p class=\"lead\">Microproject Begin with the code from the class example on recursive descent parsers in Scala. That program implements a parser for the following grammar: S -: E$ E -: Terminal E2 E2 -: + E E2 -: NIL Terminal -: Const Terminal -: Var It also implements evaluation for parse trees in that grammar. Modify the program to implement the&hellip;<\/p>\n<p class=\"more-link-p\"><a class=\"btn btn-warning\" href=\"https:\/\/danielschlegel.org\/wp\/teaching\/csc344-fall-2026\/project-3-logical-expression-simplifier\/\">Read more<\/a><\/p>\n","protected":false},"author":1,"featured_media":0,"parent":6032,"menu_order":0,"comment_status":"closed","ping_status":"closed","template":"","meta":{"_editorskit_title_hidden":false,"_editorskit_reading_time":0,"_editorskit_is_block_options_detached":false,"_editorskit_block_options_position":"{}","footnotes":""},"class_list":["post-6202","page","type-page","status-publish","hentry"],"yoast_head":"<!-- This site is optimized with the Yoast SEO plugin v28.8 - https:\/\/yoast.com\/product\/yoast-seo-wordpress\/ -->\n<title>Project 3 - Logical Expression Simplifier - Daniel R. Schlegel<\/title>\n<meta name=\"robots\" content=\"index, follow, max-snippet:-1, max-image-preview:large, max-video-preview:-1\" \/>\n<link rel=\"canonical\" href=\"https:\/\/danielschlegel.org\/wp\/teaching\/csc344-fall-2026\/project-3-logical-expression-simplifier\/\" \/>\n<meta property=\"og:locale\" content=\"en_US\" \/>\n<meta property=\"og:type\" content=\"article\" \/>\n<meta property=\"og:title\" content=\"Project 3 - Logical Expression Simplifier - Daniel R. Schlegel\" \/>\n<meta property=\"og:description\" content=\"Microproject Begin with the code from the class example on recursive descent parsers in Scala. That program implements a parser for the following grammar: S -: E$ E -: Terminal E2 E2 -: + E E2 -: NIL Terminal -: Const Terminal -: Var It also implements evaluation for parse trees in that grammar. Modify the program to implement the&hellip;Read more\" \/>\n<meta property=\"og:url\" content=\"https:\/\/danielschlegel.org\/wp\/teaching\/csc344-fall-2026\/project-3-logical-expression-simplifier\/\" \/>\n<meta property=\"og:site_name\" content=\"Daniel R. Schlegel\" \/>\n<meta property=\"article:modified_time\" content=\"2026-10-16T00:55:26+00:00\" \/>\n<meta name=\"twitter:card\" content=\"summary_large_image\" \/>\n<meta name=\"twitter:label1\" content=\"Est. reading time\" \/>\n\t<meta name=\"twitter:data1\" content=\"2 minutes\" \/>\n<script type=\"application\/ld+json\" class=\"yoast-schema-graph\">{\"@context\":\"https:\\\/\\\/schema.org\",\"@graph\":[{\"@type\":\"WebPage\",\"@id\":\"https:\\\/\\\/danielschlegel.org\\\/wp\\\/teaching\\\/csc344-fall-2026\\\/project-3-logical-expression-simplifier\\\/\",\"url\":\"https:\\\/\\\/danielschlegel.org\\\/wp\\\/teaching\\\/csc344-fall-2026\\\/project-3-logical-expression-simplifier\\\/\",\"name\":\"Project 3 - Logical Expression Simplifier - Daniel R. Schlegel\",\"isPartOf\":{\"@id\":\"https:\\\/\\\/danielschlegel.org\\\/wp\\\/#website\"},\"datePublished\":\"2026-10-16T00:55:24+00:00\",\"dateModified\":\"2026-10-16T00:55:26+00:00\",\"breadcrumb\":{\"@id\":\"https:\\\/\\\/danielschlegel.org\\\/wp\\\/teaching\\\/csc344-fall-2026\\\/project-3-logical-expression-simplifier\\\/#breadcrumb\"},\"inLanguage\":\"en-US\",\"potentialAction\":[{\"@type\":\"ReadAction\",\"target\":[\"https:\\\/\\\/danielschlegel.org\\\/wp\\\/teaching\\\/csc344-fall-2026\\\/project-3-logical-expression-simplifier\\\/\"]}]},{\"@type\":\"BreadcrumbList\",\"@id\":\"https:\\\/\\\/danielschlegel.org\\\/wp\\\/teaching\\\/csc344-fall-2026\\\/project-3-logical-expression-simplifier\\\/#breadcrumb\",\"itemListElement\":[{\"@type\":\"ListItem\",\"position\":1,\"name\":\"Home\",\"item\":\"https:\\\/\\\/danielschlegel.org\\\/wp\\\/\"},{\"@type\":\"ListItem\",\"position\":2,\"name\":\"Teaching\",\"item\":\"https:\\\/\\\/danielschlegel.org\\\/wp\\\/teaching\\\/\"},{\"@type\":\"ListItem\",\"position\":3,\"name\":\"CSC344 &#8211; Fall 2026\",\"item\":\"https:\\\/\\\/danielschlegel.org\\\/wp\\\/teaching\\\/csc344-fall-2026\\\/\"},{\"@type\":\"ListItem\",\"position\":4,\"name\":\"Project 3 &#8211; Logical Expression Simplifier\"}]},{\"@type\":\"WebSite\",\"@id\":\"https:\\\/\\\/danielschlegel.org\\\/wp\\\/#website\",\"url\":\"https:\\\/\\\/danielschlegel.org\\\/wp\\\/\",\"name\":\"Daniel R. Schlegel\",\"description\":\"\",\"potentialAction\":[{\"@type\":\"SearchAction\",\"target\":{\"@type\":\"EntryPoint\",\"urlTemplate\":\"https:\\\/\\\/danielschlegel.org\\\/wp\\\/?s={search_term_string}\"},\"query-input\":{\"@type\":\"PropertyValueSpecification\",\"valueRequired\":true,\"valueName\":\"search_term_string\"}}],\"inLanguage\":\"en-US\"}]}<\/script>\n<!-- \/ Yoast SEO plugin. -->","yoast_head_json":{"title":"Project 3 - Logical Expression Simplifier - Daniel R. Schlegel","robots":{"index":"index","follow":"follow","max-snippet":"max-snippet:-1","max-image-preview":"max-image-preview:large","max-video-preview":"max-video-preview:-1"},"canonical":"https:\/\/danielschlegel.org\/wp\/teaching\/csc344-fall-2026\/project-3-logical-expression-simplifier\/","og_locale":"en_US","og_type":"article","og_title":"Project 3 - Logical Expression Simplifier - Daniel R. Schlegel","og_description":"Microproject Begin with the code from the class example on recursive descent parsers in Scala. That program implements a parser for the following grammar: S -: E$ E -: Terminal E2 E2 -: + E E2 -: NIL Terminal -: Const Terminal -: Var It also implements evaluation for parse trees in that grammar. Modify the program to implement the&hellip;Read more","og_url":"https:\/\/danielschlegel.org\/wp\/teaching\/csc344-fall-2026\/project-3-logical-expression-simplifier\/","og_site_name":"Daniel R. Schlegel","article_modified_time":"2026-10-16T00:55:26+00:00","twitter_card":"summary_large_image","twitter_misc":{"Est. reading time":"2 minutes"},"schema":{"@context":"https:\/\/schema.org","@graph":[{"@type":"WebPage","@id":"https:\/\/danielschlegel.org\/wp\/teaching\/csc344-fall-2026\/project-3-logical-expression-simplifier\/","url":"https:\/\/danielschlegel.org\/wp\/teaching\/csc344-fall-2026\/project-3-logical-expression-simplifier\/","name":"Project 3 - Logical Expression Simplifier - Daniel R. Schlegel","isPartOf":{"@id":"https:\/\/danielschlegel.org\/wp\/#website"},"datePublished":"2026-10-16T00:55:24+00:00","dateModified":"2026-10-16T00:55:26+00:00","breadcrumb":{"@id":"https:\/\/danielschlegel.org\/wp\/teaching\/csc344-fall-2026\/project-3-logical-expression-simplifier\/#breadcrumb"},"inLanguage":"en-US","potentialAction":[{"@type":"ReadAction","target":["https:\/\/danielschlegel.org\/wp\/teaching\/csc344-fall-2026\/project-3-logical-expression-simplifier\/"]}]},{"@type":"BreadcrumbList","@id":"https:\/\/danielschlegel.org\/wp\/teaching\/csc344-fall-2026\/project-3-logical-expression-simplifier\/#breadcrumb","itemListElement":[{"@type":"ListItem","position":1,"name":"Home","item":"https:\/\/danielschlegel.org\/wp\/"},{"@type":"ListItem","position":2,"name":"Teaching","item":"https:\/\/danielschlegel.org\/wp\/teaching\/"},{"@type":"ListItem","position":3,"name":"CSC344 &#8211; Fall 2026","item":"https:\/\/danielschlegel.org\/wp\/teaching\/csc344-fall-2026\/"},{"@type":"ListItem","position":4,"name":"Project 3 &#8211; Logical Expression Simplifier"}]},{"@type":"WebSite","@id":"https:\/\/danielschlegel.org\/wp\/#website","url":"https:\/\/danielschlegel.org\/wp\/","name":"Daniel R. Schlegel","description":"","potentialAction":[{"@type":"SearchAction","target":{"@type":"EntryPoint","urlTemplate":"https:\/\/danielschlegel.org\/wp\/?s={search_term_string}"},"query-input":{"@type":"PropertyValueSpecification","valueRequired":true,"valueName":"search_term_string"}}],"inLanguage":"en-US"}]}},"jetpack_sharing_enabled":true,"jetpack_shortlink":"https:\/\/wp.me\/P83Tb6-1C2","_links":{"self":[{"href":"https:\/\/danielschlegel.org\/wp\/wp-json\/wp\/v2\/pages\/6202","targetHints":{"allow":["GET"]}}],"collection":[{"href":"https:\/\/danielschlegel.org\/wp\/wp-json\/wp\/v2\/pages"}],"about":[{"href":"https:\/\/danielschlegel.org\/wp\/wp-json\/wp\/v2\/types\/page"}],"author":[{"embeddable":true,"href":"https:\/\/danielschlegel.org\/wp\/wp-json\/wp\/v2\/users\/1"}],"replies":[{"embeddable":true,"href":"https:\/\/danielschlegel.org\/wp\/wp-json\/wp\/v2\/comments?post=6202"}],"version-history":[{"count":11,"href":"https:\/\/danielschlegel.org\/wp\/wp-json\/wp\/v2\/pages\/6202\/revisions"}],"predecessor-version":[{"id":6223,"href":"https:\/\/danielschlegel.org\/wp\/wp-json\/wp\/v2\/pages\/6202\/revisions\/6223"}],"up":[{"embeddable":true,"href":"https:\/\/danielschlegel.org\/wp\/wp-json\/wp\/v2\/pages\/6032"}],"wp:attachment":[{"href":"https:\/\/danielschlegel.org\/wp\/wp-json\/wp\/v2\/media?parent=6202"}],"curies":[{"name":"wp","href":"https:\/\/api.w.org\/{rel}","templated":true}]}}