{"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":"2026-10-15T01:27:02","modified_gmt":"2026-10-15T01:27:02","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\">import 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\nsealed trait S {\n  def eval(env: Main.Environment): Int\n}\n\nsealed trait Terminal extends S\n\ncase class E(left: Terminal, right: Option[E2]) extends S {\n  def eval(env: Main.Environment): Int = {\n    val leftVal: Int = left.eval(env)\n    right match {\n      case Some(r) => leftVal + r.eval(env)\n      case None => leftVal\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  private val constRegex: Regex = \"^[0-9]+\".r\n  private val varRegex: Regex = \"^[A-Za-z]+\".r\n\n  private var index = 0\n\n  private def remainingInput: String =\n    input.substring(index)\n\n  def parseS(): S = {\n    val result = parseE()\n\n    if (index != input.length) {\n      throw new IllegalArgumentException(\n        s\"Unexpected input at position $index: '${input.substring(index)}'\"\n      )\n    }\n\n    result\n  }\n\n  private def parseE(): E = E(parseTerminal(), parseE2())\n\n  private 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{\n      None\n    }\n  }\n\n  private def parseConst(): Option[Const] = {\n    constRegex.findFirstIn(remainingInput) match {\n      case Some(const) =>\n        index += const.length\n        Some(Const(const.toInt))\n\n      case None => None\n    }\n  }\n\n  private def parseVar(): Option[Var] = {\n    varRegex.findFirstIn(remainingInput) match {\n      case Some(varName) =>\n        index += varName.length\n        Some(Var(varName))\n\n      case None => None\n    }\n  }\n\n  private def parseTerminal(): Terminal =\n    parseConst() \/\/ Check for const\n      .orElse(parseVar()) \/\/ If not there, check for var\n      .getOrElse { \/\/ If not there, fail\n        throw new IllegalArgumentException(\n          s\"Expected constant or variable at position $index in '$input'\"\n        )\n      }\n}\n\nobject Main {\n  type Environment = String => Int\n\n  def main(args: Array[String]): Unit = {\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.parseS()\n\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 sealed trait 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 v28.8 - 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 sealed trait 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=\"2026-10-15T01:27:02+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\":\"2026-10-15T01:27:02+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 sealed trait 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":"2026-10-15T01:27:02+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":"2026-10-15T01:27:02+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":6,"href":"https:\/\/danielschlegel.org\/wp\/wp-json\/wp\/v2\/pages\/3068\/revisions"}],"predecessor-version":[{"id":6218,"href":"https:\/\/danielschlegel.org\/wp\/wp-json\/wp\/v2\/pages\/3068\/revisions\/6218"}],"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}]}}