编译原理-C++编译器课程设计报告(共27页)

1、精选优质文档-倾情为你奉上编译器的设计与分析学 号： 姓 名： 李 博 专 业： 计算机科学与技术 _课 程： 编译原理 指导教师： 闫 红 实验目的本实验设计的小型编译程序涉及到编译前端的三个阶段：词法分析、语法分析和语义分析生成中间代码(四元式），编译程序的重点放在中间代码生成阶段。编译程序的输出结果包括词法分析后的二元式序列、变量名表；语法分析后的状态栈分析过程显示；语义分析生成中间代码后的四元式程序。整个程序分为三个部分：（1）词法分析部分（2）语法分析、语义分析及四元式生成部分（3)输出显示部分实验要求：本程序仅考虑由下面产生式所定义的程序语句：S if B then S else

2、S | while B do S | begin L end | AL S;L | SA i:= EB BB|BB|B|(B)|I rop i|i 其中，各个非终结符的含义是：S-语句L语句串A赋值句B-布尔表达式E-算术表达式各个终结符的含义：i-整型变量或常数，布尔变量或常数；rop-为六种关系运算符的代表；-起语句分隔作用；：=-赋值符号-逻辑非运算符；-逻辑与运算符；-逻辑或运算符；规定程序是由一条语句或由begin和end嵌套起来的复合语句组成的，并且规定的语句末加上#表示程序结束。下面是符合规定的程序示例： begin A:=A+B*C; C:=A+2; while A<C

3、do while A>B do if M=N THEN C:=D else while A<=D do A:=Dend#实验内容：第一部分：词法分析一词法分析的功能：输入：所给文法的源程序字符串输出：1.二元组（单词种别,单词符号的属性值）构成的序列2.关键字: (相当于Pascal语言中的begin) , if ,else , while , (相当于Pascal语言中的end ) 所有的关键字都是小写字母. 3.运算符: + , - , * , / , = , < , <= , = , > , >= ,<> , && ,| ,

4、 ! 4.界 符: 逗号 ,分号 ,左圆括号 , 右圆括号 , # 5.常 数: 在这里只涉及到int型常量 6.其他单词是标识符（ID）和整形常数（NUM），通过以下正规式定义： ID = letter（letter|digit）*NUM = digit digit * 7.空格由空白，制表符和换行符组成，空格一般用来分隔ID，NUM，运算符，界符和关键字，词法分析阶段通常会被过滤掉。二词法分析程序设计 单 词内部码编码号If Sy_if0thenSy_then1elseSy_else2whileSy_while3beginSy_begin4DoSy_do5endSy_end6andop_a

5、nd39Orop_or40notop_not41+Plus34*Times36：becomes38；Semicolon 8(lparent48)rparent49AccAcc-2=rop423.自动机转换图三程序实现数据结构：struct nTabint tc;int fc;nTab2200;int Label = 0;struct rWordschar sp10;int sy;struct rWords ResWords10 = "if",Sy_if,"do",Sy_do,"else",Sy_else,"while&quo

6、t;,Sy_while,"then",Sy_then,"begin",Sy_begin,"end",Sy_end,"and",op_and,"or",op_or,"not",op_not;struct aa int sy1;int pos;buf1000,n,n1,E,sstack100,ibuf100,stack1000;void ReadLine( )char ch1;Pline = Line;ch1 = cfile.get();while( ch1 != 'n&

7、#39;)*Pline = ch1;Pline +;ch1 = cfile.get();*Pline = '0'Pline = Line;void Readch( )if (ch = '0')ReadLine( );Lnum +;ch = *Pline;Pline +;void Scan ( ) while (ch != '') switch(ch) case ' ':break;case 'a': case 'b':case 'c':case 'd':case &#

8、39;e':case 'f':case 'g':case 'h':case 'i':case 'j':case 'k':case 'l':case 'm':case 'n':case 'o':case 'p':case 'q':case 'r':case 's':case 't':case 'u':case 'v':c

9、ase 'w':case 'x':case 'y':case 'z':Identifer( );break;case '0':case '1':case '2':case '3':case '4':case '5':case '6':case '7':case '8':case '9':Number(); break;case '<': Readch(

10、 ); if (ch ='=') bufCount.pos = 0; else if (ch = '>') bufCount.pos = 4; else bufCount.pos = 1; Pline -; bufCount.sy1 = rop; Count +; break;case '>': Readch( ); if (ch ='=') bufCount.pos = 2; else bufCount.pos = 3; Pline -; bufCount.sy1 = rop; Count +; break;case

11、'(': bufCount.sy1 = lParent;Count +;break;case')':bufCount.sy1 = rParent;Count +; break;case'#':bufCount.sy1 = JingHao;Count +; break;case'+':bufCount.sy1 = Plus;Count +; break;case'*':bufCount.sy1 = Times;Count +; break;case':': Readch();if (ch ='

12、=') bufCount.sy1 = Becomes;Count +; break;case'=':bufCount.sy1 = rop;bufCount.pos = 5;Count +; break;case'':bufCount.sy1 = Semicolon;Count +; break; Readch( );bufCount.sy1 = -1;nt Find(char spe1 )int ss1 = 0;int ii = 0;while (ss1 = 0 && ii < nLength) if (!strcmp(spe1,n

13、Tab1ii) ss1 = 1;ii +;if (ss1 = 1) return ii - 1;elsereturn -1;void Identifer( )int i = 0,j,k = 0;int ss = 0;do Spellingk = ch;k+;Readch( ); while(ch >= 'a' && ch <= 'z') | (ch >='0' && ch <= '9'); Pline -;Spelling k = '0' while (ss

14、= 0 && i < 10)if (!strcmp(Spelling,ResWordsi.sp) ss = 1;i +;if (ss = 1) bufCount.sy1 = ResWordsi - 1.sy;elsebufCount.sy1 = ident;j = Find(Spelling);if (j = -1)bufCount.pos = tt1;strcpy(nTab1tt1,Spelling);tt1 +;nLength +;else bufCount.pos = j;Count +;for (k = 0; k < 10; k+)Spellingk =&#

15、39; 'void Number( )int iValue = 0;int digit;do digit = ch -'0'iValue = iValue * 10 + digit;Readch( ); while (ch >= '0' && ch <= '9');bufCount.sy1 = intConst;bufCount.pos = iValue;Count +;Pline -;四心得体会此次实验让我了解了如何设计、编制并调试词法分析程序，并加深了我对词法分析器原理的理解；熟悉了直接构造词法分析器的方法

16、和相关原理，并学会使用c+语言直接编写词法分析器；同时更熟练的掌握用c+语言编写程序，实现一定的实际功能。通过这次实验，我对词法分析器有了进一步的了解，把理论知识应用于实验中。也让我重新熟悉了C+语言的相关内容，加深了对C语言知识的深化和用途的理解。第二部分 语法分析一根据给定的文法画出算术表达式、布尔表达式、程序语句的LR（0）项目集规范族，验证上述的SLR分析表是否正确。算术表达式的LR分析表算术表达式文法GE如下：EE+E|E*E|（E）|i将文法GE拓广为文法GE：（0）SE（1）EE+E（2）EE*E（3）E（E）（4）Ei算术表达式的SLR（1）分析表状态 ACTIONGOTOI+

17、*（）# E0S3S2 11S4S5ACC2S3S2 63R4R4R4R44S3S2 75S3S2 86D4S5S97R1S5R1R18R2R2R2R29R3R3R3R3布尔表达式的分析表布尔表达式的文法如下：B BB|BB|B|(B)|i rop i|i为了便于语法分析加工处理。将文法改为如下形式GS：B BAB|BOB|B|(B)|i rop i|iBA BBOB将文法拓广为GS:(0)SB(1)Bi(2)Bi rop i(3)B(B)(4)Bnot B(5)AB and(6)BAB(7)OBor(8)BOB布尔表达式的SLR(1)分析表:状态 ACTION GOTOIrop()notan

18、dor#BAO0S1S4S313781S2R1R1R1R12S33R2R2R2R24S1S4S511785S1S4S56786R4S9S10R47S1S4S514788S1S4S515789R5R5R510R7R7R711S12S9S1012R3R3R3R313S9S10ACC14R6S9S10R615R8S9S10R8程序语句的分析表程序语句的文法如下：Sif e then S else S| while e do S|begin L end|aLS;L|S由于在编译程序设计与实现中，我们将赋值语句与算术表达式归为一类处理，故在此将赋值语句仅看成为程序语句中的一个终结符a，将布尔表达式B也看

19、作为终结符e。将文法拓广为：(0)SS(1)Sif e then S else S(2)Swhile e do S (3) Sbegin L end (4)Sa(5)LS(6)LS;L程序语句的SLR(1)分析表:状态 ACTION GOTOifthenelseWhilebegindoenda;e#SL0S3S3S511ACC2S63S74S2S3S4S5985R4R4R4R46S107S118S129R5S1310S2S3S4S51411S2S3S4S51512R3R3R3R313S2S3S4S591614S1715R2R2R2R216R617S2S3S4S51818R1R1R1R1二语法分

20、析程序的设计1分析框图，即程序之间的调用关系2，四元式的结构形式。三程序实现数据结构struct aa int sy1;int pos;buf1000,n,n1,E,sstack100,ibuf100,stack1000;算法设计void Readnu( )if (pbuf -> sy1 >= 0)n.sy1 = pbuf -> sy1;n.pos = pbuf -> pos;pbuf+;int newTemp( )newt +;return newt;int Gen (char op1,struct aa arg11,struct aa arg22,int resul

21、t1)strcpy(fexpnxq.op,op1);fexpnxq.arg1.sy1 = arg11.sy1;fexpnxq.arg1.pos = arg11.pos;fexpnxq.arg2.sy1 = arg22.sy1;fexpnxq.arg2.pos = arg22.pos;fexpnxq.result = result1;nxq +;return nxq - 1;int Merg(int p1,int p2)int p;if ( p2 = 0 ) return p1;elsep = p2;while (fexpp.result != 0) p = fexpp.result;fexpp

22、.result = p1;return p2;void BackPatch(int p,int t)int tempq;int q;q = p;while (q != 0)tempq = fexpq.result;fexpq.result = t;q = tempq;int Change1(int chan)switch(chan)case intConst:case ident: return 0;case Plus: return 1;case Times: return 2;case lParent: return 3;case rParent: return 4;case JingHa

23、o: return 5;case Tempsy:return 6;int Change2(int chan)switch(chan)case intConst:case ident:return 0;case rop:return 1;case lParent:return 2;case rParent: return 3;case op_not:return 4;case op_and:return 5;case op_or:return 6;case JingHao:return 7;case Tempsy:return 8;case EA:return 9;case EO:return

24、10;int Test(int value)switch(value)case intConst:case ident:case Plus:case Times:case Becomes:case lParent:case rParent:case rop:case op_and:case op_or:case op_not:return 1;default:return 0;int LrParse()int i1 = 0;int num = 0;if (Test(n.sy1)if (stacksp.sy1 = Sy_while)sign = 2;elseif (stacksp.sy1 = S

25、y_if) sign = 3;else sign = 1;doibufi1.sy1 = n.sy1;ibufi1.pos = n.pos;Readnu( );i1 +;while (Test(n.sy1);ibufi1.sy1 = JingHao;pbuf -;sstack0.sy1 = JingHao;ssp = 0;if (sign = 1)sp1 = 0;stack1sp1 = 0;num = 2;n1.sy1 = ibufnum.sy1;n1.pos = ibufnum.pos;LrParse1(num);n.sy1 = a; if (sign = 2 | sign = 3)Point

26、Mark +;LabelMarkPointMark.nxq1 = nxq;sp1 = 0;stack1sp1 = 0;num = 0;n1.sy1 = ibufnum.sy1;n1.pos = ibufnum.pos;LrParse2(num);LabelMarkPointMark.tc1 = nTab2Label - 1.tc;LabelMarkPointMark.fc1 = nTab2Label - 1.fc;BackPatch(LabelMarkPointMark.tc1,nxq);n.sy1 = e;Ir = actionstacksp.posn.sy1;cout << s

27、p <<"t" <<stacksp.pos<<"t"<<n.sy1<<"t"<<Ir<<"n"if (Ir < 19 && Ir >= 0)sp +;stacksp.pos = Ir;stacksp.sy1 = n.sy1;Readnu( );LrParse( ); if (Ir <= 106 && Ir >= 100)switch (Ir)case 100:break;cas

28、e 101:cout <<"S->if e then S else S归约n"sp = sp - 6;n.sy1 = S;fexpLabelTempPointTemp.result = nxq;PointTemp -;if (stacksp.sy1 = Sy_then)Gen("j",oth1,oth1,0);BackPatch(LabelMarkPointMark.fc1,nxq);PointTemp +;LabelTempPointTemp = nxq - 1;PointMark -;if (stacksp.sy1 = Sy_do)

29、Gen("j",oth1,oth1,LabelMarkPointMark.nxq1);BackPatch(LabelMarkPointMark.fc1,nxq);break;case 102:cout <<"S->while e do S归约n"sp = sp -4;n.sy1 = S;if (stacksp.sy1 = Sy_do)Gen("j",oth1,oth1,LabelMarkPointMark.nxq1);BackPatch(LabelMarkPointMark.fc1,nxq);if (stacksp.sy1 = Sy_then)Gen("j",oth1,oth1,0);fexpLabelMarkPointMark.fc1.result = nxq;PointTemp +;LabelTempPointTemp = nxq - 1;break;case 103:cout <<"S->begin L end 归约n&q