北京工业大学-编译原理--实验报告.docx

计算机学院实验报告课程名称：编译原理实验人学号：110703xx姓名：XXX实验完成日期：2022年5月20日报告完成日期：2022年5月20日目录实验一词法分析程序的设计与实现3词法的正规式描述：3状态图：4词法分析程序数据结构与算法：4词法分析算法：5实验结果：7实验中遇到的问题及其解决：81、保留字的检测问题：82、关于。为首位的数字是int8、intl和intl6的判断问题：83、关于回退的问题：8实验二自顶向下的语法分析一递妇子程序法9改写后的产生式集合：9化简后的语法图：9递归子程序算法10实验结果：13实验中遇到的问题及其解决：141、消除左递归，提取左因子之后的E、T对应的子程序的编写问题：142、缩进的控制：14实验三语法制导的三地址代码生成程序15语法制导定义：15三地址代码生成器的数据结构16三地址生成器算法：17实验结果：21实验中遇到的问题及其解决：221、根据化简后的产生式修改语法制导定义：222、使用真假出口法和继承属性来确定goto的标号：22实验一词法分析程序的设计与实现词法的正规式描述：标识符字母(字母1数字字符)*十进制整数O(I2i3456789)(01123456789)*八进制整数0(01234567)(01234567)*十六进制整数0(xX)(0l23456789abcdef)(0l23456789abcdeIf)*运算符和分隔符+-*/=();关键字ifthenelsewhiledo.状态图:lfthenwhiledoels词法分析程序数据结构与算法：/单词类classTokenpublic:inttype;/种别stringValUe;/属性值stringname;/单词具体内容Token()type=DEFAULT;value=NONE_OF_VALUE;Token(inttype,stringvalue,stringname):type(type),value(value),name(name)Token()；词法分析算法:Token*TokenScan(ifstream&from_file)charch”/用于保存从文件中读取的字符读第一个字符inti=0;charvalue30=用来存放token的属性值ch=from_file.get();while(ch=BLANKch=TABch=NEWLINE)ch=from_fiIe.get();)/以下为标识符的检测/if(isalpha(ch)valuei+=ch;ch=from_file.getO;/判断后续的是否为工DN的成分(数字或字母)while(isalnum(ch)valuei+=ch;ch=from_file.get();)直到不是工DN成分，回退一字符from_file.unget();/TODO：这里加上保留字检测部分进行字符串的对比，即可比较出保留字，通过压栈的形式来获得完整的属性值/以下为保留字的检测/if(strcm(value,W0RD_IF)=0)returnnewToken(IF,NONE_OF_VALUE,WORDIF);if(strcm(value,WORD_THEN)=0)returnnewToken(THEN,NONE_OF_VALUE,WORD_THEN);if(strcmp(value,WORD_ELSE)=0)returnnewToken(ELSE,NONE_OF_VALUE,WORD_ELSE);if(strcm(value,WORD_WHILE)=0)returnnewToken(WHILE,NoNEJDJVALUEzWORDWHILE);if (strcmp(value,WORD DO) = 0)return new Token(DO, NONEJ)F_VALUE, WORD_DO);returnnewToken(IDN,value,value);Iflllllllllllllllllllll以下为数字的检测Iiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiif(isdigit(ch)valuei+=ch;/如果第一个数字是O,则有可能是工NTlCl的Q、工NT8或INTI6if(Ch=,O,)ch=from_file.get();if(ch>=,O,&&ch<,8,)IIch=,x,ch=,X,)/如果。后面紧跟着数字0-8,则为工NT8if(isdigit(ch)while(ch>=,0,&&ch<,8,)valuei+=ch;ch=from_file.get();from_file.unget();returnnewToken(INT8zvalue,value);valuei+=ch;/到这一步的都是INT16ch=from_file.get();while(isdigit(ch)(ch>=,a,&&ch<=,f,)valuei+=ch;ToDO:这里没有解决Oxrtr的问题ch=from_file.get();from_file.unget();returnnewToken(INT16zvalue,value);else0后面的不为0-7的digit或X或X等8或16进制特征字符，则为10进制的0,回退一个字符from_file.unget();returnnewToken(INT10zvalue,value);)能到这一步的都是工NTl0,且不为0打头ch=from_file.get();while(isdigit(ch)valuei+=ch;ch=from_file.get();from_file.unget();returnnewToken(INT10,value,value);/以下为运算符的检测/valuei+=ch;switch(ch)case,+,:returnnewToken(ADDzvalue,+")；casereturnnewToken(MINUS,value,caset*».returnnewToken(MULzvalue,"*,)；case',:returnnewToken(DICzvalue,/")；case,>':returnnewToken(MORE,value,">,)；case,<,:returnnewToken(LESS,value,"<")；casereturnnewToken(EQUzvalue,"=');case,(,:returnnewToken(LBRACzvalue,(");case,),:returnnewToken(RBRACzvalue,),);casereturnnewToken(COMMA,value,"；"）；default:ErrorHandle(from_file);break;returnnewToken(DEFAULT,NONE_OF_VALUE,NONE_OF_VALUE);实验结果：实验中遇到的问题及其解决:1、保留字的检测问题：一开始的时候我的想法是遇到if、while,do、then等单词的首字母时即开始划分状态，后来发现这样子判断的分支会特别多，而且效率不是很高，对保留字集合的扩展支持的也不是很好。后来我发现保留字存在于标识符的子集，所以为什么不先判断标识符然后再判断是不是保留字呢？后来我就照着这个思路成功实现了功能。2、关于0为首位的数字是int8、intl和imi6的判断问题：当读入的第一个字符为。时，可能为int8、可能是intl的。也可能是intl6的开头，当下一个字符是07时，开始进行int8的匹配：当下一个字符是X或X时，开始进行intl6的匹配；当下一个字符为其他字符时，说明这是一个十进制的0(此时还需进行一字节的回退)3、关于回退的问题：有些时候需要进行同退，否则不能正常的进行完整个分析过程，需要进行回退的场合为:(1)匹配标识符(或保留字时)，向后逐字读取的时候当下一个不是字母或数字的时候需要将读取的字符回退，才能继续向下进行；(2)判断为intl的0的时候需要一步回退：else/。后面的不为的digit或X或X等8或16进制特征字符，则为10进制的0,回退一个字符from_file.unget();returnnewToken(INTI0zvalue,value);(3)判断数字的时候到最后一个不为数字的都需要向退。实验二自顶向下的语法分析一递归子程序法改写后的产生式集合:S->id=E;S->ifCthenS;S->whileCdoS;C->E>E;C->E<=E;E->T(+T)*;E->T(-T)*;T->F(*F)*;T->F(F)*;F->(E);F->id;F->int8;F->intl;F->intl6;化简后的语法图:递归子程序算法intProcedures(ifstream&from_file)Indent();cout<<,S,<<endl<<endl;indentation+=4;/子程序开始Indent();Token*token=TokenScan(from_file);if(token->type=IF)cout<<token->name<<endl<<endl;ProcedureC(from_file);token=TokenScan(from_file);Indent();if(token->type=THEN)cout<<token->name<<endl<<endl;Procedures(from_file);elseexit(-1);elseif(token->type=WHILE)cout<<token->name<<endl<<endl;ProcedureC(from_file);token=TokenScan(from_file);Indent();if(token->type=DO)cout<<token->name<<endl<<endl;Procedures(from_file);elseexit(-1);)elseif(token->type=IDN)cout<<,id:,<<token->name<<endl<<endl;token=TokenScan(from_file);if(token->type=EQU)Indent();cout<<token->name<<endl<<endl;ProcedureE(from_file);elseexit(-1);indentation-=4;/子程序结束returnO;intProcedureC(ifstream&from_file)Indent();cot<<,C,<<endl<<endl;indentation+=4;/子程序开始Token*token;ProcedureE(from_file);token=TokenScan(from_file);Indent();if(token->type=MORE)cout<<token->name<<endl<<endl;ProcedureE(from_file);elseif(token->type=LESS)cout<<token->name<<endl<<endl;ProcedureE(from_file);elseexit(-1);)indentation-=4;/子程序结束returnO;)intProcedureE(ifstream&from_file)Indent();cout<<,E,<<endl<<endl;indentation+=4;/子程序开始Token*token;ProcedureT(from_file);while(true)token=TokenScan(from_file);if(token->type=ADD)Indent();cout<<token->name<<endl<<endl;ProcedureT(from_file);elseif(token->type=MINUS)Indent();cout<<token->name<<endl<<endl;ProcedureT(from_file);elsefor(inti=O;i<(int)token->name.length();i+)from_file.unget();/Mifiindentation-=4;/子程序结束returnO;indentation-=4;/子程序结束return0;)intProcedureT(ifstream&from_file)Indent();cout<<,T,<<endl<<endl;indentation+=4;/子程序开始Token*token;ProcedureF(from_file);while(true)token=TokenScan(from_file);if(token->type=MUL)Indent();cout<<token->name<<endl<<endl;ProcedureF(from_file);elseif(token->type=DIC)Indent();cout<<token->name<<endl<<endl;ProcedureF(from_file);elsefor(inti=O;i<(int)token->name.length();i+)from_file.unget();/回退indentation-=4;/子程序结束returnO;indentation-=4;/子程序结束returnO;intProcedureF(ifstreamsfrom_file)Indent();cout<<',F,<<endl<<endl;indentation+=4;/子程序开始Token*token;token=TokenScan(from_file);if(token->type=LBRAC)cout<<token->name<<endl<<endl;ProcedureE(from_file);token=TokenScan(from_file);cout<<token->name<<endl<<endl;Indent();if(token->type=IDN)cout<<,id:,<<token->name<<endl<<endl;)if(token->type=INT8)cot<<,int8:,<<ValueOfINT8(token->value)<<endl<<endl;if(token->type=INTlO)cout<<,intlO:"<<token->value<<endl<<endl;)if(token->type=INT16)cout<<intl:,'<<ValueOfINT16(token->value)<<endl<<endl;indentation-=4;子程序结束return0;实验结果:实验中遇到的问题及其解决:1、消除左递归，提取左因子之后的E、T对应的子程序的编写问题：经过多次测试，我发现在一个expression超过两个运算符的时候我的E、T子程序就只能成功的分析出第一段的式子，后来发现E->T(+T)*类似的产生式没有写循环调用控制，后来在(+T)*的最外层加了一个WhiIe(true)循环，然后在While(true)的首行加入了不是'+'就return的判定，成功解决了问题。2、缩进的控制：这个实验中碰到的第二个问题就是语法树缩进的控制问题，最终通过一个全局变量indentation来控制缩进的字符数量，一个IndentO函数来输出缩进(其实就是空格)，控制缩进数量的关键点有两个：一为进入子程序的时候indentation+=*二为结束子程序的时候indentation-二4。剩下的就是根据调试来选择在哪里输出缩进空格的问题了。实验三语法制导的三地址代码生成程序语法制导定义:也生式语义规则S->id=E;S.code=E.codegen(id.placeE.place)S->ifCthenSC.true=newlabel;C.false=S.next;Si.next=S.next;S.code=C.codegen(C.trueISI.codeS->whileCdoSS.begin=newlabel;C.true=newlabel;C.false=S.next;Si.next=S.begin;S.code=gen(S.beginC.codeIIgen(C.trueSi.codeIIgen('goto,S.begin);C->Ei>E2C.code=Ei.codeE2.codegen('if,Ei.place'>'E2.place'gotofC.true)gen('goto,C.false)C->Ei<E2C.code=Ei.codeIIE2.c0deIIgen('if,Ei.place'<zE2.place'goto/C.true)gen('goto,C.false)E->Ti(+T2)*E.place=newtemp;(E.code=Tl.codeIIT2.codeIgen(E.placeTl.place'+,T2.place);Tl.place=E.place;Tl.code=E.code;)+E->Ti(-T2)*E.place=newtemp;(E.code=Tl.codeT2.codeIgen(E.placeTl.place'-,T2.place);Tl.place=E.place;Tl.code=E.code;)+E->TE.place=T.place;E.code=T.codeT->FT.place=F.place;T.code=F.codeT->Fl(*F2)*T.place=newtemp;(T.code=Fl.codeF2.codegen(T.place'Fl.place'*,F2.place);Fl.place=T.place;Fl.code=T.code;)+T->Fl(/F2)*T.place=newtemp;(T.code=Fl.codeF2.codegen(T.place'Fl.place',F2.place);Fl.place=T.place;Fl.code=T.code;)+F->(E)F.place=E.place;F.code=E.codeF->idF.place=id.name;F.code=wF->int8F.place=int8.value;F.code=',F->intlF.place=intl.value;F.code=',F->inti6F.place=intl6.value;F.code=',三地址代码生成器的数据结构typedefstructcharcodeCODESIZE;intbegin;intnext;AttrS;typedefstructcharcodeCODESIZE;/CodeSize=500charplaceBUFSIZE;/BufSize=200AttrE;typedefstructcharcodeCODESIZE;intJfalSe;/用来标记入口intc_true;/用来标记入口AttrC;typedefstructcharcodeCODESIZE;/CodeSize=500charplaceBUFSIZE;/BufSize=200*S的属性定义*/*E的属性定义*/*C的属性定义*/*T的属性定义*/AttrT;*F的属性定义*/tyedefstructcharcodeCODESIZE;/CodeSize=500charplaceBUFSIZE;/BufSize=200*IDN的属性定义*/AttrF;tyedefstructcharidnameBUFSIZE;intentry;AttrIDN;三地址生成器算法：intProcedures(ifstream&from_file,AttrS&s)AttrCc;/C的属性AttrSSSI的属性AttrE的属性chartemp_idn_name50;/用来暂存当下一个是工DN时s->id:=E的id的nameToken*token=TokenScan(from_file);/s->ifCthenSl/Iiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiif(token->tye=IF)c.c_true=NeWLabel();/c.c_true出口有了新标签si.begin=c.c_true;11C真则往SI走si.next=c.c_false=s.next;/c假则走S的下一步为LO标签，在前面预置了ProcedureC(from_file,c);token=TokenScan(from_file);if(token->tye=THEN)Procedures(from_file,si);sprintf_s(s.code,nt%snL%d:t%su,c.code,c.c_true,si.code);/将中间代码输出至IJs.code中elseexit(-1);/s->whileCdoSl/Iiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiielseif(token->tye=WHILE)si.next=s.begin=NewLabel();c.c_true=si.begin=NewLabel();/CM则往Sl走c.cfalse=s.next;/C假则走S的下步为LO标签，在前面预置ProcedureC(from_file,c);token=TokenScan(from_file);if(token->type=DO)Procedures(from_file,si);sprintf_s(s.code,nL%d:t%snL%d:t%sntgotoLd",s.begin,c.code,c.c_true,si.code,s.begin);elseexit(-1);/s->id:=E/Iiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiielseif(token->type=工DN)strcpy_s(temp_idn_name,token->name.c_str();token=TokenScan(from_file);if(token->type=EQU)ProcedureE(from_file,e);sprintf_s(s.code,%snts=%s",e.code,temp_idn_name,e.place)；elseexit(-1);returnO;intProcedureC(ifstream&from_file,AttrC&c)AttrEel”el的属性AttrEe2;/e2的属性Token*token;ProcedureE(from_file,el);token=TokenScan(from_file);if(token->type=MORE)ProcedureE(from_file,e2);sprintf_s(c.code,%s%sntif%s>%sgotoLdntgotoLd,el.code,e2.code,el.place,e2.place,c.c_true,c.c_false);elseif(token->type=LESS)ProcedureE(from_file,e2);sprintf_s(c.code,',%s%sntif%s<%sgotoL%dntgotoL'%dn,el.code,e2.code,el.place,e2.place,c.c_true,c.c_false);elseexit(-1);returnO;intProcedureE(ifstream&fromfile,AttrE&e)AttrTtl;AttrTt2;Token*token;ProcedureT(from_file,tl);while(true)token=TokenScan(from_file);if(token->type=ADD)ProcedureT(from_file,t2);strcpy_s(e.place,NewTemp();sprintf_s(e.COde,“落s%snt宅S=落s+%s”,tl.code,t2.code,e.place,tl.place,t2.place);/这里是关键，用tl.code和tl.place临时记录了上一次While的e.code和e.place,随着While的不断加深，tl的代码会不断长长StrCPV_s(tl.code,e.code);strcpy_s(tl.place,e.place);elseif(token->type=MINUS)ProcedureT(from_file,t2);strcpy_s(e.place,NewTemp();sprintf_s(e.code,"%s%snt%s=%s-s,ztl.code,t2.code,e.place,tl.place,t2.place);strcpy_s(tl.code,e.code);strcpy_s(tl.place,e.place);elsefor(inti=O;i<(int)token->name.length();i+)from_file.unget();/Mifi/E->T/Iiiiiiiiiiiiiiiiiiiiiiiiihiistrcpy_s(e.place,tl.place);sprintf_s(e.code,"%s,'ztl.code);break;returnO;intProcedureT(ifstream&from_file,AttrT&t)AttrFfl;AttrFf2;Token*token;Procedure?(from_file,f1);while(true)token-TokenScan(from_file);if (token->typeMUL) Procedure?(from_file,f2);strcpy_s(t.place,NewTemp();sprintf_s(t.code,n%s%snt%s=%s*%s,fl.code,f2.code,t.place,fl.place,f2.place);strcpy_s(fl.code,t.code);strcpy_s(fl.place,t.place);elseif(token->type=DIC)Procedure?(from_file,f2);strcpy_s(t.place,NewTemp();sprintf_s(t.code,n%s%snt%s=%s%s,fl.code,f2.code,t.place,fl.place,f2.place);strcpy_s(fl.code,t.code);strcpy_s(fl.place,t.place);elsefor(inti=0;i<(int)token->name.length();i+)from_file.unget();/Mifi)strcpy_s(t.place,fl.place);sprintf_s(t.code,%s,zfl.code);break;return0;intProcedure?(ifstream&from_file,AttrF&f)AttrEe;Token*token;chartemp_value50;token=TokenScan(from_file);if(token->type=LBRAC)ProcedureE(from_file,e);strcpy_s(f.place,e.place);/f.place=e.placesprintf_s(f.code,%sze.code);token=TokenScan(frOrn;/匹配右括号)if(token->type=工DN)strcpy_s(f.place,token->name.c_str();sprintf_s(f.code,0);)if(token->type=INT8)sprintf_s(temp_value,%du,ValueOfINT8(token->value);strcpy_s(f.place,temp_value);sprintf_s(f.code,0);if(token->type=INTlO)/sprintf_s(temp_value,%d",_itoa_s(token->value,);strcpy_s(f.place,token->value.c_str();sprintf_s(f.code,0);if(token->type=INTl)sprintf_s(temp_value,%d,*,ValueOfINTl(token->value);strcpy_s(f.place,temp_value);sprintf_s(f.code,0);return0;实验结果：实验中遇到的问题及其解决:1、根据化简后的产生式修改语法制导定义：主要难点在于EfTl(+T2)*此种产生式当循环调用的次数多于1的时候需要做一步Tl.place=E.place;Tl.code=E.code将上一次循环的E.code和E.place暂存至IJTLCode和Tl.place中，这样在下一次循环中通过E.code=Tl.codeT2.code11gen(E.place*:=zTl.place'+'T2.place)就可以正确的重新生成E的新的三地址代码。2、使用真假出口法和继承属性来确定goto的标号：在本程序中并没有使用拉链回填的方法实现got。，而是使用下面的实现方法：例如,S->ifCthenS和S->whileCdoS这种的产生式，(1)在S中，先创建所有用到的非终结符的属性结构体：AttrCc;C的属性AttrSsi;/SI的属性AttrEe;/e的属性在match完if和WhiIe后，用以下语句构造真假出口if(token->type=IF)c.c_true=NeWLabeI();/c.c_true出口有了新标签si.begin=c.c_true;/C真则往SI走si.next=c.c_false=s.next;/C假贝J走S的下一步为Le)标签，在前面预置了elseif(token->type=WHILE)si.next=s.begin=NewLabel();c.c_true=si.begin=NewLabel();/cX贝U彳主Sl走c.cfalse=s.next;/C假则走