- laboratory work number : PLMM 5
- variant description : Regular expression
- list of group members : Liu Jun ; Wang Xin Yue
- contribution summary for each group member (should be checkable by git log and git blame);
- Liu Jun's main contribution is in the grammatical analysis and the establishment of NFA,
- Wang Xin Yue's main contribution is in the lexical analysis and testing
- Together to Complete readme.md
Regular expression.
- Support special characters: , ^, ., $, *, +, [ ], [ ^ ], { }.
- Support functions: match, sub.
- Visualization as a finite state machine (state diagram or table).
We use the NFA way to write our regular expression state machine, first perform the lexical analysis of the expression, then use the bottom-up method for grammatical analysis, and then establish NFA, and finally used to match the string.
-
work demonstration (how to use developed software, how to test it), should be repeatable by an instructor by given command-line examples;
- output
- visualization using GraphViz
The regular expression can be executed by constructing an equivalent NFA and then executing NFA to match the input string.
-
NFA means Nondeterministic Finite Automaton
The working process of the finite state machine is the process of automatically performing state transition from the starting state according to different inputs.
-
From regular expression to NFA
We use the Thompson algorithm to convert regular expressions to NFA. It is not the most efficient algorithm, but it is practical and easy to understand.
- 1.the Lexer wrapper the regular make it easier to handle
- 2.Nfa is the Data Structure of nfa
- 3.ErrorHandler deal the error in the project
- NfaInterpretor to get the graph of nfa.
- 4.NfaManager to manager the nfa node, include set node num ...
- 5.NfaMachineConstructor use to construct the nfa of the regular expression.
- 6.Re deal the nfa. include the method match and sub;
- 7.Test do the unit Test of the regular expression engine
you can see the test in the file "Test"