lex_range.h (7079B)
1 /* kit_gram_lex_range.h - alphabet-neutral range-set NFA + determinizer 2 * front-half. 3 * 4 * Extracted from the utf8 scalar pipeline (gen/kit_gram_lex_scalar.c) so it can 5 * be shared by both the scalar (UTF-8) pipeline and the token-alphabet pipeline 6 * (gen/kit_gram_lex_tokens.c, %machine). The Thompson combinators, the atom 7 * partition (scalar_atom_ranges / scalar_atom_classes), and the one 8 * determinization (scalar_nfa_to_dfa) never look at the alphabet -- they 9 * operate on ScalarSet ranges over an arbitrary ordered universe -- so they 10 * form a universe-agnostic core. Only the *leaves* (Unicode char-class / 11 * property sets; token symbol sets) and the back-end encode/lowering step are 12 * alphabet-specific and stay in the per-alphabet TUs. 13 * 14 * This TU is non-gated (built even under KIT_GRAM_NO_UNICODE), mirroring how the 15 * determinizer core was extracted to gen/kit_gram_lex_dfa.{c,h}: the scalar 16 * pipeline adds Unicode property resolution + UTF-8 byte lowering on top, the 17 * token pipeline adds only leaves + a direct atom-DFA emit, and slim builds 18 * that drop the Unicode TUs still get the range core. 19 * 20 * Included from kit_gram_internal.h after kit_gram_lex_dfa.h (it needs NfaFrag, 21 * NfaBndKind, IntSet/IntSetScratch, AcceptSigMap) and after the ScalarSet 22 * types. Cross-TU symbols follow the kit_gram_internal.h macro-alias convention: 23 * a short name in source, an gramgen_-prefixed external symbol. 24 */ 25 #ifndef KIT_GRAM_LEX_RANGE_H 26 #define KIT_GRAM_LEX_RANGE_H 27 28 typedef struct { 29 ScalarSet chars; 30 int dst; 31 } ScalarNfaEdge; 32 33 typedef struct { 34 IntSet eps; 35 ScalarNfaEdge* edges; 36 size_t nedges, cap_edges; 37 NfaBndEdge* bnd; /* zero-width edge-anchor edges (not in eps-closure) */ 38 size_t nbnd, cap_bnd; 39 int accept; 40 } ScalarNfaState; 41 42 typedef struct { 43 GramgenContext* ctx; 44 ScalarNfaState* states; 45 size_t nstates, cap_states; 46 } ScalarNfaBuilder; 47 48 /* A compressed symbol alphabet. The `natoms` atoms (maximal ranges with 49 * constant edge membership; see scalar_atom_ranges) are partitioned into 50 * classes so that all atoms in a class intersect exactly the same set of NFA 51 * edges -- hence lead to identical destinations from every state. The subset 52 * construction can then treat each class as a single symbol. Each class is the 53 * union of its atoms' ranges, stored flat: ranges[off[c] .. off[c+1]), 54 * ascending within a class, so ranges[off[c]] is a valid representative atom 55 * for the class. */ 56 typedef struct { 57 uint16_t nclasses; 58 ScalarRange* ranges; /* concatenated, one entry per constituent atom */ 59 uint32_t* off; /* nclasses + 1 offsets into ranges */ 60 } ScalarClasses; 61 62 /* A LexAlphabet is the per-alphabet front end to the shared range core: the 63 * combinator layer (seq / alt / group / ? * + {n,m}) is alphabet-neutral and 64 * lives here, so an alphabet supplies only the *leaves* — how a literal, a 65 * `[ … ]` class, a `\p{…}` property, `.`, and a bare NAME each become a 66 * range-set NFA fragment — plus whether to drop the UTF-8 surrogate gap from 67 * the atom partition. Two instances exist: the utf8 scalar alphabet (Unicode 68 * leaves + UTF-8 lowering, gen/kit_gram_lex_scalar.c) and the token alphabet 69 * (symbol leaves + direct atom-DFA emit, gen/kit_gram_lex_tokens.c). The byte 70 * pipeline is the third front end but keeps its own 256-bit CharSet 71 * representation (not range-based), so it is not yet expressed through this 72 * vtable. Each hook returns the NFA fragment for one leaf node; an alphabet 73 * points an unused leaf at a hook that raises a located error (e.g. a symbol 74 * NAME in scalar mode, a string literal in token mode). */ 75 typedef struct LexAlphabet LexAlphabet; 76 struct LexAlphabet { 77 void* ud; /* alphabet-specific state (e.g. the symbol table) */ 78 int exclude_surrogates; /* scalar: 1 (UTF-8 universe); token: 0 (dense) */ 79 NfaFrag (*leaf_literal)(ScalarNfaBuilder* nfa, const LexAlphabet* a, 80 AstLexNode* node); 81 NfaFrag (*leaf_class)(ScalarNfaBuilder* nfa, const LexAlphabet* a, 82 AstLexNode* node); 83 NfaFrag (*leaf_prop)(ScalarNfaBuilder* nfa, const LexAlphabet* a, 84 AstLexNode* node); 85 NfaFrag (*leaf_any)(ScalarNfaBuilder* nfa, const LexAlphabet* a, 86 AstLexNode* node); 87 NfaFrag (*leaf_name)(ScalarNfaBuilder* nfa, const LexAlphabet* a, 88 AstLexNode* node); 89 }; 90 91 #define scalar_classes_free kit_gram_scalar_classes_free 92 #define range_nfa_from_lex_alt kit_gram_range_nfa_from_lex_alt 93 #define scalar_nfa_new_state kit_gram_scalar_nfa_new_state 94 #define scalar_nfa_eps kit_gram_scalar_nfa_eps 95 #define scalar_nfa_bnd kit_gram_scalar_nfa_bnd 96 #define scalar_nfa_edge kit_gram_scalar_nfa_edge 97 #define scalar_set_from_single_value kit_gram_scalar_set_from_single_value 98 #define scalar_nfa_empty kit_gram_scalar_nfa_empty 99 #define scalar_nfa_scalar_set kit_gram_scalar_nfa_scalar_set 100 #define scalar_nfa_concat kit_gram_scalar_nfa_concat 101 #define scalar_nfa_alt kit_gram_scalar_nfa_alt 102 #define scalar_nfa_opt kit_gram_scalar_nfa_opt 103 #define scalar_nfa_rep kit_gram_scalar_nfa_rep 104 #define scalar_nfa_to_dfa kit_gram_scalar_nfa_to_dfa 105 106 void scalar_classes_free(GramgenContext* ctx, ScalarClasses* sc); 107 int scalar_nfa_new_state(ScalarNfaBuilder* nfa); 108 void scalar_nfa_eps(ScalarNfaBuilder* nfa, int src, int dst); 109 void scalar_nfa_bnd(ScalarNfaBuilder* nfa, int src, NfaBndKind kind, int dst); 110 void scalar_nfa_edge(ScalarNfaBuilder* nfa, int src, ScalarSet chars, int dst, 111 Loc loc); 112 ScalarSet scalar_set_from_single_value(GramgenContext* ctx, uint32_t cp); 113 NfaFrag scalar_nfa_empty(ScalarNfaBuilder* nfa); 114 NfaFrag scalar_nfa_scalar_set(ScalarNfaBuilder* nfa, ScalarSet set, Loc loc); 115 NfaFrag scalar_nfa_concat(ScalarNfaBuilder* nfa, NfaFrag* parts, size_t n); 116 NfaFrag scalar_nfa_alt(ScalarNfaBuilder* nfa, NfaFrag* parts, size_t n); 117 NfaFrag scalar_nfa_opt(ScalarNfaBuilder* nfa, NfaFrag part); 118 NfaFrag scalar_nfa_rep(ScalarNfaBuilder* nfa, NfaFrag part); 119 /* Build the range-set NFA fragment for one pattern alternative, dispatching the 120 * leaves through `a` and threading the shared combinators. Used by both the 121 * scalar and token pipelines on their desugared recognizer ASTs. */ 122 NfaFrag range_nfa_from_lex_alt(ScalarNfaBuilder* nfa, const LexAlphabet* a, 123 AstLexAlt* alt); 124 /* The one determinization, over atoms. `exclude_surrogates` drops the 125 * UTF-8 surrogate gap (0xD800..0xDFFF) from the atom partition (scalar/UTF-8 126 * universe); token alphabets pass 0 (dense 0..NSYM-1, no holes). With no start 127 * anchors the two start-state out-params both come back 0. */ 128 void scalar_nfa_to_dfa(GramgenContext* ctx, Loc loc, ScalarNfaBuilder* nfa, 129 int start, int exclude_surrogates, 130 ScalarClasses* classes_out, uint16_t** trans_out, 131 uint16_t** accept_out, uint16_t* nstates_out, 132 AcceptSigMap* sigmap, uint16_t* start_text_out, 133 uint16_t* start_line_out); 134 135 #endif /* KIT_GRAM_LEX_RANGE_H */