编译 DO-WHILE循环语句的翻译程序设计(LR方法、输出三地址表示).doc

DO-WHILE循环语句的翻译程序设计 （LR方法、输出三地址表示） 1.系统描述 1.1设计目的 通过设计、编制、调试一个DO-WHILE循环语句的语法及语义分析程序，加深对语法及语义分析原理的理解，并实现词法分析程序对单词序列的词法检查和分析。 1.2设计内容及步骤 对循环语句： DO〈赋值语句〉WHILE 〈表达式〉 按给定的题目写出符合自身语法分析方法要求的文法和属性文法描述。 (1)按给定的题目给出语法分析方法的思想及分析表设计。 (2)按给定的题目给出中间代码序列的结构设计。 (3)完成相应的词法分析、语法分析和语义分析程序设计。 (4)编制好分析程序后，设计若干用例，上机测试并通过所设计的分析程序。 2文法的描述 本程序所用的文法如下： G[S]: (1)S-do{E;}while(B) {if B.true goto B.true else goto B.false;} (2)B-I1 rop I2 {B.type=bool;B.val=I1.val rop I2.val;} (3)E-I1=I2 op I3 {I1.val=I2.val op I3.val;} (4)I-id {I.val=id.val;} 注意：rop is or ，op is +,-,*,/, id is any number or identifier 由上可知，非终结符B表示布尔表达式，E表示赋值表达式 3.语法分析方法描述及语法分析表设计 3.1语法分析方法描述 本实验采用LR分析方法对DO-WHILE语句进行语法分析。LR分析法是一种能根据当前分析栈中的符号串（通常以状态表示）和向右顺序查看输入串的K个（K=0）符号就能惟一的确定分析器的动作是移进还是归约和用哪个产生式归约，因而也就能惟一的确定句柄。LR分析法的归约过程是规范推导的逆过程，所以LR分析过程是一种规范过程。 一个LR分析器由3个部分组成： 总控程序，也可以称为驱动程序。对所有的LR分析器，总控程序是相同的。 分析表或分析函数。不同的方法分析表将不同，同一个方法采用的LR分析器不同时，分析表也不同，分析表表又可以分为动作（ACTION）表和状态转换（GOTO）表两个部分，它们都可以用二维数组表示。 分析栈，包括文法符号栈和相应的状态栈。它们均是先进后出栈。 分析器的动作由栈顶状态和当前输入符号所决定。 LR分析器工作过程示意图如图所示： 其中SP为栈顶指针，S[i]为状态栈，X[i]为文法符号栈。状态转换表内容按关系GOTO[Si,X]=Sj确定，改关系式是指当前栈顶状态为Si遇到当前文法符号为X时应转向状态Sj。X为终结符或非终结符。 ACTION[Si,a]规定了栈顶状态为Sj时遇到输入符号c[i]应该执行的动作。动作有以下四种可能： 移进：当Sj=GOTO[Si，a]成立，则把Sj移入到文法符号栈。其中i，j表示状态号。 规约：当在栈顶形成句柄为b时，则用b归约为相应的非终结符A，即当文法中有A-b的产生式，而b的长度为r，则从状态栈和文法符号栈中自栈顶向下去掉r个符号。并把A移入文法符号栈内，再把满足Sj=GOTO[Si，A]的状态移进状态栈，其中Si为修改指针后的栈顶状态。 接受acc：当归约到文法符号栈中只剩下文法的开始符号S时，并且输入符号串已结束即当前输入符是‘#’，则为分析成功。 报错：当遇到状态栈顶为某一状态下出现不该遇到的文法符号时，则报错，说明输入串不是该分发能接受的句子。 3.2语法分析表设计 3.2.1构造文法的DFA I0:S’-.S S-.do{E;}while(B) I1:S’-S. I2:S-do.{E;}while(B) I3:S-do{.E;}while(B) E-.I= I op I I-.id I4:S-do{E.;}while(B) I5:E-I . =I op I I6:I-id. I7:S-do{E;.}while(B) I8:E-I=.I op I I-.id I9:S-do{E;}.while(B) I10:E-I = I. op I I11:S-do{E;}while.(B) I12:E-I=I op .I I=.id I13:S-do{E;}while(.B) B-.I rop I I-.id I14:E-I=I op I. I15:S-do{E;}while(B.) I16:B-I .rop I I17:S-do{E;}while(B). I18:B-I rop .I I19:B-IropI. 3.2.2然后写出LR分析表： 状态 ACTION GOTO Do { = ; } While ( ) Rop Op Id # S B E I 0 S2