编译原理.doc

给定程序的说明：本程序仅考虑由下面产生式所定义的程序语句：S if B then S else 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嵌套起来的复合语句组成的，并且规定的语句末加上#表示程序结束。词法分析的功能说明及运行结果，包括：一. 输入的源程序文件名称及内容原程序文件名：pas.cpp内容： while (a=n then a:=a+1 else a:=a+1 end#二. 输出-（1）相应Token序列（w，”NULL”）(,”NULL”)(i,”a”)(=,”NULL”)(i,”NULL”)(t,”NULL”)(i,”a”)(:=,”NULL”)(i,”a”) (+,”NULL”) (x,”1”) (e,”) (i,”a”) (:=,”NULL”) 3 048 056 042 356 149 05 04 00 056 242 256 31 056 038 056 034 057 12 056 038 056 034 057 16 010 0三.关键词等对照表的内容,界限符、常数等内部码的表达方式 内部码编码号ifSy_if0thenSy_then1elseSy_else2whileSy_while3beginSy_begin4doSy_do5endSy_end6标识符Ident56#JingHao10；Semicolon8+Plus34*Times36:Becomes38(lParent48)rParent49四.程序用到的数据结构说明1.struct rWords ：定义单词数组。char sp10;int sy; ;是对单词数组的数范围定义。2.static char Spelling10 = ;：是对单词拼写进行结构体进行定义。3.struct FourExp:四元式定义。4.static int action1913，static int action1107 ，static int action21611：是对SLR(1)的定义。5. while (ss1 = 0 & ii nLength) if (!strcmp(spe1,nTab1ii) ss1 = 1;ii +;if (ss1 = 1) return ii - 1;elsereturn -1;:是以循环集组成的。 五.用自然语言描述算法1.void Scan是单词浏览扫描,是扫描小写字母a到z，之后将扫描的单词放入函数Identifer，还对数字进行扫描，之后放到函数number中。若是=放入Readch中，查找是大于等于或小于等于。2.EO是关系表达式的和取3.定义eGn是生成四元式，nxp是下标，将所得数据放入NXP中。六语法分析的程序分析及要求：1、根据给定的文法画出的算术表达式、布尔表达式、程序语句的LR（0）项目集规范族，及验证上述的SLR分析表的结果。1) 算术表达式的项目集规范族I0:S. EE. E+EE. E*EE. (E)E. II2:E( . E)E. E+EE. E*EE. (E)E. II4:EE+. EE. E+EE. E*EE. (E)E. iI6:E(E . )EE .+EEE .*EI8:EE*E .EE.+EEE.*EI1:SE.EE.+EEE.*EE.E+EE.E*EE.( E)E.i I3:Ei . I5:EE*. EE. E+EE. E*EE. (E)E. iI7:EE+E .EE .+EEE .*EI9:E(E) .有错误,在6状态下当前输入符号为+时，应移进4状态，即s4.2)布尔表达式的项目集规范族I0:S.BB.iB.iropiB.(B)B.notBB.ABB.OBA.BandO.BorI4:B(.B)B.iB.iropiB.(B)B.notBB.ABB.OBA.BandO.BorI8:BO.BB.iB.iropiB.(B)B.notBB.ABB.OBA.BandO.BorI12:B(B).I1:Bi.Bi.ropiI5:Bnot.BB.iB.iropiB.(B)B.notBB.ABB.OBA.BandO.BorI9:ABand.I13:SB.AB.andOB.orI2:Birop.iI6:BnotB.AB.andOB.orI10:OBor.I14:BAB.AB.andOB.orI3:Biropi.I7:BA.BB.iB.iropiB.(B)B.notBB.ABB.OBA.BandO.BorI11:B(B.)AB.andOB.orI15:BOB.AB.andOB.or3)程序语句的项目集规范族I0:S.SS.if e then S else SS.while e do SS.begin L endS.aI4:Sbegin. L endL.SL.S;lS.if e then S else SS.while e do SS.begin L endS.aI8:Sbegin L. endI12:Sbegin L end.I16:LS;L.I1:SS.I5:Sa.I9:LS.LS.;LI13:LS;.LL.SL.S;LS.if e then S else SS.while e do SS.begin L endS.aI17:Sif e then S else.SS.if e then S else SS.while e do SS.begin L endS.aI2:Sif. e then S else SI6:Sif e. then S else SI10:Sif e then .S else SS.if e then S else SS.while e do SS.begin L endS.aI14:Sif e then S.else SI18:Sif e then S else S.I3:Swhile. e do SI7:Swhile e. do SI11:Swhile e do.SS.if e then S else SS.while e do SS.begin L endS.aI15:Swhile e do S.有错误,在0状态下当前输入符号为if时，应移进2状态，即s2在0状态下当前输入符号为begin时，应移进4状态，即s42、语法分析程序中各子程序的调用关系main( )Readnu( )LrParse( )Disp2( )LrParse( )LrParse1( ) Merg()LrParse2( )Gen()newTemp()BackPatch( )LrParse1(）Gen( )newTemp()LrParse2()Test( )newTemp( )Readnu( )BackPatch( )Change2()Change1()状态栈变化过程及规约顺序:0 0 3 31 3 9 72 7 5 113 11 4 44 4 0 25 2 9 66 6 1 107 10 7 58 5 2 104S-a 归约7 10 11 148 14 2 179 17 7 510 5 6 104S-a 归约9 17 11 1810 18 6 101S-if e then S else S归约4 4 11 95 9 6 105归约4 4 12 85 8 6 126 12 10 103S-begin L end 归约3 11 11 154 15 10 102S-while e do S归约0 0 11 11 1 10 -23、程序中使用的四元式的结构形式。共五列，第一列为地址，在输出程序Disp2( )中用temp1表示；第二列是算符OP，存储在程序中fexptemp1.op中；第三列是第一操作数，存储在程序中的nTab1fexptemp1.arg1.pos中；第四列是第二操作数，存储在程序中的nTab1fexptemp1.arg2.pos中；第五列是出口，程序中用tr和fr分别存储真出口和假出口线性表：int LabelTemp10暂时存储四元式中的地址二维数组：action1913用来存储程序语句的slr(1)分析表结构体：struct aa int sy1; int pos;Stack存储程序语句中语法分析过的二元式其中stack.pos 表示该文法的slr（1）分析表中的状态号ibuf100存储整个bool表达式或算术表达式语句 rWordschar sp10;int sy;ResWords10存储关键字及与之对应的token内部码4、找出程序中使用的数据结构(1)structrWordsResWords10(2)structaa(3)structFourExp(4)staticintaction1913staticintaction1107staticintaction21611(5)staticcharSpelling10（6）线性表：int LabelTemp10暂时存储四元式中的地址（7）二维数组：action1913用来存储程序语句的slr(1)分析表（8）结构体：struct aa int sy1; int pos;Stack存储程序语句中语法分析过的二元式其中stack.pos 表示该文法的slr（1）分析表中的状态号ibuf100存储整个bool表达式或算术表达式语句 rWordschar sp10;int sy;ResWords10存储关键字及与之对应的token内部码5、 用伪代码或自然语言描述的程序的算法先从token序列中读取一组二元式，使用LrParse（）判断六.总结通过这学期对编译原理的学习，这门课程不仅介绍了很多新的和编译程序的知识，还涉及数据结构和算法设计等学科的内容。在这次进行上机