summaryrefslogtreecommitdiffstats
diff options
context:
space:
mode:
authorKaz Kylheku <kaz@kylheku.com>2015-09-27 21:56:41 -0700
committerKaz Kylheku <kaz@kylheku.com>2015-09-27 21:56:41 -0700
commit10a77c022921502a7136aa4f7769406a438596d8 (patch)
tree6768caa86bad5aed998661af7824581d4622de77
parentd7fa4564690c217d6ac6c62019938a84627f1468 (diff)
downloadtxr-10a77c022921502a7136aa4f7769406a438596d8.tar.gz
txr-10a77c022921502a7136aa4f7769406a438596d8.tar.bz2
txr-10a77c022921502a7136aa4f7769406a438596d8.zip
Support t regex in NFA compiler and in printer.
The t regex means "match nothing". This patch allows the NFA compiler to handle it. This will be necessary for an upcoming regex optimizer which can put out such an object. Also, the recursive regex printer can print the object now. * regex.c (nfa_kind_t): New enum member, nfa_reject. (nfa_state_reject): New static function. (nfa_compile_regex): Compile t regex into a reject state which cannot reach its corresponding acceptance state. (nfa_map_states): Handle nfa_reject case in switch, similarly to nfa_accept: nothing to transition into. (print_rec): Render the t regex as the empty character class [].
-rw-r--r--regex.c17
1 files changed, 16 insertions, 1 deletions
diff --git a/regex.c b/regex.c
index 8da87469..86e070fb 100644
--- a/regex.c
+++ b/regex.c
@@ -189,7 +189,7 @@ typedef union char_set {
} char_set_t;
typedef enum {
- nfa_accept, nfa_empty, nfa_wild, nfa_single, nfa_set
+ nfa_accept, nfa_reject, nfa_empty, nfa_wild, nfa_single, nfa_set
} nfa_kind_t;
struct nfa_state_accept {
@@ -812,6 +812,14 @@ static nfa_state_t *nfa_state_accept(void)
return st;
}
+static nfa_state_t *nfa_state_reject(void)
+{
+ nfa_state_t *st = coerce(nfa_state_t *, chk_malloc(sizeof *st));
+ st->a.kind = nfa_reject;
+ st->a.visited = 0;
+ return st;
+}
+
static nfa_state_t *nfa_state_empty(nfa_state_t *t0, nfa_state_t *t1)
{
nfa_state_t *st = coerce(nfa_state_t *, chk_malloc(sizeof *st));
@@ -1044,6 +1052,10 @@ static nfa_t nfa_compile_regex(val exp)
} else {
uw_throwf(error_s, lit("bad operator in regex syntax: ~s"), sym, nao);
}
+ } else if (exp == t) {
+ nfa_state_t *acc = nfa_state_accept();
+ nfa_state_t *s = nfa_state_reject();
+ return nfa_make(s, acc);
} else {
uw_throwf(error_s, lit("bad object in regex syntax: ~s"), exp, nao);
}
@@ -1060,6 +1072,7 @@ static void nfa_map_states(nfa_state_t *s,
switch (s->a.kind) {
case nfa_accept:
+ case nfa_reject:
break;
case nfa_empty:
nfa_map_states(s->e.trans0, ctx, fun, visited);
@@ -1887,6 +1900,8 @@ static void print_rec(val exp, val stream)
} else {
uw_throwf(error_s, lit("bad operator in regex syntax: ~s"), sym, nao);
}
+ } else if (exp == t) {
+ put_string(lit("[]"), stream);
} else if (exp != nil) {
uw_throwf(error_s, lit("bad object in regex syntax: ~s"), exp, nao);
}