{"id":3068,"date":"2019-10-12T14:50:48","date_gmt":"2019-10-12T14:50:48","guid":{"rendered":"https:\/\/danielschlegel.org\/wp\/?page_id=3068"},"modified":"2025-10-08T12:48:06","modified_gmt":"2025-10-08T12:48:06","slug":"recursive-descent-parser-in-scala","status":"publish","type":"page","link":"https:\/\/danielschlegel.org\/wp\/teaching\/recursive-descent-parser-in-scala\/","title":{"rendered":"Recursive Descent Parser in Scala"},"content":{"rendered":"\n<pre class=\"scala\">\nimport scala.util.matching.Regex\n\n\/\/ Unambiguous grammar\n\/\/ S -> E$\n\/\/ E -> T + E | T\n\/\/ T -> Const | Var\n\n\/\/ Easier to parse grammar\n\/\/ S -> E$\n\/\/ E -> Terminal E2\n\/\/ E2 -> + E\n\/\/ E2 -> NIL\n\/\/ Terminal -> Const\n\/\/ Terminal -> Var\n\nabstract class S {\n  def eval(env: Main.Environment): Int\n}\nabstract class Terminal extends S\ncase class E(l: Terminal, right: Option[E2]) extends S {\n  def eval(env: Main.Environment): Int = {\n    val a1: Int = l match {\n      case v:Var => v.eval(env)\n      case c:Const => c.eval(env)\n    }\n    right match {\n      case Some(r) => a1 + r.eval(env)\n      case None => a1\n    }\n  }\n}\ncase class E2(l: E) extends S {\n  def eval(env: Main.Environment): Int = l.eval(env)\n}\ncase class Var(n: String) extends Terminal {\n  def eval(env: Main.Environment): Int = env(n)\n}\ncase class Const(v: Int) extends Terminal {\n  def eval(env: Main.Environment): Int = v\n}\n\nclass RecursiveDescent(input:String) {\n  val constregex: Regex = \"^[0-9]+\".r\n  val varregex: Regex = \"^[A-Za-z]+\".r\n\n  var index = 0\n\n  def parseS(): S = parseE()\n\n  def parseE(): E = E(parseTerminal(), parseE2())\n\n  def parseE2(): Option[E2] = {\n    if (index < input.length &#038;&#038; input(index) == '+'){\n      index+=1; \/\/ Advance past +\n      Some(E2(parseE()))\n    }\n    else None\n  }\n\n  def parseTerminal(): Terminal = {\n    \/\/ Get the unparsed part of the string.\n    val currStr = input.substring(index)\n\n    \/\/ Get either the const or var which is there.\n    val consts = constregex.findAllIn(currStr)\n    if (consts.hasNext){\n      val const: String = consts.next()\n      index += const.length()\n      Const(const.toInt)\n    }\n    else {\n      val vars = varregex.findAllIn(currStr)\n      val varname = vars.next()\n      index += varname.length()\n      Var(varname)\n    }\n  }\n}\n\nobject Main {\n  type Environment = String => Int\n\n  def main(args: Array[String]) = {\n    val env: Environment = { case \"x\" => 5 case \"y\" => 7 }\n\n    val rd = new RecursiveDescent(\"x+x+7+y\")\n    val exp2rd:S = rd.parseE()\n    println(exp2rd)\n    println(exp2rd.eval(env))\n  }\n}\n<\/pre>\n","protected":false},"excerpt":{"rendered":"<p class=\"lead\">import scala.util.matching.Regex \/\/ Unambiguous grammar \/\/ S -> E$ \/\/ E -> T + E | T \/\/ T -> Const | Var \/\/ Easier to parse grammar \/\/ S -> E$ \/\/ E -> Terminal E2 \/\/ E2 -> + E \/\/ E2 -> NIL \/\/ Terminal -> Const \/\/ Terminal -> Var abstract class S { def eval(env:&hellip;<\/p>\n<p class=\"more-link-p\"><a class=\"btn btn-warning\" href=\"https:\/\/danielschlegel.org\/wp\/teaching\/recursive-descent-parser-in-scala\/\">Read more<\/a><\/p>\n","protected":false},"author":1,"featured_media":0,"parent":11,"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-3068","page","type-page","status-publish","hentry"],"yoast_head":"<!-- This site is optimized with the Yoast SEO plugin v27.7 - https:\/\/yoast.com\/product\/yoast-seo-wordpress\/ -->\n<title>Recursive Descent Parser in Scala - 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\/recursive-descent-parser-in-scala\/\" \/>\n<meta property=\"og:locale\" content=\"en_US\" \/>\n<meta property=\"og:type\" content=\"article\" \/>\n<meta property=\"og:title\" content=\"Recursive Descent Parser in Scala - Daniel R. Schlegel\" \/>\n<meta property=\"og:description\" content=\"import scala.util.matching.Regex \/\/ Unambiguous grammar \/\/ S -&gt; E$ \/\/ E -&gt; T + E | T \/\/ T -&gt; Const | Var \/\/ Easier to parse grammar \/\/ S -&gt; E$ \/\/ E -&gt; Terminal E2 \/\/ E2 -&gt; + E \/\/ E2 -&gt; NIL \/\/ Terminal -&gt; Const \/\/ Terminal -&gt; Var abstract class S { def eval(env:&hellip;Read more\" \/>\n<meta property=\"og:url\" content=\"https:\/\/danielschlegel.org\/wp\/teaching\/recursive-descent-parser-in-scala\/\" \/>\n<meta property=\"og:site_name\" content=\"Daniel R. Schlegel\" \/>\n<meta property=\"article:modified_time\" content=\"2025-10-08T12:48:06+00:00\" \/>\n<meta name=\"twitter:card\" content=\"summary_large_image\" \/>\n<script type=\"application\/ld+json\" class=\"yoast-schema-graph\">{\"@context\":\"https:\\\/\\\/schema.org\",\"@graph\":[{\"@type\":\"WebPage\",\"@id\":\"https:\\\/\\\/danielschlegel.org\\\/wp\\\/teaching\\\/recursive-descent-parser-in-scala\\\/\",\"url\":\"https:\\\/\\\/danielschlegel.org\\\/wp\\\/teaching\\\/recursive-descent-parser-in-scala\\\/\",\"name\":\"Recursive Descent Parser in Scala - Daniel R. Schlegel\",\"isPartOf\":{\"@id\":\"https:\\\/\\\/danielschlegel.org\\\/wp\\\/#website\"},\"datePublished\":\"2019-10-12T14:50:48+00:00\",\"dateModified\":\"2025-10-08T12:48:06+00:00\",\"breadcrumb\":{\"@id\":\"https:\\\/\\\/danielschlegel.org\\\/wp\\\/teaching\\\/recursive-descent-parser-in-scala\\\/#breadcrumb\"},\"inLanguage\":\"en-US\",\"potentialAction\":[{\"@type\":\"ReadAction\",\"target\":[\"https:\\\/\\\/danielschlegel.org\\\/wp\\\/teaching\\\/recursive-descent-parser-in-scala\\\/\"]}]},{\"@type\":\"BreadcrumbList\",\"@id\":\"https:\\\/\\\/danielschlegel.org\\\/wp\\\/teaching\\\/recursive-descent-parser-in-scala\\\/#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\":\"Recursive Descent Parser in Scala\"}]},{\"@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":"Recursive Descent Parser in Scala - 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\/recursive-descent-parser-in-scala\/","og_locale":"en_US","og_type":"article","og_title":"Recursive Descent Parser in Scala - Daniel R. Schlegel","og_description":"import scala.util.matching.Regex \/\/ Unambiguous grammar \/\/ S -> E$ \/\/ E -> T + E | T \/\/ T -> Const | Var \/\/ Easier to parse grammar \/\/ S -> E$ \/\/ E -> Terminal E2 \/\/ E2 -> + E \/\/ E2 -> NIL \/\/ Terminal -> Const \/\/ Terminal -> Var abstract class S { def eval(env:&hellip;Read more","og_url":"https:\/\/danielschlegel.org\/wp\/teaching\/recursive-descent-parser-in-scala\/","og_site_name":"Daniel R. Schlegel","article_modified_time":"2025-10-08T12:48:06+00:00","twitter_card":"summary_large_image","schema":{"@context":"https:\/\/schema.org","@graph":[{"@type":"WebPage","@id":"https:\/\/danielschlegel.org\/wp\/teaching\/recursive-descent-parser-in-scala\/","url":"https:\/\/danielschlegel.org\/wp\/teaching\/recursive-descent-parser-in-scala\/","name":"Recursive Descent Parser in Scala - Daniel R. Schlegel","isPartOf":{"@id":"https:\/\/danielschlegel.org\/wp\/#website"},"datePublished":"2019-10-12T14:50:48+00:00","dateModified":"2025-10-08T12:48:06+00:00","breadcrumb":{"@id":"https:\/\/danielschlegel.org\/wp\/teaching\/recursive-descent-parser-in-scala\/#breadcrumb"},"inLanguage":"en-US","potentialAction":[{"@type":"ReadAction","target":["https:\/\/danielschlegel.org\/wp\/teaching\/recursive-descent-parser-in-scala\/"]}]},{"@type":"BreadcrumbList","@id":"https:\/\/danielschlegel.org\/wp\/teaching\/recursive-descent-parser-in-scala\/#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":"Recursive Descent Parser in Scala"}]},{"@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-Nu","_links":{"self":[{"href":"https:\/\/danielschlegel.org\/wp\/wp-json\/wp\/v2\/pages\/3068","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=3068"}],"version-history":[{"count":5,"href":"https:\/\/danielschlegel.org\/wp\/wp-json\/wp\/v2\/pages\/3068\/revisions"}],"predecessor-version":[{"id":5703,"href":"https:\/\/danielschlegel.org\/wp\/wp-json\/wp\/v2\/pages\/3068\/revisions\/5703"}],"up":[{"embeddable":true,"href":"https:\/\/danielschlegel.org\/wp\/wp-json\/wp\/v2\/pages\/11"}],"wp:attachment":[{"href":"https:\/\/danielschlegel.org\/wp\/wp-json\/wp\/v2\/media?parent=3068"}],"curies":[{"name":"wp","href":"https:\/\/api.w.org\/{rel}","templated":true}]}}