home *** CD-ROM | disk | FTP | other *** search
/ Garbo / Garbo.cdr / pc / unix / dgrep.arc / DFA.H < prev    next >
Encoding:
C/C++ Source or Header  |  1990-01-18  |  5.1 KB  |  181 lines
  1. /**********************************************************************\
  2.  *
  3.  *    DFA.H
  4.  *
  5.  * Definitions for deterministic finite state automata.
  6.  *
  7.  * Author: Jarmo Ruuth 15-Mar-1988
  8.  *
  9.  * Copyright (C) 1988-90 by Jarmo Ruuth
  10.  * May be freely copied for any non-commercial usage.
  11. \**********************************************************************/
  12.  
  13. #include "set.h"
  14.  
  15. /* Definitions for different nodes in syntax tree. */
  16.  
  17. typedef enum {
  18.     CAT,        /* cat node */
  19.     OR,        /* or node */
  20.     CLOSURE,    /* closure node */
  21.     ID,        /* id node, leaf */
  22.     EMPTY_ID,    /* id node, empty leaf */
  23.     CLASS_ID    /* id node, character class leaf */
  24. } node_type_t;
  25.     
  26. /* tree node structure */
  27. typedef struct {
  28.     int    left;
  29.     int    right;
  30. } next_node_t; 
  31.  
  32. /* union for possible values of tree node */
  33. typedef union {
  34.     unsigned    item;
  35.     set_t*        class;
  36.     next_node_t    next;
  37. } node_value_t;
  38.  
  39. /* structure for tree node  */
  40. typedef struct {
  41.     node_type_t    type;
  42.     node_value_t    val;
  43.     unsigned    nullable;
  44.     set_t*        firstpos;
  45.     set_t*        lastpos;
  46. } node_t;
  47.  
  48. #define BOL        NCHARS        /* beginning of line */
  49. #define EOL        (NCHARS+1)    /* end of line */
  50. #define REM        (NCHARS+2)    /* right-end marker */
  51.  
  52. #define NLANG        (REM+1)        /* characters in recognized language */
  53.  
  54. #ifdef TEST
  55.  
  56. /*
  57.     In test version use large FIXTRAN, because it is easier to
  58.     debug transition tables when they are fully done.
  59. */
  60. #define FIXTRAN        30
  61. #define CACHETRAN    10
  62. #define NTRAN        (FIXTRAN+CACHETRAN)
  63.  
  64. #else
  65.  
  66. /*
  67.     If tran_t is a 8 bit char, then 40 states reserves 10 kb. In the fast
  68.     version, with 16 bit pointers (PC small model) it is 20 kb and with 32 
  69.     bit pointers (PC large model, most Unix systems) 40 kb.
  70. */
  71. #define FIXTRAN        0        /* number of fixed transition tables */
  72. #define CACHETRAN    40
  73. #define NTRAN        (FIXTRAN+CACHETRAN)
  74.  
  75. #endif
  76.  
  77. /*
  78.     Special states. Note that the number of special states has
  79.     effect on the tran_t type in the below. In the fast version
  80.     we rely on the fact that none of the transition table pointers
  81.     will be allocated from the memory at addresses 0xfffb - 0xffff.
  82.     Also we rely on the fact that the tran_t type conversion will
  83.     make these values actually very large unsigned values, so that
  84.     they will be larger that the last pointer allocated to the 
  85.     rbuf.dstates.
  86. */
  87. #define NSPECIAL    4
  88.  
  89.  
  90. #define    UNKNOWN        (tran_t)-1    /* transition not known */
  91. #define END_OF_LINE    (tran_t)-2    /* used to detect line boundaries */
  92. #define STOPSTATE    (tran_t)-3    /* stops matching */
  93. #define ACCEPTING    (tran_t)-4    /* real transition would be to the */
  94.                     /* accepting state */
  95. #define MAXTRAN        ACCEPTING    /* smallest special transition */
  96.  
  97. /* forward definition needed in FAST case */
  98. typedef struct statestruct state_t;
  99.  
  100. #ifdef FAST
  101.  
  102. /*
  103.     Fast version stores direct pointers to other states to the
  104.     transition tables. It makes the reg_exec faster by removing
  105.     memory accesses.
  106. */
  107. typedef state_t*    tran_t;
  108.  
  109. #define FIRST_STATE    rbuf.dstates[0]
  110.  
  111. #else
  112.  
  113. /*
  114.     Normally, transition table contains only index of the next state.
  115.     If possible, we use characters for indexing to save space. Note
  116.     that the tran_t must be some unsigned type (see comment of the
  117.     special transitions).
  118. */
  119. #if (NTRAN+NSPECIAL > MAXCHAR)
  120. typedef    unsigned short    tran_t;
  121. #else
  122. typedef    unsigned char    tran_t;
  123. #endif
  124.  
  125. #define FIRST_STATE    0
  126.  
  127. #endif
  128.  
  129. /* Structure for state positions and transition tables. */
  130. struct statestruct {
  131.     tran_t        tran[NLANG];    /* transition tables */
  132.     set_t*        set;        /* state followpositions */
  133.     unsigned    marked;
  134. };
  135.  
  136. /* regular expression buffer structure */
  137. typedef struct {
  138.     state_t*    dstates[NTRAN];    /* dfa states */
  139.     set_t**        follow_array;    /* followpositions */
  140.     int        setsize;    /* position set size */
  141.     int        last_state;    /* last used state in dstates */
  142.     tran_t        default_tran;    /* default transition */
  143.     int        root;        /* tree root position */
  144.     node_t*        tree;        /* syntax tree for regexp */
  145.     uint*        language;    /* characters in language */
  146.     char        eol;        /* end of line character */
  147.     char        eol2;        /* second end of line character */
  148.     char        neol;        /* number of end of line characters */
  149.     char*        regmust;    /* regmust, if any */
  150.     char*        reg_error;    /* error message, if any */
  151.     char        ignorecase;    /* flag to ignore case */
  152.     char        search;        /* are we building substring searcher*/
  153.     char        full;        /* must we get longest possible match*/
  154.     char        mem_allocated;    /* is there allocated memory in rbuf */
  155.     char        begline;    /* can we match beginning of line */
  156.     char        endline;    /* can we match end of line */
  157.     set_t*        tmpstate;    /* temporary working space */
  158. } regbuf_t;
  159.  
  160. extern regbuf_t rbuf;
  161.     
  162. extern int create_tree(uchar* str);
  163. extern bool find_regmust(node_t* tree, int root);
  164. extern bool calcpos(void);
  165. extern bool dfa(void);
  166. extern tran_t get_transition(tran_t tran, unsigned input);
  167.  
  168. /**********************************************************************
  169.  *
  170.  *    state_of
  171.  *
  172.  * Returns the state structure specified by the transition.
  173.  * In the FAST version it is the same as the transition, otherwise
  174.  * it is the state pointer indexed by the transition.
  175.  */
  176. #ifdef FAST
  177. #define state_of(_tran)    (_tran)
  178. #else
  179. #define state_of(_tran)    (rbuf.dstates[_tran])
  180. #endif
  181.