1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152
153
154
155
156
157
158
159
160
161
162
163
164
165
166
167
168
169
170
171
172
173
174
175
176
177
178
179
180
181
182
183
184
185
186
187
188
189
190
191
192
193
194
195
196
197
198
199
200
201
202
203
204
205
206
207
208
209
210
211
212
213
214
215
216
217
218
219
220
221
222
223
224
225
226
227
228
229
230
231
232
233
234
235
236
237
238
239
240
241
242
243
244
245
246
247
248
249
250
251
|
/* 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);
}
|
