Home > Software engineering >  How to evaluate combinators productions right to left in Scala
How to evaluate combinators productions right to left in Scala

Time:01-15

I have a simple parser which recognizes programs with the following form print <expression> where <declarations>, an example of complete program is

print x y z 1 x -3 where x = 25, y = 1, z = -7

I've written the following evaluator for it

import scala.util.parsing.combinator._

class DeskParserCombinators() extends JavaTokenParsers {
    var memory : Map[String, Int] = Map()

    def desk = "print" ~> expression ~ ("where" ~> variable_inizialization) ^^ {case e ~ d => (e, memory)}
    def expression = repsep(element, " ") ^^ {elements => elements.foldLeft(0){_ _}}
    def element = variable | value
    def variable_inizialization = repsep(declaration, ",")
    def declaration = """[a-z]""".r ~ ("=" ~> value) ^^ {case n ~ v => memory = memory   (n -> v)}
    def variable = """[a-z]""".r ^^ {(name: String) =>
        if(!memory.contains(name))
            throw new Exception("variable not declared "   name)
        memory(name)
    }
    def value = wholeNumber ^^ {v => v.toInt}
}

// === main ===
val parser = new DeskParserCombinators()
parser.parseAll(parser.desk, program) match {
    case parser.Success((result, memory), _) =>
        println(result)
        println(memory)
    case x => print(x.toString)
}

The program compiles, but as it is written in the case of the first desk rule the expression part is evaluated before the variable declaration part and therefore every execution that contains variables in the first part raises the defined exception

Is there a way to have the right-hand side evaluate first and only then evaluate the expression?

CodePudding user response:

By keeping the same structure of your definitions, you can prevent expression from being evaluated early by making its result a function, that way you can decide when to evaluate it:

import scala.util.parsing.combinator._

class DeskParserCombinators() extends JavaTokenParsers {
    var memory : Map[String, Int] = Map()

    def desk = "print" ~> expression ~ ("where" ~> variable_inizialization) ^^ {case e ~ d => (e(), memory)}
    def expression = repsep(element, " ") ^^ {elements =>
        elements.foldLeft(() => 0)((f1, f2) => () => f1()   f2())  
    }
    def element = variable | value
    def variable_inizialization = repsep(declaration, ",")
    def declaration = """[a-z]""".r ~ ("=" ~> value) ^^ {case n ~ v => memory = memory   (n -> v())}
    def variable = """[a-z]""".r ^^ {(name: String) =>
        () => {
            if(!memory.contains(name))
                throw new Exception("variable not declared "   name)
            memory(name)
        }
    }
    def value = wholeNumber ^^ {v => () => {v.toInt}}
}

Of course, other definitions must also be changed to make them return functions
There is probably a better solution, but this doesn't alter the structure of the grammar you defined

  • Related