《编译原理》实验说明书2009.doc

编译原理实验指导书执笔人：陈义仁2008年3月 实验一 词法分析器的设计一、实验目的和要求加深对状态转换图的实现及词法分析器的理解。熟悉词法分析器的主要算法及实现过程。要求学生掌握词法分析器的设计过程，并实现词法分析。二、实验基本内容给出一个简单语言的词法规则，画出状态转换图，并依据状态转换图编制出词法分析程序，能从输入的源程序中，识别出各个具有独立意义的单词，即基本保留字、标识符、常数、运算符、分隔符五大类。并依次输出各个单词的内部编码及单词符号自身值。（遇到错误时可显示“Error”，然后跳过错误部分继续显示）词法规则如下：单词符号种别码内码单词符号种别码内码break101209char102210do103211double104212else105！213float106&214for107|215if108!216int109217return110218void111|219while112&220201221202222*203223/204*224%205225206%226207227208228单词符号种别码内码单词符号种别码内码&229306|230#307301；308302,309(303标识符400)304常数500二进制形式305三、实验时间：上机三次。第一次按照自己的思路设计一个程序。第二、三次在理论课学习后修改程序，使得程序结构更加合理。四、实验过程和指导：（一）准备：1.阅读课本有关章节（c/c+，数据结构），花一周时间明确语言的语法，写出基本算法以及采用的数据结构和要测试的程序例。2.初步编制好程序。3.准备好多组测试数据。（二）上课上机：将源代码拷贝到机上调试，发现错误，再修改完善。（400，”main”）（303，”（“）（304，”）“）（305，”“（109，”int”）（400，”a”）（309，”,”）（400，”b”）（308，”;”）（400，”a”）（221，”=”）（500，”1010”）（308，”;”）（400，”b”）（221，”=”）（400，”a”）（201，”+”）（500，”10100”）（308，”;”）（306，”“）（三）程序要求：程序输入/输出示例：输入如下一段：main()/* 一个简单的c+程序*/int a,b; /定义变量a = 10; b = a + 20;要求输出如右图。要求：(1) 剔除注解符(2) 常数为无符号整数（可增加实型数，字符型数等）（四）练习该实验的目的和思路：程序开始变得复杂起来，可能是大家以前编过的程序中最复杂的，但相对于以后的程序来说还是简单的。因此要认真把握这个过渡期的练习。程序规模大概为200行及以上。通过练习，掌握对字符进行灵活处理的方法。（五）为了能设计好程序，注意以下事情：1.模块设计：将程序分成合理的多个模块（函数/类），每个模块（类）做具体的同一事情。2.写出（画出）设计方案：模块关系简图、流程图、全局变量、函数接口等。3.编程时注意编程风格：空行的使用、注释的使用、缩进的使用等。4程序设计语言不限，建议使用面向对象技术及可视化编程语言，如C+，VC,JAVA,VJ+等。四、上交：1.程序源代码及可执行文件（当堂检查/通过网络提交）；2.已经测试通过的测试数据3组（全部存在一个文本文件中，以“第一组输入/输出/第二组输入/输出/第三组输入/输出”的顺序存放）；3.实验报告按照提供的模板填写：（1） 功能描述：该程序具有什么功能？（2） 算法描述：所采用的数据结构，基本实现算法及某些特殊过程的实现算法（如在处理某个问题时，你所采取的好的处理方法等）注意此处不要简单的将源程序抄上来。（源程序将打印出来作为附录）（3） 程序结构描述：函数调用格式、参数含义、返回值描述、函数功能；另外可以附加函数之间的调用关系图、程序总体执行流程图及类的层次图。（4） 实验总结：你在编程过程中花时多少？多少时间在纸上设计？多少时间上机输入和调试？多少时间在思考问题？遇到了哪些难题？你是怎么克服的？你对你的程序的评价？你的收获有哪些？（5） 写出上机调试时发现的问题，以及解决的过程；（6） 附上源程序（打印的）五、问题描述及基本算法提示1 状态转换图的实现让每个结点对应一小段程序。 需引进一组全局变量和过程 （1）ch 字符变量，存放最新读进的源程序字符。（2）strToken 字符数组，存放构成单词符号的字符串。 （3）GetChar 子程序过程，将下一输入字符读到ch中，搜索指示器前移一字符位置。 （4）GetBC 子程序过程，检查ch中字符是否为空白。若是，则调用GetChar直至ch中进入一个非空白字符。（5）Concat 子程序过程，将ch中的字符连接到strToken之后。例如， 假定strToken 原来的值为“AB”,而ch中存放着C,经调用Concat后，strToken的值就变为”ABC”。（6）IsLetter和IsDigit 布尔函数过程，它们分别判断ch中的字符是否为字母和数字。（7）Reserve 整型函数过程，对strToken中的字符找保留字表，若它是一个保留字，则返回它的编码，否则返回0值。（8）Retract 子程序过程，将搜索指示器回调一个字符位置，将ch置为空白字符。（9）InsertId 整型函数过程，将strToken中的标识符插入符号表，返回符号表指针。（10）InsertConst 整型函数过程，将strToken中的常数插入常数表，返回常数表指针。2词法分析器构造基本算法int code,value;strToken:=“”; 置strToken为空串GetChar();GetBC();if (IsLetter()begin while (IsLetter() or IsDigit() begin Concat();GetChar(); end Retract(); code : = Reserve(); if(code = 0) begin value : = InsertId(strToken); return($ID,value); end else return(code,-);endelse if (IsDigit()begin while(IsDigit() begin Concat();GetChar(); end Retract(); value : = InsertConst(strToken); returnr($INT,value);endelse if (ch = = ) retutn($ASSIGN,-);else if (ch = +) return ($PLUS,-);else if (ch =*)begin GetChar(); If (ch = *) return ($POWER,-); Retract() ; return ($STAR,-);endelse if (ch = ;) return ($SEMICOLON,-);else if (ch = () return ($LPAR,-);else if (ch = ) return ($RPAR,-);else if (ch = ) return ($LBRACE,-);else if (ch = ) rerurn ($RBRACE,);else ProcError(); /错误处理/实验二 语法分析器设计之一 -预测分析器一实验目的和要求 理解预测分析器程序的构造过程,掌握预测分析程序的设计.二实验基本内容编写预测分析程序，能实现：1. 给定文法，消除左递归及左公因子2构造并输出FIRST和FOLLOW（A）3. 构造并输出分析表,判断是否为LL(1)文法4. 任意输入一个输入串,可得到成功的分析或错误的提示，输出其分析过程或打印语法分析树。三问题描述及算法提示 1理解左递归消除算法及左公因子的提取。 2求出FIRST（）和FOLLOW（A） （1）FIRST（X）构造算法：若 XVT,则FIRST(X)X若XVN,且有产生式Xa ,则a加入FIRST（X）,若X，则加入FIRST（X）若XY 是一产生式且YVN ,则把FIRST（Y）中所有的非元素加到FIRST(X)中；若XY1Y2YK是一个产生式，Y1, Y2, ,Yi-1VN,且对于 , , FIRST(Yj)都含有(Y1Yi-1=*),则把FIRST(Yi)中所有非元素都加到FIRST(X)中；若所有FIRST(Yj)均含有,j=1,2,k, 则把加到FIRST(X)中。重复 、直到所有FIRST(X)不再扩大为止。 （2）FOLLOW（B）构造算法：对于文法的开始符号S,把#加入FOLLOW(S)。 (由语句括号“#S#”中的S#得到)若有AaBb (a可为空),则将FIRST(b)加入FOLLOW(B)。若有AaB或AaBb且b =*, 则把FOLLOW(A)加入到FOLLOW(B)。重复、直到FOLLOW集不再增大为止。 3依据FIRST（A）和FOLLOW（A）构造分析表 对文法G的每个产生式A 执行， 对任意a FIRST(),把A加至MA, a中 若 FIRST(),则对任意b FOLLOW(A),把A加至MA,b中 把所有无定义的MA, a标上 “出错标志” 4依据分析表进行分析 将“#”和文法开始符号依次入栈; 把第一个输入符读入a; while(1) 把栈顶符号弹出并放入x中; if (xVT) if (xa) 将下一输入符读入a; else error( ); else if(x= =#) if(x= =a) break; else error( ); else if (Mx,a “xy1y2yk”) 把ykyk-1y1依次入栈;/即y1y2yk逆序依次入栈 /若y1y2yk = ，则不进行入栈操作 else error( ); 实验二 语法分析器设计之二 算符优先分析器一实验目的和要求熟悉FIRSTVT、LASTVT、优先关系表构造算法的实现，掌握算符优先分析器的构造过程。二实验基本内容编写一个自下而上的语法分析程序，能够实现1 输入文法，判断是否为算符文法2 输出该文法的每个非终结符的FIRSTVT集和LASTVT集3 构造并输出分析表，判断是否为算符优先文法，若不是提示无法进行分析4 生成算符优先文法语法分析程序5 用户输入句子若合法,输出归约的过程或语法树三问题描述及算法提示1 理解算符文法，算符优先文法的概念2 求出FIRSTVT和LASTVT3 依据FIRSTVT，LASTVT 构造优先表FOR每条产生式PX1X2XnFOR I : =1 TO n-1 DO BEGIN IF Xi 和Xi+1均为终结符THEN置Xi Xi+1 IF in2且Xi 和Xi+2都为终结符但Xi+1为非终结符THEN置Xi Xi+2 IF Xi 为终结符而且Xi+1为非终结符THEN FOR FIRSTVT（Xi+1）中的每个a DO 置 Xia IF Xi 为非终结符而且Xi+1为终结符THENFOR LASTVT（Xi）中的每个a DO 置 aXi+1 END4. 依据分析表进行算符优先分析k=1; Sk=#; /k代表栈S的使用深度 doa=下一个输入符; if (SkVT) j=k;else j=k1; /*j指栈顶终结符，任何两终结符之间最多只有一非终结符，故若Sk VT则Sk1VT */ while (Sja) /找出最左子串SjSj+1Ska doQ=Sj; /j从最左素短语末逐步移向首 if (Sj1VT) j=j1; else j=j2; while (Sj=Q); 把Sj+1Sk归约为某个N; k=j+1; Sk=N; /将归约后的非终结符N置于原Sj+1位/置 if (Sja) | (Sj=a) k=k+1; Sk=a; else error( ); /若栈顶Sja或=a则将a压栈 while (a!=#);实验三 语法分析器设计之三LR分析器一 实验目的和要求使学生理解LR分析器的构造过程及产生分析表的具体算法二 实验基本内容选择一种LR文法（LR（0）、SLR（1）、LALR（1）、LR（1），设计出一个LR分析器，能够实现：1 对输入的文法进行判断，是否为相应LR文法，若不是提示重新输入文法。2 输出相应的项目集规范簇3 输出相应的LR分析表。4 输入一个句子，输出其分析过程（移进，归约，接受）三 问题描述及算法提示1 文法进行拓广2 构造I 的闭包CLOSURE（I）I是文法G的任一项目集。（1）I的任何项目都属于CLOSURE（I）（2）若AB属于CLOSURE（I）。则关于BVN的产生式B项目BCLOSURE（I） （3）重复执行上述步骤直至CLOSURE（I）不再增大。3 求出状态转换函数GO（I，X）GO（I，X）CLOSURE（J）J形如AX的项目|AX属于I4求出项目集规范族C的算法（1）CLOSURE（S S）C（2）对C中每一项目集I和文法G的每个符号X做若GO(I,X)非空且不属于C,则把GO(I,X)加入C（3）重复1,2 直至C不再增大为止.5. 分析表构造假定C=I0,I1In,每个项目Ik的下标K作为分析器状态,令包含项目S S