Module:ColinTheCat/Expression: Difference between revisions

From Resonite Wiki
Expression parser module
 
No edit summary
 
(9 intermediate revisions by the same user not shown)
Line 1: Line 1:
-- This is an expression interpreter. For example, "2 * (1 + min(10, 2))" evaluates to 6
---This is an expression interpreter. For example, "2 * (1 + min(10, 2))" evaluates to 6
-- Variable lookup needs to be implemented externally and supplied by :lookup(name)
---Variable lookup needs to be implemented externally and supplied by :lookup(name)
-- through the context cx given to Expression:eval(cx).
---through the context cx given to Expression:eval(cx).
local p = {}


local p = {}
---@diagnostic disable-next-line: deprecated
local table_unpack = table.unpack or unpack


UnaryExpr = {}
---@alias Context {lookup: fun(self: self, name: string)}


function UnaryExpr:new(o)
---@class Expr
---@field eval fun(self: Expr, cx: Context): any
Expr = {}
function Expr:new(o)
   o = o or {}
   o = o or {}
   setmetatable(o, self)
   setmetatable(o, self)
Line 14: Line 19:
end
end


---@class UnaryExpr:Expr
---@field a Expr
---@field new fun(self: self, o?: UnaryExpr): UnaryExpr
---@field _eval fun(self: self, a: any): any
UnaryExpr = Expr:new()
---@param cx Context
---@return any
function UnaryExpr:eval(cx)
function UnaryExpr:eval(cx)
   return self:_eval(self.a:eval(cx))
   return self:_eval(self.a:eval(cx))
end
end


BinaryExpr = {}
---@class MinusExpr:UnaryExpr
 
---@field new fun(self: self, o: {a: any}): MinusExpr
function BinaryExpr:new(o)
MinusExpr = UnaryExpr:new()
  o = o or {}
function MinusExpr:_eval(a) return -a end
  setmetatable(o, self)
  self.__index = self
  return o
end


---@class BinaryExpr:Expr
---@field a Expr
---@field b Expr
---@field new fun(self: self, o?: {a: Expr, b: Expr}): self
---@field _eval fun(self: BinaryExpr, a: any, b: any): any
BinaryExpr = Expr:new()
---@param cx Context
---@return any
function BinaryExpr:eval(cx)
function BinaryExpr:eval(cx)
   return self:_eval(self.a:eval(cx), self.b:eval(cx))
   return self:_eval(self.a:eval(cx), self.b:eval(cx))
end
end


---@class AddExpr:BinaryExpr
---@field new fun(self: self, o: {a: Expr, b: Expr}): self
AddExpr = BinaryExpr:new()
AddExpr = BinaryExpr:new()
function AddExpr:_eval(a, b) return a + b end


function AddExpr:_eval(a, b) return a + b end
---@class ModExpr:BinaryExpr
---@field new fun(self: self, o: {a: Expr, b: Expr}): self
ModExpr = BinaryExpr:new()
function ModExpr:_eval(a, b) return a % b end


---@class SubExpr:BinaryExpr
---@field new fun(self: self, o: {a: Expr, b: Expr}): self
SubExpr = BinaryExpr:new()
SubExpr = BinaryExpr:new()
function SubExpr:_eval(a, b) return a - b end
function SubExpr:_eval(a, b) return a - b end


---@class MulExpr:BinaryExpr
---@field new fun(self: self, o: {a: Expr, b: Expr}): self
MulExpr = BinaryExpr:new()
MulExpr = BinaryExpr:new()
function MulExpr:_eval(a, b) return a * b end
function MulExpr:_eval(a, b) return a * b end


---@class DivExpr:BinaryExpr
---@field new fun(self: self, o: {a: Expr, b: Expr}): self
DivExpr = BinaryExpr:new()
DivExpr = BinaryExpr:new()
function DivExpr:_eval(a, b) return a / b end
function DivExpr:_eval(a, b) return a / b end


---@class PowExpr:BinaryExpr
---@field new fun(self: self, o: {a: Expr, b: Expr}): self
PowExpr = BinaryExpr:new()
PowExpr = BinaryExpr:new()
function PowExpr:_eval(a, b) return a ^ b end


function PowExpr:_eval(a, b) return math.pow(a, b) end
---@class CallExpr:Expr
 
---@field func Expr
CallExpr = {}
---@field args Expr[]
 
---@field new fun(self: self, o: {func: Expr, args: Expr[]}): self
function CallExpr:new(o)
CallExpr = Expr:new()
  o = o or {}
---@param cx Context
  setmetatable(o, self)
---@return any
  self.__index = self
  return o
end
 
function CallExpr:eval(cx)
function CallExpr:eval(cx)
   local eval_args = {}
   local eval_args = {}
Line 65: Line 89:
     eval_args[i] = arg:eval(cx)
     eval_args[i] = arg:eval(cx)
   end
   end
   return self.func:eval(cx)(table.unpack(eval_args))
   return self.func:eval(cx)(table_unpack(eval_args))
end
 
VarExpr = {}
 
function VarExpr:new(o)
  o = o or {}
  setmetatable(o, self)
  self.__index = self
  return o
end
end


---@class VarExpr:Expr
---@field name string
---@field new fun(self: self, o: {name: string}): self
VarExpr = Expr:new()
---@param cx Context
---@return any
function VarExpr:eval(cx)
function VarExpr:eval(cx)
  assert(cx, "Variables require a context")
  assert(cx.lookup, "Missing variable lookup function")
   return cx:lookup(self.name)
   return cx:lookup(self.name)
end
end


ConstExpr = {}
---@class ConstExpr:Expr
 
---@field value any
function ConstExpr:new(o)
---@field new fun(self:self, o: {value: any}): self
  o = o or {}
ConstExpr = Expr:new()
  setmetatable(o, self)
---@param cx Context
  self.__index = self
---@return any
  return o
end
 
function ConstExpr:eval(cx)
function ConstExpr:eval(cx)
   return self.value
   return self.value
end
end


---@class Tokenizer
---@field str string
p.Tokenizer = {}
p.Tokenizer = {}


---Create a new tokenizer
---@param o {str: string}
---@return Tokenizer
function p.Tokenizer:new(o)
function p.Tokenizer:new(o)
   o = o or {}
   o = o or {}
Line 103: Line 128:
end
end


---Retrieves the next token without consuming
---@return {type: string, value: any, offset: number, length: number}|nil
function p.Tokenizer:peek()
function p.Tokenizer:peek()
   if self.peeked then return self.peeked end
   if self.peeked then return self.peeked end
Line 109: Line 136:
   local offset = 1 + #self.str - #str
   local offset = 1 + #self.str - #str
   local m
   local m
  m = str:match('^"([^"]*)"')
  if m then
    self.peeked = { type = "lit", value = m, offset = offset, length = #m + 2 }
    return self.peeked
  end
   m = str:match("^%p")
   m = str:match("^%p")
   if m then
   if m then
     self.peeked = {type="punct",value=m,offset=offset,length=1}
    if m == '"' then
      error("Unclosed string near: " .. str)
    end
     self.peeked = { type = "punct", value = m, offset = offset, length = 1 }
     return self.peeked
     return self.peeked
   end
   end
   m = str:match("^%a[%a%d]*")
   m = str:match("^%a[%a%d]*")
   if m then
   if m then
     self.peeked = {type="name",value=m,offset=offset,length=#m}
     self.peeked = { type = "name", value = m, offset = offset, length = #m }
     return self.peeked
     return self.peeked
   end
   end
   m = str:match("^[%d%.]+")
   m = str:match("^[%d%.]+")
   if m == "0" or m:match("^[1-9]%d*$") or m:match("^[1-9]%d*%.%d+$") then
   if m then
    self.peeked = {type="lit",value=tonumber(m),offset=offset,length=#m}
    if m == "0" or m:match("^[1-9]%d*$") or m:match("^0%.%d+$") or m:match("^[1-9]%d*%.%d+$") then
    return self.peeked
      self.peeked = { type = "lit", value = tonumber(m), offset = offset, length = #m }
  else error("Invalid numeric literal: "..m) end
      return self.peeked
   error("Invalid token near: "..str:sub(1, 5))
    else
      error("Invalid numeric literal: " .. m)
    end
  end
 
   error("Invalid token near: " .. str:sub(1, 5))
end
end


---Consumes the currently peeked token
function p.Tokenizer:eat()
function p.Tokenizer:eat()
   local token = self.peeked
   local token = self.peeked
Line 135: Line 180:
end
end


---Retrieves the next token
---@return {type: string, value: any, offset: number, length: number}|nil
function p.Tokenizer:next()
function p.Tokenizer:next()
   local token = self:peek()
   local token = self:peek()
Line 148: Line 195:


function p.Tokenizer:syntax_error_message()
function p.Tokenizer:syntax_error_message()
   return "Invalid syntax near: "..self.str:sub(1, 10)
   return "Invalid syntax near: " .. self.str:sub(1, 10)
end
end


function parse_type(tokens, accepted)
---Parses a token of the given types
---@param tokens Tokenizer
---@param accepted string
---@return any|nil value The token value if it was found or nil
local function parse_type(tokens, accepted)
   local token = tokens:peek()
   local token = tokens:peek()
   if token.type == accepted then
   if token and token.type == accepted then
     tokens:eat()
     tokens:eat()
     return token.value
     return token.value
Line 159: Line 210:
end
end


function parse_punct(tokens, punct)
---Parses a punctuation token with the given symbol
---@param tokens Tokenizer
---@param punct string
---@return string|nil
local function parse_punct(tokens, punct)
   local token = tokens:peek()
   local token = tokens:peek()
   if token.type == "punct" and token.value == punct then
   if token and token.type == "punct" and token.value == punct then
     tokens:eat()
     tokens:eat()
     return punct
     return punct
Line 167: Line 222:
end
end


function make_parse_binary(ops, parse_next, rec)
---Creates a parses function for a binary expression
---@param ops table<string, BinaryExpr> Map from operator to expression type
---@param parse_next fun(tokens: Tokenizer): Expr|nil
---@param rec any
---@return fun(tokens: Tokenizer): Expr|nil
local function make_parse_binary(ops, parse_next, rec)
   local function parse_binary(tokens)
   local function parse_binary(tokens)
     local a = parse_next(tokens)
     local a = parse_next(tokens)
Line 177: Line 237:
     tokens:eat()
     tokens:eat()
     local b = assert((rec and parse_binary or parse_next)(tokens), tokens:syntax_error_message())
     local b = assert((rec and parse_binary or parse_next)(tokens), tokens:syntax_error_message())
     return Op:new{a=a, b=b}
     return Op:new { a = a, b = b }
   end
   end
   return parse_binary
   return parse_binary
end
end


---Parses a variable expression
---@param tokens Tokenizer
---@return Expr|nil
local function parse_var(tokens)
local function parse_var(tokens)
   local next = tokens:next()
   local next = tokens:next()
   if next.type == "name" then return VarExpr:new{name=next.value} end
  if not next then return end
   if next.type == "lit" then return ConstExpr:new{value=next.value} end
   if next.type == "name" then return VarExpr:new { name = next.value } end
   if next.type == "lit" then return ConstExpr:new { value = next.value } end
   if next.type == "punct" and next.value == "(" then
   if next.type == "punct" and next.value == "(" then
     local expr = assert(p.parse_expr(tokens), tokens:syntax_error_message())
     local expr = assert(p.parse_expr(tokens), tokens:syntax_error_message())
Line 193: Line 257:
end
end


---Parses a call expression
---@param tokens Tokenizer
---@return Expr|nil
local function parse_call(tokens)
local function parse_call(tokens)
   local name = parse_type(tokens, "name")
   local name = parse_type(tokens, "name")
   if not name then return parse_var(tokens) end
   if not name then return parse_var(tokens) end
   local func = VarExpr:new{name=name}
   local func = VarExpr:new { name = name }
   if not parse_punct(tokens, "(") then return func end
   if not parse_punct(tokens, "(") then return func end
   local args = {}
   local args = {}
   local peek = tokens:peek()
   local peek = assert(tokens:peek(), tokens:syntax_error_message())
   if peek.type == "punct" and peek.value == ")" then
   if peek.type == "punct" and peek.value == ")" then
     tokens:eat()
     tokens:eat()
Line 207: Line 274:
       local arg = assert(p.parse_expr(tokens), tokens:syntax_error_message())
       local arg = assert(p.parse_expr(tokens), tokens:syntax_error_message())
       table.insert(args, arg)
       table.insert(args, arg)
       peek = tokens:peek()
       local peek = tokens:peek()
       if not peek or peek.type ~= "punct" then error(tokens:syntax_error_message()) end
       if not (peek and peek.type == "punct") then error(tokens:syntax_error_message()) end
       if peek.value == ")" then done = true
       if peek.value == ")" then
       else assert(peek.value == ",", tokens:syntax_error_message()) end
        done = true
       else
        assert(peek.value == ",", tokens:syntax_error_message())
      end
       tokens:eat()
       tokens:eat()
     until done
     until done
   end
   end
   return CallExpr:new{func=func, args=args}
   return CallExpr:new { func = func, args = args }
end
 
---Parses a unary minus expression
---@param tokens Tokenizer
---@return Expr|nil
local function parse_minus(tokens)
  if parse_punct(tokens, "-") then
    local expr = assert(parse_call(tokens), tokens:syntax_error_message())
    return MinusExpr:new { a = expr }
  end
  return parse_call(tokens)
end
end


local parse_pow = make_parse_binary({["^"]=PowExpr}, parse_call, false)
local parse_pow = make_parse_binary({ ["^"] = PowExpr }, parse_minus, false)
local parse_mul_div = make_parse_binary({["*"]=MulExpr, ["/"]=DivExpr}, parse_pow, true)
local parse_mul_div = make_parse_binary({ ["*"] = MulExpr, ["/"] = DivExpr }, parse_pow, true)
local parse_add_sub = make_parse_binary({["+"]=AddExpr, ["-"]=SubExpr}, parse_mul_div, true)
local parse_mod = make_parse_binary({ ["%"] = ModExpr }, parse_mul_div, false)
local parse_add_sub = make_parse_binary({ ["+"] = AddExpr, ["-"] = SubExpr }, parse_mod, true)


---Parses a variable expression
---@param tokens Tokenizer
---@return Expr|nil
function p.parse_expr(tokens)
function p.parse_expr(tokens)
   return parse_add_sub(tokens)
   return parse_add_sub(tokens)
Line 226: Line 311:


function p.Eval(frame)
function p.Eval(frame)
   local tok = p.Tokenizer:new{str=frame.args[1]}
   local tok = p.Tokenizer:new { str = frame.args[1] }
  ---@type table<string, any>
   local vars = mw.text.jsonDecode(frame.args[2] or "{}")
   local vars = mw.text.jsonDecode(frame.args[2] or "{}")


   local expr = p.parse_expr(tok)
   local expr = assert(p.parse_expr(tok), "Invalid expression: " .. tok.str)
  if tok:peek() then error("Leftover tokens: " .. tok.str) end


   local cx = {}
   local cx = {}
  ---@param name string
   function cx:lookup(name)
   function cx:lookup(name)
     return vars[name] or math[name] or error("Variable not found: "..name)
     return vars[name] or math[name] or error("Variable not found: " .. name)
   end
   end



Latest revision as of 20:06, 12 February 2024

EBNF Grammar

What's EBNF?

For a graphical representation, take a look at this website.

Expr  ::= Add
Add   ::= Mod (PlusMinus Add)?
Mod   ::= Mul ('%' Mul)?
Mul   ::= Pow (MulDiv Mul)?
Pow   ::= Minus ('^' Minus)?
Minus ::= '-'? Call
Call  ::= Var | Name ('(' Args ')')?
Var   ::= Name | Num | Str | '(' Expr ')'

Args ::= Expr (',' Expr)?

PlusMinus ::= [+-]                           /* ws: explicit */
MulDiv    ::= [*/]                           /* ws: explicit */
Num       ::= ('0' | [1-9]+) ('.' [0-9]+)?   /* ws: explicit */
Str       ::= '"' [^"]* '"'                  /* ws: explicit */
Name      ::= [a-z] [a-z0-9_]*               /* ws: explicit */

Example

{{#invoke:ColinTheCat/Expression|Eval
| 2 * (1 + min(10, x))
| {"x": 2}
}}

2 * (1 + min(10, x)) (x=2) evaluates to 6


---This is an expression interpreter. For example, "2 * (1 + min(10, 2))" evaluates to 6
---Variable lookup needs to be implemented externally and supplied by :lookup(name)
---through the context cx given to Expression:eval(cx).
local p = {}

---@diagnostic disable-next-line: deprecated
local table_unpack = table.unpack or unpack

---@alias Context {lookup: fun(self: self, name: string)}

---@class Expr
---@field eval fun(self: Expr, cx: Context): any
Expr = {}
function Expr:new(o)
  o = o or {}
  setmetatable(o, self)
  self.__index = self
  return o
end

---@class UnaryExpr:Expr
---@field a Expr
---@field new fun(self: self, o?: UnaryExpr): UnaryExpr
---@field _eval fun(self: self, a: any): any
UnaryExpr = Expr:new()
---@param cx Context
---@return any
function UnaryExpr:eval(cx)
  return self:_eval(self.a:eval(cx))
end

---@class MinusExpr:UnaryExpr
---@field new fun(self: self, o: {a: any}): MinusExpr
MinusExpr = UnaryExpr:new()
function MinusExpr:_eval(a) return -a end

---@class BinaryExpr:Expr
---@field a Expr
---@field b Expr
---@field new fun(self: self, o?: {a: Expr, b: Expr}): self
---@field _eval fun(self: BinaryExpr, a: any, b: any): any
BinaryExpr = Expr:new()
---@param cx Context
---@return any
function BinaryExpr:eval(cx)
  return self:_eval(self.a:eval(cx), self.b:eval(cx))
end

---@class AddExpr:BinaryExpr
---@field new fun(self: self, o: {a: Expr, b: Expr}): self
AddExpr = BinaryExpr:new()
function AddExpr:_eval(a, b) return a + b end

---@class ModExpr:BinaryExpr
---@field new fun(self: self, o: {a: Expr, b: Expr}): self
ModExpr = BinaryExpr:new()
function ModExpr:_eval(a, b) return a % b end

---@class SubExpr:BinaryExpr
---@field new fun(self: self, o: {a: Expr, b: Expr}): self
SubExpr = BinaryExpr:new()
function SubExpr:_eval(a, b) return a - b end

---@class MulExpr:BinaryExpr
---@field new fun(self: self, o: {a: Expr, b: Expr}): self
MulExpr = BinaryExpr:new()
function MulExpr:_eval(a, b) return a * b end

---@class DivExpr:BinaryExpr
---@field new fun(self: self, o: {a: Expr, b: Expr}): self
DivExpr = BinaryExpr:new()
function DivExpr:_eval(a, b) return a / b end

---@class PowExpr:BinaryExpr
---@field new fun(self: self, o: {a: Expr, b: Expr}): self
PowExpr = BinaryExpr:new()
function PowExpr:_eval(a, b) return a ^ b end

---@class CallExpr:Expr
---@field func Expr
---@field args Expr[]
---@field new fun(self: self, o: {func: Expr, args: Expr[]}): self
CallExpr = Expr:new()
---@param cx Context
---@return any
function CallExpr:eval(cx)
  local eval_args = {}
  for i, arg in ipairs(self.args) do
    eval_args[i] = arg:eval(cx)
  end
  return self.func:eval(cx)(table_unpack(eval_args))
end

---@class VarExpr:Expr
---@field name string
---@field new fun(self: self, o: {name: string}): self
VarExpr = Expr:new()
---@param cx Context
---@return any
function VarExpr:eval(cx)
  assert(cx, "Variables require a context")
  assert(cx.lookup, "Missing variable lookup function")
  return cx:lookup(self.name)
end

---@class ConstExpr:Expr
---@field value any
---@field new fun(self:self, o: {value: any}): self
ConstExpr = Expr:new()
---@param cx Context
---@return any
function ConstExpr:eval(cx)
  return self.value
end

---@class Tokenizer
---@field str string
p.Tokenizer = {}

---Create a new tokenizer
---@param o {str: string}
---@return Tokenizer
function p.Tokenizer:new(o)
  o = o or {}
  setmetatable(o, self)
  self.__index = self
  return o
end

---Retrieves the next token without consuming
---@return {type: string, value: any, offset: number, length: number}|nil
function p.Tokenizer:peek()
  if self.peeked then return self.peeked end
  local str = self.str:match("^%s*(.-)$")
  if #str == 0 then return end
  local offset = 1 + #self.str - #str
  local m

  m = str:match('^"([^"]*)"')
  if m then
    self.peeked = { type = "lit", value = m, offset = offset, length = #m + 2 }
    return self.peeked
  end

  m = str:match("^%p")
  if m then
    if m == '"' then
      error("Unclosed string near: " .. str)
    end
    self.peeked = { type = "punct", value = m, offset = offset, length = 1 }
    return self.peeked
  end

  m = str:match("^%a[%a%d]*")
  if m then
    self.peeked = { type = "name", value = m, offset = offset, length = #m }
    return self.peeked
  end

  m = str:match("^[%d%.]+")
  if m then
    if m == "0" or m:match("^[1-9]%d*$") or m:match("^0%.%d+$") or m:match("^[1-9]%d*%.%d+$") then
      self.peeked = { type = "lit", value = tonumber(m), offset = offset, length = #m }
      return self.peeked
    else
      error("Invalid numeric literal: " .. m)
    end
  end

  error("Invalid token near: " .. str:sub(1, 5))
end

---Consumes the currently peeked token
function p.Tokenizer:eat()
  local token = self.peeked
  if token then
    self.str = self.str:sub(token.offset + token.length)
    self.peeked = nil
  end
end

---Retrieves the next token
---@return {type: string, value: any, offset: number, length: number}|nil
function p.Tokenizer:next()
  local token = self:peek()
  self:eat()
  return token
end

function p.Tokenizer:iter()
  return function()
    return self:next()
  end
end

function p.Tokenizer:syntax_error_message()
  return "Invalid syntax near: " .. self.str:sub(1, 10)
end

---Parses a token of the given types
---@param tokens Tokenizer
---@param accepted string
---@return any|nil value The token value if it was found or nil
local function parse_type(tokens, accepted)
  local token = tokens:peek()
  if token and token.type == accepted then
    tokens:eat()
    return token.value
  end
end

---Parses a punctuation token with the given symbol
---@param tokens Tokenizer
---@param punct string
---@return string|nil
local function parse_punct(tokens, punct)
  local token = tokens:peek()
  if token and token.type == "punct" and token.value == punct then
    tokens:eat()
    return punct
  end
end

---Creates a parses function for a binary expression
---@param ops table<string, BinaryExpr> Map from operator to expression type
---@param parse_next fun(tokens: Tokenizer): Expr|nil
---@param rec any
---@return fun(tokens: Tokenizer): Expr|nil
local function make_parse_binary(ops, parse_next, rec)
  local function parse_binary(tokens)
    local a = parse_next(tokens)
    if not a then return end
    local peek = tokens:peek()
    if not peek or peek.type ~= "punct" then return a end
    local Op = ops[peek.value]
    if not Op then return a end
    tokens:eat()
    local b = assert((rec and parse_binary or parse_next)(tokens), tokens:syntax_error_message())
    return Op:new { a = a, b = b }
  end
  return parse_binary
end

---Parses a variable expression
---@param tokens Tokenizer
---@return Expr|nil
local function parse_var(tokens)
  local next = tokens:next()
  if not next then return end
  if next.type == "name" then return VarExpr:new { name = next.value } end
  if next.type == "lit" then return ConstExpr:new { value = next.value } end
  if next.type == "punct" and next.value == "(" then
    local expr = assert(p.parse_expr(tokens), tokens:syntax_error_message())
    if parse_punct(tokens, ")") then return expr end
  end
  error(tokens:syntax_error_message())
end

---Parses a call expression
---@param tokens Tokenizer
---@return Expr|nil
local function parse_call(tokens)
  local name = parse_type(tokens, "name")
  if not name then return parse_var(tokens) end
  local func = VarExpr:new { name = name }
  if not parse_punct(tokens, "(") then return func end
  local args = {}
  local peek = assert(tokens:peek(), tokens:syntax_error_message())
  if peek.type == "punct" and peek.value == ")" then
    tokens:eat()
  else
    local done = false
    repeat
      local arg = assert(p.parse_expr(tokens), tokens:syntax_error_message())
      table.insert(args, arg)
      local peek = tokens:peek()
      if not (peek and peek.type == "punct") then error(tokens:syntax_error_message()) end
      if peek.value == ")" then
        done = true
      else
        assert(peek.value == ",", tokens:syntax_error_message())
      end
      tokens:eat()
    until done
  end
  return CallExpr:new { func = func, args = args }
end

---Parses a unary minus expression
---@param tokens Tokenizer
---@return Expr|nil
local function parse_minus(tokens)
  if parse_punct(tokens, "-") then
    local expr = assert(parse_call(tokens), tokens:syntax_error_message())
    return MinusExpr:new { a = expr }
  end
  return parse_call(tokens)
end

local parse_pow = make_parse_binary({ ["^"] = PowExpr }, parse_minus, false)
local parse_mul_div = make_parse_binary({ ["*"] = MulExpr, ["/"] = DivExpr }, parse_pow, true)
local parse_mod = make_parse_binary({ ["%"] = ModExpr }, parse_mul_div, false)
local parse_add_sub = make_parse_binary({ ["+"] = AddExpr, ["-"] = SubExpr }, parse_mod, true)

---Parses a variable expression
---@param tokens Tokenizer
---@return Expr|nil
function p.parse_expr(tokens)
  return parse_add_sub(tokens)
end

function p.Eval(frame)
  local tok = p.Tokenizer:new { str = frame.args[1] }
  ---@type table<string, any>
  local vars = mw.text.jsonDecode(frame.args[2] or "{}")

  local expr = assert(p.parse_expr(tok), "Invalid expression: " .. tok.str)
  if tok:peek() then error("Leftover tokens: " .. tok.str) end

  local cx = {}
  ---@param name string
  function cx:lookup(name)
    return vars[name] or math[name] or error("Variable not found: " .. name)
  end

  return expr:eval(cx)
end

return p