home *** CD-ROM | disk | FTP | other *** search
/ OS/2 Shareware BBS: 10 Tools / 10-Tools.zip / dmake40.zip / percent.c < prev    next >
C/C++ Source or Header  |  1994-10-23  |  7KB  |  261 lines
  1. /* RCS      -- $Header: /u5/dvadura/src/public/dmake/src/RCS/percent.c,v 1.1 1994/10/06 17:42:51 dvadura Exp $
  2. -- SYNOPSIS -- handle building or %-rule meta-target nfa.
  3. -- 
  4. -- DESCRIPTION
  5. --    Builds the NFA used by dmake to match targets against %-meta
  6. --    rule constructs.  The NFA is built as a set of DFA's.
  7. -- 
  8. -- AUTHOR
  9. --      Dennis Vadura, dvadura@watdragon.uwaterloo.ca
  10. --      CS DEPT, University of Waterloo, Waterloo, Ont., Canada
  11. --
  12. -- COPYRIGHT
  13. --      Copyright (c) 1992,1994 by Dennis Vadura.  All rights reserved.
  14. -- 
  15. --      This program is free software; you can redistribute it and/or
  16. --      modify it under the terms of the GNU General Public License
  17. --      (version 1), as published by the Free Software Foundation, and
  18. --      found in the file 'LICENSE' included with this distribution.
  19. -- 
  20. --      This program is distributed in the hope that it will be useful,
  21. --      but WITHOUT ANY WARRANTY; without even the implied warrant of
  22. --      MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the
  23. --      GNU General Public License for more details.
  24. -- 
  25. --      You should have received a copy of the GNU General Public License
  26. --      along with this program;  if not, write to the Free Software
  27. --      Foundation, Inc., 675 Mass Ave, Cambridge, MA 02139, USA.
  28. --
  29. -- LOG
  30. --     $Log: percent.c,v $
  31.  * Revision 1.1  1994/10/06  17:42:51  dvadura
  32.  * dmake Release Version 4.0, Initial revision
  33.  *
  34. */
  35.  
  36. #include "extern.h"
  37.  
  38. static DFAPTR _build_dfa ANSI((char *));
  39. static char   _shift_dfa ANSI((DFAPTR, char *));
  40.  
  41.  
  42. #define NO_ACTION    0
  43. #define START_PERCENT    1
  44. #define END_PERCENT    2
  45. #define ACCEPT        4
  46. #define FAIL           -1
  47.  
  48. static  NFAPTR _nfa = NIL( NFA );
  49.  
  50.  
  51. PUBLIC DFALINKPTR
  52. Match_dfa( buf )/*
  53. ==================
  54.    This routines runs all DFA's in parrallel and selects the one that best
  55.    matches the string.  If no match then it returns NIL( DFA ) */
  56. char *buf;
  57. {
  58.    register NFAPTR nfa;
  59.    int         adv;
  60.    DFALINKPTR       dfa_list = NIL(DFALINK);
  61.  
  62.    DB_ENTER( "Match_dfa" );
  63.    DB_PRINT( "dfa", ("Matching %s", buf) );
  64.  
  65.    /* Run each of the DFA's on the input string in parallel, we terminate
  66.     * when all DFA's have either failed or ACCEPTED, if more than one DFA
  67.     * accepts we build a list of all accepting DFA's sorted on states with
  68.     * those matching in a higher numbered state heading the list. */
  69.  
  70.    do {
  71.       adv = FALSE;
  72.  
  73.       for( nfa = _nfa; nfa != NIL( NFA ); nfa = nfa->next )
  74.      if( nfa->status != (char) FAIL && nfa->status != (char) ACCEPT ) {
  75.         adv++;
  76.         nfa->status = _shift_dfa( nfa->dfa, buf );
  77.  
  78.         /* Construct the list of matching DFA's */
  79.         if( nfa->status == (char) ACCEPT ) {
  80.            DFALINKPTR dl;
  81.  
  82.            TALLOC( dl, 1, DFALINK );
  83.            dl->dl_meta  = nfa->dfa->node;
  84.            dl->dl_per   = DmSubStr( nfa->dfa->pstart, nfa->dfa->pend );
  85.            dl->dl_state = nfa->dfa->states - nfa->dfa->c_state;
  86.  
  87.            if( dfa_list == NIL(DFALINK) )
  88.               dfa_list = dl;
  89.            else {
  90.           DFALINKPTR tdli = dfa_list;
  91.           DFALINKPTR tdlp = NIL(DFALINK);
  92.  
  93.           for( ; tdli != NIL(DFALINK); tdli = tdli->dl_next ) {
  94.              if( dl->dl_state >= tdli->dl_state )
  95.             break;
  96.              tdlp = tdli;
  97.           }
  98.  
  99.           if( tdli != NIL(DFALINK) ) {
  100.              tdli->dl_prev = dl;
  101.              dl->dl_next   = tdli;
  102.           }
  103.  
  104.           if( tdlp != NIL(DFALINK) ) {
  105.              tdlp->dl_next = dl;
  106.              dl->dl_prev   = tdlp;
  107.           }
  108.           else
  109.              dfa_list = dl;
  110.            }
  111.  
  112.            DB_PRINT( "dfa", ("Matched [%s]", dl->dl_meta->CE_NAME) );
  113.         }
  114.      }
  115.  
  116.       buf++;
  117.    }
  118.    while ( adv );
  119.  
  120.    for( nfa = _nfa; nfa != NIL( NFA ); nfa = nfa->next ) {
  121.       nfa->status = 0;
  122.       nfa->dfa->c_state = nfa->dfa->states;
  123.    }
  124.  
  125.    DB_RETURN( dfa_list );
  126. }
  127.  
  128.  
  129. PUBLIC void
  130. Check_circle_dfa()/*
  131. ====================
  132.    This function is called to test for circularities in the DFA lists
  133.    constructed from %-meta targets. */
  134. {
  135.    register NFAPTR nfa;
  136.  
  137.    for( nfa = _nfa; nfa != NIL(NFA); nfa = nfa->next )
  138.       if( Test_circle( nfa->dfa->node, FALSE ) )
  139.      Fatal( "Detected circular dependency in inference graph at [%s]",
  140.         nfa->dfa->node->CE_NAME );
  141. }
  142.  
  143.  
  144. PUBLIC void
  145. Add_nfa( name )/*
  146. =================
  147.    Given name, build a DFA and add it to the NFA.  The NFA is maintained as
  148.    a singly linked list of DFA's. */
  149. char *name;
  150. {
  151.    NFAPTR nfa;
  152.  
  153.    TALLOC(nfa, 1, NFA);
  154.    nfa->dfa = _build_dfa(name);
  155.  
  156.    if( _nfa != NIL(NFA) ) nfa->next = _nfa;
  157.  
  158.    _nfa = nfa;
  159. }
  160.  
  161.  
  162. static DFAPTR
  163. _build_dfa( name )/*
  164. ====================
  165.    Construct a dfa for the passed in cell name.  The routine returns a struct
  166.    that represents a finite state machine that can recognize a regular
  167.    expression with exactly one '%' sign in it.  The '%' symbol is used as a
  168.    wildcard character that will match anything except the character that
  169.    immediately follows it or NUL.
  170.  
  171.    The Construction of DFA's is well known and can be found in Hopcroft and
  172.    Ullman or any other book discussing formal language theory.
  173.    A more practical treatise can be found in Compilers, Aho, Sethi and Ullman.
  174. */
  175. char *name;
  176. {
  177.    DFAPTR   dfa;
  178.    int      nstates;
  179.    register STATEPTR sp;
  180.    STATEPTR per_state = NIL(STATE);
  181.    int      pcount=0;
  182.    int      end_percent=FALSE;
  183.  
  184.    nstates = strlen(name)+2;
  185.  
  186.    /* Allocate a DFA node and the right number of states. */
  187.    TALLOC(dfa, 1, DFA);
  188.    TALLOC(sp=dfa->c_state=dfa->states, nstates, STATE);
  189.    dfa->node = Def_cell( name );
  190.  
  191.    /* Now construct the state table for the DFA */
  192.    do {
  193.       if( *name == '%' ) {
  194.      if( pcount++ > 0 )
  195.         Error( "Only one %% allowed within a %%-meta target" );
  196.  
  197.      sp->symbol   = 0;
  198.      sp->action   = START_PERCENT;
  199.      sp->no_match = sp->match = per_state = sp+1;
  200.      end_percent  = TRUE;
  201.       }
  202.       else {
  203.      sp->symbol   = *name;
  204.      sp->no_match = per_state;
  205.  
  206.      if( *name == '\0' ) {
  207.         sp->action = ACCEPT;
  208.         sp->match  = dfa->states;
  209.      }
  210.      else {
  211.         sp->action = NO_ACTION;
  212.         sp->match  = sp+1;
  213.      }
  214.  
  215.      if( end_percent ) {
  216.         sp->action |= END_PERCENT;
  217.         end_percent = FALSE;
  218.      }
  219.       }
  220.       
  221.       sp++; 
  222.    }
  223.    while( *name++ );
  224.  
  225.    return(dfa);
  226. }
  227.  
  228.  
  229. static char
  230. _shift_dfa( dfa, data )/*
  231. =========================
  232.    Take a given dfa and advance it based on the current state, the shift
  233.    action in that state, and the current data value. */
  234. DFAPTR dfa;
  235. char   *data;
  236. {
  237.    register STATEPTR sp = dfa->c_state;
  238.    char c = *data;
  239.  
  240.    /* Check if it is a START_PERCENT action if so then we need to save
  241.     * a pointer to the start of the string and advance to the next state. */
  242.    if( sp->action & START_PERCENT ) {
  243.       dfa->pstart = data;
  244.       sp++;
  245.    }
  246.  
  247.    /* Now check if the current char matches the character expected in the
  248.     * current state.  If it does then perform the specified action, otherwise
  249.     * either shift it or fail.  We fail if the next state on no-match is
  250.     * NIL. */
  251.    if( sp->symbol == c ) {
  252.       if( sp->action & END_PERCENT ) dfa->pend = data;
  253.       if( sp->action & ACCEPT ) return(ACCEPT);
  254.       dfa->c_state = sp->match;
  255.    }
  256.    else if( (dfa->c_state = sp->no_match) == NIL(STATE) || !c )
  257.       return((unsigned char) FAIL);
  258.  
  259.    return(NO_ACTION);
  260. }
  261.