diff options
| -rw-r--r-- | ChangeLog | 10 | ||||
| -rw-r--r-- | regex.c | 35 |
2 files changed, 39 insertions, 6 deletions
@@ -1,5 +1,15 @@ 2010-01-18 Kaz Kylheku <kkylheku@gmail.com> + * regex.c (reg_derivative_list, reg_derivative): Recognition + of cases to reduce consing. In reg_derivative_list, we avoid + consing the full or expression if either branch is t, and + also save a cons when the first element has a null derivative. + In reg_derivative the oneplus and zeroplus cases are split, + since zeroplus can re-use the input expression, when it's + just a one-character match, deriving nil. + +2010-01-18 Kaz Kylheku <kkylheku@gmail.com> + Adjust semantics of non-greedy operator R%S, to avoid the broken case whereby R%S matches nothing at all when S is not empty but equivalent to empty, or more generally when S is nullable. @@ -1243,11 +1243,26 @@ static val reg_derivative_list(val exp_list, val ch) { if (rest(exp_list)) { if (reg_nullable(first(exp_list))) { - return list(or_s, cons(compound_s, - cons(reg_derivative(first(exp_list), ch), - rest(exp_list))), - reg_derivative_list(rest(exp_list), ch), - nao); + val d_first = reg_derivative(first(exp_list), ch); + val d_rest = reg_derivative_list(rest(exp_list), ch); + + if (d_rest == t && d_first == t) + return t; + + if (d_rest == t) + return if3(d_first == nil, + cons(compound_s, rest(exp_list)), + cons(compound_s, cons(d_first, rest(exp_list)))); + + if (d_first == t) + return d_rest; + + return list(or_s, + if3(d_first == nil, + cons(compound_s, rest(exp_list)), + cons(compound_s, cons(d_first, rest(exp_list)))), + d_rest, + nao); } else { val d_first = reg_derivative(first(exp_list), ch); @@ -1290,7 +1305,7 @@ static val reg_derivative(val exp, val ch) return reg_derivative_list(args, ch); } else if (sym == optional_s) { return reg_derivative(first(args), ch); - } else if (sym == oneplus_s || sym == zeroplus_s) { + } else if (sym == oneplus_s) { val arg = first(args); val d_arg = reg_derivative(arg, ch); if (d_arg == t) @@ -1300,6 +1315,14 @@ static val reg_derivative(val exp, val ch) return cons(compound_s, cons(d_arg, cons(cons(zeroplus_s, cons(arg, nil)), nil))); + } else if (sym == zeroplus_s) { + val arg = first(args); + val d_arg = reg_derivative(arg, ch); + if (d_arg == t) + return t; + if (d_arg == nil) + return exp; + return cons(compound_s, cons(d_arg, cons(exp, nil))); } else if (sym == compl_s) { return cons(sym, cons(reg_derivative(first(args), ch), nil)); } else if (sym == or_s) { |