author | Francesco Abbate <francesco.bbt@gmail.com> | 2013年05月10日 18:07:56 +0200 |
---|---|---|
committer | Francesco Abbate <francesco.bbt@gmail.com> | 2013年05月10日 18:07:56 +0200 |
commit | 204fa404431f9c619f0dfc5ae3efc463749fa8ed (patch) | |
tree | 825fc39707d7c7b3e734c5ffb3fd04af8f325530 | |
parent | 58dd27ba0c1776644db561cc4d565a281e2f7b2b (diff) | |
download | gsl-shell-204fa404431f9c619f0dfc5ae3efc463749fa8ed.tar.gz |
-rw-r--r-- | expr-actions.lua | 20 | ||||
-rw-r--r-- | expr-lexer.lua | 93 | ||||
-rw-r--r-- | expr-parse.lua | 150 | ||||
-rw-r--r-- | expr-parser.lua | 238 | ||||
-rw-r--r-- | expr-print.lua | 5 | ||||
-rw-r--r-- | gdt-expr.lua | 57 | ||||
-rw-r--r-- | gdt-lm.lua | 40 | ||||
-rw-r--r-- | gdt-plot.lua | 65 |
diff --git a/expr-actions.lua b/expr-actions.lua index 79862f97..17fc015e 100644 --- a/expr-actions.lua +++ b/expr-actions.lua @@ -1,4 +1,6 @@ +local type = type + local function mult(a, b) if a == 1 then return b end if b == 1 then return a end @@ -27,6 +29,21 @@ end local function ident_action(id) return id end +-- return true iff expr is a variable (with enums or not). +-- if it is a variable returns, in addition, the var_name and the enumeration flag +local function is_variable(expr) + if type(expr) == 'string' then + local esc_name = string.match(expr, "^%%(.*)") + return true, esc_name or expr, (esc_name ~= nil) + else + return false + end +end + +local function is_number(expr) + return type(expr) == 'number' +end + return { infix = infix_action, ident = ident_action, @@ -36,4 +53,7 @@ return { number = function(x) return x end, exprlist = function(a, ls) if ls then ls[#ls+1] = a else ls = {a} end; return ls end, schema = function(x, y, conds) return {x= x, y= y, conds= conds} end, + + is_variable = is_variable, + is_number = is_number, } diff --git a/expr-lexer.lua b/expr-lexer.lua new file mode 100644 index 00000000..c075d8a5 --- /dev/null +++ b/expr-lexer.lua @@ -0,0 +1,93 @@ +local len, match = string.len, string.match + +local expr_lexer = {} + +local lexer_mt = { + __index = expr_lexer, +} + +local literal_chars = {['('] = 1, [')'] = 1, ['~'] = 1, [','] = 1, ['|'] = 1, [':'] = 1} + +local oper_table = {['+'] = 0, ['-'] = 0, ['*'] = 1, ['/'] = 1, ['^'] = 2, ['='] = 3, ['>'] = 3, ['<'] = 3, ['%'] = -1} + +expr_lexer.operators = oper_table +expr_lexer.max_oper_prio = 3 + +function expr_lexer.new(src) + local lexer = {n = 1, src= src} + setmetatable(lexer, lexer_mt) + lexer:next() + return lexer +end + +function expr_lexer.char(lexer) + local n = lexer.n + return lexer.src:sub(n, n) +end + +function expr_lexer.incr(lexer, n) + lexer.n_current = lexer.n + lexer.n = lexer.n + (n or 1) +end + +function expr_lexer.match(lexer, pattern) + return match(lexer.src, '^' .. pattern, lexer.n) +end + +function expr_lexer.consume(lexer, pattern) + local m = match(lexer.src, '^' .. pattern, lexer.n) + if m then + lexer.n_current = lexer.n + lexer.n = lexer.n + len(m) + return m + end +end + +function expr_lexer.skip(lexer, pattern) + local m = match(lexer.src, '^' .. pattern, lexer.n) + if m then lexer.n = lexer.n + len(m) end +end + +function expr_lexer.next_token(lexer) + lexer:skip('%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_][%l%u%d_.$]*') + return {type= 'ident', value= str} + end + if lexer:match('%d') then + local str = lexer:consume('%d+%.%d*[Ee]%+?%d+') + str = str or lexer:consume('%d+%.%d*[Ee]%-?%d+') + str = str or lexer:consume('%d+%.%d*') + str = str or lexer:consume('%d+') + return {type= 'number', value= tonumber(str)} + end + lexer:local_error("syntax error in expression:", lexer.n) +end + +function expr_lexer.next(lexer) + lexer.token = lexer:next_token() +end + +function expr_lexer.local_error(lexer, msg, n_pos) + n_pos = n_pos or lexer.n_current + local line = string.format(' %s', lexer.src) + local pos = string.format(' %s^', string.rep(' ', n_pos - 1)) + error(string.format("%s\n%s\n%s", msg, line, pos)) +end + +return expr_lexer diff --git a/expr-parse.lua b/expr-parse.lua new file mode 100644 index 00000000..20129478 --- /dev/null +++ b/expr-parse.lua @@ -0,0 +1,150 @@ +local expr_lexer = require 'expr-lexer' + +local function accept(lexer, token_type) + if lexer.token.type == token_type then + lexer:next() + return true + end + return false +end + +local function expect(lexer, token_type) + if not accept(lexer, token_type) then + lexer:local_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() + if accept(lexer, '(') then + local arg = expr(lexer, actions, 0) + expect(lexer, ')') + return actions.func_eval(id, arg) + else + return actions.ident(id) + end + 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 + elseif token.type == 'operator' and token.symbol == '%' then + lexer:next() + if lexer.token.type ~= 'ident' then + lexer:local_error("expecting identifier:") + end + local id = lexer.token.value + lexer:next() + return actions.enum(id) + end + lexer:local_error('unexpected symbol:') +end + +local function ident_singleton(lexer, actions) + local token = lexer.token + if token.type == 'ident' then + local id = token.value + lexer:next() + if accept(lexer, '(') then + lexer:local_error('expecting simple identifier') + end + return actions.ident(id) + else + lexer:local_error('expecting simple identifier') + end +end + +local max_oper_prio = expr_lexer.max_oper_prio + +expr = function(lexer, actions, prio) + if prio > max_oper_prio 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, ',') do + local b = expr(lexer, actions, 0) + els = actions.exprlist(b, els) + end + return els +end + +local function ident_list(lexer, actions) + local a = ident_singleton(lexer, actions) + local els = actions.exprlist(a) + while accept(lexer, ',') do + local b = ident_singleton(lexer, actions) + els = actions.exprlist(b, els) + end + return els +end + +local function enums(lexer, actions) + if accept(lexer, '|') then + return ident_list(lexer, actions) + end + return {} +end + +local function conditions(lexer, actions) + if accept(lexer, ':') then + return expr_list(lexer, actions) + end + return {} +end + +local function schema(lexer, actions, accept_enums) + local y = expr(lexer, actions, 0) + expect(lexer, '~') + local x = expr_list(lexer, actions) + local enums = accept_enums and enums(lexer, actions) + local conds = conditions(lexer, actions) + expect(lexer, 'EOF') + return actions.schema(x, y, conds, enums) +end + +local expr_parse = {} + +function expr_parse.schema(formula, actions, accept_enums) + local l = expr_lexer.new(formula) + return schema(l, actions, accept_enums) +end + +function expr_parse.expr(formula, actions) + local l = expr_lexer.new(formula) + return expr(l, actions, 0) +end + +return expr_parse diff --git a/expr-parser.lua b/expr-parser.lua deleted file mode 100644 index 9e9178d9..00000000 --- a/expr-parser.lua +++ /dev/null @@ -1,238 +0,0 @@ - -local len, match = string.len, string.match - -local mini_lexer = {} - -local mini_lexer_mt = { - __index = mini_lexer, -} - -local literal_chars = {['('] = 1, [')'] = 1, ['~'] = 1, [','] = 1, ['|'] = 1, [':'] = 1} -local oper_table = {['+'] = 0, ['-'] = 0, ['*'] = 1, ['/'] = 1, ['^'] = 2, ['='] = 3, ['>'] = 3, ['<'] = 3, ['%'] = -1} -local max_oper_prio = 3 - -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.incr(lexer, n) - lexer.n_current = 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_current = lexer.n - lexer.n = lexer.n + len(m) - return m - end -end - -function mini_lexer.skip(lexer, pattern) - local m = match(lexer.src, '^' .. pattern, lexer.n) - if m then lexer.n = lexer.n + len(m) end -end - -function mini_lexer.next_token(lexer) - lexer:skip('%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_][%l%u%d_.$]*') - return {type= 'ident', value= str} - end - if lexer:match('%d') then - local str = lexer:consume('%d+%.%d*[Ee]%+?%d+') - str = str or lexer:consume('%d+%.%d*[Ee]%-?%d+') - str = str or lexer:consume('%d+%.%d*') - str = str or lexer:consume('%d+') - return {type= 'number', value= tonumber(str)} - end - lexer:local_error("syntax error in expression:", lexer.n) -end - -function mini_lexer.next(lexer) - lexer.token = lexer:next_token() -end - -function mini_lexer.local_error(lexer, msg, n_pos) - n_pos = n_pos or lexer.n_current - local line = string.format(' %s', lexer.src) - local pos = string.format(' %s^', string.rep(' ', n_pos - 1)) - error(string.format("%s\n%s\n%s", msg, line, pos)) -end - -local function accept(lexer, token_type) - if lexer.token.type == token_type then - lexer:next() - return true - end - return false -end - -local function expect(lexer, token_type) - if not accept(lexer, token_type) then - lexer:local_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() - if accept(lexer, '(') then - local arg = expr(lexer, actions, 0) - expect(lexer, ')') - return actions.func_eval(id, arg) - else - return actions.ident(id) - end - 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 - elseif token.type == 'operator' and token.symbol == '%' then - lexer:next() - if lexer.token.type ~= 'ident' then - lexer:local_error("expecting identifier:") - end - local id = lexer.token.value - lexer:next() - return actions.enum(id) - end - lexer:local_error('unexpected symbol:') -end - -local function ident_singleton(lexer, actions) - local token = lexer.token - if token.type == 'ident' then - local id = token.value - lexer:next() - if accept(lexer, '(') then - lexer:local_error('expecting simple identifier') - end - return actions.ident(id) - else - lexer:local_error('expecting simple identifier') - end -end - -expr = function(lexer, actions, prio) - if prio > max_oper_prio 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, ',') do - local b = expr(lexer, actions, 0) - els = actions.exprlist(b, els) - end - return els -end - -local function ident_list(lexer, actions) - local a = ident_singleton(lexer, actions) - local els = actions.exprlist(a) - while accept(lexer, ',') do - local b = ident_singleton(lexer, actions) - 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) - local conds = {} - if accept(lexer, ':') then - conds = expr_list(lexer, actions) - end - if lexer.token.type ~= 'EOF' then - lexer:local_error('unexpected symbol:') - end - return actions.schema(x, y, conds) -end - -local function gschema(lexer, actions) - local y = expr_list(lexer, actions) - expect(lexer, '~') - local x = expr_list(lexer, actions) - local enums - if accept(lexer, '|') then - enums = ident_list(lexer, actions) - else - enums = {} - end - local conds = {} - if accept(lexer, ':') then - conds = expr_list(lexer, actions) - end - if lexer.token.type ~= 'EOF' then - lexer:local_error('unexpected symbol:') - end - return actions.schema(x, y, conds, enums) -end - -local function parse_expr(lexer, actions) - return expr_list(lexer, actions) -end - -return {lexer = new_lexer, schema= schema, gschema= gschema, parse = parse_expr} diff --git a/expr-print.lua b/expr-print.lua index 5d106296..03b1e185 100644 --- a/expr-print.lua +++ b/expr-print.lua @@ -1,7 +1,8 @@ +local expr_lexer = require 'expr-lexer' + local format, concat = string.format, table.concat --- TODO: this information is duplicated from expr-parser => remove the duplication -local oper_table = {['+'] = 0, ['-'] = 0, ['*'] = 1, ['/'] = 1, ['^'] = 2, ['='] = 3, ['>'] = 3, ['<'] = 3, ['%'] = -1} +local oper_table = expr_lexer.operators local ex_print diff --git a/gdt-expr.lua b/gdt-expr.lua index 83050118..17e77799 100644 --- a/gdt-expr.lua +++ b/gdt-expr.lua @@ -1,8 +1,6 @@ -local mini = require 'expr-parser' local expr_print = require 'expr-print' -local AST_actions = require('expr-actions') -local type, pairs, ipairs = type, pairs, ipairs +local pairs, ipairs = pairs, ipairs local gdt_expr = {} @@ -24,7 +22,7 @@ local function level_number(factors, levels) end local function expr_is_unit(e) - return type(e) == 'number' and e == 1 + return e == 1 end local function add_expr_refs(expr, refs) @@ -270,55 +268,4 @@ function gdt_expr.eval_matrix(t, expr_list, y_expr, conditions, annotate) return X, Y, info, index_map end -function var_is_factor(t, var_name) - local esc_name = string.match(var_name, "^%%(.*)") - if esc_name or t:col_type(var_name) == 'factor' then - return true, esc_name or var_name - else - return false, var_name - end -end - -local function expr_find_factors_rec(t, expr, factors) - if type(expr) == 'number' then - return expr - elseif type(expr) == 'string' then - local is_factor, var_name = var_is_factor(t, expr) - if is_factor then - factors[#factors+1] = var_name - return 1 - else - return expr - end - elseif expr.operator == '*' then - local a, b = expr[1], expr[2] - local sa1 = expr_find_factors_rec(t, a, factors) - local sa2 = expr_find_factors_rec(t, b, factors) - return AST_actions.infix('*', sa1, sa2) - else - return expr - end -end - -function gdt_expr.extract_factors(t, expr_list) - local els = {} - for i, e in ipairs(expr_list) do - local et, factors = {}, {} - et.scalar = expr_find_factors_rec(t, e, factors) - if #factors > 0 then et.factor = factors end - els[i] = et - end - return els -end - -function gdt_expr.parse_schema(formula) - local l = mini.lexer(formula) - return mini.schema(l, AST_actions) -end - -function gdt_expr.parse_expr(formula) - local l = mini.lexer(formula) - return mini.parse(l, AST_actions) -end - return gdt_expr diff --git a/gdt-lm.lua b/gdt-lm.lua index 1638ebf1..c5393eb9 100644 --- a/gdt-lm.lua +++ b/gdt-lm.lua @@ -1,10 +1,12 @@ +local expr_parse = require 'expr-parse' local expr_print = require 'expr-print' local gdt_expr = require 'gdt-expr' local check = require 'check' local mon = require 'monomial' +local AST = require 'expr-actions' local sqrt, abs = math.sqrt, math.abs -local type, ipairs = type, ipairs +local ipairs = ipairs local function monomial_to_expr(m, context) local coeff = m[1] @@ -18,7 +20,7 @@ local function monomial_to_expr(m, context) end local function expr_to_monomial(expr, context) - if type(expr) == 'number' then + if AST.is_number(expr) then return {expr} elseif expr.operator == '*' then local a = expr_to_monomial(expr[1], context) @@ -166,8 +168,40 @@ function FIT.eval(fit, tn) return sy end +local function expr_find_factors_rec(t, expr, factors) + if AST.is_number(expr) then + return expr + elseif AST.is_variable(expr) then + local _, var_name, force_enum = AST.is_variable(expr) + if force_enum or t:col_type(var_name) == 'factor' then + factors[#factors+1] = var_name + return 1 + else + return expr + end + elseif expr.operator == '*' then + local a, b = expr[1], expr[2] + local sa1 = expr_find_factors_rec(t, a, factors) + local sa2 = expr_find_factors_rec(t, b, factors) + return AST.infix('*', sa1, sa2) + else + return expr + end +end + +function gdt_expr.extract_factors(t, expr_list) + local els = {} + for i, e in ipairs(expr_list) do + local et, factors = {}, {} + et.scalar = expr_find_factors_rec(t, e, factors) + if #factors > 0 then et.factor = factors end + els[i] = et + end + return els +end + local function lm(t, model_formula, options) - local schema = gdt_expr.parse_schema(model_formula) + local schema = expr_parse.schema(model_formula, AST, false) print("SCHEMA'x xs") for _, e in ipairs(schema.x) do print(e) end diff --git a/gdt-plot.lua b/gdt-plot.lua index 2a02be25..88355145 100644 --- a/gdt-plot.lua +++ b/gdt-plot.lua @@ -1,4 +1,4 @@ -local mini = require 'expr-parser' +local mini = require 'expr-parse' local expr_print = require 'expr-print' local AST_actions = require 'expr-actions' local gdt_expr = require 'gdt-expr' @@ -143,13 +143,13 @@ local function vec2d_incr(r, i, j) return v + 1 end -local function eval_scalar_gen(t) - local i - local id_res = function(expr) return t:get(i, expr.index) end - local func_res = function(expr) return math[expr.func] end - local set = function(ix) i = ix end - return set, {ident= id_res, func= func_res} -end +-- local function eval_scalar_gen(t) +-- local i +-- local id_res = function(expr) return t:get(i, expr.index) end +-- local func_res = function(expr) return math[expr.func] end +-- local set = function(ix) i = ix end +-- return set, {ident= id_res, func= func_res} +-- end local function rect_funcbin(t, jxs, jys, jes) local eval_set, eval_scope = eval_scalar_gen(t) @@ -199,40 +199,6 @@ local function rect_funcbin(t, jxs, jys, jes) return labels, enums, val end -local function infix_ast(sym, a, b) - return {operator= sym, a, b} -end - -local function prefix_ast(sym, a) - return {operator= sym, a} -end - -local function func_eval_ast(func_name, arg_expr) - return {func= func_name, arg= arg_expr} -end - -local function itself(x) return x end - -local function plot_actions_gen(t) - - local function ident_ast(id) - local i = t:col_index(id) - if not i then error('unknown column name: '..id) end - return {name= id, index= i} - end - - return { - infix = infix_ast, - prefix = prefix_ast, - ident = ident_ast, - enum = ident_ast, - func_eval = func_eval_ast, - number = itself, - exprlist = function(a, ls) if ls then ls[#ls+1] = a else ls = {a} end; return ls end, - schema = function(x, y, enums) return {x= x, y= y, enums= enums} end, - } -end - local stat_lookup = { mean = {f = function(accu, x, n) return (accu * (n-1) + x) / n end}, stddev = {f = f_stddev, f0 = || {0, 0, 0}, fini = f_stddev_fini}, @@ -403,17 +369,16 @@ local function expr_get_functions(exprs) return jys end -local function schema_from_plot_descr(plot_descr, t) - local l = mini.lexer(plot_descr) - local actions = plot_actions_gen(t) - return mini.gschema(l, actions) -end +-- local function schema_from_plot_descr(plot_descr, t) +-- local l = mini.lexer(plot_descr) +-- return mini.gschema(l, AST_actions) +-- end local function gdt_table_category_plot(plotter, t, plot_descr, opt) local show_plot = true if opt then show_plot = (opt.show ~= false) end - local schema = schema_from_plot_descr(plot_descr, t) + local schema = gdt_expr.parse_gen_schema(plot_descr) local jxs = idents_get_column_indexes(t, schema.x) local jys = stat_expr_get_functions(schema.y) local jes = idents_get_column_indexes(t, schema.enums) @@ -429,7 +394,7 @@ local function gdt_table_category_plot(plotter, t, plot_descr, opt) end function gdt.xyline(t, plot_descr) - local schema = schema_from_plot_descr(plot_descr, t) + local schema = gdt_expr.parse_gen_schema(plot_descr) local jxs = expr_get_functions(schema.x) local jys = expr_get_functions(schema.y) @@ -464,7 +429,7 @@ local function gdt_table_xyplot(t, plot_descr, opt) local use_lines = opt and opt.lines local use_markers = opt and (opt.markers ~= false) or true - local schema = schema_from_plot_descr(plot_descr, t) + local schema = gdt_expr.parse_gen_schema(plot_descr) local jxs = expr_get_functions(schema.x) local jys = expr_get_functions(schema.y) local jes = idents_get_column_indexes(t, schema.enums) |