Parsing 3

• Transforming combinator results
• Choosing grammars

Reminder: Context-Free Grammar

• Productions

  expr ::= term ( "+" | "-" ) expr
  term ::= factor ( "*" | "/") term
  factor ::= wholeNumber | "(" expr ")"

• Non-terminals expr term factor
• Terminals (tokens) wholeNumber "(" "+" ...
• Parse tree shows derivation process

  

  Not the same as an expression tree!

Reminder: Scala Combinator Parser

• Each nonterminal becomes a function
• Terminals (strings) and nonterminals (functions) are combined with operators
  • Sequence ~, returns instance of class ~ (similar to a pair)
  • Alternative |
  • 0 or more rep(P), returns List of the results of P
  • 0 or 1 opt(P), returns Option: Some of the result of P, or None

  class SimpleLanguageParser extends JavaTokenParsers {    
    def expr: Parser[Any] = term ~ opt(("+" | "-") ~ expr)
    def term: Parser[Any] = factor ~ opt(("*" | "/" ) ~ term)
    def factor: Parser[Any] = wholeNumber | "(" ~ expr ~ ")"
  }

Transforming Combinator Parser Results

• Default combinator parser result is inconvenient

  ((3~None)~Some((-~((4~Some((*~(5~None))))~None))))

• Use ^^ operator to transform. For example,

  wholeNumber ^^ (_.toDouble) 

• Use pattern matching for transforms

  def expr: Parser[Double] = (term ~ opt(("+" | "-") ~ expr)) ^^ { 
      case a ~ None => a
      case a ~ Some("+" ~ b) => a + b
      case a ~ Some("-" ~ b) => a - b
    }

• Use ~>, <~ to discard tokens

  def factor: Parser[Double] = wholeNumber ^^ (_.toDouble) |
     "(" ~> expr <~ ")"

• The Parser[...] type must match the return type of the transforms (here, Double)

Returning Expression Trees

• Returning Double works if we interpret an arithmetic expression without variables
• If we have variables in a loop, need to evaluate multiple times
• Want an expression tree: Parser[ExprTree]

  class ExprTree
  case class Number(value : Int) extends ExprTree
  case class Variable(name : String) extends ExprTree
  case class Operator(left : ExprTree, right : ExprTree, 
    f: (Int, Int) => Int) extends ExprTree

• class SimpleLanguageParser extends JavaTokenParsers {    
    def expr: Parser[ExprTree] = (term ~ opt(("+" | "-") ~ expr)) ^^ { 
      case a ~ None => a
      case a ~ Some("+" ~ b) => Operator(a, b, _ + _)
      case a ~ Some("-" ~ b) => Operator(a, b, _ - _)
    } 
    ...
  }

• Returns tree such as

  Operator(Number(3),Operator(Number(4),Number(5),<function>),<function>)

A Grammar Problem

• Consider the input 3 - 4 - 5
• Parse:

  expr ::= term - expr
    ::= term - term - expr
      

• Resulting expression tree:

  

• That's the wrong tree. 3 - (4 - 5) is 3 - (-1) = 4
• We want - to be left associative: (3 - 4) - 5
• How about switching expr and term?
• In theory, this works, but in practice, the Scala combinator parser gets into an infinite recursion

  expr ::= expr - term 
   ::= expr - expr - term
   :: expr - expr - expr - term

Remedy: Manually Group Terms

• Reorganize Grammar

  class SimpleLanguageParser extends JavaTokenParsers {    
    def expr: Parser[ExprTree] = term ~ rep(("+" | "-") ~ term)
    def term: Parser[ExprTree] = factor ~ rep(("*" | "/" ) ~ factor)
    def factor: Parser[ExprTree] = wholeNumber | "(" ~ expr ~ ")"
      

• Now we have a list of all terms
• Manually group them left to right

  Operator(Operator(...(Operator(term1, term2, op1), term3, op2), ...)

• Reminder from lecture 5: foldLeft or the /: operator

  def sum(lst: List[Int]) = (0 /: lst) ((x, y) => x + y)

• The /: indicates the tree shape

        +
       / \
      +   c
     / \
    +   b
   / \
  0   a

Use foldLeft

• Parsing 3 - 4 - 5 yields

  3 ~ List("-" ~ 4, "-" ~ 5)

• Note that the tail is a flat list
• Want the tree

      -
     / \
    -   5
   / \
  3   4

• Initial element is 3
• Next element is "-" ~ 4
• Fold operator is

  case (x, "+" ~ y) => Operator(x, y, _ + _)
  case (x, "-" ~ y) => Operator(x, y, _ - _)

• Now everything together:

  def expr: Parser[ExprTree] = (term ~ rep(("+" | "-") ~ term)) ^^ { 
      case a ~ lst =>  (a /: lst) { 
        case (x, "+" ~ y) => Operator(x, y, _ + _)
        case (x, "-" ~ y) => Operator(x, y, _ - _)
      }

• Result: Parser yields ExprTree with the correct structure
• Next lecture: What can we do with the tree?

Lab

• Check into eCampus in the usual way
• Scribe puts in report
• Buddy puts in comment with scribe's name

Step 1

Complete the program from slide 4.

package lab11.step1

import java.io._
import scala.util.parsing.combinator._

class SimpleLanguageParser extends JavaTokenParsers {    
  def expr: Parser[Double] = (term ~ opt(("+" | "-") ~ expr)) ^^ { 
    case a ~ None => a
    case a ~ Some("+" ~ b) => a + b
    case a ~ Some("-" ~ b) => a - b
    } 
  . . .
  def factor: Parser[Double] = wholeNumber ^^ (_.toDouble) | "(" ~> expr <~ ")"
}

object Main {
  def main(args : Array[String]) : Unit = {}
  val parser = new SimpleLanguageParser
  val result = parser.parse(parser.expr, new InputStreamReader(System.in))
  println(result)       
}

1. How did you complete the parser?
2. What result do you get when you input 3 + 4 * 5?
3. On your platform, how did you have to indicate the end of console input? (I had to type Ctrl+D in Linux.)
4. Why isn't the output a tree?

Step 2

Complete the program from Slide 5.

package lab11.step2

import java.io._
import scala.util.parsing.combinator._

class ExprTree
case class Number(value : Int) extends ExprTree
case class Variable(name : String) extends ExprTree
case class Operator(left : ExprTree, right : ExprTree, 
  f: (Int, Int) => Int) extends ExprTree

class SimpleLanguageParser extends JavaTokenParsers {    
  def expr: Parser[ExprTree] = (term ~ opt(("+" | "-") ~ expr)) ^^ { 
    case a ~ None => a
    case a ~ Some("+" ~ b) => Operator(a, b, _ + _)
    case a ~ Some("-" ~ b) => Operator(a, b, _ - _)
    } 
  ...
}

object Main {
  def main(args : Array[String]) : Unit = {}
  val parser = new SimpleLanguageParser
  val result = parser.parse(parser.expr, new InputStreamReader(System.in))
  println(result)       
}

NOTE: For some reason, (Number(_.toInt)) didn't work out for me, and I had to use { x : String => Number(x.toInt) }

1. How did you complete the code?
2. What did you get when you parsed 3 + 4 * 5?
3. What did you get when you parsed 3 - 4 - 5?
4. What happens when you flip expr and term in the right hand side of the first production? Try parsing 3 - 4 - 5 again.

Step 3

Complete the program from slide 8:

package lab11.step3

import java.io._
import scala.util.parsing.combinator._

class ExprTree
case class Number(value : Int) extends ExprTree
case class Variable(name : String) extends ExprTree
case class Operator(left : ExprTree, right : ExprTree, 
  f: (Int, Int) => Int) extends ExprTree

class SimpleLanguageParser extends JavaTokenParsers {    
  def expr: Parser[ExprTree] = (term ~ rep(("+" | "-") ~ term)) ^^ { 
      case a ~ lst =>  (a /: lst) { 
        case (x, "+" ~ y) => Operator(x, y, _ + _)
        case (x, "-" ~ y) => Operator(x, y, _ - _)
      }
    } 
  ...
}

object Main {
  def main(args : Array[String]) : Unit = {}
  val parser = new SimpleLanguageParser
  val result = parser.parse(parser.expr, new InputStreamReader(System.in))
  println(result)       
}

1. How did you complete the program?
2. What did you get when you parsed 3 - 4 - 5?
3. We never did anything about Variable. How can you enhance your program to parse them as well, e.g. 3 - 4 * x?