Expression Evaluator

This guide builds a math expression evaluator supporting arithmetic (+, -, *, /), exponentiation (**), unary minus, parentheses, constants (pi), and functions (sin, atan2). It demonstrates Alpaca's operator precedence and conflict resolution.

What you'll learn: dynamic token names, named productions, the before/after DSL, and how to express a complete precedence hierarchy.

The Lexer

import halotukozak.alpaca.*

val CalcLexer = lexer:
  case "\\s+" => Token.Ignored
  case "#.*" => Token.Ignored
  case "\\*\\*" => Token["exp"]
  case literal @ ("\\+" | "-" | "\\*" | "/" | "\\(" | "\\)" | ",") =>
    Token[literal.type]
  case keyword @ ("pi" | "sin" | "atan2") =>
    Token[keyword.type]
  case x @ """(\d+\.\d*|\.\d+)([eE][+-]?\d+)?""" => Token["float"](x.toDouble)
  case x @ "\\d+" => Token["int"](x.toInt)

calc-lexer

"\\*\\*" (exponentiation) and "\\*" (multiplication) can be declared in either order: the lexer takes the longest match, so ** is always one exp token (see How a Token Is Chosen).

The Parser

Named productions ("plus", "times", etc.) let us reference specific alternatives in conflict resolution.

The grammar on its own is ambiguous: 1 - 2 * 3 can be read as (1 - 2) * 3 or 1 - (2 * 3), and without help the compiler rejects the parser with 30 shift/reduce conflicts. The given Resolutions[CalcParser.type] below settles each of them. The parse table is built when CalcParser is compiled, so the given is declared together with it (see Where resolutions Live):

import halotukozak.alpaca.*

val CalcLexer = lexer:
  case "\\s+" => Token.Ignored
  case "#.*" => Token.Ignored
  case "\\*\\*" => Token["exp"]
  case literal @ ("\\+" | "-" | "\\*" | "/" | "\\(" | "\\)" | ",") =>
    Token[literal.type]
  case keyword @ ("pi" | "sin" | "atan2") =>
    Token[keyword.type]
  case x @ """(\d+\.\d*|\.\d+)([eE][+-]?\d+)?""" => Token["float"](x.toDouble)
  case x @ "\\d+" => Token["int"](x.toInt)
object CalcParser extends Parser:
  val root: Rule[Double] = rule:
    case Expr(v) => v

  val Expr: Rule[Double] = rule(
    "plus"   { case (Expr(a), CalcLexer.`\\+`(_), Expr(b)) => a + b },
    "minus"  { case (Expr(a), CalcLexer.`-`(_), Expr(b)) => a - b },
    "times"  { case (Expr(a), CalcLexer.`\\*`(_), Expr(b)) => a * b },
    "divide" { case (Expr(a), CalcLexer.`/`(_), Expr(b)) => a / b },
    "exp"    { case (Expr(a), CalcLexer.`exp`(_), Expr(b)) => math.pow(a, b) },
    "uminus" { case (CalcLexer.`-`(_), Expr(a)) => -a },
    "pi"     { case CalcLexer.pi(_) => math.Pi },
    "sin"    { case (CalcLexer.sin(_), CalcLexer.`\\(`(_), Expr(a), CalcLexer.`\\)`(_)) => math.sin(a) },
    "atan2"  {
      case (CalcLexer.atan2(_), CalcLexer.`\\(`(_), Expr(y), CalcLexer.`,`(_), Expr(x), CalcLexer.`\\)`(_)) =>
        math.atan2(y, x)
    },
    { case (CalcLexer.`\\(`(_), Expr(a), CalcLexer.`\\)`(_)) => a },
    { case CalcLexer.float(x) => x.value },
    { case CalcLexer.int(n) => n.value.toDouble },
  )

given Resolutions[CalcParser.type] = resolutions(
  // Exponentiation: right-associative, highest binary precedence
  CalcLexer.exp.before(production.uminus, production.exp, production.times, production.divide),
  production.exp.before(CalcLexer.`\\*`, CalcLexer.`/`),

  // Unary minus binds tighter than * /
  production.uminus.before(CalcLexer.`\\*`, CalcLexer.`/`),

  // Multiplication/division: left-associative, higher than +/-
  production.times.before(CalcLexer.`\\*`, CalcLexer.`/`),
  production.divide.before(CalcLexer.`\\*`, CalcLexer.`/`),

  // Addition/subtraction: left-associative, lowest binary precedence
  production.plus.after(CalcLexer.`\\*`, CalcLexer.`/`),
  production.plus.before(CalcLexer.`\\+`, CalcLexer.`-`),
  production.minus.after(CalcLexer.`\\*`, CalcLexer.`/`),
  production.minus.before(CalcLexer.`\\+`, CalcLexer.`-`),
)

calc-resolved

The precedence hierarchy from highest to lowest: ** > unary - > * / > + -. See The before/after DSL for what each form means.

Running It

import halotukozak.alpaca.*

val CalcLexer = lexer:
  case "\\s+" => Token.Ignored
  case "#.*" => Token.Ignored
  case "\\*\\*" => Token["exp"]
  case literal @ ("\\+" | "-" | "\\*" | "/" | "\\(" | "\\)" | ",") =>
    Token[literal.type]
  case keyword @ ("pi" | "sin" | "atan2") =>
    Token[keyword.type]
  case x @ """(\d+\.\d*|\.\d+)([eE][+-]?\d+)?""" => Token["float"](x.toDouble)
  case x @ "\\d+" => Token["int"](x.toInt)
object CalcParser extends Parser:
  val root: Rule[Double] = rule:
    case Expr(v) => v

  val Expr: Rule[Double] = rule(
    "plus"   { case (Expr(a), CalcLexer.`\\+`(_), Expr(b)) => a + b },
    "minus"  { case (Expr(a), CalcLexer.`-`(_), Expr(b)) => a - b },
    "times"  { case (Expr(a), CalcLexer.`\\*`(_), Expr(b)) => a * b },
    "divide" { case (Expr(a), CalcLexer.`/`(_), Expr(b)) => a / b },
    "exp"    { case (Expr(a), CalcLexer.`exp`(_), Expr(b)) => math.pow(a, b) },
    "uminus" { case (CalcLexer.`-`(_), Expr(a)) => -a },
    "pi"     { case CalcLexer.pi(_) => math.Pi },
    "sin"    { case (CalcLexer.sin(_), CalcLexer.`\\(`(_), Expr(a), CalcLexer.`\\)`(_)) => math.sin(a) },
    "atan2"  {
      case (CalcLexer.atan2(_), CalcLexer.`\\(`(_), Expr(y), CalcLexer.`,`(_), Expr(x), CalcLexer.`\\)`(_)) =>
        math.atan2(y, x)
    },
    { case (CalcLexer.`\\(`(_), Expr(a), CalcLexer.`\\)`(_)) => a },
    { case CalcLexer.float(x) => x.value },
    { case CalcLexer.int(n) => n.value.toDouble },
  )

given Resolutions[CalcParser.type] = resolutions(
  // Exponentiation: right-associative, highest binary precedence
  CalcLexer.exp.before(production.uminus, production.exp, production.times, production.divide),
  production.exp.before(CalcLexer.`\\*`, CalcLexer.`/`),

  // Unary minus binds tighter than * /
  production.uminus.before(CalcLexer.`\\*`, CalcLexer.`/`),

  // Multiplication/division: left-associative, higher than +/-
  production.times.before(CalcLexer.`\\*`, CalcLexer.`/`),
  production.divide.before(CalcLexer.`\\*`, CalcLexer.`/`),

  // Addition/subtraction: left-associative, lowest binary precedence
  production.plus.after(CalcLexer.`\\*`, CalcLexer.`/`),
  production.plus.before(CalcLexer.`\\+`, CalcLexer.`-`),
  production.minus.after(CalcLexer.`\\*`, CalcLexer.`/`),
  production.minus.before(CalcLexer.`\\+`, CalcLexer.`-`),
)
val input = "sin(pi / 2) + 2 ** 3 * 4"
val lexemes = CalcLexer.tokenize(input).getOrThrow
val result = CalcParser.parse(lexemes).getOrThrow
println(result) // 33.0 (1.0 + 8.0 * 4.0)

Exercises

Add a modulo operator (%) with the same precedence as * and /
Add variable assignment (x = expr) with right-associative binding
Add cos, tan, and sqrt functions

In this article

Generated with

made with ❤️ and coffee