《编译原理》课程设计说明书-DO-WHILE循环语句的翻译程序设计(LR方法、输出三地址表示).doc

*理工大学编译原理课程设计说明书第1页共16页DO-WHILE循环语句的翻译程序设计（LR方法、输出三地址表示）1.系统描述1.1设计目的通过设计、编制、调试一个DO-WHILE循环语句的语法及语义分析程序，加深对语法及语义分析原理的理解，并实现词法分析程序对单词序列的词法检查和分析。1.2设计内容及步骤对循环语句：DO赋值语句WHILE表达式按给定的题目写出符合自身语法分析方法要求的文法和属性文法描述。(1)按给定的题目给出语法分析方法的思想及分析表设计。(2)按给定的题目给出中间代码序列的结构设计。(3)完成相应的词法分析、语法分析和语义分析程序设计。(4)编制好分析程序后，设计若干用例，上机测试并通过所设计的分析程序。2文法的描述本程序所用的文法如下：GS:(1)S->doE；while(B)ifB.truegotoB.trueelsegotoB.false；(2)B->I1ropI2B.type=bool；B.val=I1.valropI2.val；(3)E->I1=I2opI3I1.val=I2.valopI3.val；(4)I->idI.val=id.val；注意：ropis<or>，opis+,-,*,/,idisanynumberoridentifier由上可知，非终结符B表示布尔表达式，E表示赋值表达式3.语法分析方法描述及语法分析表设计3.1语法分析方法描述本实验采用LR分析方法对DO-WHILE语句进行语法分析。LR分析法是一种能根据当前分析栈中的符号串（通常以状态表示）和向右顺序查看输入串的K个（K>=0）符号就能惟一的确定分析器的动作是移进还是归约和用哪个产生式归约，因而也就能惟一的确定句柄。LR分析法的归约过程是规范推导的逆过程，所以LR分析过程是一种规范过程。一个LR分析器由3个部分组成：总控程序，也可以称为驱动程序。对所有的LR分析器，总控程序是相同的。分析表或分析函数。不同的方法分析表将不同，同一个方法采用的LR分析器不同时，分析表也不同，分析表表又可以分为动作（ACTION）表和状态转换（GOTO）表两个部分，它们都可以用二维数组表示。分析栈，包括文法符号栈和相应的状态栈。它们均是先进后出栈。*理工大学编译原理课程设计说明书第2页共16页分析器的动作由栈顶状态和当前输入符号所决定。LR分析器工作过程示意图如图所示：其中SP为栈顶指针，Si为状态栈，Xi为文法符号栈。状态转换表内容按关系GOTOSi,X=Sj确定，改关系式是指当前栈顶状态为Si遇到当前文法符号为X时应转向状态Sj。X为终结符或非终结符。ACTIONSi,a规定了栈顶状态为Sj时遇到输入符号ci应该执行的动作。动作有以下四种可能：移进：当Sj=GOTOSi，a成立，则把Sj移入到文法符号栈。其中i，j表示状态号。规约：当在栈顶形成句柄为b时，则用b归约为相应的非终结符A，即当文法中有A->b的产生式，而b的长度为r，则从状态栈和文法符号栈中自栈顶向下去掉r个符号。并把A移入文法符号栈内，再把满足Sj=GOTOSi，A的状态移进状态栈，其中Si为修改指针后的栈顶状态。接受acc：当归约到文法符号栈中只剩下文法的开始符号S时，并且输入符号串已结束即当前输入符是#，则为分析成功。报错：当遇到状态栈顶为某一状态下出现不该遇到的文法符号时，则报错，说明输入串不是该分发能接受的句子。3.2语法分析表设计3.2.1构造文法的DFAI0:S->.SS->.doE；while(B)I1:S->S.I2:S->do.E；while(B)I3:S->do.E；while(B)E->.I=IopII->.id输入串XXX#总控程序ACTION表GOTO表Sn.S1S0Xn.X1#SP输出*理工大学编译原理课程设计说明书第3页共16页I4:S->doE.；while(B)I5:E->I.=IopII6:I->id.I7:S->doE；.while(B)I8:E->I=.IopII->.idI9:S->doE；.while(B)I10:E->I=I.opII11:S->doE；while.(B)I12:E->I=Iop.II=.idI13:S->doE；while(.B)B->.IropII->.idI14:E->I=IopI.I15:S->doE；while(B.)I16:B->I.ropII17:S->doE；while(B).I18:B->Irop.II19:B->IropI.3.2.2然后写出LR分析表：状态ACTIONGOTODo=；While()RopOpId#SBEI0S211acc2S3I1I0I19I4I13I9I14I15I12I6I10I8I2I7I16I11I5I3I17I18*理工大学编译原理课程设计说明书第4页共16页3S6454S75S86R4R4R4R4R4R4R4R4R4R4R4R47S98S6109S1110S1211S1312S1413S6151614R3R3R3R3R3R3R3R3R3R3R3R315S1716S1817R1R1R1R1R1R1R1R1R1R1R1R118S61919R2R2R2R2R2R2R2R2R2R2R2R24.中间代码形式的描述及中间代码序列的结构设计4.1中间代码形式的描述在本程序中作用三地址码表示中间代码三地址码的表达形式为：标号结果：=操作数1操作符操作数2常见三地址表示举例：赋值语句t1:=aopb，a:=b条件转移iftruegotoLabel无条件转移gotoLabel4.2中间代码序列的结构设计本程序用标号来表示程序的跳转过程，示例如下100赋值语句101赋值语句102条件跳转语句103无条件转移语句