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.5  1996-01-08 09:09:48  adam
   8  * Function dfa_parse got 'const' string argument.
   9  *
  10  * Revision 1.4  1995/01/25  11:31:04  adam
  11  * Simple error reporting when parsing regular expressions.
  12  *
  13  * Revision 1.3  1995/01/24  16:01:30  adam
  14  * Added -ansi to CFLAGS.
  15  * New functions and change of data structures.
  16  *
  17  * Revision 1.2  1994/09/26  16:31:23  adam
  18  * Minor changes. xmalloc declares xcalloc now.
  19  *
  20  * Revision 1.1  1994/09/26  10:17:43  adam
  21  * Dfa-module header files.
  22  *
  23  */
  24
  25 #ifndef DFA_H
  26 #define DFA_H
  27
  28 #include <bset.h>
  29 #include <set.h>
  30
  31 struct DFA_tran {
  32     unsigned char ch[2];      /* transition on ch[0] <= c <= ch[1] to */
  33     unsigned short to;        /* this state */
  34 };
  35
  36 struct DFA_trans {
  37     struct DFA_trans *next;   /* next DFA transition block */
  38     struct DFA_tran *tran_block; /* pointer to transitions */
  39     int  ptr;                 /* index of next transition in tran_block */
  40     int  size;                /* allocated size of tran_block */
  41 };
  42
  43 struct DFA_state {
  44     struct DFA_state *next;   /* next entry in free/unmarked/marked list */
  45     struct DFA_state *link;   /* link to next entry in hash chain */
  46     struct DFA_tran *trans;   /* transition list */
  47     Set set;                  /* set of positions (important nfa states) */
  48     short no;                 /* no of this state */
  49     short tran_no;            /* no of transitions to other states */
  50     short rule_no;            /* if non-zero, this holds accept rule no */
  51     short rule_nno;           /* accept rule no - except start rules */
  52 };
  53
  54 struct DFA {
  55     int no_states;
  56     struct DFA_state  **states;
  57     struct DFA_states *state_info;
  58     struct DFA_parse  *parse_info;
  59 };
  60
  61 struct DFA *dfa_init (void);
  62 int dfa_parse (struct DFA *, const char **);
  63 void dfa_mkstate (struct DFA *);
  64 void dfa_delete (struct DFA **);
  65
  66 void dfa_parse_cmap_clean (struct DFA *d);
  67 void dfa_parse_cmap_new (struct DFA *d, const int *cmap);
  68 void dfa_parse_cmap_del (struct DFA *d, int from);
  69 void dfa_parse_cmap_add (struct DFA *d, int from, int to);
  70
  71 extern int  debug_dfa_trav;
  72 extern int  debug_dfa_tran;
  73 extern int  debug_dfa_followpos;
  74 extern int  dfa_verbose;
  75
  76 extern unsigned short
  77         dfa_thompson_chars[],
  78         dfa_ccl_chars[];
  79
  80 #define L_LP 1
  81 #define L_RP 2
  82 #define L_CHAR 3
  83 #define L_CHARS 4
  84 #define L_ANY 5
  85 #define L_ALT 6
  86 #define L_ANYZ 7
  87 #define L_WILD 8
  88 #define L_QUEST 9
  89 #define L_CLOS1 10
  90 #define L_CLOS0 11
  91 #define L_END 12
  92 #define L_START 13
  93
  94 #define DFA_ERR_SYNTAX 1
  95 #define DFA_ERR_LP     2
  96 #define DFA_ERR_RP     3
  97 #endif