Module:ColinTheCat/Expression

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 = {}

UnaryExpr = {}

function UnaryExpr:new(o)
  o = o or {}
  setmetatable(o, self)
  self.__index = self
  return o
end

function UnaryExpr:eval(cx)
  return self:_eval(self.a:eval(cx))
end

BinaryExpr = {}

function BinaryExpr:new(o)
  o = o or {}
  setmetatable(o, self)
  self.__index = self
  return o
end

function BinaryExpr:eval(cx)
  return self:_eval(self.a:eval(cx), self.b:eval(cx))
end

AddExpr = BinaryExpr:new()

function AddExpr:_eval(a, b) return a + b end

SubExpr = BinaryExpr:new()

function SubExpr:_eval(a, b) return a - b end

MulExpr = BinaryExpr:new()

function MulExpr:_eval(a, b) return a * b end

DivExpr = BinaryExpr:new()

function DivExpr:_eval(a, b) return a / b end

PowExpr = BinaryExpr:new()

function PowExpr:_eval(a, b) return math.pow(a, b) end

CallExpr = {}

function CallExpr:new(o)
  o = o or {}
  setmetatable(o, self)
  self.__index = self
  return o
end

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)(unpack(eval_args))
end

VarExpr = {}

function VarExpr:new(o)
  o = o or {}
  setmetatable(o, self)
  self.__index = self
  return o
end

function VarExpr:eval(cx)
  assert(cx, "Variables require a context")
  assert(cx.lookup, "Missing variable lookup function")
  return cx:lookup(self.name)
end

ConstExpr = {}

function ConstExpr:new(o)
  o = o or {}
  setmetatable(o, self)
  self.__index = self
  return o
end

function ConstExpr:eval(cx)
  return self.value
end

p.Tokenizer = {}

function p.Tokenizer:new(o)
  o = o or {}
  setmetatable(o, self)
  self.__index = self
  return o
end

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("^%p")
  if m then
    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 == "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
  error("Invalid token near: "..str:sub(1, 5))
end

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

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

function parse_type(tokens, accepted)
  local token = tokens:peek()
  if token and token.type == accepted then
    tokens:eat()
    return token.value
  end
end

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

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

local function parse_var(tokens)
  local next = tokens:next()
  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

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 = tokens:peek()
  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)
      peek = tokens:peek()
      if not peek or 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

local parse_pow = make_parse_binary({["^"]=PowExpr}, parse_call, false)
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)

function p.parse_expr(tokens)
  return parse_add_sub(tokens)
end

function p.Eval(frame)
  local tok = p.Tokenizer:new{str=frame.args[1]}
  local vars = mw.text.jsonDecode(frame.args[2] or "{}")

  local expr = p.parse_expr(tok)

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

  return expr:eval(cx)
end

return p