资源描述：
《词法分析报告册_》由会员上传分享，免费在线阅读，更多相关内容在工程资料-天天文库。
1、实验一词法分析实验报告报告-・实验名称：词法分析器实验。二•实验目的：将给定正规式转化为NFA,再将NFA转化为DFA,最后务DFA最小化。三•实验设计1、正规式转化为NFA采用的是Thompson算法，Thompson算法是先将正规式分解为最基本的正规式,然后再根据以下规则构造：(1)、对^构造NFA如图所示。其中，sO为初态，f为终态，该NFA接受闾。SOE厂、'1(2)、对》上的每一个字符a,构造NFA下。其中，是sO为初态，f为终态,该NFA接受｛a｝。(31若N(p)和N(q)是正规式p和q的NFA,则A)对正规式p
2、q,构造NFA如下。其
3、中，sO为初态，f为终态，该NFA接受B)对正规式pq,构造NFA如下。其中，sO为初态，f为终态，该NFA接受L(p)L(q)；N(p)N(q)C)对正规式p*,构造NFA如下。其中，sO为初态，f为终态，该NFA接受L(P*lD)对正规式(p)，使用本身的NFA,不再构造新的NFA。2、NFA转化为DFA采用的是子集法。先求每个状态的闭包，以消除NFA的不确定性。3、DFA的简化采用书上算法2.6减少DFA的状态数。四・实验内容：⑴令I是NFAN的状态集S的一个子集，I的£闭包的jClosure(I)构造规则如下：(a)若swl,则ses_Clo
4、sure(I);(b)若ses_Closure(I)且5(s,s)=sz而s'$8_Closure(I)，则s'Gs_Closure(I)根据上面的规则，下面给出了一个计算I的£闭包的算法£_Closure(I)oSETS;SETs_Closure(input)SET*input;{S=input;/*初始化*/push();/*把输入状态集中的全部状态压入栈中Vwhile(栈非空){Nfa_statei;pop();/*把栈顶元素弹出并送入iVif(存在6(i,£)=j)if(j不在S中){把i加到S中;}returnS;/*返回£_Closure
5、(input)集合*/完成上述算法的设计。⑵令I是NFAN的状态集S的一个子集，aeZz转换函数Move(La)定义为：Move(Iza)=s_Closure(J)其中/J={s/
6、sel且5(s,a)二s'}转换函数Move(Iza)的设计通过调用s_Closure(input)实现z完成该函数的设计。⑶从NFAN构造一个与其等价的DFAM的子集构造算法，就是要为DFAM构造状态转换表Transz表中的每个状态是NFAN状态的集合,DFAM将〃并行〃地模拟NFAN面对输入符号串所有可能的移动。下面给出了子集构造算法Subset_Constructi
7、on的框架，请完成其设计过程。有关数据结构:States[]是一个M的数组，每个状态有两个域，set域存放N的状态集合，fig域为一标识。Trans[]■1是M的转移矩阵(输入字母表》元素个数x最大状态数),Trans[i][a]=T-状态。M的当前状态号a输入符号,aeZNstates[]M的下一新状态号S定义M的一个状态的N的状态集初始化：States[0].set=£_Closure({N的初态})States[O].flg=FALSENstates=1i=0S=(PTrans初始化为无状态’while(States[i]的fig为FALSE)
8、{States[i].flg二TRUE;for(每个输入符号aeZ){S=E_Closure(Move(States[i].set,a));if(S非空)instates中没有set域等于S的状态){States[Nstates].set=S;States[Nstates].flg=FALSE;Trans[i][a]=Nstates++;}elseTrans[i][a]=States中一个set域为S的下标;此算法的输出M主要由Trans矩阵描述，其中省略了每个状态是否为终态的描述，应加以完善。(4)测试用例对下图所示的NFAN用子集构造算法Subs
9、et_Construction确定化。11NFAN的初态为12,DFAM的初态为s_Closure({12})o整个转换过程可用下表来概括。DFANFAMovefD‘)终状态状态「ClosureMove(r')Move('e')NFADFANFADFANFADFA0{12}{024612}{1,5}10一0-否1{1,5}{1,5}1{8}2{15}3是2{8},18,19}{10}4(P—$—否3{15}{8,9}{16}5—0—否4{10}{15}{10}4(P—{15}3是5{16}{9,10,11,13,14,18,19}{15z16z17z
10、19}{16}5(P0是4DFAM的状态转换图如下。五•运行结果词法分析请输入正则表达式：*abb
