Regular expression of compilation principle to NFA

xiaoxiao2021-03-05 29

Foreword: After the last "written a simple C word scan program", the compilation principle experimental class requires a regral expression to turn NFA.

Diagram, this is nothing difficult to algorithm, introduces the Thompson's conversion algorithm in the "Compilation Principle and Practice" book, the book is THMPSON

The algorithm has made detailed text description. If you want to know more about the algorithm, the algorithm is deeper, the mechanical industry publishing house, "Compilation Principles and Practice" translation.

text:

I. Analysis:

Require a regular expression, convert it to NFA, and output the result. There are many ways to transform, using Thompson knot

The conversion method of the structure is the most simple. Thompson Structure: It uses Epsilon-conversion to "paste the regular expressive machine fragment" "

To constitute the entire expression corresponding to the entire expression. It is shown in accordance with the structure defined by the regular expression: an NFA is displayed for each basic regular expression.

Each regular expression is then connected by the operation of the connector. There are four types of regular expressions: connection, selection, closing package

, Positive closure (this program does not support this operation).

Second, the system design:

Overall design: In order to improve the portability of the program, divide it into interface, NFA map, NFA_NODE (NFA diagram point) class, Converte

R (Converter) class and a transition structure.

Program Design: Select C Builder6.0 (BCB6) as a development tool. Converted operation Similar to ordinary four arithmetic, Union operators

To "|", the operator of the Closure is "*", and the Connect connection operation in the expression is expressed as two characters connected EG: AB,

Then need to introduce a symbol to distinguish whether it is a connection operation, introduced "&" as a connection symbol, that is, the upper alteration is A & B, for this purpose, easy to program

. The priority of the three operations from high to low is: *, &, |, and the operation method is completely in accordance with the Thompson structure, so there is this

No squeezing. Refer to ordinary four operations, in the conversion operation of the regular expression, two stacks are introduced, one is an operator stack, the other is

The operation count, and the number of arithmeters is part of the local NFA map. Stack design application template, reduce unnecessary duplicate code, improve design

Abstract degree.

interface design:

http://blog.9cbs.net/images/blog_9cbs_net/zjt621/111594/o_nfainterface.jpg

Third, some of the program source code: (In order to save the switching method, the main algorithm's annotation is used in English, given the poor English,

Mainly written to yourself, if you don't understand your comments, please forgive me. ) / * The following is the event trigger section of the interface * /

/ * Do preprocessing the input string, insert "&" and "=" * / Ansistring __fastcall tform1 :: pretreatstr (ANSISTRING INREGEX) {INT i = 1; char ch, prech; inregex = INREGEX '='; Prech = INREGEX [i ]; ch = INREGEX [I];

While (INREGEX [I]! = '=') {IF ((Isalpha (Prech) && Isalpha (CH) || (isalpha (prech) && ch == '(') ||

(prech == ')' && isalpha (ch)) || (prech == '*' && isalpha (ch) || (prech == '*' && ch == ') {INREGEX.INSERT (' & ', i);} prech = INREGEX [i ]; ch = INREGEX [i];

Return INREGEX;

/ * Traversing NFA Figure * / void __fastcall tform1 :: display (nfa grap) {memo1-> lines-> add ("Convert to NFA results:"); grap.ncurrent = grap.nstart; // set current = Start And Begin Scan Memo1-> Lines-> Add (INTTOSTR (Grap.ncurrent-> StateID) "Start Status"); While (Grap.ncurrent-> nNext! = null) {if (grap.ncurrent-> thead -> TNEXT! = Null) // while have transmit {grap.ncurrent-> tcurrent = grap.ncurrent-> thead-> tnext; while (grap.ncurrent-> tcurrent-> tnext! = Null) {IF (Grap. Ncurrent-> tcurrent-> INCEPT! = '@') {