contrib/tre/lib/tre-ast.h

   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   int num_submatches;
  48   int 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   long code_min;
  59   long 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 */