Calculator Interpreter

Tutorial Purpose

The purpose of this document is to provide users with an example of how Kanonic can be leveraged in the own codebase. All of the code described in this document can be found within examples/calculator.

Calculator Goal

The goal of this mini-example is to write an interpreter from scratch that handles the syntax of a calculator. In short, we hope to allow users to execute 1 + 1 and receive 2 as the result.

Calculator's Grammar

You can find the full grammar in examples/calculator/src/main/kanonic/calculator.knc.

Tokens

Here's what the tokens, at the time of writing, look like:

/** TOKENS **/

INTEGER: "[0-9]+";
PLUS: "\+";
MINUS: "-";
ASTERISK: "\*";
SLASH_FORWARD: "/";
CARROT: "\^";
PAREN_LEFT: "\(";
PAREN_RIGHT: "\)";
WS: "[\s]" --> hidden;

Rules

/** RULES **/

root
    : expr
    ;

expr
  : @lhs=expr @op=(PLUS|MINUS) @rhs=math_op --> expr_plus
  | math_op                                 --> expr_atomic
  ;

math_op
    : @lhs=math_op @op=(SLASH_FORWARD|ASTERISK) @rhs=math_op_second --> expr_div
    | math_op_second                                                --> math_op_fallback
    ;

math_op_second
    : @lhs=math_op_second CARROT @rhs=atomic --> math_op_second
    | atomic                                 --> expr_atom
    ;

atomic
  : INTEGER                          --> int
  | PAREN_LEFT @exp=expr PAREN_RIGHT --> paren
  ;

With the above syntax, we can:

1. syntactically support ADDs, MINUSs, DIVIDEs, MULTIPLYs, and EXPONENTs
2. simplify rules using aliases (see lhs, op, and rhs)
3. express precedence using the order of rules

• For those unfamiliar with expression precedence in grammars, it's important to note that the precedence can be seen as "bottom to top". So, in the above grammar, atomic holds the highest precedence. Then, math_op_second holds the second highest, and so on.
• The result of this is that the parser can understand how to parse: 1 + 2^3 / 4 - 2 * 7. As humans, while it might take us a few seconds, we intuitively could re-write the equation to be: (1) + (((2)^(3)) / 4) - (2 * 7).

Calculator Parser Generation

All of the generated code can be found under examples/calculator/src/main/kotlin/io/johnedquinn/calculator/generated.

Calculator Parser

Now that we have all of the generated code, all we need to do to convert equations into ASTs is to instantiate and use the KanonicParser:

val parser = KanonicParser.Builder.standard().withSpecification(CalculatorSpecification).build()
val ast = parser.parse("1 + 2^3 / 4 - 2 * 7")

Calculator Parser

Now that we have all of the generated code, all we need to do to convert equations into ASTs is to instantiate and use the KanonicParser:

val parser = KanonicParser.Builder.standard().withSpecification(CalculatorSpecification).build()
val ast = parser.parse("1 + 2^3 / 4 - 2 * 7")

Calculator Interpreter

Now, what do we do with this AST? Well, since we are creating an interpreter, we just need to visit the tree and accumulate our result!

Using the generated CalculatorBaseVisitor, we can override some visits:

/**
 * When we parse a terminal, or token, we attempt to grab the integer
 * from the string.
 */
override fun visitTerminal(node: TerminalNode, ctx: Unit): Int {
    return when (val int = node.token.content.toIntOrNull()) {
        null -> 0
        else -> int
    }
}

override fun visitExprDiv(node: CalculatorNode.MathOpNode.ExprDivNode, ctx: Unit): Int {
    val op = when (node.op().type) {
        5 -> { a: Int, b: Int -> a * b }
        6 -> { a: Int, b: Int -> a / b }
        else -> error("Didn't understand op type: ${node.op().type}")
    }
    val lhs = visitMathOp(node.lhs(), ctx)
    val rhs = visitMathOpSecond(node.rhs(), ctx)
    return op(lhs, rhs)
}

Now, we can traverse the AST and calculate the result of equations!