🎓 A1Learner
🔍
0 of 45 lessons completed

Project: JSON Parser

A JSON parser reads JSON text and builds a value a program can use. JSON is a text format for data built from objects, arrays, strings, numbers, booleans, and null.

A sealed trait lists every value form

The trait is the shared type for all JSON values. Each case is one form the data can take.

sealed trait Json
case class JObj(fields: List[(String, Json)]) extends Json
case class JArr(items: List[Json]) extends Json
case class JStr(value: String) extends Json
case class JNum(value: Double) extends Json
case class JBool(value: Boolean) extends Json
case object JNull extends Json
@main def main(): Unit =
  val doc = JObj(List(("name", JStr("Ada")), ("age", JNum(36.0))))
  println(doc.fields.size)
  println(doc.fields.head._2 match {
    case JStr(v) => v
    case _ => "?"
  })

A parser reads text into a value

The parser moves through the text one piece at a time. It builds the matching value for each piece it finds.

sealed trait Json
case class JObj(fields: List[(String, Json)]) extends Json
case class JArr(items: List[Json]) extends Json
case class JStr(value: String) extends Json
case class JNum(value: Double) extends Json
case class JBool(value: Boolean) extends Json
case object JNull extends Json
class Parser(text: String):
  var pos = 0
  def skip(): Unit =
    while pos < text.length && text(pos).isWhitespace do
      pos += 1
  def peek: Char =
    skip()
    if pos < text.length then text(pos) else 0.toChar
  def expect(c: Char): Unit =
    skip()
    if pos < text.length && text(pos) == c then pos += 1
  def parseValue(): Json =
    skip()
    text(pos) match
      case '{' => parseObject()
      case '[' => parseArray()
      case '"' => JStr(parseString())
      case 't' => parseWord("true", JBool(true))
      case 'f' => parseWord("false", JBool(false))
      case 'n' => parseWord("null", JNull)
      case _ => parseNumber()
  def parseWord(word: String, value: Json): Json =
    pos += word.length
    value
  def parseString(): String =
    pos += 1
    val out = new StringBuilder
    while pos < text.length && text(pos) != '"' do
      if text(pos) == '\\' then
        pos += 1
        text(pos) match
          case 'n' => out.append('\n')
          case 't' => out.append('\t')
          case '"' => out.append('"')
          case '\\' => out.append('\\')
          case other => out.append(other)
        pos += 1
      else
        out.append(text(pos))
        pos += 1
    pos += 1
    out.toString
  def parseNumber(): Json =
    val start = pos
    while pos < text.length && (text(pos).isDigit || text(pos) == '.' || text(pos) == '-') do
      pos += 1
    JNum(text.substring(start, pos).toDouble)
  def parseArray(): Json =
    expect('[')
    var items = List.empty[Json]
    if peek == ']' then
      pos += 1
      JArr(items)
    else
      var done = false
      while !done do
        items = items :+ parseValue()
        if peek == ',' then pos += 1 else done = true
      expect(']')
      JArr(items)
  def parseObject(): Json =
    expect('{')
    var fields = List.empty[(String, Json)]
    if peek == '}' then
      pos += 1
      JObj(fields)
    else
      var done = false
      while !done do
        skip()
        val key = parseString()
        expect(':')
        val value = parseValue()
        fields = fields :+ (key, value)
        if peek == ',' then pos += 1 else done = true
      expect('}')
      JObj(fields)
def find(obj: Json, key: String): Json =
  obj match
    case JObj(fields) => fields.find((k, v) => k == key) match
      case Some((k, v)) => v
      case None => JNull
    case _ => JNull
@main def main(): Unit =
  val doc = Parser("{\"title\":\"Cats\",\"pages\":120}").parseValue()
  println(find(doc, "title") match {
    case JStr(v) => v
    case _ => "?"
  })
  println(find(doc, "pages") match {
    case JNum(n) => n.toLong
    case _ => 0
  })

A printer turns a value back into text

The printer matches each value form in turn. It joins the pieces into one compact JSON string.

sealed trait Json
case class JObj(fields: List[(String, Json)]) extends Json
case class JArr(items: List[Json]) extends Json
case class JStr(value: String) extends Json
case class JNum(value: Double) extends Json
case class JBool(value: Boolean) extends Json
case object JNull extends Json
def render(json: Json): String =
  json match
    case JStr(v) => "\"" + v + "\""
    case JNum(n) => if n == n.toLong.toDouble then n.toLong.toString else n.toString
    case JBool(v) => v.toString
    case JNull => "null"
    case JArr(items) => items.map(render).mkString("[", ",", "]")
    case JObj(fields) => fields.map((k, v) => "\"" + k + "\":" + render(v)).mkString("{", ",", "}")
@main def main(): Unit =
  val doc = JObj(List(("name", JStr("Ada")), ("age", JNum(36.0)), ("tags", JArr(List(JStr("a"), JStr("b"))))))
  println(render(doc))

Example

sealed trait Json
case class JObj(fields: List[(String, Json)]) extends Json
case class JArr(items: List[Json]) extends Json
case class JStr(value: String) extends Json
case class JNum(value: Double) extends Json
case class JBool(value: Boolean) extends Json
case object JNull extends Json
class Parser(text: String):
  var pos = 0
  def skip(): Unit =
    while pos < text.length && text(pos).isWhitespace do
      pos += 1
  def peek: Char =
    skip()
    if pos < text.length then text(pos) else 0.toChar
  def expect(c: Char): Unit =
    skip()
    if pos < text.length && text(pos) == c then pos += 1
  def parseValue(): Json =
    skip()
    text(pos) match
      case '{' => parseObject()
      case '[' => parseArray()
      case '"' => JStr(parseString())
      case 't' => parseWord("true", JBool(true))
      case 'f' => parseWord("false", JBool(false))
      case 'n' => parseWord("null", JNull)
      case _ => parseNumber()
  def parseWord(word: String, value: Json): Json =
    pos += word.length
    value
  def parseString(): String =
    pos += 1
    val out = new StringBuilder
    while pos < text.length && text(pos) != '"' do
      if text(pos) == '\\' then
        pos += 1
        text(pos) match
          case 'n' => out.append('\n')
          case 't' => out.append('\t')
          case '"' => out.append('"')
          case '\\' => out.append('\\')
          case other => out.append(other)
        pos += 1
      else
        out.append(text(pos))
        pos += 1
    pos += 1
    out.toString
  def parseNumber(): Json =
    val start = pos
    while pos < text.length && (text(pos).isDigit || text(pos) == '.' || text(pos) == '-') do
      pos += 1
    JNum(text.substring(start, pos).toDouble)
  def parseArray(): Json =
    expect('[')
    var items = List.empty[Json]
    if peek == ']' then
      pos += 1
      JArr(items)
    else
      var done = false
      while !done do
        items = items :+ parseValue()
        if peek == ',' then pos += 1 else done = true
      expect(']')
      JArr(items)
  def parseObject(): Json =
    expect('{')
    var fields = List.empty[(String, Json)]
    if peek == '}' then
      pos += 1
      JObj(fields)
    else
      var done = false
      while !done do
        skip()
        val key = parseString()
        expect(':')
        val value = parseValue()
        fields = fields :+ (key, value)
        if peek == ',' then pos += 1 else done = true
      expect('}')
      JObj(fields)
def render(json: Json): String =
  json match
    case JStr(v) => "\"" + v + "\""
    case JNum(n) => if n == n.toLong.toDouble then n.toLong.toString else n.toString
    case JBool(v) => v.toString
    case JNull => "null"
    case JArr(items) => items.map(render).mkString("[", ",", "]")
    case JObj(fields) => fields.map((k, v) => "\"" + k + "\":" + render(v)).mkString("{", ",", "}")
def find(obj: Json, key: String): Json =
  obj match
    case JObj(fields) => fields.find((k, v) => k == key) match
      case Some((k, v)) => v
      case None => JNull
    case _ => JNull
@main def main(): Unit =
  val doc = Parser("{\"name\":\"Ada\",\"age\":36,\"active\":true,\"tags\":[\"scala\",\"json\"]}").parseValue()
  println(find(doc, "name") match {
    case JStr(v) => v
    case _ => "?"
  })
  println(find(doc, "age") match {
    case JNum(n) => n.toLong
    case _ => 0
  })
  println(find(doc, "active") match {
    case JBool(v) => v
    case _ => false
  })
  println(find(doc, "tags") match {
    case JArr(items) => items.size
    case _ => 0
  })
  println(find(doc, "tags") match {
    case JArr(items) => items.head match {
      case JStr(v) => v
      case _ => "?"
    }
    case _ => "?"
  })
  println(render(doc))

Key points

  • Sealed trait: a sealed trait is a closed family of types with a fixed list of members.
  • Value forms: JSON values are objects, arrays, strings, numbers, booleans, or null.
  • Parser: a parser is code that reads text and builds a value from it.
  • Recursion: recursion means a rule calls itself to handle nested values.
  • Printer: a printer turns a value back into JSON text.
  • Lookup: a lookup finds one field in an object by its name.

In this example, the parser reads a document with a name, an age, a flag, and a tag list. The lookups pull out the name, the age, the flag, and the tag count. The first tag is read from the list. The printer then renders the whole document back into compact text.

Note

a case object is a single value with no fields, so it fits JSON null exactly.

Try it Yourself

Edit the code, then press Run.

Running is simulated · Scastie

Exercise

What does the parser build from the text {"age": 36}?