Build an interpreter for a simpler Ruby-like language in Scala

18 Mar 2017

I have been experimenting with scala.util.parsing. I think it's capable of building an interpreter for a language like Ruby.

The library is so powerful. It's a huge upgrade from using regular expression. For example, we can have a language like below:

msg = "Hello world!" robot = getRobot("Rory") anotherRobot = getRobot("Lorerai") robot.send(msg).moveTo(anotherRobot.getPosition()) # Chained and nested methods println(robot) # Use object as an argument

The language supports declaring a variable, invoking a method, and chaining methods. Here's the interpreter in Scala:

import scala.util.parsing.combinator.RegexParsers sealed trait Expr sealed trait Value extends Expr case class StringVal(value: String) extends Value // Represent the void type that is the return type of a void method. case class VoidVal() extends Value // Represent an instance. abstract class RefVal extends Value { def get(key: String): Value } // Represent a method. abstract class MethodVal(val name: String) extends Value { def apply(args: Value*): Value } case class Identifier(value: String) extends Expr case class Args(expr: Expr, nextOpt: Option[Args]) extends Expr case class Invoke(name: Identifier, argsOpt: Option[Args]) extends Expr case class Chain(expr: Expr, nextOpt: Option[Chain]) extends Expr case class Declare(name: Identifier, value: Expr) extends Expr case class NewLine() extends Expr class Parser extends RegexParsers { def string: Parser[StringVal] = "\"[^\"]*\"".r ^^ { s => StringVal(s.substring(1, s.length - 1)) } def newLine: Parser[NewLine] = "[ ]*\n".r ^^ { _ => NewLine() } def expr: Parser[Expr] = (chain | string) ^^ identity def args: Parser[Args] = expr ~ ("," ~ args).? ^^ { case first ~ Some(_ ~ next) => Args(first, Some(next)) case first ~ None => Args(first, None) } def identifier: Parser[Identifier] = "[0-9a-zA-Z-_]+".r ^^ Identifier.apply def invoke: Parser[Invoke] = identifier ~ "(" ~ args.? ~ ")" ^^ { case func ~ _ ~ argsOpt ~ _ => Invoke(func, argsOpt) } def chain: Parser[Chain] = (invoke | identifier) ~ ("." ~ chain).? ^^ { case first ~ None => Chain(first, None) case first ~ Some(_ ~ invoke) => Chain(first, Some(invoke)) } def declare: Parser[Declare] = identifier ~ "=" ~ expr ^^ { case name ~ _ ~ rhs => Declare(name, rhs) } def instruction: Parser[Expr] = (declare | chain) ^^ identity def script: Parser[Seq[Expr]] = { phrase(rep1(instruction | newLine)) ^^ { exprsOrNewLines => exprsOrNewLines.filterNot(_.isInstanceOf[NewLine]) } } }

It took me a while to get it correctly. There's one lesson that I learn from building this simple interpreter:

It's much better to use recursion than a list. For example, Args contains the main constituent and points to next, which is, in turn, an Args. This makes it really easy to build the rule.

Here's how we can use it:

val parser = new Parser println(parser.parse(parser.script, "robot.send(msg)"))

The output is:

Seq( Chain( Identifier("robot"), Some(Chain( Invoke(Identifier("send"), Some(Args(Identifier("msg"), None))), None )) ) )

I haven't built the part where we execute the AST yet. I think it's called AST. But it shouldn't be that difficult because we should be able to do it recursively while maintaining its context (which contains variables' values).

Give it a kudos