readme.txt

扫描样本字符串

Readme

This project is implemented based on C/C++ language and Visual C++ 6.0 compiler, and
include four major modules. Pls. compile it on VC++6.0.

module 1:  
The marjor function is preliminary processing, include read file and seperate the RE and sample lines.

module 2:
The marjor function is build up NFA data structures according to the RE.
The NFA data structure include two parts: NFA_list, the state stes; 
and NODE_list, the adjoining edge table list.
Finally they are united into NFA_List, Array of NODE_LIST*.

module 3:
The marjor function is useing subset construction to seperate labeleds tates and unlabeled 
states in each step. Each step add one unabled state and count its e_closure
set U, and if the e_closure set U is not found in Dstates, then add U in 
Dstates as unlabeled. Finally buildup DFA data structure as two parts
STATE_LIST* DFAStateArray and NODE_LIST* DFAtransArray. Also startlist
and acceptlist is build up by considering if the old start or accept NFA state 
bcan be found in the new DFA states.

module 4:
The marjor function is verify each sample line by DFA data structure. Also considering the empty string situation by check if startlist can be found in acceptlist.

Some major function explanation:
Translate() -- add some union symbol "&" in the string;
GetLetters() --  build up the alphabeteic character stack;
RToNFA() -- Analyze the incoming character from sample string and check the fore and current 
operator symbol( "(",")","|","*","&") in the operator symbol stack, then decide push or pop the operator symbol and whether should do according operation. The operator symbol has opeartion priority.
TranslateNFA() -- unite the two different tables of the NFA data structure into one new table.
NFAToDFA() -- construct DFA data structure based on subset construction method.  
TranslateDFA() -- change the DFA data structure into two parts:  DFAStateArray and DFAtransArray.
VerifySample() -- check the sample line by tracing the DFAtransArray fromt he start state.Also considered the special case of  input character of "e".


For programming and codeing, I reference some implementation of compiler and automata machine module from Internet.