2011秋本科生可视化编译器实验指导书

计算机科学与软件学院2009级统招生《编译原理》课外实验小组实验指导书试用版编制人:许智宏编制时间：2011年10月针对《编译原理》课程教学中存在的知识点多、概念抽象、算法难于理解的情况，2010向学院和学校申报了《高级语言可视化编译器》教学研究项目，目的是通过对编译过程中词法分析，语法分析主要方法的分析过程的可视化，帮助学生深刻理解编译器的工作原理和实现方法；在系统中尽量多地展示主要编译算法的实现算法及相关数据结构，加强学生理解算法和数据结构的结合使用；逐步在编译原理实验中加入和本项目相关的扩展内容，引导学生将编译原理的理论知识学习、数据结构知识使用、数据存储和信息处理、软件工程理论实践、可视化编程工具使用相结合，提高其专业知识的综合使用能力。目前已经实现了类c语言的文法编辑与检查、词法分析、语法分析、语义处理的过程展示，系统功能结构如图1所示。系统界面布局一致、操作简便，采用单步分析展示每个分析步骤的分析图、表的利用和变化情况，便于观察和分析编译过程，也提供一次性分析。图1过程可视化编译系统功能结构图LL(1)语法分析语法编辑与检查预测分析表的生成First-Follow集的生成语法分析LR(0)语法分析分析表的生成项目集的生成语法分析语法编辑与检查可视化编译系统文件编辑新建打开保存另存为词法分析词法分析状态转换图生成状态转换矩阵生成词法编辑与检查语法分析算符优先语法分析语法编辑与检查优先分析表的生成firstVT-followVT集的生成语法分析语义处理语义分析代码生成错误处理在此基础上，拟在计算机科学与软件学院本科生中开展系统功能测试，程序代码完善，软件结构调整和功能补充等工作，要求开发环境、系统架构、界面风格与原有系统保持一致。实验内容作为《编译原理实验》课的扩展实验，实验小组成员由2009级本科生自愿报名参加，四人为一小组，小组组成情况表见附录一。组长负责任务的分配与完成情况记录等日常工作，实验情况记录表见附录二。要求每个成员在每项工作中都有独立负责的任务，小组内各成员要充分讨论与合作，共同提高。一、已有功能测试测试记录见附录三。测试内容如下：1.文件部分(1)用户能否通过新建和打开按钮创建新的文件窗体？（用打开按钮创建新的文件窗体合理吗）(2)打开按钮创建的窗体名称是否是文本文件的名字?(3)能否进行文件的编辑操作，如剪切，复制，粘贴，撤销，恢复等。2.词法文法分析部分(1)点击“示例文法”按钮能够将数据库中词法文法读出？(2)能否完成数据库的保存，删除，修改操作？(3)保存文法能否完成文法的检查并提示错误？选择错误的行能否完成在文法中实现行的定位？(4)能否通过浏览添加文法？(5)通过自拟文法添加终结符和非终结符时如果有重复字符是否会提示。如终结符输入“a，b，a”将会出现“终结符中存在重复字符，是自动删除重复字符还是手动删除？“的提示框。(6)点击“添加产生式“能否完成产生式的检测并提示错误，如果没有错误将产生式添加到文法显示框内。例如：对于终结符为：a，b。非终结符为：S，A；如果输入产生式为B-a将会提示产生式左部不是非终结符，并将焦点定位到左部框内。如果输入产生式为S-Aa,将会提示产生式不是右线性文法，并将焦点定位到右部框内。如果输入产生式为S-aA则会提示产生是错误。因为文法规定在右部出现的非终结符要用标记，非终结符要用空格隔开。(7)状态转换矩阵的生成，状态转换图的生成是否正确。3.词法分析部分(1)选择单步分析时结果是否正确，是否实现了状态矩阵相应位置的变色处理。(2)选择一次分析时结果是否在正确。4.LR(0)文法分析(1)读出的文法是否跟选择的词法相关的文法。(2)能否完成数据库的保存，删除，修改操作？(3)保存文法能否完成文法的检查并提示错误？(4)项目集簇的生成和分析表的生成是否正确？5.LR(0)语法分析(1)选择单步分析时结果是否正确，是否实现了状态矩阵相应位置的变色处理。(2)选择一次分析时结果是否在正确。(3)在单步分析和一次分析过程中的语义处理操作是否正确。6.算符优先文法分析(1)示例文法是否读出的是bin目录下的算符文法文件夹内所有的以‘wenfa‘开头的文本文件。（bin目录下存示例文法合理吗？）(2)能否完成算符文法文件夹内的文本文件的删除？(3)能否将文本文件保存到算符文法文件夹内，保存文法时能否完成文法的检查（主要是检查是否有两个非终结符相连的情形。如果有提示文法错误不予保存。否则进行保存）？(4)文法必须进行保存后才可以进行first-follow集的生成。检查生成的first-follow集是否正确？(5)检查生成的优先矩阵是否正确？7.算符优先语法分析(1)完成语法单步分析操作，结果是否正确？(2)完成一次分析操作，结果是否正确？8.LL(1)文法分析(1)点击“示例文法”按钮能够将数据库中LL(1)语法中与选择的词法文法相关的语法读出？(2)能否完成数据库的保存，删除，修改操作？(3)保存文法能否完成文法的检查并提示错误？(4)能否通过浏览添加文法？(5)通过自拟文法添加终结符和非终结符时如果有重复字符是否会提示。如终结符输入“a，b，a”将会出现“终结符中存在重复字符，是自动删除重复字符还是手动删除？“的提示框。(6)点击“添加产生式“能否完成产生式的检测并提示错误，如果没有错误将产生式添加到文法显示框内。例如：对于终结符为：a，b。非终结符为：S，A；如果输入产生式为B-a将会提示产生式左部不是非终结符，并将焦点定位到左部框内。如果输入产生式为S-aA则会提示产生式错误。因为文法规定在右部出现的非终结符要用标记，非终结符要用空格隔开。(7)first-follow的生成是否正确。并完成LL(1)文法的检查判断其是否属于LL(1)文法。(8)分析表的生成是否正确。9.LL(1)语法分析(1)完成语法单步分析操作，结果是否正确？(2)完成一次分析操作，结果是否正确？二、程序代码完善1、为程序中的主要类及其属性、函数、常量、变量，界面中的窗口、控件等制定命名规则。2、对所有代码进行编程风格检查，主要包括缩进格式、必要注释等。3、提取主要数据结构和核心算法代码，进行适当描述（合理源码、伪码、流程图等），对原有界面调整以进行展示。三、软件结构调整1、对软件进行界面层、算法实现层、数据处理层分层检查，对不符合三层结构的部分进行调整。2、提取软件中可复用的代码，形成可复用模块。3、对展示效果有待改进的界面进行调整。四、功能补充1、LR分析中增加SLR（1）和LR（1）分析，帮助用户比较两者的异同。2增加语法制导翻译模块，展示语法分析、语义处理、中间代码生成的过程和阶段结果。3增加局部优化功能，对输入程序划分基本块，并在块内进行优化。（1）基本块划分方法所谓基本块是指程序的一组顺序执行的语句序列，其中只有一个入口和一个出口，入口就是其中的第一个语句，出口就是其中的最后一个语句。中间代码一级的基本块划分方法如下：（a）确定各基本块的入口，其规则为（i）程序的第一个四元式；（ii）由控制转移所转向的四元式；（iii）紧跟在条件转移四元式之后的四元式。（b）从每一个入口四元式开始，分别确定各基本块应包含的四元式。即每一入口以及此入口到下一入口之间的四元式（不包含下一入口），或者直至停机四元式为止的所有四元式都属于相应的基本块。（c）执行上述第（1）步和第（2）步之后，凡未包含在任何基本块中的，都是控制不可能达到的四元式，它们绝不会被执行，故可以删除。对基本块进行分析的一种有效数据结构是无回路有向图，简称DAG。由于DAG能够给出基本块中每一运算结果用于块中其后续运算的一个完整描述，所以为每一个四元式序列形式的基本块构造一DAG，对基本块的后续优化是一个好方法。有关构造DAG的过程，详见课本296页。由基本块构造相应的DAG图，算法如下，其中函数NODE(A)的功能就是以A（结点的标记或附加标识符）查找相应的结点：如果DAG中此时尚无以A标记的结点，则NODE(A)无定义（例如可令NODE(A)=null）；否则便回送新近建立的与A相关联的结点之编号ni。for(i=0;iQlistLength;i++)/*QlistLenth之值为基本块中四元式的个数*/{取出第i四元式Qi；if(NODE(B)==NULL){建立一个以B为标记的叶结点，其编号为NODE(B)；switch(Qi){case0:NODE(B)=n;break;case1:if(NODE(B)是常数为标记的叶结点){执行P=opB;/*合并已知量*/if(NODE(B)是处理Qi时新建立的结点)删除NODE(B)；if(NODE(P)==NULL){建立NODE(P)；NODE(P)=n;}}else{if(DAG中已有以NODE(B)为惟一后继且标记为op的结点/*查找公共子表达式*/)令已有结点为n；else建立新结点n;}/*endif(NODE(B)是常数为标记的叶结点)*/break;case2:if(NODE(C)==NULL){构造以C为标记的新结点；if(NODE(B)为常数结点&&NODE(C)为常数结点){执行P=BopC;/*合并已知量*/if(NODE(B)或NODE(C)是处理Qi时新建立的结点)删除之；if(NODE(P)==NULL){建立NODE(P);NODE(P)=n;}break;}}elseif(DAG中已有以NODE(B)和NODE(C)分别为左、右后继，且标记为op的结点)令已有结点为nelse建立新结点n；/*endif(NODE(B)为常数结点&&NODE(C)为常数结点)*/break;}if(NODE(A)==NULL){把A附加到结点n；NODE(A)=n;}else{从NODE(A)的附加标识符集中将A删去；把A附加到结点n;NODE(A)=n;}/*endif(NODE(A)==NULL)*/}/*endif*/}/*endforloop*/构造DAG的过程中，要根据结点的标记查出相应结点的编号及相应结点的关系，这就需要设置一张信息记录表，如下表所示。Node（结点）Token（标记）Leftson（左后继）Rightson（右后继）N1N2N3……测试用例：下面是求最大公因子的四元式程序，将其划分为基本块。(1)readX(2)readY(3)R=XmodY(4)ifR==0goto(8)(5)X=Y(6)Y=R(7)goto(3)(8)writeY(9)halt（2）基本块内的优化在一个基本块内，常用的优化技术有三种：合并常量、删除公共子表达式和删除无用赋值。（a）合并常量所谓合并常量是指在编译时就计算表达式中的常量运算，然后利用计算所得值去替换表达式中出现的所有这种常量运算，而不必等到程序运行时再计算。（b）删除公共子表达式如果一个表达式E多次出现，每次出现它的值都不变，则称E为公共子表达式。对于公共子表达式，我们可以避免对它的重复计算，这称为删除公共子表达式。（c）删除无用赋值在一个基本块内，合并常量和删除公共子表达式比较容易实现，而删除无用赋值实现起来要困难一些。这是因为，如果孤立的考虑一个基本块常常不能确定一个赋值是否真的无用。无用赋值有以下三种情形：（i）对某变量X赋值后，X值在整个程序中未被引用，则变量X的赋值为无用赋值。（ii）对某变量X赋值后，在X值被引用前又对X重新赋值，则前一次赋值为无用赋值。（iii）对某变量X进行递归赋值，如X=X+Y，而且X值在程序中仅在此递归运算中被引用，则此递归赋值为无用赋值。利用DAG进行基本块优化的基本思想是：首先顺序对一个基本块内的所有四元式构造一个DAG，然后再按照构造结点的顺序将DAG还原成四元式序列。构造DAG的同时已经作了局部优化，所以最后得到的四元式序列也进行了相应的优化。（1）合并常量：如果运算对象是常量，则不生成该结点值得内部结点，而是执行该运算，将计算结果生成一个叶结点。（2）删除公共子表达式：对于具有公共子表达式的所有四元式，它只产生一个