include/dfa.h

   1 /*
   2  * Copyright (C) 1994, Index Data I/S
   3  * All rights reserved.
   4  * Sebastian Hammer, Adam Dickmeiss
   5  *
   6  * $Log: dfa.h,v $
   7  * Revision 1.2  1994-09-26 16:31:23  adam
   8  * Minor changes. xmalloc declares xcalloc now.
   9  *
  10  * Revision 1.1  1994/09/26  10:17:43  adam
  11  * Dfa-module header files.
  12  *
  13  */
  14
  15 #ifndef DFA_H
  16 #define DFA_H
  17
  18 #include <bset.h>
  19 #include <set.h>
  20 #define CAT     16000
  21 #define OR      16001
  22 #define STAR    16002
  23 #define PLUS    16003
  24 #define EPSILON 16004
  25
  26 typedef struct Tnode_ {
  27     union  {
  28         struct Tnode_ *p[2];  /* CAT,OR,STAR,PLUS (left,right) */
  29         short ch[2];          /* if ch[0] >= 0 then this Tnode represents */
  30                               /*   a character in range [ch[0]..ch[1]]    */
  31                               /* otherwise ch[0] represents */
  32                               /*   accepting no (-acceptno) */
  33     } u;
  34     unsigned pos : 15;        /* CAT/OR/STAR/EPSILON or non-neg. position */
  35     unsigned nullable : 1;
  36     Set firstpos;             /* first positions */
  37     Set lastpos;              /* last positions */
  38 } Tnode;
  39
  40 typedef struct Tblock_ {      /* Tnode bucket (block) */
  41     struct Tblock_ *next;     /* pointer to next bucket */
  42     Tnode *tarray;            /* array of nodes in bucket */
  43 } Tblock;
  44
  45 typedef struct  {
  46     Tnode *root;              /* root of regular syntax tree */
  47     Tnode *top;               /* regular tree top (returned by parse_dfa) */
  48     int position;             /* no of positions so far */
  49     int rule;                 /* no of rules so far */
  50     BSetHandle *charset;      /* character set type */
  51     BSet anyset;              /* character recognized by `.' */
  52     int use_Tnode;            /* used Tnodes */
  53     int max_Tnode;            /* allocated Tnodes */
  54     Tblock *start;            /* start block of Tnodes */
  55     Tblock *end;              /* end block of Tnodes */
  56 } DFA;
  57
  58 typedef struct {
  59     unsigned char ch[2];      /* transition on ch[0] <= c <= ch[1] to */
  60     unsigned short to;        /* this state */
  61 } DFA_tran;
  62
  63 typedef struct DFA_trans_ {
  64     struct DFA_trans_ *next;  /* next DFA transition block */
  65     DFA_tran *tran_block;     /* pointer to transitions */
  66     int  ptr;                 /* index of next transition in tran_block */
  67     int  size;                /* allocated size of tran_block */
  68 } DFA_trans;
  69
  70 typedef struct DFA_state_ {
  71     struct DFA_state_ *next;  /* next entry in free/unmarked/marked list */
  72     struct DFA_state_ *link;  /* link to next entry in hash chain */
  73     DFA_tran *trans;          /* transition list */
  74     Set set;                  /* set of positions (important nfa states) */
  75     short no;                 /* no of this state */
  76     short tran_no;            /* no of transitions to other states */
  77     short rule_no;            /* if non-zero, this holds accept rule no */
  78 } DFA_state;
  79
  80 typedef struct DFA_stateb_ {
  81     struct DFA_stateb_ *next;
  82     DFA_state *state_block;
  83 } DFA_stateb;
  84
  85 typedef struct  {
  86     DFA_state *freelist;      /* chain of unused (but allocated) DFA states */
  87     DFA_state *unmarked;      /* chain of unmarked DFA states */
  88     DFA_state *marked;        /* chain of marked DFA states */
  89     DFA_stateb *statemem;     /* state memory */
  90     int no;                   /* no of states (unmarked+marked) */
  91     SetType st;               /* Position set type */
  92     int hash;                 /* no hash entries in hasharray */
  93     DFA_state **hasharray;    /* hash pointers */
  94     DFA_state **sortarray;    /* sorted DFA states */
  95     DFA_trans *transmem;      /* transition memory */
  96 } DFA_states;
  97
  98 DFA *       init_dfa        (void);
  99 void        rm_dfa          (DFA **dfap);
 100 int         parse_dfa       (DFA *, char **, const unsigned short *);
 101 DFA_states* mk_dfas         (DFA *, int poset_chunk);
 102 void        rm_dfas         (DFA_states **dfas);
 103
 104 Tnode *     mk_Tnode        (void);
 105 Tnode *     mk_Tnode_cset   (BSet charset);
 106 void        term_Tnode      (void);
 107
 108 int         init_DFA_states (DFA_states **dfasp, SetType st, int hash);
 109 int         rm_DFA_states   (DFA_states **dfasp);
 110 int         add_DFA_state   (DFA_states *dfas, Set *s, DFA_state **sp);
 111 DFA_state   *get_DFA_state  (DFA_states *dfas);
 112 void        sort_DFA_states (DFA_states *dfas);
 113 void        add_DFA_tran    (DFA_states *, DFA_state *, int, int, int);
 114
 115 extern int  debug_dfa_trav;
 116 extern int  debug_dfa_tran;
 117 extern int  debug_dfa_followpos;
 118 extern int  dfa_verbose;
 119
 120 extern unsigned short
 121         dfa_thompson_chars[],
 122         dfa_ccl_chars[];
 123 #endif