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