1 /* 2 tre-ast.h - Abstract syntax tree (AST) definitions 3 4 This software is released under a BSD-style license. 5 See the file LICENSE for details and copyright. 6 7 */ 8 9 10 #ifndef TRE_AST_H 11 #define TRE_AST_H 1 12 13 #include "tre-mem.h" 14 #include "tre-internal.h" 15 #include "tre-compile.h" 16 17 /* The different AST node types. */ 18 typedef enum { 19 LITERAL, 20 CATENATION, 21 ITERATION, 22 UNION 23 } tre_ast_type_t; 24 25 /* Special subtypes of TRE_LITERAL. */ 26 #define EMPTY -1 /* Empty leaf (denotes empty string). */ 27 #define ASSERTION -2 /* Assertion leaf. */ 28 #define TAG -3 /* Tag leaf. */ 29 #define BACKREF -4 /* Back reference leaf. */ 30 #define PARAMETER -5 /* Parameter. */ 31 32 #define IS_SPECIAL(x) ((x)->code_min < 0) 33 #define IS_EMPTY(x) ((x)->code_min == EMPTY) 34 #define IS_ASSERTION(x) ((x)->code_min == ASSERTION) 35 #define IS_TAG(x) ((x)->code_min == TAG) 36 #define IS_BACKREF(x) ((x)->code_min == BACKREF) 37 #define IS_PARAMETER(x) ((x)->code_min == PARAMETER) 38 39 40 /* A generic AST node. All AST nodes consist of this node on the top 41 level with `obj' pointing to the actual content. */ 42 typedef struct { 43 tre_ast_type_t type; /* Type of the node. */ 44 void *obj; /* Pointer to actual node. */ 45 int nullable; 46 int submatch_id; 47 size_t num_submatches; 48 size_t num_tags; 49 tre_pos_and_tags_t *firstpos; 50 tre_pos_and_tags_t *lastpos; 51 } tre_ast_node_t; 52 53 54 /* A "literal" node. These are created for assertions, back references, 55 tags, matching parameter settings, and all expressions that match one 56 character. */ 57 typedef struct { 58 int code_min; 59 int code_max; 60 int position; 61 union { 62 tre_ctype_t class; 63 int *params; 64 } u; 65 tre_ctype_t *neg_classes; 66 } tre_literal_t; 67 68 /* A "catenation" node. These are created when two regexps are concatenated. 69 If there are more than one subexpressions in sequence, the `left' part 70 holds all but the last, and `right' part holds the last subexpression 71 (catenation is left associative). */ 72 typedef struct { 73 tre_ast_node_t *left; 74 tre_ast_node_t *right; 75 } tre_catenation_t; 76 77 /* An "iteration" node. These are created for the "*", "+", "?", and "{m,n}" 78 operators. */ 79 typedef struct { 80 /* Subexpression to match. */ 81 tre_ast_node_t *arg; 82 /* Minimum number of consecutive matches. */ 83 int min; 84 /* Maximum number of consecutive matches. */ 85 int max; 86 /* If 0, match as many characters as possible, if 1 match as few as 87 possible. Note that this does not always mean the same thing as 88 matching as many/few repetitions as possible. */ 89 unsigned int minimal:1; 90 /* Approximate matching parameters (or NULL). */ 91 int *params; 92 } tre_iteration_t; 93 94 /* An "union" node. These are created for the "|" operator. */ 95 typedef struct { 96 tre_ast_node_t *left; 97 tre_ast_node_t *right; 98 } tre_union_t; 99 100 tre_ast_node_t * 101 tre_ast_new_node(tre_mem_t mem, tre_ast_type_t type, size_t size); 102 103 tre_ast_node_t * 104 tre_ast_new_literal(tre_mem_t mem, int code_min, int code_max, int position); 105 106 tre_ast_node_t * 107 tre_ast_new_iter(tre_mem_t mem, tre_ast_node_t *arg, int min, int max, 108 int minimal); 109 110 tre_ast_node_t * 111 tre_ast_new_union(tre_mem_t mem, tre_ast_node_t *left, tre_ast_node_t *right); 112 113 tre_ast_node_t * 114 tre_ast_new_catenation(tre_mem_t mem, tre_ast_node_t *left, 115 tre_ast_node_t *right); 116 117 #ifdef TRE_DEBUG 118 void 119 tre_ast_print(tre_ast_node_t *tree); 120 121 /* XXX - rethink AST printing API */ 122 void 123 tre_print_params(int *params); 124 #endif /* TRE_DEBUG */ 125 126 #endif /* TRE_AST_H */ 127 128 /* EOF */ 129