code wiki / _hdl_build / nx_regex_vm.nx
nx_regex_vm.nx
buildroot/runtime/_hdl_build/nx_regex_vm.nx
about
nx_regex_vm.nx -- FULL regex with ALTERNATION | and GROUPS () via a Thompson NFA, still LINEAR-TIME (epsilon-
closure state-set, NO backtracking => ReDoS-immune). Closes the regex gap beyond the atom-NFA (nx_regex_lib).
Pipeline: re2post (iterative, paren-stack) -> post2nfa (explicit state graph) -> sim (state-set).
T1 'a|b' T2 '(ab)+' T3 'a(b|c)d' T4 '(a|b)*c' T5 EXCEED '(a|a)*b' on 24 a's = LINEAR T6 teeth non-match.
expect_exit: 0 Sovereign: nx_syscalls.
dependencies 2 imports · 0 importers
imports: nx_syscalls.nxnx_itoa_lib.nx
imported by: nobody (leaf or entry point)
call flow from main pre-order; caps 40 nodes / depth 6 declared; ↻ = already shown
structs
| none |
consts
| 8 | const K_MAGIC_1024: i64 = 1024 |
functions
| 10 | func g_puts(s: *u8) -> i64 { var n: i64=0; while s[n]!=(0 as u8){n=n+1} sys_write(1,s,n); return 0 } |
| 15 | func g_pn(v: i64) -> i64 { nxi_out(v); return 0 } |
| 16 | func ck(name: *u8, c: i64) -> i64 { if c==1 { g_puts(" PASS " as *u8) } else { g_puts(" FAIL " as *u8) } g_puts(name); g_puts("\n" as *u8); return c } |
| 17 | func cs_set(csbm: *i64, base: i64, ch: i64) -> i64 { csbm[base+(ch>>6)]=csbm[base+(ch>>6)]|(1<<(ch&63)); return 0 } called by 1: re2post |
| 18 | func cs_match(csbm: *i64, cls: i64, ch: i64) -> i64 { return (csbm[cls*4+(ch>>6)]>>(ch&63))&1 } called by 1: re_vm_match |
| 22 | func re2post(re: *u8, pop: *i64, parg: *i64, csbm: *i64, pcsn: *i64) -> i64 |
| 54 | func post2nfa(pop: *i64, parg: *i64, np: i64, scls: *i64, sto: *i64, se1: *i64, se2: *i64, pns: *i64, pmatch: *i64) -> i64 |
| 86 | func addstate(scls: *i64, sto: *i64, se1: *i64, se2: *i64, s: i64, clist: *i64, cnp: *i64, seen: *i64, gen: i64, mst: i64, mf: *i64) -> i64 |
| 95 | func re_vm_match(re: *u8, text: *u8, tn: i64) -> i64 |
| 118 | func main() -> i64 |