exp.lua

--[[
  Simple arithmetic expression parser
  using LPeg with re module
--]]

require 'table.clear' -- luajit extension
local dprint = dbg and print or function() end
local dump = require 'pl.pretty'.dump
local re = require 're'
re.updatelocale()

local ops =
{
  ['+'] = function(lhs, rhs) return lhs + rhs end,
  ['-'] = function(lhs, rhs) return lhs - rhs end,
  ['*'] = function(lhs, rhs) return lhs * rhs end,
  ['/'] = function(lhs, rhs) return lhs / rhs end,
}
local exp_stack = {}
local exp_actions =
{
  push = function(n)
    if type(n) ~= 'table' then
      n = tonumber(n)
    end
    table.insert(exp_stack, n)
    dprint ("push", n)
  end,
  reduce = function(op)
    assert(#exp_stack > 1)
    local rhs = table.remove(exp_stack)
    local lhs = table.remove(exp_stack)
    table.insert(exp_stack, {lhs, rhs, op = ops[op]})
    dprint ("reduce", op)
  end,
  getast = function()
    return exp_stack[1]
  end,
  reset = function() dprint("clearing stack"); table.clear(exp_stack) end
}

local exp = re.compile(
[[
  start   <-  S -> reset (exp !.) -> getast
  exp     <-  term ((TERM_OP term) -> reduce)*
  term    <-  factor ((FACTOR_OP factor) -> reduce)*
  factor  <-  operand
  pexp    <-  LPAREN exp RPAREN
  operand <-  pexp / NUM -> push
  TERM_OP   <-  { '+' / '-' } S
  FACTOR_OP <-  { '*' / '/' } S
  LPAREN    <- '(' S
  RPAREN    <- ')' S
  NUM       <- { '-'?%d+('.'%d+)? } S
  S         <- %s*
]], exp_actions)

local tests =
{
  "42",
  "-42",
  "1 + 2",
  "3*4",
  "3 * 4 - 1",
  "1 + 2 * 5",
  "  -1 + 2 * 5 + (-3 + 8)",
  "42 /0",
}

local function eval(ast)
  if type(ast) == 'number' then return ast end
  local lhs, rhs = eval(ast[1]), eval(ast[2])
  return ast.op(lhs, rhs)
end
for _, v in ipairs(tests) do
  local r = exp:match(v)
  dump(r)
  print( eval(r) )
end