From 769e5c9b42bf87531296013fac0af819af9228ee Mon Sep 17 00:00:00 2001 From: Adam Dickmeiss Date: Mon, 26 Sep 1994 10:17:42 +0000 Subject: [PATCH] Dfa-module header files. --- include/bset.h | 44 ++++++++++++++++++++ include/dfa.h | 122 ++++++++++++++++++++++++++++++++++++++++++++++++++++++++ include/set.h | 40 +++++++++++++++++++ 3 files changed, 206 insertions(+) create mode 100644 include/bset.h create mode 100644 include/dfa.h create mode 100644 include/set.h diff --git a/include/bset.h b/include/bset.h new file mode 100644 index 0000000..8c9966c --- /dev/null +++ b/include/bset.h @@ -0,0 +1,44 @@ +/* + * Copyright (C) 1994, Index Data I/S + * All rights reserved. + * Sebastian Hammer, Adam Dickmeiss + * + * $Log: bset.h,v $ + * Revision 1.1 1994-09-26 10:17:42 adam + * Dfa-module header files. + * + */ +#ifndef BSET_H +#define BSET_H + +typedef unsigned short BSetWord; +typedef BSetWord *BSet; + +typedef struct BSetHandle_ { + unsigned size; /* size of set in members */ + unsigned wsize; /* size of individual set (in BSetWord)*/ + unsigned offset; /* offset in current set block */ + unsigned chunk; /* chunk, i.e. size of each block */ + struct BSetHandle_ *setchain; + BSetWord setarray[1]; +} BSetHandle; + +BSetHandle *mk_BSetHandle (int size, int chunk); +void rm_BSetHandle (BSetHandle **shp); +int inf_BSetHandle (BSetHandle *sh, long *used, long *alloc); +BSet cp_BSet (BSetHandle *sh, BSet dst, BSet src); +void add_BSet (BSetHandle *sh, BSet dst, unsigned member); +void union_BSet (BSetHandle *sh, BSet dst, BSet src); +BSet mk_BSet (BSetHandle **shp); +void rm_BSet (BSetHandle **shp); +void res_BSet (BSetHandle *sh, BSet dst); +void com_BSet (BSetHandle *sh, BSet dst); +void pr_BSet (BSetHandle *sh, BSet src); +unsigned test_BSet (BSetHandle *sh, BSet src, unsigned member); +int trav_BSet (BSetHandle *sh, BSet src, unsigned member); +int travi_BSet (BSetHandle *sh, BSet src, unsigned member); +unsigned hash_BSet (BSetHandle *sh, BSet src); +int eq_BSet (BSetHandle *sh, BSet dst, BSet src); +void pr_charBSet (BSetHandle *sh, BSet src, void (*f)(int)); + +#endif diff --git a/include/dfa.h b/include/dfa.h new file mode 100644 index 0000000..0d58314 --- /dev/null +++ b/include/dfa.h @@ -0,0 +1,122 @@ +/* + * Copyright (C) 1994, Index Data I/S + * All rights reserved. + * Sebastian Hammer, Adam Dickmeiss + * + * $Log: dfa.h,v $ + * Revision 1.1 1994-09-26 10:17:43 adam + * Dfa-module header files. + * + */ + +#ifndef DFA_H +#define DFA_H + +#include +#include +#define CAT 16000 +#define OR 16001 +#define STAR 16002 +#define PLUS 16003 +#define EPSILON 16004 + +typedef struct Tnode_ { + union { + struct Tnode_ *p[2]; /* CAT,OR,STAR,PLUS (left,right) */ + short ch[2]; /* if ch[0] >= 0 then this Tnode represents */ + /* a character in range [ch[0]..ch[1]] */ + /* otherwise ch[0] represents */ + /* accepting no (-acceptno) */ + } u; + unsigned pos : 15; /* CAT/OR/STAR/EPSILON or non-neg. position */ + unsigned nullable : 1; + Set firstpos; /* first positions */ + Set lastpos; /* last positions */ +} Tnode; + +typedef struct Tblock_ { /* Tnode bucket (block) */ + struct Tblock_ *next; /* pointer to next bucket */ + Tnode *tarray; /* array of nodes in bucket */ +} Tblock; + +typedef struct { + Tnode *root; /* root of regular syntax tree */ + Tnode *top; /* regular tree top (returned by parse_dfa) */ + int position; /* no of positions so far */ + int rule; /* no of rules so far */ + BSetHandle *charset; /* character set type */ + BSet anyset; /* character recognized by `.' */ + int use_Tnode; /* used Tnodes */ + int max_Tnode; /* allocated Tnodes */ + Tblock *start; /* start block of Tnodes */ + Tblock *end; /* end block of Tnodes */ +} DFA; + +typedef struct { + unsigned char ch[2]; /* transition on ch[0] <= c <= ch[1] to */ + unsigned short to; /* this state */ +} DFA_tran; + +typedef struct DFA_trans_ { + struct DFA_trans_ *next; /* next DFA transition block */ + DFA_tran *tran_block; /* pointer to transitions */ + int ptr; /* index of next transition in tran_block */ + int size; /* allocated size of tran_block */ +} DFA_trans; + +typedef struct DFA_state_ { + struct DFA_state_ *next; /* next entry in free/unmarked/marked list */ + struct DFA_state_ *link; /* link to next entry in hash chain */ + DFA_tran *trans; /* transition list */ + Set set; /* set of positions (important nfa states) */ + short no; /* no of this state */ + short tran_no; /* no of transitions to other states */ + short rule_no; /* if non-zero, this holds accept rule no */ +} DFA_state; + +typedef struct DFA_stateb_ { + struct DFA_stateb_ *next; + DFA_state *state_block; +} DFA_stateb; + +typedef struct { + DFA_state *freelist; /* chain of unused (but allocated) DFA states */ + DFA_state *unmarked; /* chain of unmarked DFA states */ + DFA_state *marked; /* chain of marked DFA states */ + DFA_stateb *statemem; /* state memory */ + int no; /* no of states (unmarked+marked) */ + SetType st; /* Position set type */ + int hash; /* no hash entries in hasharray */ + DFA_state **hasharray; /* hash pointers */ + DFA_state **sortarray; /* sorted DFA states */ + DFA_trans *transmem; /* transition memory */ +} DFA_states; + +DFA * init_dfa (void); +void rm_dfa (DFA **dfap); +int parse_dfa (DFA *, char **, const unsigned short *); +DFA_states* mk_dfas (DFA *, int poset_chunk); +void rm_dfas (DFA_states **dfas); + +Tnode * mk_Tnode (void); +Tnode * mk_Tnode_cset (BSet charset); +void term_Tnode (void); + +int init_DFA_states (DFA_states **dfasp, SetType st, int hash); +int rm_DFA_states (DFA_states **dfasp); +int add_DFA_state (DFA_states *dfas, Set *s, DFA_state **sp); +DFA_state *get_DFA_state (DFA_states *dfas); +void sort_DFA_states (DFA_states *dfas); +void add_DFA_tran (DFA_states *, DFA_state *, int, int, int); + +extern int debug_dfa_trav; +extern int debug_dfa_tran; +extern int debug_dfa_followpos; +extern int dfa_verbose; + +extern unsigned short + thompson_chars[], + brief_chars[], + grep_chars[], + ccl_chars[]; +#endif diff --git a/include/set.h b/include/set.h new file mode 100644 index 0000000..ed31c8f --- /dev/null +++ b/include/set.h @@ -0,0 +1,40 @@ +/* + * Copyright (C) 1994, Index Data I/S + * All rights reserved. + * Sebastian Hammer, Adam Dickmeiss + * + * $Log: set.h,v $ + * Revision 1.1 1994-09-26 10:17:44 adam + * Dfa-module header files. + * + */ +#ifndef SET_H +#define SET_H + +typedef struct SetElement_ { + struct SetElement_ *next; + int value; +} SetElement, *Set; + +typedef struct { + Set alloclist; + Set freelist; + long used; + int chunk; +} *SetType; + +SetType mk_SetType (int chunk); +int inf_SetType (SetType st, long *used, long *allocated); +SetType rm_SetType (SetType st); +Set mk_Set (SetType st); +Set add_Set (SetType st, Set s, int value); +Set merge_Set (SetType st, Set s1, Set s2); +Set union_Set (SetType st, Set s1, Set s2); +Set rm_Set (SetType st, Set s); +Set cp_Set (SetType st, Set s); +void pr_Set (SetType st, Set s); +unsigned hash_Set (SetType st, Set s); +int eq_Set (SetType s, Set s1, Set s2); + +#endif + -- 1.7.10.4