local len, match = string.len, string.match local mini_lexer = {} local mini_lexer_mt = { __index = mini_lexer, } local literal_chars = {['('] = 1, [')'] = 1, ['~'] = 1, [','] = 1} local oper_table = {['+'] = 0, ['-'] = 0, ['*'] = 1, ['/'] = 1, ['^'] = 2} local function new_lexer(src) local lexer = {n = 1, src= src} setmetatable(lexer, mini_lexer_mt) lexer:next() return lexer end function mini_lexer.char(lexer) local n = lexer.n return lexer.src:sub(n, n) end function mini_lexer.consume(lexer, char) local c = lexer:char() assert(c == char, "expecting character " .. char) lexer.n = lexer.n + 1 end function mini_lexer.incr(lexer, n) lexer.n = lexer.n + (n or 1) end function mini_lexer.match(lexer, pattern) return match(lexer.src, '^' .. pattern, lexer.n) end function mini_lexer.consume(lexer, pattern) local m = match(lexer.src, '^' .. pattern, lexer.n) if m then lexer.n = lexer.n + len(m) return m end end function mini_lexer.next_token(lexer) lexer:consume('%s*') if lexer.n> len(lexer.src) then return {type= 'EOF'} end local c = lexer:char() if c == '[' then local str = lexer:consume('%b[]') return {type= 'ident', value= str:sub(2,-2)} end if oper_table[c] then local prio = oper_table[c] lexer:incr() return {type= 'operator', symbol= c, priority = prio} end if literal_chars[c] then lexer:incr() return {type= c} end if lexer:match('[%l%u_]') then local str = lexer:consume('[%l%u_][%w_]*') return {type= 'ident', value= str} end if lexer:match('[1-9]') then local str = lexer:consume('[1-9]%d*%.%d*') if not str then str = lexer:consume('[1-9]%d*') end return {type= 'number', value= tonumber(str)} end msg = { "syntax error in expression:", string.format(' %s', lexer.src), string.format(' %s^', string.rep(' ', lexer.n - 1)) } error(table.concat(msg, '\n')) end function mini_lexer.next(lexer) lexer.token = lexer:next_token() end local function accept(lexer, token_type) if lexer.token.type == token_type then lexer:next() return 1 end return 0 end local function expect(lexer, token_type) if accept(lexer, token_type) == 0 then error("expecting " .. token_type) end end local expr local function factor(lexer, actions) local token = lexer.token if token.type == 'ident' then local id = token.value lexer:next() return actions.ident(id) elseif token.type == 'number' then local x = token.value lexer:next() return actions.number(x) elseif token.type == '(' then lexer:next() local a = expr(lexer, actions, 0) expect(lexer, ')') return a end error('expecting variable or number') end expr = function(lexer, actions, prio) if prio> 2 then return factor(lexer, actions) end local a local token = lexer.token if prio == 0 and token.type == 'operator' and token.symbol == '-' then local symbol = token.symbol lexer:next() local b = expr(lexer, actions, prio + 1) a = actions.prefix(symbol, b) else a = expr(lexer, actions, prio + 1) end token = lexer.token while token.type == 'operator' and token.priority>= prio do local symbol = token.symbol accept(lexer, 'operator') local b = expr(lexer, actions, prio + 1) a, token = actions.infix(symbol, a, b), lexer.token end return a end local function expr_list(lexer, actions) local a = expr(lexer, actions, 0) local els = actions.exprlist(a) while accept(lexer, ',')> 0 do local b = expr(lexer, actions, 0) els = actions.exprlist(b, els) end return els end local function schema(lexer, actions) local y = expr(lexer, actions, 0) expect(lexer, '~') local x = expr_list(lexer, actions) return actions.schema(x, y) end local function parse_expr(lexer, actions) return expr(lexer, actions, 0) end return {lexer = new_lexer, schema= schema, parse = parse_expr}