No edit summary |
No edit summary |
||
Line 78: | Line 78: | ||
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 |
Revision as of 01:30, 12 February 2024
EBNF Grammar
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