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

《北京工业大学-编译原理--实验报告.docx》由会员分享，可在线阅读，更多相关《北京工业大学-编译原理--实验报告.docx（23页珍藏版）》请在课桌文档上搜索。

1、计算机学院实验报告课程名称：编译原理实验人学号：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对应的子程

2、序的编写问题：142、缩进的控制：14实验三语法制导的三地址代码生成程序15语法制导定义：15三地址代码生成器的数据结构16三地址生成器算法：17实验结果：21实验中遇到的问题及其解决：221、根据化简后的产生式修改语法制导定义：222、使用真假出口法和继承属性来确定goto的标号：22实验一词法分析程序的设计与实现词法的正规式描述：标识符字母(字母1数字字符)*十进制整数O(I2i3456789)(01123456789)*八进制整数0(01234567)(01234567)*十六进制整数0(xX)(0l23456789abcdef)(0l23456789abcdeIf)*运算符和分隔符+-

3、*/=();关键字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”/用于保

4、存从文件中读取的字符读第一个字符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：这里加上保留字检测部分进行字符串的对比

5、，即可比较出保留字，通过压栈的形式来获得完整的属性值/以下为保留字的检测/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,

6、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

7、(Ch=,O,)ch=from_file.get();if(ch=,O,&ch=,0,&ch=,a,&ch:returnnewToken(MORE,value,)；case,:returnnewToken(LESS,value,id=E;S-ifCthenS;S-whileCdoS;C-EE;C-ET(+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,endltype=IF)coutname

8、endltype=THEN)coutnameendltype=WHILE)coutnameendltype=DO)coutnameendltype=IDN)cout,id:,nameendltype=EQU)Indent();coutnameendlendl;ProcedureE(from_file);elseexit(-1);indentation-=4;/子程序结束returnO;intProcedureC(ifstream&from_file)Indent();cot,C,endltype=MORE)coutnameendltype=LESS)coutnameendlendl;Proce

9、dureE(from_file);elseexit(-1);)indentation-=4;/子程序结束returnO;)intProcedureE(ifstream&from_file)Indent();cout,E,endltype=ADD)Indent();coutnameendltype=MINUS)Indent();coutnameendlendl;ProcedureT(from_file);elsefor(inti=O;iname.length();i+)from_file.unget();/Mifiindentation-=4;/子程序结束returnO;indentation-

10、=4;/子程序结束return0;)intProcedureT(ifstream&from_file)Indent();cout,T,endltype=MUL)Indent();coutnameendltype=DIC)Indent();coutnameendlendl;ProcedureF(from_file);elsefor(inti=O;iname.length();i+)from_file.unget();/回退indentation-=4;/子程序结束returnO;indentation-=4;/子程序结束returnO;intProcedureF(ifstreamsfrom_fi

11、le)Indent();cout,F,endltype=LBRAC)coutnameendlendl;ProcedureE(from_file);token=TokenScan(from_file);coutnameendltype=IDN)cout,id:,nameendltype=INT8)cot,int8:,value)endltype=INTlO)cout,intlO:valueendltype=INT16)coutintl:,value)endlT(+T)*类似的产生式没有写循环调用控制，后来在(+T)*的最外层加了一个WhiIe(true)循环，然后在While(true)的首行加

12、入了不是+就return的判定，成功解决了问题。2、缩进的控制：这个实验中碰到的第二个问题就是语法树缩进的控制问题，最终通过一个全局变量indentation来控制缩进的字符数量，一个IndentO函数来输出缩进(其实就是空格)，控制缩进数量的关键点有两个：一为进入子程序的时候indentation+=*二为结束子程序的时候indentation-二4。剩下的就是根据调试来选择在哪里输出缩进空格的问题了。实验三语法制导的三地址代码生成程序语法制导定义:也生式语义规则S-id=E;S.code=E.codegen(id.placeE.place)S-ifCthenSC.true=newlabel

13、;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-EiE2C.code=Ei.codeE2.codegen(if,Ei.placeE2.placegotofC.true)gen(goto,C.false)C-EiE2C.code=Ei.codeI

14、IE2.c0deIIgen(if,Ei.placeTi(+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.pl

15、ace;T.code=F.codeT-Fl(*F2)*T.place=newtemp;(T.code=Fl.codeF2.codegen(T.placeFl.place*,F2.place);Fl.place=T.place;Fl.code=T.code;)+T-Fl(/F2)*T.place=newtemp;(T.code=Fl.codeF2.codegen(T.placeFl.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.co

16、de=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

17、_true;/用来标记入口AttrC;typedefstructcharcodeCODESIZE;/CodeSize=500charplaceBUFSIZE;/BufSize=200*S的属性定义*/*E的属性定义*/*C的属性定义*/*T的属性定义*/AttrT;*F的属性定义*/tyedefstructcharcodeCODESIZE;/CodeSize=500charplaceBUFSIZE;/BufSize=200*IDN的属性定义*/AttrF;tyedefstructcharidnameBUFSIZE;intentry;AttrIDN;三地址生成器算法：intProcedures(

18、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假则

19、走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(

20、);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/Iiiiiiiiiiiiiiiiiiiiiiiiiii

21、iiiiiiiiielseif(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;P

22、rocedureE(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%stype=ADD)ProcedureT(from_file,t2

23、);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,

24、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;iname.length();i+)from_file.unget();/Mifi/E-T/Iiiiiiiiiiiiiiiiiiiiiiiiihiistrcpy_s(e.place,tl.place);sprintf_s(e.code,%s,ztl.code);break;returnO;int

25、ProcedureT(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)

26、;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;iname.length();i+)from_file.unget();/Mifi)strcpy_s(t.pla

27、ce,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;/匹配

28、右括号)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()

29、;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中，

30、这样在下一次循环中通过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假则走