2023年11月29日发(作者：)

编译原理之正则表达式转NFA

本⽂转载⾃

输⼊⼀个正则表达式，输出⼀个NFA。

我的做法：输⼊⼀个字符串表⽰正则，输出则是把输出到⼀个.dot⽂件中并将dot⽂件编译成pdf，fedora需要sudo yum install dot，然后

evince 就可以查看⽣成的NFA了。

具体算法是按照龙书上的Tompson算法来的。

废话不多说，放码过来：

/*

Author：ChrisZZ(zchrissirhcz@)

Time:2013-12-25 14:13:09

输⼊：正则表达式

输出：⾃动机

算法步骤：

1.把正则表达式转化为后缀表达式

2.把后缀表达式转化为NFA

3.⽤dot语⾔把NFA输出到PDF

参考：

r Expression Matching Can Be Simple And Fast

/~rsc/regexp/

2.龙书 chap3.7.4 从正则表达式构造NFA

学长的project中dot语⾔的使⽤

其他说明：

1.需要安装dot，并添加到系统path中

2.在windows下运⾏时，控制台因为编码不⽀持可能导致中⽂提⽰⽆法显⽰

*/

#include

#include

#include

#include

#include

#include

#include

using namespace std;

const int Match = 256;

const int Split = 257;//表⽰epsilon分⽀

struct Paren{//括号结构体

int natom;

int nalt;

};

string re2post(string re){

Paren paren;//括号

stackparenStk;

string postExpr="";

int i, len=();

int nalt=0, natom=0;

const string invalidRegExp = "⾮法的正则表达式";

for(i=0; i

if(isspace(re[i])) continue;

if(isalpha(re[i])){

if(natom>1){

natom--;

postExpr = postExpr + '.';

}

natom++;

postExpr = postExpr + re[i];

}

}

while(nalt-->0){

postExpr = postExpr + '|';

}

paren=();

();

natom = ;

nalt = ;

natom++;

}

else if(re[i]=='*'){

if(natom==0)

throw runtime_error(invalidRegExp+":提前出现'*'");

postExpr = postExpr + re[i];

}

else if(re[i]=='|'){

if(natom==0) throw runtime_error(invalidRegExp+":提前出现'|'");

tail->c = Split;

tail->out = newTail;

->c = Split;

->out = newTail;

tail = newTail;

head = newHead;

= NULL;

= NULL;

}

void doStar(){

State* newTail = new State(Match, NULL, NULL);

State* newHead = new State(Split, head, newTail);

tail->c = Split;

tail->out = newTail;

if(p->out1!=NULL){

flag = 1;

if(p->out1->id==0)

p->out1->id = id++;

else

flag = 0;

fprintf(file, "t%d -> %d [label = <ε>]n", p->id, p->out1->id);

what = p->out1;

if(flag) (what);

}

}

}

for(i=1; i

fprintf(file, "t%d [shape = circle", i);

if(circle[i])

fputs(", peripheries = 2", file);

fprintf(file, "]n");

string postExpr = re2post(re);

cout << "postExpr is : " << postExpr << endl;

NFA nfa = post2nfa(postExpr);

2graph(re);

cout << "继续吗?(y/n)n" << endl;

char c;

cin >> c;