正则表达式直接转为DFA算法www

正则表达式直接转DFA

一、 设计原理

1. 正则表达式转换为DFA

算法描述

2. 正则表达式转换为DFA

（1） 建立字母表。输入的正则表达式由于一般不输入“与”操作符，因此

首先给表达式加入 .作为与操作。再利用逆波兰式的堆栈操作，把操作符与字母分开，便得到了字母表。

（2） 详解NULLABLE、FIRSTPOS、LASTPOS和FOLLOWPOS的计算规则 （3） 转载请注明出处：http://www.cnblogs.com/dzodzo/archive/2009/12/15/1624225.html （4） PDF版：http://www.fsderno.com/pdf/complier1.pdf （5） 引入 （6） 正在上编译原理的课程，为了对抗遗忘，写下这篇文章加强自己的记忆，

同时也希望能给大家带来帮助。

（7） 在编译原理中，要把正则表达式转化为DFA，其中有一步就是要计算语法

分析树上各结点的nullable、firstpos、lastpos和followpos。如果不理解其中的原理去背计算规则，这是一件非常痛苦的事情，本文的目的就是希望能说清楚两个问题，为什么要计算，如何计算。

（8） 前置知识：

（9） 句子：给定文法G[Z],若有Z +=> x, 且x∈VT*；则称x是文法G[Z]

的句子。

（10） or结点：标号为并运算符|的内部结点。 （11） cat结点：标号为连接运算符·的内部结点。 （12） star结点：标号为星号运算符*的内部结点。 （13） 位置：每个终结符对应一个位置。如图1。

（14）

（15） 计算NULLABLE(N)

（16） 说完了前置知识，我们先说一下比较容易理解的nullable(n)，为什么要

计算nullable(n)呢？那是因为我们要根据结点n的nullable(n)函数的取值而采取不同的方法去计算firstpos和lastpost。说到这里可能有人要骂我了，“你这说了等于没说嘛”。希望大家稍安勿躁，因为问题是环环相扣的，我只是把解答放到后面了呵呵。

（17） nullable(n)表示以n为根结点推导出的句子集合是否包括空串，当推导

出的句子集合包含空串，那么nullable(n)=true；如果不包含空串，那么nullable(n)=false。现在我们针对结点n的五种情况进行分析： （18） 1、当结点n是叶子结点并且取值为空，此时以n为根结点推导出的句子

肯定为空，所以此时nullable(n)为true。如图2所示。

（19）

（20） 2、当结点n是叶子结点并且取值为id，此时以n推导出的句子有非空值

id，所以此时nullable(n)为false。

（21）

（22） 3、当结点n是or结点，此时n结点肯定为内部结点。由于是或运算，

当结点n的左子树(c1)或者右子树(c2)能推导出空串时，结点n也能推导出空串。即nullable(n)=nullable(c1) or nullable(c2)。以下三种情况都会使nullable(n)=true。(c1->ε表示c1能推导出空串ε，下同)

（23）

（24） 4、当结点n是cat结点，此时n结点肯定为内部结点。由于是连接运算，

当结点n的左子树（c1）和右子树（c2）能同时推导出空串，则结点n能推导出空串，即nullable(n)=nullable(c1) and nullable(c2)。以下一种情况nullable(n)=true。

（25）

（26） 5、当结点n是star结点，此时n结点肯定为内部结点，由Kleene闭包

运算的定义可知结点n推导出的句子集合包括空串，因此nullable(n)=true。

（27）

（28） 计算FIRSTPOS(N)

（29） 说完了nullable的计算规则，我们来说下firstpos(n)。为什么要算

firstpos？那是因为我们在为计算followpos做准备：）不要郁闷，继续往下看，你一定会知道终极的原因！firstpos(n)函数定义了以结点n为根的子树中的位置集合。这些位置对应于以结点n为根推导出的某个句子的第一个符号（“某个”代表可能有多个，因此firstpos的计算结果是位置的集合）。我们还是按照nullable的分析方法，以五种结点类型说明firstpos(n)的计算规则。

（30） 1、当结点n为叶子结点并且为空串，因为是空串，所以此时没有第一个符号，即firstpos(n)={?}。

（31）

（32） 2、当结点n为位置i的叶子结点。此时结点n只能推导出位置i的终结符，因此firstpos(n)={i}

（33）

（34） 3、当结点n为or结点（内部结点），此时进行or运算，左子树(c1)推

导出的第一个位置的集合firstpos(c1)包含于firstpos(n)，同样右子树(c1)推导出的第一个位置的集合firstpos(c2)包含于firstpos(n)。因此firstpos(n)等于左右子树firstpos的并集。即firstpos(n)=firstpos(c1) U firstpos(c2)。

（35）

（36） 4、当结点n为cat结点（内部结点），此时进行连接运算，若左子树不能

推导出空串，那么结点n推导出的某个句子的第一个符号一定在firstpos(n)中。若左子树能推导出空串，那么第一个符号就有可能出现在右子树推导出的句子中。 （37） 因此：if(nullable(c1))

（38） firstpos(n)=firstpos(c1) U firstpos (c2) //图9 （39） else

（40） firstpos(n)=firstpos(c1) //图10

（41）

（42） 5、当结点n为star结点（内部结点），结点n只有一个棵子树(c1)，无

论结点n的能不能推导出空串，firstpos(n)=firstpos(c1)。

Stack *s1,*s2; //s1为保存运算符的堆栈，s2为逆波兰式的输出结果 s1=(Stack *)malloc(sizeof(Stack)); s2=(Stack *)malloc(sizeof(Stack)); InitList(s1); InitList(s2); Push(s1,'#');

if((fp=fopen(\路径的写法 {

printf(\ exit(0); } else {

while((ch=fgetc(fp))!=EOF) {

if(Isalpha(ch)) {

Push(s2,ch); }

//begin ：求取逆波兰式 else {

//括号的处理 if(ch=='(') { Push(s1,ch); } else {

if(ch==')') {

temp=GetTop(s1); while(temp!='('){ Push(s2,temp); Pop(s1);

temp=GetTop(s1); }

Pop(s1); } else { temp=GetTop(s1); //putchar(temp);

if(temp=='(') Push(s1,ch); else {

if(PriorCompare(ch,temp))//新的运算符的优先级高于栈顶元素 { Push(s1,ch); }

else {

while(PriorCompare(ch,temp)==0) {

Push(s2,temp); Pop(s1);

temp=GetTop(s1); if(temp=='(') break; }

Push(s1,ch); } } } } } } }

while(StackEmpty(s1)!=1) {

temp=GetTop(s1); Push(s2,temp); Pop(s1);

}//end:求取逆波兰式结束

//begin:下为显示逆波兰表达式，并将其存入到一个数组中的结果 int i = s2->top ; char nbl[i+1];

if(!StackEmpty(s2)) {

printf(\将正则表达式转换为逆波兰表达式后为：\ for(int j=0;j

nbl[j]= s2->data[j]; putchar(nbl[j]); }

nbl[i]='.';

putchar(nbl[i]); printf(\ }

//end:显示逆波兰结束

//begin:采用直接转为DFA的算法 int length= s2->top+1; bool nullable[length];

int position[length];//标识字符位置 int firstpos[length][length]; int lastpos[length][length]; int followpos[length][length]; int pos=1;

for(int i=0;i

for(int j=0;j

firstpos[i][j]=lastpos[i][j]=followpos[i][j]=0; } }

// printf(\ for(int i=0;i

if(Isalpha(nbl[i])||nbl[i]=='#') { position[i]=pos; pos++; nullable[i]=false; firstpos[i][0]=position[i]; lastpos[i][0]=position[i]; } else { position[i]=0;//运算符的position设为0 if(nbl[i]=='|') { nullable[i]=(nullable[i-2]||nullable[i-1]); int j=0; while(firstpos[i-1][j]!=0) { firstpos[i][j]=firstpos[i-1][j]; lastpos[i][j]=firstpos[i-1][j];

j++;

}

int k=0; int m;

while(firstpos[i-2][k]!=0) {

for(m=0;m

if(firstpos[i][m]==firstpos[i-2][k]) break; }

if(m==j) {

firstpos[i][j]=firstpos[i-2][k]; lastpos[i][j]=firstpos[i-2][k]; j++; } k++; } }

else if(nbl[i]=='*') { nullable[i]=true; int j=0; while(firstpos[i-1][j]!=0) { firstpos[i][j]=firstpos[i-1][j]; lastpos[i][j]=firstpos[i-1][j]; j++; }

}

else //连接符. { nullable[i]=(nullable[i-2]&&nullable[i-1]); if(nullable[i-2]==1) { int j=0; int m; while(firstpos[i-1][j]!=0) {

firstpos[i][j]=firstpos[i-1][j]; j++;

}

int k=0;

while(firstpos[i-2][k]!=0) {

for(m=0;m

if(firstpos[i][m]==firstpos[i-2][k]) break; }

if(m==j) {

firstpos[i][j]=firstpos[i-2][k]; j++; } k++; } } else { int j=0; while(firstpos[i-2][j]!=0) { firstpos[i][j]=firstpos[i-2][j]; j++; }

}

if(nullable[i-1]) { int j=0; while(firstpos[i-1][j]!=0) { lastpos[i][j]=firstpos[i-1][j]; j++;

}

int k=0; int m;

while(firstpos[i-2][k]!=0) {

for(m=0;m

if(lastpos[i][m]==firstpos[i-2][k])

break; }

if(m==j) {

lastpos[i][j]=firstpos[i-2][k]; j++; } k++; } } else { int j=0; while(firstpos[i-1][j]!=0) { lastpos[i][j]=firstpos[i-1][j]; j++; }

} } } }

for(int i=0;i

int j=0;

while(firstpos[i][j]!=0) { printf(\ j++;

}

printf(\ }

printf(\ for(int i=0;i

int j=0;

while(lastpos[i][j]!=0) { printf(\

j++;

}

printf(\ }

for(int i=0;i

if(nbl[i]=='.') {

int m=0;

while(lastpos[i-2][m]!=0) {

int k;

for(k=0;k

if(followpos[lastpos[i-2][m]][k]==0) break; }

int n=0;

while(firstpos[i-1][n]!=0) {

followpos[lastpos[i-2][m]][k]=firstpos[i-1][n]; n++; k++; } m++; } }

if(nbl[i]=='*') {

int m=0;

while(lastpos[i][m]!=0) {

int n;

for(n=0;n

if(followpos[lastpos[i][m]][n]==0) break; }

int k=0;

while(firstpos[i][k]!=0) {

followpos[lastpos[i][m]][n]=firstpos[i][k]; k++;

n++; } m++; } } }

printf(\ for(int i=0;i

if(position[i]!=0) {

int k=0;

printf(\

while(followpos[position[i]][k]!=0) { printf(\ k++;

}

printf(\ } }

//end:直接转为DFA的算法 getch(); return 0; }

本文来源：https://www.bwwdw.com/article/zr0r.html