实验一利用子集法构造DFA

实验一利用子集法构造DFA

一、实验目的

掌握将非确定有限自动机确定化的方法和过程

二、实验要求及内容

实验要求：

1.输入一个NFA,输出一个接受同一正规集的DFA；

2.采用C++语言，实现该算法；

3.编制测试程序；

4.调试程序。

实验步骤：

1.输入一个NFA关系图；

2.通过一个转换算法将NFA转换为DFA；

3.显示DEA关系图。

三、实验环境

计算机、Windows操作系统、VisualC++程序集成环境。

四、程序代码

*include"stdafx.h"

#include<iostream>

#include<algorithm>

#include<queue>

#include<stack>

^inclucle<string>

usingnamespacestd:

structedge{

intstart,end;

charc;

}

E[100],Ekong[100];//E保存所有的边，Ekong保存转换字符为空的边

structState{

int状态集合

intcount;//状态集合中的元素个数

intflag;〃是否是接受状态

intmark;〃状态编号

}；

intn;〃n:边数

inink-0;〃空字符转换的边数

intfirst,accept;//开始状态，接受状态

charalpha[100];//输入字母表,#代表空串

intnumofchar=0;〃字母表中的字符个数

intuscof_char[256];〃该转换字符是否用过

intf[200];〃状态属性标志：0表示始态，1表示接受态，T表示中间态

StateDFA[100];〃DFA状态集

intuseof_DFA[100];//标志构造出来的状态是否已存在

intnumof_Dtran=0;〃最后得到的DFA中的状态数

charDtran[100][100];〃DFA状态转换表

voidinput。

(

inti,s,e;

charch;

cout<〈”请输入转换的有向边数n："<<endl;

cin»n;

cout<<”请输入NFA的开始状态："《endl;

cin»first;

cout<<“请输入NFA的接受状态(输入-1结束)：*«endl;

mcmsct(f,-1,sizoof(f));

mcmset(useof_char,0,sizeof(useof_char));

f[first]=0:

cin»accept;

while(accept!=-l)

(

f[acccpt]=l;

cin»accept;

}

cout<<”请输入NFA,起点，终点，转换字符('#'我示空字符)：*«endl：

intk=0;

for(i=0;i<n;i++)

(

cin»s»c»ch;

E[i].start=s：

E[i].end=e;

E[i].c=ch:

if(ch!=>&&!useofchar[ch])

{

alpha[numof_char++]=ch:

useof_char[ch]=l;

)

if(ch=='#')

{

Ekong[nk].start=s;

EkongEnk].end=e;

Ekong[nk].c=ch;

nk++;

}

)

Statemove(StateT,chars)//c!=，

(

Statetemp;

temp.count=0;

temp.mark=T.mark;

inti,j=0,k=0;

for(i=0:i<T.count:i++)

(

j=0;

while(j<n)

{

if(E[j].start==T.c==s)

{temp.H[temp.count++]=E[J.end:

)

j++；

}

)

returntemp;

)

voidarriveBynone(intt,intresult[],int&num)〃搜索状态t通过一个或多个空字符到达的状态，结果存在

result中

{

intk=0;

intm=0;

num-0;

stack<int>S;

S.push(t);

intj;

whilc(!S.empty())

(

j=S.topO；

S.pop();

m=0;

while(m<nk)

(

if(EkongLm].slarl==j)

(

resu11[num++]=rkong[mj.end;

S.push(Ekong[m].end);

)

m++;

)

)

boolcheck(inti,StateT)//判断状态i是否在T中

(

intj:

for(j=0:j<T.count：j++)

(

if(T.H[j]==i)

returntrue;

)

returnfalse:

}

Stateclosure(StateT)〃求闭包

{

stack<int>STACK;

Statetemp;

inti,j,k;

for(i=0：i<T.count：i++)

(

STACK,push(T.H[i]>;

temp.H[i]=T.Il[i];

)

temp.count=T.count;

temp.mark=T.mark:

while(!STACK,empty())

(

intt=STACK.top();

STACK.pop();

〃搜索状态i通过一个或多个空字符到达的状态

intsearchresult[100]：

intnum;

arriveBynone(t,searchresult,num);

for(j=0;j<num;j++)

{

if(!check(search_result[j],temp))

(

temp.H[temp.count++]=searchresult[j];

STACK.push(search_resultLjJ);

}

)

)

for(k=0;k<temp.count;k++)

(

if(f[temp.H[k]]=l)

temp.flag=l：

break;

)

if(f[temp.H[kj]==O)

temp.flag=O;

break;

)

}

sort(temp.H,temp.H+temp.count);

for(i=0:i<numof_Dtran;i++)

(

if(temp.count!=DFA[i].count)

continue;

sort(DFA[i].H,DFA[i].H+DFA[i].count);

for(j=0;j<DFA[i].count;j++)

{

if(DFA[i].H[j]!=temp.H[j])

break：

)

if(j>-DFA[i].count)

temp.mark=DFA[i].nark;

}

returntemp;

)

intcheckinDFAO//检查DFA中是否存在未被标记的状态，有则返回标号，否则返回-1

(

inti;

for(i=0;i<numof_Dtran;i++)

{

if(!useofDFA[i])

returni;

)

return-1;

)

boolcheckwhetherinDFA(StateT)

(

inti,j;

sort(T.H,T.H+T.count);

for(i=0：i<numof_Dtran;i++)

(

if(T.count!=DFA[i].count)

continue;

sort(DI'A[i].H,DI'A[i].H+DFA[i].count);

for(j=0;j<DFA[i].count;j++)

{

if(DFA[i].H[j]!=T.H[j])

break:

)

if(j>=DFA[i].count)

returntrue：

}

if(i>=numof_Dtran)

returnfalse;

else

returntrue;

}

voidchildmethod0

(

intm,n：

for(m=0;m<100;m++)

for(n=0;n<100;n++)

Dtran[m][n]=*;

for(m=0;m<100;m++)

DFA[m].flag=~l;

StateSO,U;

SO.flag-0;

SO.count=l;

SO.H[0]=first：

StateT;

T=closure(S0):

T.mark=0;

T.flag=0;

DFA[numof_Dtran++]=T：

memset(useofDFA,0,sizeof(useofDFA));

intj=check_inDFA();

intk;

while(j!=-l)

(

useof_DFA[j]=l;

for(k=0;k<numof_char;k++)

(

U=closure(move(DEA[j],alpha[k]));

//ifU不在DFA中

if(!check_whetherin_DFA(U))

{U.mark=numof_Dtran;

DFA[numof_Dtran++]=U;

)

Dtran[DFA[j].mark^[U.mark]=alpha[k];

)

j=checkinDFA();

}

)

voidprint0

inti,j;

for(i=0:i<numofDtran：i++)

cout«i«*:*;

for(j=0;j<DFA[i].count;j++)

cout«DFA[i].H[j]«*

if(DFA[i].flag==l)

cout<<"此为DEA的接受状态”；

if(DFA[i].flag==0)

cout«”此为DFA的开始状态“；

cout«endl;

}

cout«endl：

for(i=0;i<numof_Dtran;i++)

(

for(j=0;j<numofDtran：j++)

{if(Dtran[i][j]!=，)

(cout«i«*->*«j<<*By*«Dtran[i][j]«ondl;

}

)

)

}

voidjudge(stringch)

(

inti,j,k;

intnum=ch.length();

Statetemp;

k=0;

for(i=0;i<num;i++)

(

for(j=0;j<numof_Dtran;j++)

{

if(Dtran[k][j]=alpha[i])

(

temp=DFA[j];

k=j;

break:

}

)

}

if(temp.flag!=l)

字符串无法由该DFA得到”《endl;

else

cout<〈"字符串"<Xch«"可以山该DFA得到"Gendl;

cout«cndl;

int_tmain(intargc,_TCHAR*argv[])

(

input0;

child_method()：

cout«endl;

print();

strings;

while(cin»s)

judge(s):

system("pause");

return0;

五、实验结果

QS"C:documentsandSeEngs\AdnEstr3tor\M面"FA将换OFA9ebuoVMFA转换DFA.exu"-|口|x|

六、算法分析

使用子集构造法对非确定有限自动机进行确定化的过程中存在大量重复计算的

问题。为解决此问题,基于非确定有限自动机的特点并针对子集构造法的不足，提出了

一种优化的非确定有限自动机确定化算法。首先定义了识别符的有效引出状态集概念

并证明了£-closure的并定理以保证算法的正确性，其次给出了用于避免重复计算的

识别符的有效引出状态集的构造子算法和单状态集的£-closure的求算子算法,基于

这两个子算法给出了优化的非确定有限自动机确定化算法，最后将算法应用于实例，

实验结果表明计算量远小于子集构造法的计算量。相比子集构造法,算法能更有效地

对非确定有限自动机进行确定化。

七、实验小结

以前上课时有许多的问题并没有真正的认识到，但通过这次实验，使我掌握了许

多更重要的知识点。通过实验，我们可以知道将NFA转换成接受同样语言的DFA的算

法称为子集构造算法。NFA变换到DFA的基本思想是：让DFA的每个状态对应NFA的

一个状态集。实验实现了NFA到DFA的转换。

实验二THOMPSON算法的实现

一、实验目的

掌握将正规表达式转换为NFA的方法和过程

三、实验要求及内容

1.输入一个正规表达式，输出一个接受同一语言的NFA

2.采用C++语言，实现该算法

3.编制测试程序

4.调试程序

三、实验环境

计算机、Windows操作系统、VisualC++程序集成环境。

四、程序代码

Uinclude"Thompson,h*

voidmain()

(

stringRegularExpression="(a|b)*abb”;

cellNFA_Cell;

input(Regu1ar_Expression);//调试褥要先解敝

RegularExpression=addjoinsymbol(RegularExpressiori);

Regu1ar_Expression=postfix(Regular_Expression)：

NFACell=express2NFA(RegularExpression)：

Display(NFA_Cell);

)

cellexpress_2_NFA(siringexpression)

(

intlength=expression.size0;

charelement;

cellCell,Left,Right;

stack<cell>STACK;

for(inti=0;i<length;i++)

element=expression,at(i);

switch(element)

caseR:

Right=STACK.top()；

STACK,pop0;

Left=STACK.topO;

STACK.pop();

Cell=do_lnite(Left,Right);

STACK.push(Cell):

break;

case':

Left=STACK.;

STACK.pop()：

Cell=doStar(Left);

STACK,push(Cell);

break;

case'+':

Right-STACK.top();

STACK,pop0;

Left=STACK.topO;

STACK.pop();

Cell=do_Join(Left,Right):

STACK,push(Cell);

break;

default:

Cell=do_Cell(element);

STACK,push(Cell);

)

)

cout<<”处理完毕!*«endl：

Cell=STACK.topO;

STACK.pop();

returnCel1;

)

celldoUnite(cel1Left,cellRight)

{

cellNew€el1;

NewCe11.EdgeCounl=0;

edgeEdge1,Edge2,Edge3,Edge4;

stateStartState=newStateNode();

stateEndState=new_StateNode();

Edgel.StartState=StartState;

Edgel.EndState=Left.EdgeSet[0].StartState;

Edgel.TransSymbol=';

Edgc2.StartState=StartState;

Edge2.EndState=Right.EdgeSet[OJ.StartState;

Edge2.TransSymbol=';

Edge3.StartState=Left.EdgeSet[Left.EdgeCount-1].EndState;

Edge3.EndState=EndState;

Edge3.TransSymbol=';

Edge4.StartState=Right.EdgeSet[Right.EdgeCount-1].EndState;

Edge4.EndState=EndState;

Edge4.TransSymbol=';

//先将Left和Right的EdgeSet复制到NewCell

cellEdgeSetCopy(NewCell.Left):

cell_EdgcSct_Copy(NcwCc11,Right);

〃将新构建的四条边加入EdgeSet

NewCell.EdgeSet[NewCell.EdgeCount++]=Edgel;

NewCell.EdgeSet[NewCel1.EdgeCount++]=Edge2;

NewCell.EdgeSet[NewCel1.EdgeCount++]=Edge3;

NewCell.EdgeSet[NewCell.EdgeCount++]=Edge4;

〃构建NewCell的启示状态和结束状态

NewCell.StartState=StartState;

NewCell.EndState-EndState;

returnNewCell;

}

〃处理ab

celldo_Join(cellLeft,cellRight)

(

for(inti=0;i<Right.EdgeCount;i++)

(

if(Right.EdgeSet[i].StartState.StateName.compare(Right.StartState.StateName)==O)

{

Right.EdgeSet[i].StartState=Left.EndState;

STATE.NUM—;

)

elseif(Right.EdgeSet[i].EndState.StateName.compare(Right.StartState.StateName)==0)

(

Right.EdgeSet[i].EndState=Left.EndState;

STATE_NUM—;

)

)

Right.StartState=Left.EndState;

cell_EdgeSet_Copy(Left,Right);

Left.EndState=Right.EndState：

returnLeft;

)

celldo_Star(cellCell)

(

cellNewCel1;

NcwCc11.EdgeCount=0;

edgeEdgel,Edge2,Edge3,Edged;

stateStartState=new_StateNode();

stateEndState=newStateNodeO;

〃构建边

Edgel.StartState=StartState;

Edgel.EndState=EndState;

Edgel.TransSymbol=';

Edge2.StartState=Cel1.EndState;

Edge2.EndState=Cell.StartState;

Edge2.TransSymbol=':

Edgc3.StartState=StartState;

Edge3.EndState=Cel1.StartState;

Edge3.TransSymbol=，#，;

Edge4.StartState=Cell.EndState;

Edged.EndState=EndState;

Edge4.TransSymbol=';

〃构建单元

ccll_EdgcSct_Copy(NcwCcll,Cel1):

NcwCcll.EdgcSct[NcwCcll.EdgcCount++]-Edgel;

NewCel1.EdgeSet[NewCel1.EdgeCount++]=Edge2;

NewCel1.EdgeSet[NewCel1.EdgeCount++]=Edge3;

NewCel1.EdgeSet[NewCel1.EdgeCount++]=Edged;

NewCel1.StartState=StartState;

NewCel1.EndState=EndState;

returnNcwCcll;

)

celldo_Cell(charelement)

(

cellNewCel1;

NewCel1.EdgcCount=0;

edgeNewEdge;

staleStartState=newSlateNodeO;

stateEndState=new_StateNode();

NewEdge.StartState=StartState;

NewEdge.EndState=EndState;

NewEdge.TransSymbol=element;

NewCel1.EdgeSetLNewCell.EdgeCount++J=NewEdge;

NewCel1.StartState=NewCel1.EdgeSet[0].StartState;

NewCel1.EndState=NewCel1.EdgeSet[0].EndState;〃EdgeCQunt此时为1

returnNewCel1;

)

voidcell_EdgeSet_Copy(cel1&Destination,cellSource)

intD_count=Destination.EdgeCount;

intScount=Source.EdgeCount;

for(inti=0;i<S_count;i++)

Destination.EdgeSet[D_count+i]=Source.EdgeSet[i];

)

Destination.EdgcCount=D_count+S_count;

)

statenewStateNodeO

(

statenewState;

newState.StateName=STATE_NUM+65;〃转换成大写字母

STATENUM++:

returnnewState;

)

voidinput(string&RegularExpression)

(

cout<<”请输入正则表达式:(操作符：0*I；字符集:A⑵*«endl;

do

(

cin»RcgularExprcssion;

?whilc(!chcck_legal(Regulai'Exprcssion));

)

intcheck_legal(stringcheck_string)

(

if(check_character(check_string)&&check_parenthesis(check_string))

(

returntrue;

)

returnfalse;

)

intcheckcharacter(stringcheckstring)

(

intlength=checkstring.size();

for(inti=0;i<length;i++)

(

charcheck=checkstring,at(i);

if(is」etter(check)"/小写和大写之间有5个字符，故不能连续判断

{

)

elseif(check==,(,11check==*)>11check==***11check=*|*)

{

)

else

cout<〈”含有不合法的字符！”《endl;

coutX〈”请重新输入："<<endl;

returnfalse;

)

)

returntrue;

)

intchcck_parcnthesis(stringchcck_string)

(

intlength=checkstring.sizeO;

char*check=newchar[length]：

strepy(check,checkstring,cstr());

stack<int>STACK;

for(inti=0:i<length:i++)

(

if(check[i]==>(')

STACK,push(i);

elseif(check[i]==，*')

(

if(STACK,empty0)

(

ccrr<<”有多余的右括号”《cndl;〃行时不记录兀配位置location

coutXC/1造亘新输入："<<cndl;

returnfalse;

)

else

STACK.popO;

)

)

if(!STACK,empty())

(

cerr«*;fi1多余的左括号“<<endl;

cout<〈"请重新输入:*<<endl;

returnfalse;

)

returntrue;

}

intisletter(charcheck)

(

if(check>=，a'&&check<=，z*||check>=,A'&&check<=,Z')

returntrue;

returnfalse;

)

stringadd_join_symbol(stringadd_string)

(

stringcheck_string="abcde「g\0aaa”;

cout«check_string«endl;

intlength=check_string.sizeO;

char*check=newchar[2*length];

strepy(check,check_string.c_str())：

cout«check«endl;

char*s="ssss\Oaa";

cout«s«endl：

stringa(s);

cout«a«endl;

intlength=addstring.sizeO;

intreturn_string_length=0;

char*return_string=newchar[2*length];〃做多是两倍

charfirst,second;

for(inti=0:i<length-l:i++)

(

first=add_string.at(i);

second=add_string.al(i+l);

return_string[return_string_length++]=first;

if(first!='('&&first!='1'&&is」etter(second))

(

rcturn_string[rcturn_string_lcngth++]=';

)

elseif(second==,(*t&rirst!=*(*)

{

return_string[return_string_length++]=';

)

)

return_string[rcturn_string_lcngth++]=second:

returnstring[return_stringlength]='\0';

siringSTRING(return_string);

cout<<"力加+'后的表达式：*«STRING«endl;

returnSTRING：

)

intisp(charc)

(

switch(c)

(

case:return0;

case'(':return1;

case'*':return7;

caseT:return5;

case'+':return3;

case':return8：

)

cerr«*ERROR!*«endl;

returnfalse;

)

inticp(charc)

switch(c)

case'*':return0;

case':return8;

case'*':return6：

case'|:return4;

case'+':return2;

case')':return1;

)

cerr«*ERROR!*«endl:

returnfalse;

)

stringpostfix(siringe)

(

e=e+"#";

stack<char>s;

charch=',chi,op：

s.push(ch)：

stringout_string-

intread_localion=0;

ch=e.at(read_location++);

while(!s.empty())

if(isletter(ch))

out_string=out_string+ch;

ch=e.at(read_localion++);

)

else

{

chi=s.top()：

if(isp(chl)<icp(ch))

(

s.push(ch);

ch=e.at(read_location++)：

)

elseif(isp(chl)>icp(ch))

(

op=s.topO；

s.pop();

outstring=outstring+op;

}

else

|

op=s.top()；

s.pop();

if(op—(*)

ch=e.at(read_location++);

)

)

)

coutX〈”后缀表达式：/，«out_string«end1;

returnout_string;

)

voidDisplay(cellCell)

(

cout«wNFA的边数：z，«Ccl1.EdgcCount«cndl;

cout«/，NF/\的起始状态：*«Cel1.StartState.StateName«endl：

cout«wNFA的结束状态：*«Cel1.EndStaie.StateName«end];

for(inti=0;i<Cell.EdgeCount;i++)

(

cout<<"第+”条边的起始状态："〈〈Cell.EdgeSet[i].StartState.StateName

«*结束状态：*«Cell.EdgeSet[i].EndState.StateName

«转换符：，，«Ccll.EdgcSct[iJ.TransSymbol«cndl;

)

cout<<"结束"<<endl;

}

五、算法分析

Thompson算法的基不思想,提出一种利用算符优先关系表来实现Thompson算法

的方法，以实现正规式到rr穷自动机的转换.描述了算法的解决思路、算符优先表的生

成和NFA的表示.算法测试表明，该方法可以大大简化算法的实现,提高编译程序的工

作效率.

六、实验结果

P青输入正则表达式,(操作符,＜＞X1；字符集，a~zA~z)

labcdefg

labcdefg

jssss

达

加>^±<

后

“

处«•

诟A:

A疆

NFA

HF第

结

起

舞

、

换

12A荥a

R第-

结

换

起

第

白t

1.——C

2警t

第

换

结

起

边

第t

白B

I3.t

换

结

起

.边

第CH

4.白H

换

结

边

起BH

第-.

白|1H

边

换

结

5起Eb

第.i:

朱M

白

：

换

6.起GSw

第

.荥t

换

7起F

白,t

豆

第1:1

8-G祎M

结

白H

察90la

一

起?B

Ft

边

鬻111t

12起1•t

第

边s:t

起I<t

13*t

第

边

14起Dxt

演t

第*

起

5边Ht

1»t

演ft

蕤

第

16起Kst

边t

7颉

第

1起Jzt

婚t

边

颉st

一K

第1

起tt

南

边

J襄t

第1st

演

起

结

演

In

Iprhe演

七、实验小结

通过这次试验，我掌握了如何将正规表达式转换为NFA的方法和过程。另外，我

们要知道在构造过程中，每次构造的新状态都要赋予不同的名字。这样，任何NFA的

两个状态都具有不同的名字。即使同一符号在r中出现多次，我们也要为该符号的每

个实例创建一个独立的带有自己状态的NFA。

实验三词法分析与语法分析程序设计

一、实验目的

掌握计算机语言的词法分析程序和语法分析程序的设计方法

二、实验要求、内容及步骤

实验要求：

1.根据以下的正视式，画出状态图；

标识符：〈字母〉(〈字母＞1＜数字字符＞)*

十进制整数：0|(1|2|3|4|5|6|7|8|9)(0111213141516171819)*

运算符：$*

2.根据状态图，设计词法分析函数intscan(),实现从键盘读入数据，分

析出一个单词。

3.对于只含有+、*运算的算术表达式的文法，编写相应的语法分析程序，要

求用LL(1)分析表实现,并以id+id*id为例进行测试。

E—>TE''

E，—>+TEZ|e

T—>FT；

「—>*FT'|£

F—>(E)|id

实验步骤

1、根据状态图，设计词法分析算法

2、采用C++语言，实现该算法

3、编制测试程序

4、调试程序：输入一组单词，检查输出结果。

5、编制给定文法的非递归的预测分析程序，并加以测试。

三、实验环境

计算机、Windows操作系统、VisualC++程序集成环境。

四、实验原理

1.词法分析器读入输入串，将其转换成将被语法分析器分析的词法单元序歹八

产生下述小语言的单词序列。

单词符号种别编码

DIM1

IF2

DO3

STOP4

END5

标识符6

常数(整)7

—8

4-9

长10

**11

12

(13

)14

这个小语言的单词符号的状态转换图，如下图:

2.语法分析是决定如何使用一个文法生成一个终结符串的过程。

语法分析器能识别分加+减-乘*除/乘方一括号()操作数所组成的算术表

达式，其文法如下：

E-E+T|E-T|T

T-T*F|T/F|F

FfP'F|P

P-(E)|i

使用的算法可以是：预测分析法；递归下降分析法；算符优先分析法；LR分析法

等。

3.中间代码生成器产生上述算术表达式的中间代码(四元式序列)。

id+*()$

EE—>E—

TE，>

TE/

EzE，—E/—E/—

>>£>£

+TEf

TT—>T—

FT>

FT

TzT，—X一Tf—T/—

>e>>£>£

*FT,

FF—>F-

id>(E)

五、程序代码

(1)词法分析程序的数据结构与算法：

#include<string.h>

#inc1ude<iostream>

usingnamespacestd;

charprog[100],token[10];

charch;

intsyn,p,m=0,n,row,sum=0:

char*rwtabL20J=(dim,if,do,stop,end,and,begin,bool,case,char,

false,for,int,not,or,set,then,true,until,while

);

voidscancr()

(

for(n=0：n<9;n++)token[n]=NULL;

ch=Dro«[p++]：

while(ch=='')

(

ch=prog[p]：

p++;

)

if((ch>=,a*&&ch<=,z*)||(ch>='A'&&ch<='Z'))

m=0;

while((ch>=,O'&&ch<=>9')||(ch>='a'&&ch<=,z)|(ch>=*A*&&ch<=，Z'))

token[m++]=ch：

ch=prog[p++];

)

token[m++]=,\0*;

P-：

syn=21;

for(n=0;n<20;n++)

(

if(strcmp(token,rwtabLn])==0)

|

syn=n+l;

break;

)

)

}

elseif((ch>='0'&&ch<='9'))

sum=0;

while((ch>=,0'&&ch<=,91))

|

sum=sum*10+ch->0'：

ch=prog[p-H-];

)

)

P—；

syn=7+15;

if(sum>32767)

syn=-l;

)

elseswitch(ch)

(

case'=':syn=8+15;token[0]=ch;break：

case'4':syn=9+15;tokenL0]=ch;break;

case'*':

m=0;

token[m++]=ch;

ch=prog[p++];

if(ch==，*')

{

syn=ll+15;

token[m++]=ch;

)

else

syn=10+15;

p-：

)

break：

case*,*:syn=12+15;token[O]=ch;break;

case'(':syn=13+15;token[0]=ch;break;

case')':syn=14+15;token[0]=ch;break;

case*=':syn=0;token[0]=ch;break;

case*:m=0:tokenfm++]=ch:

ch=prog[p++];

if(ch==*>>)

(

syn=17+15：

token[m++]=ch：

)

elseif(ch=*=,)

(

syn-16+15;

Loken[m++]=ch;

)

else

(

syn=15+15;

P-；

)

break;

case>>>:m=0;token[m++]=ch：

ch=prog[p++];

if(ch==,=,)

(

syn=19+15;

token[m++]=ch;

)

else

{

syn=18+15;

P-：

)

break;

case':m=0;token[m++]=ch;

ch=prog[p++];

if(ch==，=,)

syn=21+15:

token[m++]=ch;

)

else

(

syn=20+15：

P-；

)

break;

case*/':syn=22+15;token[0]=ch;break;

case*:syn=23+15:tokenf0]=ch:break:

case':syn=24+15:token[0]=ch:break;

default:syn=-l;break;

)

}

voidmain()

(

P=0;

row=l;

cout<<cndl<<cndl<<cndl;

cout«"词法分析”《endl«endl;

cout<<”请输入一段程序(以#结束)：”；

do

(

cin.get(ch);

prog[p++]=ch;

)

while(ch!=，#');

p=0；

cout〈<endl«”词法分析结臭如|;*«endl；

cout«”种别编码自身值"<<endl;

do

(

scanerO;

switch(syn)

{

case22:cout<<*(*«syn«*,“<<sum<<")"<<endl;break;

case-1:cout«”Errorinrow"«row«"'!"'«endl：break;

default:cout«z，(A«syn«*,*«token«*)*«enill;break;

)

)

while(syn!=0);

}

(2)语法分析程序的数据结构与算法：

#include<string.h>

#include<malloc.h>

#include<iostream>

usingnamespacestd：

typedefstructtable〃分析表存储结构

(

charm[100];

}table;

tableM[100][100];〃定义分析表

typedefstructstacknode〃定义栈内元素节点(带头结点(为空)的)

(

chardata;

structstacknode*next;

}stackk;

voidinitlink(stackk*&s)//初始化新栈

(

s=(stackk*)malloc(sizeof(stackk))：

s->next=NULL;

voidpoplink(stackk*&s)〃顶元素出栈

(

stackk*p;charv;

if(s->next!=NULL)

(

p=s->next;

v=p->data;

s->next=p->next;

)

free(p);

}

voidpushlink(stackk*&s,charx)〃新元素入栈

(

stackk*p:

p=(stackk♦)mal1oc(sizeof(stackk));

p->data=