backend.ha (3713B)
1 use encoding::utf8; 2 use machine; 3 use os; 4 use strings; 5 6 // An action callback. Can return a lexeme to swallow completely this string, 7 // and continue, or a token to return to the [[next]]. 8 export type actioncb = fn( 9 scan: *scanner, 10 result: const str, 11 user: nullable *opaque = null, 12 ) (str | *token | error); 13 14 // A backend action. 15 export type action = struct { 16 expr: str, 17 cb: *actioncb, 18 name: const str, 19 user: nullable *opaque, 20 }; 21 22 // A backend. 23 export type backend = struct { 24 performfn: *backend_performfn, 25 destroyfn: *backend_destroyfn, 26 }; 27 28 // A backend perform function. 29 export type backend_performfn = fn(be: *backend, in: str) (void | (*action, str) | error); 30 // A backend destroy function. 31 export type backend_destroyfn = fn(be: *backend) void; 32 33 // Perform the backend, and return the matched action and bytes. 34 export fn perform(be: *backend, in: str) (void | (*action, str) | error) = be.performfn(be, in); 35 // Destroy a backend. 36 export fn destroy(be: *backend) void = be.destroyfn(be); 37 38 // The default backend constructor. 39 export fn def_backend() (*backendinitfb | error) = { 40 match (os::getenv("LEXER_BACKEND")) { 41 case void => 42 return &deterministic: *backendinitfb; 43 case let value: str => 44 switch (value) { 45 case "dfa" => 46 return &deterministic: *backendinitfb; 47 case "ndfa" => 48 return &nondeterministic: *backendinitfb; 49 case => 50 return "unknown backend": compile; 51 }; 52 }; 53 }; 54 55 export type backendinitfb = fn(actions: []action ) (*backend | error); 56 57 export type ndfa_backend = struct { 58 backend, 59 actions: []action, 60 mata: machine::automata, 61 }; 62 63 fn ndfa_destroy(be: *backend) void = { 64 let be = be: *ndfa_backend; 65 machine::finish(&be.mata); 66 free(be.actions); 67 free(be); 68 }; 69 70 fn ndfa_perform( 71 be: *backend, 72 in: str, 73 ) (void | (*action, str) | error) = { 74 let be = be: *ndfa_backend; 75 match (machine::resolve(&be.mata, utf8::decode(strings::toutf8(in)))) { 76 case void => return void; 77 case let err: machine::error => abort(machine::strerror(err)); 78 case let this: (size, *opaque) => 79 const new = strings::sub(in, 0, this.0); 80 return (this.1: *action, new); 81 }; 82 }; 83 84 // A non-deterministic backend. Its tests all expressions in parallel, and 85 // uses the longest matched prefix as winer. The actions are duplicated locally, 86 // and can be freed by the caller. 87 export fn nondeterministic( 88 actions: []action 89 ) (*backend | error) = { 90 const be = build_ndfa_be(actions)?: *ndfa_backend; 91 match (os::getenv("LEXER_DEBUG")) { 92 case void => void; 93 case let value: str => 94 if (value == "1") { 95 machine::debug_automata(&be.mata)!; 96 }; 97 }; 98 return be; 99 }; 100 101 // A deterministic backend. It crawl acceptable transitions linearly, and return 102 // the last encountered acceptance. The actions are duplicated locally, and can 103 // be freed by the caller. 104 export fn deterministic( 105 actions: []action 106 ) (*backend | error) = { 107 const be = build_ndfa_be(actions)?: *ndfa_backend; 108 const old = be.mata; 109 defer machine::finish(&old); 110 be.mata = machine::determine(&old)?; 111 match (os::getenv("LEXER_DEBUG")) { 112 case void => void; 113 case let value: str => 114 if (value == "1") { 115 machine::debug_automata(&be.mata)!; 116 }; 117 }; 118 return be; 119 }; 120 121 fn build_ndfa_be( 122 _actions: []action 123 ) (*backend | error) = { 124 let actions: []action = []; 125 append(actions, _actions...)?; 126 127 let exprs: [](str, *opaque) = []; 128 defer free(exprs); 129 for (let act &.. actions) { 130 append(exprs, (act.expr, act))?; 131 }; 132 133 const mata = match (machine::compute(exprs)) { 134 case let this: machine::automata => yield this; 135 case nomem => return nomem; 136 case let syn: machine::syntax => return syn: compile; 137 }; 138 139 return alloc(ndfa_backend { 140 actions = actions, 141 mata = mata, 142 performfn = &ndfa_perform, 143 destroyfn = &ndfa_destroy, 144 })?; 145 };