summaryrefslogtreecommitdiff
path: root/dmake/percent.c
diff options
context:
space:
mode:
Diffstat (limited to 'dmake/percent.c')
-rw-r--r--dmake/percent.c251
1 files changed, 0 insertions, 251 deletions
diff --git a/dmake/percent.c b/dmake/percent.c
deleted file mode 100644
index 732473ce3..000000000
--- a/dmake/percent.c
+++ /dev/null
@@ -1,251 +0,0 @@
-/* RCS $Id: percent.c,v 1.1.1.1 2000-09-22 15:33:25 hr Exp $
---
--- SYNOPSIS
--- Handle building or %-rule meta-target nfa.
---
--- DESCRIPTION
--- Builds the NFA used by dmake to match targets against %-meta
--- rule constructs. The NFA is built as a set of DFA's.
---
--- AUTHOR
--- Dennis Vadura, dvadura@dmake.wticorp.com
---
--- WWW
--- http://dmake.wticorp.com/
---
--- COPYRIGHT
--- Copyright (c) 1996,1997 by WTI Corp. All rights reserved.
---
--- This program is NOT free software; you can redistribute it and/or
--- modify it under the terms of the Software License Agreement Provided
--- in the file <distribution-root>/readme/license.txt.
---
--- LOG
--- Use cvs log to obtain detailed change logs.
-*/
-
-#include "extern.h"
-
-static DFAPTR _build_dfa ANSI((char *));
-static char _shift_dfa ANSI((DFAPTR, char *));
-
-
-#define NO_ACTION 0
-#define START_PERCENT 1
-#define END_PERCENT 2
-#define ACCEPT 4
-#define FAIL -1
-
-static NFAPTR _nfa = NIL( NFA );
-
-
-PUBLIC DFALINKPTR
-Match_dfa( buf )/*
-==================
- This routines runs all DFA's in parrallel and selects the one that best
- matches the string. If no match then it returns NIL( DFA ) */
-char *buf;
-{
- register NFAPTR nfa;
- int adv;
- DFALINKPTR dfa_list = NIL(DFALINK);
-
- DB_ENTER( "Match_dfa" );
- DB_PRINT( "dfa", ("Matching %s", buf) );
-
- /* Run each of the DFA's on the input string in parallel, we terminate
- * when all DFA's have either failed or ACCEPTED, if more than one DFA
- * accepts we build a list of all accepting DFA's sorted on states with
- * those matching in a higher numbered state heading the list. */
-
- do {
- adv = FALSE;
-
- for( nfa = _nfa; nfa != NIL( NFA ); nfa = nfa->next )
- if( nfa->status != (char) FAIL && nfa->status != (char) ACCEPT ) {
- adv++;
- nfa->status = _shift_dfa( nfa->dfa, buf );
-
- /* Construct the list of matching DFA's */
- if( nfa->status == (char) ACCEPT ) {
- DFALINKPTR dl;
-
- TALLOC( dl, 1, DFALINK );
- dl->dl_meta = nfa->dfa->node;
- dl->dl_per = DmSubStr( nfa->dfa->pstart, nfa->dfa->pend );
- dl->dl_state = nfa->dfa->states - nfa->dfa->c_state;
-
- if( dfa_list == NIL(DFALINK) )
- dfa_list = dl;
- else {
- DFALINKPTR tdli = dfa_list;
- DFALINKPTR tdlp = NIL(DFALINK);
-
- for( ; tdli != NIL(DFALINK); tdli = tdli->dl_next ) {
- if( dl->dl_state >= tdli->dl_state )
- break;
- tdlp = tdli;
- }
-
- if( tdli != NIL(DFALINK) ) {
- tdli->dl_prev = dl;
- dl->dl_next = tdli;
- }
-
- if( tdlp != NIL(DFALINK) ) {
- tdlp->dl_next = dl;
- dl->dl_prev = tdlp;
- }
- else
- dfa_list = dl;
- }
-
- DB_PRINT( "dfa", ("Matched [%s]", dl->dl_meta->CE_NAME) );
- }
- }
-
- buf++;
- }
- while ( adv );
-
- for( nfa = _nfa; nfa != NIL( NFA ); nfa = nfa->next ) {
- nfa->status = 0;
- nfa->dfa->c_state = nfa->dfa->states;
- }
-
- DB_RETURN( dfa_list );
-}
-
-
-PUBLIC void
-Check_circle_dfa()/*
-====================
- This function is called to test for circularities in the DFA lists
- constructed from %-meta targets. */
-{
- register NFAPTR nfa;
-
- for( nfa = _nfa; nfa != NIL(NFA); nfa = nfa->next )
- if( Test_circle( nfa->dfa->node, FALSE ) )
- Fatal( "Detected circular dependency in inference graph at [%s]",
- nfa->dfa->node->CE_NAME );
-}
-
-
-PUBLIC void
-Add_nfa( name )/*
-=================
- Given name, build a DFA and add it to the NFA. The NFA is maintained as
- a singly linked list of DFA's. */
-char *name;
-{
- NFAPTR nfa;
-
- TALLOC(nfa, 1, NFA);
- nfa->dfa = _build_dfa(name);
-
- if( _nfa != NIL(NFA) ) nfa->next = _nfa;
-
- _nfa = nfa;
-}
-
-
-static DFAPTR
-_build_dfa( name )/*
-====================
- Construct a dfa for the passed in cell name. The routine returns a struct
- that represents a finite state machine that can recognize a regular
- expression with exactly one '%' sign in it. The '%' symbol is used as a
- wildcard character that will match anything except the character that
- immediately follows it or NUL.
-
- The Construction of DFA's is well known and can be found in Hopcroft and
- Ullman or any other book discussing formal language theory.
- A more practical treatise can be found in Compilers, Aho, Sethi and Ullman.
-*/
-char *name;
-{
- DFAPTR dfa;
- int nstates;
- register STATEPTR sp;
- STATEPTR per_state = NIL(STATE);
- int pcount=0;
- int end_percent=FALSE;
-
- nstates = strlen(name)+2;
-
- /* Allocate a DFA node and the right number of states. */
- TALLOC(dfa, 1, DFA);
- TALLOC(sp=dfa->c_state=dfa->states, nstates, STATE);
- dfa->node = Def_cell( name );
-
- /* Now construct the state table for the DFA */
- do {
- if( *name == '%' ) {
- if( pcount++ > 0 )
- Error( "Only one %% allowed within a %%-meta target" );
-
- sp->symbol = 0;
- sp->action = START_PERCENT;
- sp->no_match = sp->match = per_state = sp+1;
- end_percent = TRUE;
- }
- else {
- sp->symbol = *name;
- sp->no_match = per_state;
-
- if( *name == '\0' ) {
- sp->action = ACCEPT;
- sp->match = dfa->states;
- }
- else {
- sp->action = NO_ACTION;
- sp->match = sp+1;
- }
-
- if( end_percent ) {
- sp->action |= END_PERCENT;
- end_percent = FALSE;
- }
- }
-
- sp++;
- }
- while( *name++ );
-
- return(dfa);
-}
-
-
-static char
-_shift_dfa( dfa, data )/*
-=========================
- Take a given dfa and advance it based on the current state, the shift
- action in that state, and the current data value. */
-DFAPTR dfa;
-char *data;
-{
- register STATEPTR sp = dfa->c_state;
- char c = *data;
-
- /* Check if it is a START_PERCENT action if so then we need to save
- * a pointer to the start of the string and advance to the next state. */
- if( sp->action & START_PERCENT ) {
- dfa->pstart = data;
- sp++;
- }
-
- /* Now check if the current char matches the character expected in the
- * current state. If it does then perform the specified action, otherwise
- * either shift it or fail. We fail if the next state on no-match is
- * NIL. */
- if( sp->symbol == c ) {
- if( sp->action & END_PERCENT ) dfa->pend = data;
- if( sp->action & ACCEPT ) return(ACCEPT);
- dfa->c_state = sp->match;
- }
- else if( (dfa->c_state = sp->no_match) == NIL(STATE) || !c )
- return((unsigned char) FAIL);
-
- return(NO_ACTION);
-}
generated by cgit v1.2.3 (git 2.39.1) at 2024-05-23 23:15:55 +0000