Programmation appliquée en Scala

Copyright © Cay S. Horstmann 2015 Creative Commons License
This work is licensed under a Creative Commons Attribution 4.0 International License

Context-Free Grammar

Parse Tree

Combinator Parser

Combinator Parser Result

Transforming Combinator Parser Results

Returning Expression Trees

A Grammar Problem

Remedy: Manually Group Terms

Use foldLeft

Repetition

Lab

Scary looking lab

Part 1: Expressions

  1. Make a new project unit12. Right-click on the project in the tree display at the left, select Properties → Java Build Path → Libraries → Add External JARs, then locate to the directory where the Scala IDE is installed, go to its plugins directory, and pick org.scala-lang.modules.scala-parser-combinators_1.0.1.jar.
  2. Then restart the Scala IDE.
  3. Make a worksheet expr.sc. Paste in this code:
    import scala.util.parsing.combinator._
    class ExprParser extends JavaTokenParsers {
    	def expr: Parser[Any] = term ~ rep(("+" | "-") ~ term)
    	def term: Parser[Any] = factor ~ rep("*" ~> factor)
    	def factor: Parser[Any] = wholeNumber | "(" ~ expr ~ ")"
    }
    
    val parser = new ExprParser
    parser.parseAll(parser.expr, "3-4*5")
    What do you get?
  4. That's not so instructive. Make a copy of the ExprParser class and call it ExprParser2. Change all the Parser[Any] to Parser[Int]. Now you need to put ^^ transforms behind each result. I'll give you two of them:
    ... (term ~ rep(("+" | "-") ~ term)) ^^ { 
        case a ~ lst =>  (lst.foldLeft(a)) {
          	case (x, "+" ~ y) => x + y
          	case (x, "-" ~ y) => x - y
        }
    
    ... wholeNumber ^^ { _.toInt }
    
    Figure out the other two.
  5. Now call
    val parser2 = new ExprParser2
    parser2.parseAll(parser2.expr, "3-4*5")
    What happens?
  6. That's nice. Now we have a calculator. But what if we want to build a compiler? Then we need a parse tree. First define
    class Expr
    case class Number(value : Int) extends Expr
    case class Sum(left : Expr, right : Expr) extends Expr
    case class Difference(left : Expr, right : Expr) extends Expr
    case class Product(left : Expr, right : Expr) extends Expr
    
    Now we want to make a Parser[Expr], not a Parser[Int]. So, change all the return types and change the ^^ expressions to yield instances of Expr subclasses. I'll give you one:
    ...factor ~ rep("*" ~> factor) ^^ {
      case f ~ r => r.foldLeft(f)(Product(_, _))
    }
    
  7. Now what do you get for
    val parser3 = new ExprParser3
    arser3.parseAll(parser3.expr, "3-4*5")

Part 2: JSON Parsing

  1. You have probably seen JSON, the JavaScript object notation. It is ubiquitous in web programming. It lets you describe arrays and maps of key/value pairs, where the keys are strings. Here is an example:
    [{"balance" : 10000}, "Harry", true]
    
    Check out the JSON web site. It uses “railroad diagrams” to show the JSON syntax. It's trivial to turn them into a parser:
    class JSONParser extends JavaTokenParsers {
        def value: Parser[Any] = stringLiteral | floatingPointNumber | obj | array | "true" | "false" | "null"
        def member: Parser[Any] = stringLiteral ~ ":" ~ value
        def obj: Parser[Any] = "{" ~ repsep(member, ",") ~ "}"
        def array: ...
      }
    Here, stringLiteral and floatingPointNumber are defined in the JavaTokenParsers to parse, you guessed it, a string literal and a floating point number.
    I left it for you to fill in the entry for array.
  2. Make a JSONParser and parse """[{"balance" : 10000}, "Harry", true]""". The """...""" is a convenient Scala syntax for string literals that can contain ", so you don't have to write "[{\"balance\" : 10000}, \"Harry\", true]" What do you get?
  3. Ok, that's no good. In a Scala program, we want to use the JSON expression. We could either turn it into nested case class instances, like in the preceding exercise, or, more brutally, make an object into a Map[String, Any] and an array into a List[Any]. That's what we'll do now.
    Copy the JSONParser class into JSONParser2. A value is still an Any, but a member is a pair (String, Any), an obj is a Map[String, Any], and an array is a List[Any]. Update the Parser type parameters.
  4. Next, add ^^ { ... } clauses. I'll just give you the ones for false, true, and null:
    ... "true" ^^ { _ => true } | "false" ^^ { _ => false } | "null" ^^ { _ => null }
    For a member, you want to get a pair. Do this so that you don't get error messages.
  5. For an obj, use ~> and <~ to get rid of the { } delimiters. Then the result is a list of members, i.e. a list of pairs. Call _.toMap to turn it into a map.
  6. Finally, use ~> and <~ to get rid of the [ ] delimiters for arrays. Then you get a list, and you want a list, so you don't have to do anything.
    Now make a JSONParser2 and parse again """[{"balance" : 10000}, "Harry", true]""" . What do you get?
  7. Isn't this amazing? You have parsed JSON, with your bare hands, in less than ten lines of code. Of course, for JSON, you can get an off-the-shelf library, but if you have to parse something less common, such as Dot or asciimath, Scala has you covered.

Homework

Do this as individual work, not with your partner

When all done, email the signed zip files to Fatemeh.Borran@heig-vd.ch