DFA.rar_NFA DFA_fa_java DFA_lexical nfa to dfa_nfa to dfa.cpp

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.