程序设计语言|正规式

词法分析是把构成源程序的字符串转换成单词符号序列。词法规则可用 3型文法 （正规文法）或正规表达式描述，他产生的集合是语言基本字符集Σ（字母表）上的字符串的一个子集，称为正规集。

正规式是一种表示正规集的工具，正规式是描述程序语言单词的表达式，对于字母表Σ。

正规式（正规表达式）的运算符有3个，优化级从高到低顺序排列为：（闭包）、·（连接，可省略）、|（或）。

正规式  →  正规集

ab  →  字符串ab构成的集合

a|b  →  字符串a、b构成的集合

a  →  由0个或多个a构成的字符串集合

(a|b)  →  所有字符a和b构成的串的集合

a(a|b)  →  以a为首字符的a、b字符串的集合

(a|b)abb  →  以abb结尾的a、b字符串的集合

有限自动机可以转换为正规式，正规式也可以转换为有限自动机。

词法分析器的构造步骤：

1）用正规式描述语言中的单词构成规则。

2）为每个正规式构造一个NFA，它识别正规式所表示的正规集。

3）将构造出的NFA转换成等价的DFA。

4）对DFA进行最小化处理，使其最简。

5）从DFA构造词法分析器。

using namespace std;

struct BiNode

{

char data;

BiNode lchild, rchild;

};

typedef BiNode BiTree;

int CreateBiTree(BiTree &T, const char s1, const char s2, int len)

{

if (len<=0)

{

T = NULL;

return 1;

}

else

{

T = new BiNode;

T->data = s1;

int i;

for ( i=0; i<len; i++) if (s2[i]==s1) break;

CreateBiTree(T->lchild, s1+1, s2, i);

CreateBiTree(T->rchild, s1+i+1, s2+i+1, len-(i+1));

}

return 1;

}

int DestroyBiTree(BiTree &T)

{

if (T==NULL) return 1;

DestroyBiTree(T->lchild);

DestroyBiTree(T->rchild);

delete T;

T = NULL;

return 1;

}

int ATraverse(BiTree &T)

{

if (T==NULL) return 1;

ATraverse(T->lchild);

ATraverse(T->rchild);

cout<<T->data;

return 1;

}

main()

{

char a[2000],b[2000];

while(cin>>a>>b)

{

BiTree T;

int count=0;

int n;

for(n=0;a[n]!='\0';n++);

CreateBiTree(T,a,b,n);

ATraverse(T);

cout<<" ";

cout<<endl;

DestroyBiTree(T);

具有ε动作的NFA的确定化——子集法由于现在的NFA中具有ε动作，故下面要介绍的构造相应DFA的方法和定理3�1中所给出的方法有所不同。

设已给具有ε动作的非确定的有限自动机

M=(K,Σ,f,S0,Z)

则构造相应的DFA

M′=(K′,Σ,f′,q0,Z′)

的基本思路是： 首先把从S0出发，仅经过任意条ε矢线所能到达的状态所组成的集合作为M′的初态q0，然后分别把从q0出发，经过对输入符号a∈Σ的状态转移所能到达的状态 (包括转移后再经ε矢线所能到达的状态)组成的集合作为M′的状态，如此等等，直到不再有新的状态出现为止。具体地说，构造K′及f′的步骤可递归地描述如下。

1�令K′={εCLOSURE(S0)}(给出M′的初态q0)。

2�对于K′中任一尚未标记的状态qi={Si1,Si2,…,Sim},Sik∈K，做：

(1) 标记qi；

(2) 对于每个a∈Σ，置

T=f({Si1,Si2,…,Sim},a)

qj=εCLOSURE(T)

(3) 若qj不在K′中，则将qj作为一个未加标记的状态添加到K′中，且把状态转移

f′(qi,a)=qj

添加到M′。

3�重复进行步骤2，直到K′中不再含有未标记的状态为止。对于由此构造的K′，我们把那些至少含有一个Z中的元素的qi作为M′的终态。

例3�4再考虑图310所示的NFA，对它应用上述算法进行确定化，我们有：

1�因为εCLOSURE(S0)={S0,S1,S2,S3}，故将q0={S0,S1,S2,S3}作为未标记的状态置于K′中。

2�此时K′中仅有惟一的未标记状态q0，故

(1) 标记q0；

(2) 作

f′(q0,a)=εCLOSURE(f({S0,S1,S2,S3},a))=

εCLOSURE(S0)=q0

f′(q0,b)=εCLOSURE(f({S0,S1,S2,S3},b))=

εCLOSURE({S1,S3})={S1,S3}

且把q1={S1,S3}作为未加标记的状态加入K′中，再作

f′(q0,c)=εCLOSURE(f({S0,S1,S2,S3},c))=

εCLOSURE({S2})={S2,S3}

且把q2={S2,S3}作为未加标记的状态加入K′中。

3�此时，K′={q0,q1,q2}，其中q1,q2均未加标记，故

(1) 标记q1；

(2) 作

f′(q1,a)=εCLOSURE(f({S1,S3},a))=

εCLOSURE(�)=�

f′(q1,b)=εCLOSURE(f({S1,S3},b))=

εCLOSURE({S1,S3})=q1

f′(q1,c)=εCLOSURE(f({S1,S3},c))=此时，K′未增大，但q2尚未标记，故

(1) 标记q2；(2) 类似地可求得f′(q2,a)=f′(q2,b)=� f′(q2,c)=q2；至此，K′中的状态q0,q1,q2已全部标记完毕，故确定化的过程结束。最后，容易看到，Z′={q0,q1,q2}，且所得的DFA M′如图312所示。

例3�5对于图311所示的NFA，利用上述算法所得的DFA如图313所示。其中，圆圈中的数字都是原NFA的状态编号，在图313中，q0={0,1,7,11,14,19,24,26,28,30,33,35,38,40}。标有“#”的状态意指在这些状态之下，当扫视到未在其射出弧上出现过的字母或数字字符时，将转移到状态25。显然，在按图313实现词法分析程序时，同样应采取某种策略，以区别源程序中的关键字和标识符。

图3－13M确定化后的DFA

最后，顺便提及，上面所给出的NFA确定化的算法，同样可应用于不含ε动作的NFA的确定化。

以上就是关于程序设计语言|正规式全部的内容，包括:程序设计语言|正规式、急急急，编译原理、将NFA确定化的源程序等相关内容解答，如果想了解更多相关内容，可以关注我们，你们的支持是我们更新的动力！