These simplifications aside, there are some cool things that I present in this demonstration, all of which form a good foundation for you to use as a starting point for your own language. For example, there are complex expressions, supporting multiplication, division, addition, subtraction, and modulo. There are also several things you'd expect in a small language, such as if-else statements, loops, variable references, and functions.
Here's an example script that the language can process:
// an example of a function that returns a value
func subtractNumbers( x, y, z )
return x - y - z
endfunc
// an example of a function that doesn't return anything
func doSomething()
println 100
endfunc
// main program routine
main:
var a = 10
var b = 20
if (a > b) then
loop 3 times
var d = subtractNumbers( x = 10, y = 5, z = 3 )
println d
endloop
else
if (b > 0) then
loop 2 times
println b
endloop
endif
endif
println 4
doSomething()
println 1
println 2
The architecture consists of the following components:
- A parser written with the Scala parsing library
- The output of the parser is an AST which describes the structure of the input script
- An interpreter that walks the resulting AST and processes the nodes accordingly
package net.travisdazell.parsers
import scala.util.parsing.combinator.syntactical.StandardTokenParsers
import net.travisdazell.parsers.model._
// small interpreted language with the following features:
// - variable definitions and references
// - if-else statements
// - loops
// - error handling
// - scoping
// - functions with named arguments
class SmallLanguageParser extends StandardTokenParsers {
lexical.reserved += ("var", "println", "loop", "times", "endloop", "if",
"then", "else", "endif", "func", "return", "endfunc", "main")
lexical.delimiters += ("*", "/", "%", "+", "-", "(", ")", "=",
"<", ">", "==", "!=", "<=", ">=", ",", ":")
def program: Parser[Program] = (rep(function) <~ ("main" ~ ":")) ~ codeblock ^^ {
case f ~ c => new Program(f, c)
}
def function: Parser[Function] = ("func" ~> ident) ~ ("(" ~> arguments) ~
(")" ~> codeblock) ~ opt(returnStatement) <~ "endfunc" ^^ {
case a ~ b ~ c ~ None => new Function(a, b, c, Number(0))
case a ~ b ~ c ~ d => new Function(a, b, c, d.get)
}
def returnStatement: Parser[Expr] = "return" ~> expr ^^ {
e => e
}
def arguments: Parser[Map[String, Int]] = repsep(ident, ",") ^^ {
argumentList =>
{
(for (a <- argumentList) yield (a -> 0)) toMap
}
}
def codeblock: Parser[List[Statement]] = rep(statement) ^^ { a => a }
def statement: Parser[Statement] = positioned(variableAssignment | outStatement |
loopStatement | ifStatement | functionCall | outStatement) ^^ { a => a }
def variableAssignment: Parser[VariableDefinition] = "var" ~> ident ~ "=" ~
positioned(functionCall | expr) ^^ { case a ~ "=" ~ b => { new VariableDefinition(a, b) } }
def outStatement: Parser[PrintStatement] = "println" ~> positioned(expr) ^^ {
case a => new PrintStatement(a)
}
def loopStatement: Parser[LoopStatement] = ("loop" ~> iterations <~ "times") ~
codeblock <~ "endloop" ^^ {
case i ~ s => {
new LoopStatement(i, s)
}
}
def ifStatement: Parser[IfStatement] = conditional ~ codeblock ~
opt("else" ~> codeblock) <~ "endif" ^^ {
case a ~ b ~ c => {
c match {
case None => new IfStatement(a, b, List())
case _ => new IfStatement(a, b, c.get)
}
}
}
def conditional: Parser[Condition] = "if" ~ "(" ~> condition <~ ")" ~ "then"
def condition: Parser[Condition] = positioned(expr) ~
("<" | ">" | "==" | "!=" | "<=" | ">=") ~ positioned(expr) ^^ {
case a ~ b ~ c => {
new Condition(b, a, c)
}
}
def iterations: Parser[Int] = numericLit ^^ { _ toInt }
def functionCall: Parser[FunctionCall] = ((ident) <~ "(") ~
functionCallArguments <~ ")" ^^ {
case a ~ l => new FunctionCall(a, l)
}
def functionCallArguments: Parser[Map[String, Expr]] =
repsep(functionArgument, ",") ^^ {
_ toMap
}
def functionArgument: Parser[(String, Expr)] = (ident <~ "=") ~ expr ^^ {
case a ~ b => (a, b)
}
def expr: Parser[Expr] = term ~ rep(("+" | "-") ~ term) ^^ {
case a ~ List() => a
case a ~ b => {
def appendExpression(c: Operator, p: Operator): Operator = {
p.left = c
p
}
var root: Operator = new Operator(b.head._1, a, b.head._2)
for (f <- b.tail) {
var parent =
f._1 match {
case "+" => new Operator("+", null, f._2)
case "-" => Operator("-", null, f._2)
}
root = appendExpression(root, parent)
}
root
}
}
def term: Parser[Expr] = multiplydividemodulo ^^ { l => l } | factor ^^ {
a => a
}
// note that "rep" returns a List
def multiplydividemodulo: Parser[Expr] = factor ~ rep(("*" | "/" | "%") ~ factor) ^^ {
case a ~ List() => a
case a ~ b => {
def appendExpression(e: Operator, t: Operator): Operator = {
t.left = e.right
e.right = t
t
}
var root: Operator = new Operator(b.head._1, a, b.head._2)
var current = root
// for each of these, i'm just building up the parse tree
for (f <- b.tail) {
var rightOperator =
f._1 match {
case "*" => Operator("*", null, f._2)
case "/" => Operator("/", null, f._2)
case "%" => Operator("%", null, f._2)
}
current = appendExpression(current, rightOperator)
}
root
}
}
def factor: Parser[Expr] = numericLit ^^ { a => Number(a.toInt) } |
"(" ~> expr <~ ")" ^^ { e => e } |
ident ^^ { new Identifier(_) }
def parseAll[T](p: Parser[T], in: String): ParseResult[T] = {
phrase(p)(new lexical.Scanner(in))
}
}
Next, let's take a look at the interpreter:
package net.travisdazell.parsers.runtime
import net.travisdazell.parsers.model._
class Interpreter(program: Program) {
var currentScope = new Scope("global", null)
def run() {
walk(program.statements)
}
private def getVariable(ident: Identifier): Expr = {
var s: Scope = currentScope
while ((!s.name.equals("global")) && !s.variables.contains(ident.name)) {
s = s.parentScope
}
if (s.variables.contains(ident.name)) s.variables(ident.name)
else {
sys.error("Error: Undefined variable " + ident.name +
" at position [" +
ident.pos.column + "] on line: " +
ident.pos.line)
}
}
private def calculateExpr(e: Expr): Int = {
e match {
case Number(value) => value
case Identifier(name) => {
calculateExpr(getVariable(e.asInstanceOf[Identifier]))
}
case Operator(op, left, right) => {
op match {
case "*" => calculateExpr(left) * calculateExpr(right)
case "/" => calculateExpr(left) / calculateExpr(right)
case "%" => calculateExpr(left) % calculateExpr(right)
case "+" => calculateExpr(left) + calculateExpr(right)
case "-" => calculateExpr(left) - calculateExpr(right)
}
}
}
}
private def isConditionTrue(condition: Condition): Boolean = {
val a = calculateExpr(condition.left)
val b = calculateExpr(condition.right)
condition.op match {
case "==" => (a == b)
case "!=" => (a != b)
case "<=" => (a <= b)
case "<" => (a < b)
case ">=" => (a >= b)
case ">" => (a > b)
}
}
private def executeFunction(f: Function, arguments: Map[String, Expr]) {
currentScope = new Scope(f.name, currentScope)
for (v <- arguments) currentScope.variables(v._1) = v._2
walk(f.statements)
currentScope = currentScope.parentScope
}
private def walk(tree: List[Statement]) {
if (!tree.isEmpty) {
tree.head match {
case FunctionCall(name, values) => {
val f = program.functions.filter(x => x.name == name)
if (f.size < 1) sys.error("Error: Undefined function '" +
name + "' being called at position [" +
tree.head.pos.column + "] on line: " +
tree.head.pos.line)
else {
executeFunction(f(0), values)
walk(tree.tail)
}
}
case VariableDefinition(name, value) => {
// push this variable into scope
if (value.isInstanceOf[FunctionCall]) {
val functionCall = value.asInstanceOf[FunctionCall]
val function = program.functions.filter(x => x.name == functionCall.name)
// check if proc is defined and if not throw an error
if (function.size < 1) sys.error("Error: Undefined function '" +
functionCall.name + "' being called at position [" +
tree.head.pos.column + "] on line: " +
tree.head.pos.line)
else {
executeFunction(function(0), functionCall.values)
currentScope = currentScope.parentScope
// assign the return value of the function to the variable
currentScope.variables(name) = function(0).returnValue
}
} else {
currentScope.variables(name) = value
}
walk(tree.tail)
}
case PrintStatement(value) => {
println(calculateExpr(value))
walk(tree.tail)
}
case LoopStatement(iterations, statements) => {
currentScope = new Scope("", currentScope)
for (i <- 0 until iterations) walk(statements)
currentScope = currentScope.parentScope
walk(tree.tail)
}
case IfStatement(condition, trueBranch, falseBranch) => {
currentScope = new Scope("", currentScope)
if (isConditionTrue(condition)) walk(trueBranch) else walk(falseBranch)
currentScope = currentScope.parentScope
walk(tree.tail)
}
case _ => ()
}
}
}
}
The last thing we need is a main routine that will read our input script and execute our parser:
package net.travisdazell.parsers.runtime
import scala.io.Source
import net.travisdazell.parsers.SmallLanguageParser
object SmallLanguage {
def main(args: Array[String]) {
val inputFile = Source.fromFile("scripts/program.small")
val inputSource = inputFile.mkString
val parser = new SmallLanguageParser
parser.parseAll(parser.program, inputSource) match {
case parser.Success(r, n) => {
val interpreter = new Interpreter(r)
try {
interpreter.run
} catch {
case e: RuntimeException => println(e.getMessage)
}
}
case parser.Error(msg, n) => println("Error: " + msg)
case parser.Failure(msg, n) => println("Error: " + msg)
case _ =>
}
}
}
The one thing I haven't included is the model classes that represent the AST nodes. However, as always, I've provided the full source code on GitHub: https://github.com/travisdazell/javaone-2013-BOF-small-language
