include/dfa.h

   1 /* $Id: dfa.h,v 1.11 2005-01-15 19:38:24 adam Exp $
   2    Copyright (C) 1995-2005
   3    Index Data ApS
   4
   5 This file is part of the Zebra server.
   6
   7 Zebra is free software; you can redistribute it and/or modify it under
   8 the terms of the GNU General Public License as published by the Free
   9 Software Foundation; either version 2, or (at your option) any later
  10 version.
  11
  12 Zebra is distributed in the hope that it will be useful, but WITHOUT ANY
  13 WARRANTY; without even the implied warranty of MERCHANTABILITY or
  14 FITNESS FOR A PARTICULAR PURPOSE.  See the GNU General Public License
  15 for more details.
  16
  17 You should have received a copy of the GNU General Public License
  18 along with Zebra; see the file LICENSE.zebra.  If not, write to the
  19 Free Software Foundation, 59 Temple Place - Suite 330, Boston, MA
  20 02111-1307, USA.
  21 */
  22
  23
  24
  25 #ifndef DFA_H
  26 #define DFA_H
  27
  28 #include <bset.h>
  29 #include <set.h>
  30
  31 #ifdef __cplusplus
  32 extern "C" {
  33 #endif
  34
  35 struct DFA_tran {
  36     unsigned char ch[2];      /* transition on ch[0] <= c <= ch[1] to */
  37     unsigned short to;        /* this state */
  38 };
  39
  40 struct DFA_trans {
  41     struct DFA_trans *next;   /* next DFA transition block */
  42     struct DFA_tran *tran_block; /* pointer to transitions */
  43     int  ptr;                 /* index of next transition in tran_block */
  44     int  size;                /* allocated size of tran_block */
  45 };
  46
  47 struct DFA_state {
  48     struct DFA_state *next;   /* next entry in free/unmarked/marked list */
  49     struct DFA_state *link;   /* link to next entry in hash chain */
  50     struct DFA_tran *trans;   /* transition list */
  51     Set set;                  /* set of positions (important nfa states) */
  52     short no;                 /* no of this state */
  53     short tran_no;            /* no of transitions to other states */
  54     short rule_no;            /* if non-zero, this holds accept rule no */
  55     short rule_nno;           /* accept rule no - except start rules */
  56 };
  57
  58 struct DFA {
  59     int no_states;
  60     struct DFA_state  **states;
  61     struct DFA_states *state_info;
  62     struct DFA_parse  *parse_info;
  63 };
  64
  65 struct DFA *dfa_init (void);
  66 void dfa_set_cmap (struct DFA *dfa, void *vp,
  67                    const char **(*cmap)(void *vp, const char **from, int len));
  68 int dfa_parse (struct DFA *, const char **);
  69 void dfa_mkstate (struct DFA *);
  70 void dfa_delete (struct DFA **);
  71
  72 void dfa_parse_cmap_clean (struct DFA *d);
  73 void dfa_parse_cmap_new (struct DFA *d, const int *cmap);
  74 void dfa_parse_cmap_del (struct DFA *d, int from);
  75 void dfa_parse_cmap_add (struct DFA *d, int from, int to);
  76
  77 extern int  debug_dfa_trav;
  78 extern int  debug_dfa_tran;
  79 extern int  debug_dfa_followpos;
  80 extern int  dfa_verbose;
  81
  82 extern unsigned short
  83         dfa_thompson_chars[],
  84         dfa_ccl_chars[];
  85
  86 #define L_LP 1
  87 #define L_RP 2
  88 #define L_CHAR 3
  89 #define L_CHARS 4
  90 #define L_ANY 5
  91 #define L_ALT 6
  92 #define L_ANYZ 7
  93 #define L_WILD 8
  94 #define L_QUEST 9
  95 #define L_CLOS1 10
  96 #define L_CLOS0 11
  97 #define L_END 12
  98 #define L_START 13
  99
 100 #define DFA_ERR_SYNTAX 1
 101 #define DFA_ERR_LP     2
 102 #define DFA_ERR_RP     3
 103
 104 #ifdef __cplusplus
 105 }
 106 #endif
 107
 108 #endif