home *** CD-ROM | disk | FTP | other *** search
/ Garbo / Garbo.cdr / pc / unix / dgrep.arc / DFA.C < prev    next >
Encoding:
C/C++ Source or Header  |  1990-03-16  |  12.7 KB  |  502 lines
  1. /**********************************************************************\
  2.  *
  3.  *    DFA.C
  4.  *
  5.  * Constructs deterministic finite state automata from followpos.
  6.  * Because of exponential space requirements on some input (and 64k
  7.  * segmentation in PC !#?@#), a sort of lazy evaluation tecnique is used. 
  8.  * FIXTRAN first transitions are always calculated and kept in memory. 
  9.  * If more states are needed, they are computed while matching the 
  10.  * expression. Calculated transitions are stored in a cache. If some 
  11.  * transition is not in the fixed transition table and it is not found 
  12.  * from those states currently in cache then one cache state is deleted 
  13.  * and new one is added.
  14.  *
  15.  * Bugs: Things get conciderably slower, if more than NTRAN
  16.  *     states are needed.
  17.  *
  18.  * Author: Jarmo Ruuth 15-Mar-1988
  19.  *
  20.  * Copyright (C) 1988-90 by Jarmo Ruuth
  21.  * May be freely copied for any non-commercial usage.
  22. \**********************************************************************/
  23.  
  24. #include "system.h"
  25. #include "dfa.h"
  26.  
  27. /**********************************************************************
  28.  *
  29.  *    init_dfa
  30.  *
  31.  * Allocates state sets and transition table.
  32.  */
  33. static bool init_dfa(void)
  34. {
  35.     REG1 int    i;
  36.     
  37.     for (i = 0; i < NTRAN; i++) {
  38.         if ((rbuf.dstates[i] = calloc(1, sizeof(state_t))) == NULL)
  39.             return FALSE;
  40.         if ((rbuf.dstates[i]->set = calloc(1, rbuf.setsize)) == NULL)
  41.             return FALSE;
  42. #ifdef FAST
  43.         assert(rbuf.dstates[i] < MAXTRAN);
  44. #endif
  45.     }
  46.     if ((rbuf.tmpstate = malloc(rbuf.setsize)) == NULL)
  47.         return FALSE;
  48.     return TRUE;
  49. }
  50.  
  51. /**********************************************************************
  52.  *
  53.  *    is_accepting
  54.  *
  55.  * Tests if the given state set is accepting state. State is accepting
  56.  * if right end marker position (at root-1) belongs to it.
  57.  */
  58. #define is_accepting(_state_set) in_set(_state_set, rbuf.root-1)
  59.  
  60. /**********************************************************************
  61.  *
  62.  *    transition_to
  63.  *
  64.  * Returns the transition to the state specified by it's index.
  65.  * In the fast version, it is the state pointer, or otherwise it
  66.  * is index to the state.
  67.  */
  68. #ifdef FAST
  69. #define transition_to(_index) ((tran_t)rbuf.dstates[_index])
  70. #else
  71. #define transition_to(_index) ((tran_t)(_index))
  72. #endif
  73.  
  74. /**********************************************************************
  75.  *
  76.  *    build_state
  77.  *
  78.  * First builds a new state set to the parameter 'state_set' by taking a
  79.  * union of all those followpositions that belong to the current position
  80.  * 'pos' and that contain 'inp'.
  81.  * Then finds a state that has same set of states as 'state_set' and returns 
  82.  * transition to it. If there isn't equal position in dstates, returns
  83.  * UNKNOWN. If RE_FULL is not specified and we have accepting state, returns
  84.  * transition to the virtual ACCEPTING state.
  85.  */
  86. static tran_t build_state(set_t* state_set, unsigned inp, state_t* state)
  87. {
  88.     REG1 int    i;
  89.     REG2 set_t*    dsset = state->set;
  90.     REG3 node_t*    tptr;
  91.     REG4 int    type;
  92.     
  93.     if (rbuf.ignorecase && islower(inp))
  94.         inp = toupper(inp);
  95.     set_clear(state_set, rbuf.setsize);
  96.     /* build union of followpositions */
  97.     for (i = rbuf.root; i >= 0; i--) {
  98.         if (!in_set(dsset, i))
  99.             continue;
  100.         tptr = &rbuf.tree[i];
  101.         type = tptr->type;
  102.         if ((type == ID && tptr->val.item == inp)
  103.             || (type == CLASS_ID && in_set(tptr->val.class, inp)))
  104.             set_union(state_set, state_set, rbuf.follow_array[i],
  105.                   rbuf.setsize);
  106.     }
  107.     if (set_empty(state_set, rbuf.setsize))
  108.         return rbuf.default_tran;
  109.     if (!rbuf.full && is_accepting(state_set))
  110.         return ACCEPTING;
  111.     /* try to find state with same set of followpositions */
  112.     for (i = rbuf.last_state; i >= 0; i--)
  113.         if (set_equal(state_set, rbuf.dstates[i]->set, rbuf.setsize))
  114.             return transition_to(i);
  115.     if (is_accepting(state_set))
  116.         return ACCEPTING;
  117.     else
  118.         return UNKNOWN;
  119. }
  120.  
  121. /**********************************************************************
  122.  *
  123.  *    add_state
  124.  *
  125.  * Adds new state to dstates in position 'state'. Initializes also
  126.  * state transition table in dstates.
  127.  */
  128. static void add_state(set_t* state_set, REG2 state_t* state)
  129. {
  130.     REG1 int    i;
  131.     REG3 unsigned*    langptr;
  132.     
  133.     /* set default transition */
  134.     if (is_accepting(state_set))
  135.             for (i = 0; i < NLANG; i++)
  136.                     state->tran[i] = ACCEPTING;
  137.     else
  138.             for (i = 0; i < NLANG; i++)
  139.                     state->tran[i] = rbuf.default_tran;
  140.     state->tran[EOL] = state->tran[rbuf.eol];
  141.     state->tran[rbuf.eol] = END_OF_LINE;
  142.     if (rbuf.full || !is_accepting(state_set)) {
  143.         i = rbuf.language[0];
  144.         langptr = rbuf.language + i;
  145.         while (i--)
  146.             state->tran[*langptr--] = UNKNOWN;
  147.     }
  148.     set_copy(state->set, state_set, rbuf.setsize);
  149. }
  150.  
  151. /**********************************************************************
  152.  *
  153.  *    add_transition
  154.  *
  155.  * Adds transition to dtran. Handles also end of line transition if 
  156.  * transition isn't UNKNOWN. Returns transition, which can be changed
  157.  * in the case of end of line transition.
  158.  */
  159. static tran_t add_transition(REG2 state_t* state, REG3 int input,
  160.                  REG1 tran_t tran)
  161. {
  162.     if (tran != UNKNOWN && input == rbuf.eol) {
  163.         state->tran[EOL] = tran;
  164.         tran = END_OF_LINE;
  165.     }
  166.     state->tran[input] = tran;
  167.     if (rbuf.ignorecase && isalpha(input))
  168.         state->tran[CHCASE(input)] = tran;
  169.     return tran;
  170. }
  171.  
  172. /**********************************************************************
  173.  *
  174.  *    free_dfamem
  175.  *
  176.  * Frees all unnecessary memory.
  177.  */
  178. static void free_dfamem(void)
  179. {
  180.     d_free(&rbuf.tree[rbuf.root].firstpos);
  181. }
  182.  
  183. #if FIXTRAN > 0        /* don't include unused code */
  184.  
  185. /**********************************************************************
  186.  *
  187.  *    unmarked
  188.  *
  189.  * Finds next unmarked state.
  190.  */
  191. static state_t* unmarked(void)
  192. {
  193.     REG1 int    i;
  194.     
  195.     for (i = 0; i <= rbuf.last_state; i++)
  196.         if (!rbuf.dstates[i]->marked)
  197.             return rbuf.dstates[i];
  198.     return NULL;
  199. }
  200.  
  201. /**********************************************************************
  202.  *
  203.  *    build_maxtran
  204.  *
  205.  * Constructs FIXTRAN first transitions to dtran.
  206.  */
  207. static void build_maxtran(void)
  208. {
  209.     REG1 int    input;
  210.     REG2 tran_t    tran;
  211.     REG3 int    i;
  212.     REG4 state_t*    state;
  213.     REG5 int    state_cnt;
  214.  
  215.     state_cnt = 0;
  216.     while (state_cnt++ < FIXTRAN && (state = unmarked()) != NULL) {
  217.         state->marked = TRUE;
  218.         for (i = 0; i < rbuf.language[0]; i++) {
  219.             input = rbuf.language[i+1];
  220.             if (input == EOL)
  221.                 continue;
  222.             tran = build_state(rbuf.tmpstate, input, state);
  223.             if (tran == UNKNOWN && rbuf.last_state < NTRAN-1) {
  224.                 rbuf.last_state++;
  225.                 tran = transition_to(rbuf.last_state);
  226.                 add_state(rbuf.tmpstate, state_of(tran));
  227.                 state_of(tran)->marked = FALSE;
  228.             }
  229.             add_transition(state, input, tran);
  230.         }
  231.     }
  232. }
  233.  
  234. #endif    /* FIXTRAN > 0 */
  235.  
  236. /**********************************************************************
  237.  *
  238.  *    dfa
  239.  */
  240. bool dfa(void)
  241. {
  242.     assert(MAXTRAN < UNKNOWN);
  243.     if (!init_dfa()) {
  244.         free_dfamem();
  245.         return FALSE;
  246.     }
  247.     rbuf.last_state = 0;
  248.     rbuf.default_tran = rbuf.search ? FIRST_STATE : STOPSTATE;
  249.     /* create initial state */
  250.     add_state(rbuf.tree[rbuf.root].firstpos, rbuf.dstates[0]);
  251.     rbuf.dstates[0]->marked = FALSE;
  252. #if FIXTRAN > 0
  253.     build_maxtran();
  254. #endif
  255.     free_dfamem();
  256.     return TRUE;
  257. }
  258.  
  259. #ifdef TEST
  260. static int     removed_tran_cnt = 0;
  261. #endif
  262.  
  263. /**********************************************************************
  264.  *
  265.  *    remove_transition
  266.  *
  267.  * Removes all transitions to given state.
  268.  */
  269. static void remove_transition(tran_t tran)
  270. {
  271.     REG3 int    i;
  272.     REG1 int    j;
  273.     REG2 tran_t*    pos;
  274.  
  275. #ifdef TEST
  276.     ++removed_tran_cnt;
  277. #endif
  278.     for (i = 0; i < NTRAN; i++) {
  279.         pos = rbuf.dstates[i]->tran;
  280.         for (j = 0; j < NLANG; j++, pos++) {
  281.                 if (*pos == tran)
  282.                         *pos = UNKNOWN;
  283.         }
  284.     }
  285. }
  286.  
  287. /**********************************************************************
  288.  *
  289.  *    free_cache_pos
  290.  *
  291.  * Returns free cache position. If cache is full, removes old one
  292.  * and returns it as free position. For each state rbuf.dstates[state].marked
  293.  * is used as a use counter for that state (i.e. how many transitions there
  294.  * are to that state). When cache position is needed, the one with smallest
  295.  * reference count is freed and returned. If there are more than one state with
  296.  * the same reference count then the last one is taken.
  297.  */
  298. static tran_t free_cache_pos(REG4 state_t* state)
  299. {
  300.     REG1 unsigned    i;
  301.     REG2 unsigned    mincnt;
  302.     REG3 unsigned    minpos;
  303.     REG5 int    minstate;
  304.     
  305.     if (rbuf.last_state < NTRAN-1) {
  306.         rbuf.last_state++;
  307.         return transition_to(rbuf.last_state);
  308.     }
  309.     mincnt = ~0; /* == maxint */
  310.     minstate = max(FIXTRAN, 1);    /* never remove state zero */
  311.     /* find the removed state (the one with smallesr reference count) */
  312.     for (i = rbuf.last_state; i >= minstate; i--) {
  313.         if (mincnt > rbuf.dstates[i]->marked
  314.             && rbuf.dstates[i] != state)
  315.         {
  316.             mincnt = rbuf.dstates[i]->marked;
  317.             minpos = i;
  318.         }
  319.     }
  320.     rbuf.dstates[minpos]->marked = 1;
  321.     remove_transition(transition_to(minpos));
  322.     return transition_to(minpos);
  323. }
  324.  
  325. /**********************************************************************
  326.  *
  327.  *    get_transition
  328.  *
  329.  * Gets real transition for UNKNOWN transition. This function is called
  330.  * when matching the pattern.
  331.  */
  332. tran_t get_transition(REG2 tran_t tran, REG3 unsigned input)
  333. {
  334.     REG1 tran_t    new_tran;
  335.  
  336.     new_tran = build_state(rbuf.tmpstate, input, state_of(tran));
  337.     if (new_tran == UNKNOWN) {
  338.         /* new state is not one of the old states */
  339.         new_tran = free_cache_pos(state_of(tran));
  340.         add_state(rbuf.tmpstate, state_of(new_tran));
  341.     } else if (new_tran < MAXTRAN)
  342.         state_of(new_tran)->marked++;
  343.     return add_transition(state_of(tran), input, new_tran);
  344. }
  345.  
  346. #ifdef TEST
  347.  
  348. /**********************************************************************
  349.  *
  350.  *    show_dfa_report
  351.  */
  352. void show_dfa_report(void)
  353. {
  354.     int    i, j;
  355.     long    ntran, utran;
  356.     
  357.     ntran = utran = 0L;
  358.     printf ("%u states of %u possible states used\n"
  359.         "%u cache states deleted\n",
  360.         rbuf.last_state+1,
  361.         NTRAN,
  362.         removed_tran_cnt);
  363.     for (i = 0; i <= rbuf.last_state; i++)
  364.         for (j = 0; j < rbuf.language[0]; j++)
  365.             if (rbuf.dstates[i]->tran[rbuf.language[j+1]] == UNKNOWN)
  366.                 utran++;
  367.     ntran = (rbuf.last_state+1)*rbuf.language[0];
  368.     printf("%lu transitions of %lu possible unknown transitions (%lu%%) are unknown\n",
  369.         utran, ntran, ntran == 0 ? 0 : utran*100/ntran);
  370. #ifdef __TURBOC__
  371.     printf("%lu bytes memory free\n", (unsigned long)coreleft());
  372. #endif
  373.     fflush(stdout);
  374. }
  375.         
  376. /**********************************************************************
  377.  *
  378.  *    print_accepting_states
  379.  */
  380. void print_accepting_states(void)
  381. {
  382.     REG1 int    i;
  383.     
  384.     printf("Accepting states: ");
  385.     for (i = 0; i <= rbuf.last_state; i++)
  386.         if (is_accepting(rbuf.dstates[i]->set))
  387.             printf("%d ", i);
  388.     printf("\n");
  389.     fflush(stdout);
  390. }
  391.  
  392. /**********************************************************************
  393.  *
  394.  *    char_image
  395.  */
  396. char* char_image(int c)
  397. {
  398.     static char    s[3];
  399.     char*        s1;
  400.     
  401.     switch (c) {
  402.         case REM:
  403.             s1 = "REM";
  404.             break;
  405.         case EOL:
  406.             s1 = "EOL";
  407.             break;
  408.         case BOL:
  409.             s1 = "BOL";
  410.             break;
  411.         default:
  412.             if (iscntrl(c)) {
  413.                 s[0] = '^';
  414.                 s[1] = '@' + c;
  415.                 s[2] = '\0';
  416.             } else {
  417.                 s[0] = c;
  418.                 s[1] = '\0';
  419.             }
  420.             s1 = s;
  421.             break;
  422.     }
  423.     return s1;
  424. }
  425.  
  426. /**********************************************************************
  427.  *
  428.  *    print_language
  429.  */
  430. void print_language(void)
  431. {
  432.     int    i;
  433.  
  434.     printf("    ");
  435.     for (i = 0; i < rbuf.language[0]; i++)
  436.         printf("%3s ", char_image(rbuf.language[i+1]));
  437.     printf("\n");
  438.     fflush(stdout);
  439. }
  440.  
  441. /**********************************************************************
  442.  *
  443.  *    show_tran
  444.  */
  445. static void show_tran(tran_t t)
  446. {
  447.     int i;
  448.  
  449.     if (t == ACCEPTING)
  450.         printf("%3s ", "Acc");
  451.     else if (t == STOPSTATE)
  452.         printf("%3s ", "Sto");
  453.     else if (t == END_OF_LINE)
  454.         printf("%3s ", "Eol");
  455.     else if (t == UNKNOWN)
  456.         printf("%3s ", "Unk");
  457.     else {
  458. #ifdef FAST
  459.             /* find index of the t */
  460.             for (i = 0; i < NTRAN; i++)
  461.                 if (rbuf.dstates[i] == t)
  462.                     break;
  463.             assert(i < NTRAN);
  464. #else
  465.             i = (int)t;
  466. #endif
  467.             printf("%3d ", i);
  468.     }
  469.     fflush(stdout);
  470. }
  471.  
  472. /**********************************************************************
  473.  *
  474.  *    print_dtran
  475.  */
  476. void print_dtran(void)
  477. {
  478.     int    i, j;
  479.     
  480.     printf("Dstates for each state:\n");
  481.     for (i = 0; i <= rbuf.last_state; i++) {
  482.         printf("%2d:", i);
  483.         for (j = 0; j <= rbuf.root; j++)
  484.             if (in_set(rbuf.dstates[i]->set, j))
  485.                 printf(" %d", j);
  486.         printf("\n");
  487.     }
  488.     printf("Transition table (default transition is ");
  489.     show_tran(rbuf.default_tran);
  490.     printf("):\n");
  491.     print_language();
  492.     for (i = 0; i <= rbuf.last_state; i++) {
  493.         printf("%2d: ", i);
  494.         for (j = 0; j < rbuf.language[0]; j++)
  495.             show_tran(rbuf.dstates[i]->tran[rbuf.language[j+1]]);
  496.         printf("\n");
  497.     }
  498.     fflush(stdout);
  499. }
  500.  
  501. #endif /* TEST */
  502.