编译原理实验指导.doc
【精品文档】如有侵权,请联系网站删除,仅供学习与交流编译原理实验指导.精品文档.编译原理实验指导书主编:徐静 李娜 信息与电气工程学院2010年3月概 述一、本课程实验的目的和任务 编译原理是一门实践性很强的课程,只有通过实践,才能真正掌握。实际的编译程序是十分复杂的,有时由多达十几万条指令组成。为此,编译原理的实践教学,采用简化编译过程的办法,选择最关键的3个环节词法分析、语法分析(包括语义处理、产生无优化的目标指令)、连接调试,进行编程和调试训练。每个环节作为一个实践课题。先分别编程调试,再连接在一起总调。 二、实验方法 任何一个实用的高级语言,其语法都比较复杂,如选其作为源语言,很难实践全过程。故本实验将定义一个简化的语言 C语言的一个子集作为源语言,设计调试出它的编译程序。前后贯穿这一条主线进行实践。每次都可利用课余时间编程,利用上机时间进行输入和调试。 三、实验报告的规范和要求 每个实验完成后写出实验报告。实验报告的内容包括如下内容:一、 实验目的二、 程序设计时采用的算法和方法三、 输入的源程序四、 词法分析程序清单和输出结果。 五、 心得体会实验一 词法分析一、实验目的: (1)通过设计编制调试一个具体的词法分析程序,理解词法分析在编译程序中的作用。(2)加深对有穷自动机模型的理解。(3)掌握词法分析程序的实现方法和技术。(4)用C语言对一个简单语言的子集编制一个一遍扫描的程序,以加深对编译原理的理解,掌握编译程序的实现方法和技术。编制一个读单词过程,从输入的源程序中,识别出各个具有独立意义的单词,即基本保留字、标识符、常数、运算符、分隔符五大类。并依次输出各个单词的内部编码及单词符号自身值。(遇到错误时可显示“Error”,然后跳过错误部分继续显示) 。二、实验预习提示 1. 词法分析器的功能和输出格式词法分析器的功能是输入源程序,输出单词符号。词法分析器的单词符号常常表示成以下的二元式(单词种别码,单词符号的属性值)。本实验中,采用的是一类符号一种别码的方式。2. 单词的BNF表示<标识符> <字母><字母数字串><字母数字串><字母><字母数字串>|<数字> <字母数字串>|<下划线><字母数字串>|<无符号整数> <数字> <数字串><数字串> <数字><数字串> |<加法运算符> +<减法运算符> -<大于关系运算符> ><大于等于关系运算符> >=3. “超前搜索”方法词法分析时,常常会用到超前搜索方法。如当前待分析字符串为“a>+”,当前字符为“ >”,此时,分析器到底是将其分析为大于关系运算符还是大于等于关系运算符呢?显然,只有知道下一个字符是什么才能下结论。于是分析器读入下一个字符“+”,这时可知应将“ >”解释为大于运算符。但此时,超前读了一个字符“+”,所以要回退一个字符,词法分析器才能正常运行。在分析标识符,无符号整数等时也有类似情况。4. 模块结构YNYN调用返回输出缓冲区中是否还有字符取单词扫描一个字符结束主函数main()输入文件名判断能否打开文件缓冲区扫描一个字符三、实验过程和指导: (一)准备: 1.阅读课本有关章节,明确语言的语法,写出基本保留字、标识符、常数、运算符、分隔符和程序例。2.初步编制好程序。3.准备多组测试数据。(二)上课上机: 将源代码拷贝到机上调试,发现错误,再修改完善。第二次上机调试通过。(三)程序要求:程序输入/输出示例:如源程序为C语言。输入如下一段:main( ) int a,b;a = 10; b = a + 20;要求输出如下图。(2,”main”)(5,”(“)(5,”)“)(5,”“)(1,”int”)(2,”a”)(5,”,”)(2,”b”)(5,”;”)(2,”a”)(4,”=”)(3,”10”)(5,”;”)(2,”b”)(4,”=”)(2,”a”)(4,”+”)(3,”20”)(5,”;”)(5,”“)要求:1. 识别保留字:if、int、for、while、do、return、break、continue;单词种别码为1。2. 其他的都识别为标识符;单词种别码为2。3. 常数为无符号整型数;单词种别码为3。4. 运算符包括:+、-、*、/、=、<、=、<=、!= ;单词种别码为4。5. 分隔符包括:,、;、(、); 单词种别码为5。以上为参考,具体可自行增删。(四)程序思路(仅供参考):这里以开始定义的C语言子集的源程序作为词法分析程序的输入数据。在词法分析中,自文件头开始扫描源程序字符,一旦发现符合“单词”定义的源程序字符串时,将它翻译成固定长度的单词内部表示,并查填适当的信息表。经过词法分析后,源程序字符串(源程序的外部表示)被翻译成具有等长信息的单词串(源程序的内部表示),并产生两个表格:常数表和标识符表,它们分别包含了源程序中的所有常数和所有标识符。0. 定义部分:定义常量、变量、数据结构。1. 初始化:从文件将源程序全部输入到字符缓冲区中。2. 取单词前:去掉多余空白。3. 取单词后:去掉多余空白。4. 取单词:读出单词的每一个字符,组成单词,分析类型。(关键是如何判断取单词结束?取到的单词是什么类型的单词?)5. 显示结果。(五)练习该实验的目的和思路:程序开始变得复杂起来,可能是大家目前编过的程序中最复杂的,但相对于以后的程序来说还是简单的。因此要认真把握这个过渡期的练习。本实验和以后的实验相关。通过练习,掌握对字符进行灵活处理的方法。(六)为了能设计好程序,注意以下事情:1. 模块设计:将程序分成合理的多个模块(函数),每个模块做具体的同一事情。2. 写出(画出)设计方案:模块关系简图、流程图、全局变量、函数接口等。3. 编程时注意编程风格:空行的使用、注释的使用、缩进的使用等。 (七)程序框架:#include<stdio.h>#include<string.h>char program80,token8; /*数组program存放的为源程序所有字符,数组token为存放的单词自身字符串*/char ch;int syn,p,m,n,row; /*syn为单词种别码*/long int num; /*sum为整型常数*/char *key 8= "if","int","for","while","do","return","break","continue" /*保留字*/void main( ) p=0; row=1; printf("n please input string:n"); do /*从文件将源程序全部输入到字符缓冲区中*/ ch=getchar(); programp+=ch; while(ch!='#'); p=0; do scaner( ); switch(syn) case 3: printf("n(%d, %d)",syn,num);break; case -1: printf("nFOUND ERROR IN ROW %d",row);break; case -2: row=row+;break; default: printf("n(%d, %s)",syn,token);break; while(syn!=0); getch( );scaner( ) for(n=0;n<8;n+) tokenn=NULL; m=0; ch=programp+; while(ch=' ') ch=programp+; /*分类判断1.识别标识符(包括保留字)。建议:关键字作为特殊标识符处理,把它们预先安排在一张表格中(保留字表),当扫描程序识别标识符时,查关键字,否则为一般标识符。注意:识别保留字:if、int、for、while、do、return、break、continue;单词种别码为1。其他的都识别为标识符;单词种别码为2。2.识别常数。注意:常数的有效范围,如果产生溢出则设置syn的值,与主函数的代码呼应。case 3: printf("n(%d, %d)",syn,num);break;case -1: printf("nFOUND ERROR IN ROW %d",row);break;常数为无符号整型数;单词种别码为3。3.识别运算符。注意:区分两个运算符<和<=。 (switch语句)运算符包括:+、-、*、/、=、<、=、<=、!= 单词种别码为4。4.识别界符。分隔符包括:,、;、(、) 单词种别码为5。 (switch语句)实验二 递归下降分析法一、实验目的: 根据某一文法编制调试递归下降分析程序,以便对任意输入的符号串进行分析。本次实验的目的主要是加深对递归下降分析法的理解。二、实验预习提示 1递归下降分析法的功能词法分析器的功能是利用函数之间的递归调用模拟语法树自上而下的构造过程。2递归下降分析法的前提改造文法:消除二义性、消除左递归、提取左因子,判断是否为LL(1)文法。3递归下降分析法实验设计思想及算法为G的每个非终结符号U构造一个递归过程,不妨命名为U。U的产生式的右边指出这个过程的代码结构:(1) 若是终结符号,则和向前看符号对照,若匹配则向前进一个符号;否则出错。(2) 若是非终结符号,则调用与此非终结符对应的过程。当A的右部有多个产生式时,可用选择结构实现。具体为: 对于每个非终结符号U u1|u2|un处理的方法如下:U( )ch=当前符号;if(ch可能是u1字的开头) 处理u1的程序部分;else if(ch可能是u2字的开头) 处理u2的程序部分;else error(); 对于每个右部ux1x2xn的处理架构如下:处理x1的程序;处理x2的程序;处理xn的程序; 如果右部为空,则不处理。 对于右部中的每个符号xi。A 如果xi为终结符号:if(xi= = 当前的符号) NextChar(); Return; else出错处理B如果xi为非终结符号,直接调用相应的过程xi( )。说明: NextChar为前进一个字符函数。三、实验过程和指导: (一)准备: 1.阅读课本有关章节,2.考虑好设计方案;3.设计出模块结构、测试数据,初步编制好程序。(二)上课上机: 将源代码拷贝到机上调试,发现错误,再修改完善。第二次上机调试通过。(三)程序要求:程序输入/输出示例: 对下列文法,用递归下降分析法对任意输入的符号串进行分析: (1)ETG(2)G+TG|TG(3)G(4)TFS(5)S*FS|/FS(6)S(7)F(E)(8)Fi输出的格式如下:(1) 递归下降分析程序,编制人:姓名,学号,班级(2) 输入一以#结束的符号串(包括+*/()i#):在此位置输入符号串例如:i+i*i# (3) 输出结果:i+i*i#为合法符号串 备注:输入一符号串如i+i*#,要求输出为“非法的符号串”。注意:1.表达式中允许使用运算符(+-*/)、分割符(括号)、字符I,结束符#; 2.如果遇到错误的表达式,应输出错误提示信息(该信息越详细越好);3.对学有余力的同学,可以详细的输出推导的过程,即详细列出每一步使用的产生式。(四)程序思路(仅供参考):0. 定义部分:定义常量、变量、数据结构。1. 初始化:从文件将输入符号串输入到字符缓冲区中。2. 利用递归下降分析法分析,对每个非终结符编写函数,在主函数中调用文法开始符号的函数。(五)练习该实验的目的和思路: 程序开始变得复杂起来,需要利用到程序设计语言的知识和大量编程技巧,递归下降分析法是一种较实用的分析法,通过这个练习可大大提高软件开发能力。通过练习,掌握函数间相互调用的方法。(六)为了能设计好程序,注意以下事情:1. 模块设计:将程序分成合理的多个模块(函数),每个模块做具体的同一事情。2. 写出(画出)设计方案:模块关系简图、流程图、全局变量、函数接口等。3. 编程时注意编程风格:空行的使用、注释的使用、缩进的使用等。实验三 LL(1)分析法一、实验目的: 根据某一文法编制调试LL(1)分析程序,以便对任意输入的符号串进行分析。本次实验的目的主要是加深对预测分析LL(1)分析法的理解。二、实验预习提示 1、LL(1)分析法的功能LL(1)分析法的功能是利用LL(1)控制程序根据显示栈栈顶内容、向前看符号以及LL(1)分析表,对输入符号串自上而下的分析过程。2、LL(1)分析法的前提改造文法:消除二义性、消除左递归、提取左因子,判断是否为LL(1)文法,3、LL(1)分析法实验设计思想及算法三、实验过程和指导: (一)准备: 1. 阅读课本有关章节。2. 考虑好设计方案。3. 设计出模块结构、测试数据,初步编制好程序。(二)上课上机: 将源代码拷贝到机上调试,发现错误,再修改完善。第二次上机调试通过。(三)程序要求:程序输入/输出示例: 对下列文法,用LL(1)分析法对任意输入的符号串进行分析: (1)ETG(2)G+TG|TG(3)G(4)TFS(5)S*FS|/FS(6)S(7)F(E)(8)Fi输出的格式如下:(1) LL(1)分析程序,编制人:姓名,学号,班级(2) 输入一以#结束的符号串(包括+*/()i#):在此位置输入符号串 (3) 输出过程如下: 步骤分析栈剩余输入串所用产生式1Ei+i*i#ETG (4) 输入符号串为非法符号串(或者为合法符号串)。 备注:(1) 在“所用产生式”一列中如果对应有推导则写出所用产生式;如果为匹配终结符则写明匹配的终结符;如分析异常出错则写为“分析出错”;若成功结束则写为“分析成功”。(2) 在此位置输入符号串为用户自行输入的符号串。(3) 上述描述的输出过程只是其中一部分的。 注意:1. 表达式中允许使用运算符(+-*/)、分割符(括号)、字符i,结束符#; 2. 如果遇到错误的表达式,应输出错误提示信息(该信息越详细越好);3. 对学有余力的同学,测试用的表达式事先放在文本文件中,一行存放一个表达式,同时以分号分割。同时将预期的输出结果写在另一个文本文件中,以便和输出进行对照;(四)程序思路(仅供参考):模块结构:(1)定义部分:定义常量、变量、数据结构。(2)初始化:设立LL(1)分析表、初始化变量空间(包括堆栈、结构体、数组、临时变量等);(3)控制部分:从键盘输入一个表达式符号串;(4)利用LL(1)分析算法进行表达式处理:根据LL(1)分析表对表达式符号串进行堆栈(或其他)操作,输出分析结果,如果遇到错误则显示错误信息。(五)练习该实验的目的和思路: 程序相当复杂,需要利用到大量的编译原理,也用到了大量编程技巧和数据结构,通过这个练习可大大提高软件开发能力。(六)为了能设计好程序,注意以下事情:1.模块设计:将程序分成合理的多个模块(函数),每个模块做具体的同一事情。2.写出(画出)设计方案:模块关系简图、流程图、全局变量、函数接口等。3.编程时注意编程风格:空行的使用、注释的使用、缩进的使用等。实验四 逆波兰式的产生与计算一、实验目的: 将非后缀式用来表示的算术表达式转换为用逆波兰式来表示的算术表达式,并计算用逆波兰式来表示的算术表达式的值。二、实验预习提示 1逆波兰式定义将运算对象写在前面,而把运算符号写在后面。用这种表示法表示的表达式也称做后缀式。逆波兰式的特点在于运算对象顺序不变,运算符号位置反映运算顺序。采用逆波兰式可以很好的表示简单算术表达式,其优点在于易于计算机处理表达式。2产生逆波兰式的前提中缀算术表达式3逆波兰式生成的实验设计思想及算法sym=当前输入符号否是是是处理将栈顶运算符弹出,且输出输入一个中缀式表示的简单运算表达式#入栈2sym是数字吗?栈顶运算符优先级低于sym吗?栈顶运算符与sym优先级相等吗?栈顶运算符优先级高于sym吗?对数字进行处理,形成一个数字串将向前看符号入栈栈顶是(且sym为)吗?程序结束栈顶运算符出栈是否否否否是(1) 首先构造一个运算符栈,此运算符在栈内遵循越往栈顶优先级越高的原则。(2) 读入一个用中缀表示的简单算术表达式,为方便起见,设该简单算术表达式的右端多加上了优先级最低的特殊符号“#”。(3) 从左至右扫描该算术表达式,从第一个字符开始判断,如果该字符是数字,则分析到该数字串的结束并将该数字串直接输出。(4) 如果不是数字,该字符则是运算符,此时需比较优先关系。做法如下:将该字符与运算符栈顶的运算符的优先关系相比较。如果,该字符优先关系高于此运算符栈顶的运算符,则将该运算符入栈。倘若不是的话,则将此运算符栈顶的运算符从栈中弹出,将该字符入栈。(5) 重复上述操作(1)-(2)直至扫描完整个简单算术表达式,确定所有字符都得到正确处理,我们便可以将中缀式表示的简单算术表达式转化为逆波兰表示的简单算术表达式。4逆波兰式计算的实验设计思想及算法读入一个逆波兰算术表达式Sym=当前输入符号Sym是运算符吗?Sym=#将该字符入栈根据运算符的特点从栈顶部取出若干个运算符对象进行该运算将运算结果入栈程序结束否否是是(1) 构造一个栈,存放运算对象。(2) 读入一个用逆波兰式表示的简单算术表达式。(3) 自左至右扫描该简单算术表达式并判断该字符,如果该字符是运算对象,则将该字符入栈。若是运算符,如果此运算符是二目运算符,则将对栈顶部的两个运算对象进行该运算,将运算结果入栈,并且将执行该运算的两个运算对象从栈顶弹出。如果该字符是一目运算符,则对栈顶部的元素实施该运算,将该栈顶部的元素弹出,将运算结果入栈。(4) 重复上述操作直至扫描完整个简单算术表达式的逆波兰式,确定所有字符都得到正确处理,我们便可以求出该简单算术表达式的值。三、实验过程和指导: (一)准备: 1.阅读课本有关章节。2.考虑好设计方案。3.设计出模块结构、测试数据,初步编制好程序。(二)上课上机: 将源代码拷贝到机上调试,发现错误,再修改完善。第二次上机调试通过。(三)程序要求:程序输入/输出示例: 输出的格式如下:(1) 逆波兰式的生成及计算程序,编制人:姓名,学号,班级(2) 输入一以#结束的中缀表达式(包括+*/()数字#):在此位置输入符号串如(28+68)*2# (3) 逆波兰式为:28&68+2* (4) 逆波兰式28&68+2*计算结果为192备注:(1) 在生成的逆波兰式中如果两个数相连则用&分隔,如28和68,中间用&分隔;(2) 在此位置输入符号串为用户自行输入的符号串。 注意:1. 表达式中允许使用运算符(+-*/)、分割符(括号)、数字,结束符#; 2. 如果遇到错误的表达式,应输出错误提示信息(该信息越详细越好);3. 对学有余力的同学,测试用的表达式事先放在文本文件中,一行存放一个表达式,同时以分号分割。同时将预期的输出结果写在另一个文本文件中,以便和输出进行对照;(四)程序思路(仅供参考):模块结构:(1)定义部分:定义常量、变量、数据结构。(2)初始化:设立算符优先分析表、初始化变量空间(包括堆栈、结构体、数组、临时变量等);(3)控制部分:从键盘输入一个表达式符号串;(4)利用算符优先分析算法进行表达式处理:根据算符优先分析表对表达式符号串进行堆栈(或其他)操作,输出分析结果,如果遇到错误则显示错误信息。(5)对生成的逆波兰式进行计算。(五)练习该实验的目的和思路: 程序较复杂,需要利用到程序设计语言的知识和大量编程技巧,逆波兰式的生成是算符优先分析法的应用,是一种较实用的分析法,通过这个练习可大大提高软件开发能力。(六)为了能设计好程序,注意以下事情:1.模块设计:将程序分成合理的多个模块(函数),每个模块做具体的同一事情。2.写出(画出)设计方案:模块关系简图、流程图、全局变量、函数接口等。3.编程时注意编程风格:空行的使用、注释的使用、缩进的使用等。实验五 LR(1)分析法一、实验目的: 构造LR(1)分析程序,利用它进行语法分析,判断给出的符号串是否为该文法识别的句子,了解LR(K)分析方法是严格的从左向右扫描,和自底向上的语法分析方法。二、实验预习提示: 1使用LR(1)的优点:(1) LR分析器能够构造来识别所有能用上下文无关文法写的程序设计语言的结构。(2) LR分析方法是已知的最一般的无回溯移进-归约方法,它能够和其他移进-归约方法一样有效地实现。(3) LR方法能分析的文法类是预测分析法能分析的文法类的真超集。(4) LR分析器能及时察觉语法错误,快到自左向右扫描输入的最大可能。为了使一个文法是LR的,只要保证当句柄出现在栈顶时,自左向右扫描的移进-归约分析器能够及时识别它便足够了。当句柄出现在栈顶时,LR分析器必须要扫描整个栈就可以知道这一点,栈顶的状态符号包含了所需要的一切信息。如果仅知道栈内的文法符号就能确定栈顶是什么句柄。LR分析表的转移函数本质上就是这样的有限自动机。不过,这个有限自动机不需要根据每步动作读栈,因为,如果这个识别句柄的有限自动机自底向上读栈中的文法符号的话,它达到的状态正是这时栈顶的状态符号所表示的状态,所以,LR分析器可以从栈顶的状态确定它需要从栈中了解的一切。2LR分析器由三个部分组成:(1) 总控程序,也可以称为驱动程序。对所有的LR分析器总控程序都是相同的。(2) 分析表或分析函数,不同的文法分析表将不同,同一个文法采用的LR分析器不同时,分析表将不同,分析表又可以分为动作表(ACTION)和状态转换(GOTO)表两个部分,它们都可用二维数组表示。(3) 分析栈,包括文法符号栈和相应的状态栈,它们均是先进后出栈。分析器的动作就是由栈顶状态和当前输入符号所决定。LR分析器结构:输入串XXX#总控程序输出Xn.X1n1.1ACTION表GOTO表其中:SP为栈指针,Si为状态栈,Xi为文法符号栈。状态转换表用GOTOi,X=j表示,规定当栈顶状态为i,遇到当前文法符号为X时应转向状态j,X为终结符或非终结符。ACTIONi,a规定了栈顶状态为i时遇到输入符号a应执行。动作有四种可能:(1) 移进:actioni,a= Sj:状态j移入到状态栈,把a移入到文法符号栈,其中i,j表示状态号。(2) 归约:actioni,a=rk:当在栈顶形成句柄时,则归约为相应的非终结符A,即文法中有A-B的产生式,若B的长度为R(即|B|=R),则从状态栈和文法符号栈中自顶向下去掉R个符号,即栈指针SP减去R,并把A移入文法符号栈内,j=GOTOi,A移进状态栈,其中i为修改指针后的栈顶状态。(3) 接受acc:当归约到文法符号栈中只剩文法的开始符号S时,并且输入符号串已结束即当前输入符是'#',则为分析成功。(4) 报错:当遇到状态栈顶为某一状态下出现不该遇到的文法符号时,则报错,说明输入端不是该文法能接受的符号串。3LL(1)分析法实验设计思想及算法0,#分别入状态栈和符号栈令ip指向w#的第一个符号令s是状态栈栈顶,a是ip所指向的符号栈actions,a=Ssactions,a=reduce分别从栈顶弹出|0|个符号,令s是当前栈顶状态,把a和gotos,A先后推入栈中,输出产生式A->0 ActionA,a=acc把a和s分别压入符号栈和状态栈;使ip前进到下一个字符结束处理是是是否否否三、实验过程和指导: (一)准备: 1.阅读课本有关章节,2.考虑好设计方案;3.设计出模块结构、测试数据,初步编制好程序。(二)上课上机: 将源代码拷贝到机上调试,发现错误,再修改完善。(三)程序要求:程序输入/输出示例: 对下列文法,用LR(1)分析法对任意输入的符号串进行分析: (1)EE+T(2)EET(3)TT*F(4)TT/F(5)F(E)(6)Fi输出的格式如下:(1) LR(1)分析程序,编制人:姓名,学号,班级(2) 输入一以#结束的符号串(包括+*/()i#):在此位置输入符号串 (3) 输出过程如下:步骤状态栈符号栈剩余输入串动作10#i+i*i#移进(4) 输入符号串为非法符号串(或者为合法符号串)备注:A在“所用产生式”一列中如果对应有推导则写出所用产生式;如果为匹配终结符则写明匹配的终结符;如分析异常出错则写为“分析出错”;若成功结束则写为“分析成功”。B 在此位置输入符号串为用户自行输入的符号串。注意:1. 表达式中允许使用运算符(+-*/)、分割符(括号)、字符i、结束符#; 2. 如果遇到错误的表达式,应输出错误提示信息(该信息越详细越好);3. 对学有余力的同学,测试用的表达式事先放在文本文件中,一行存放一个表达式,同时以分号分割。同时将预期的输出结果写在另一个文本文件中,以便和输出进行对照;(四)程序思路(仅供参考):模块结构:(1)定义部分:定义常量、变量、数据结构。(2)初始化:设立LR(1)分析表、初始化变量空间(包括堆栈、结构体、数组、临时变量等);(3)控制部分:从键盘输入一个表达式符号串;(4)利用LR(1)分析算法进行表达式处理:根据LR(1)分析表对表达式符号串进行堆栈(或其他)操作,输出分析结果,如果遇到错误则显示错误信息。(五)练习该实验的目的和思路: 程序相当复杂,需要利用到大量的编译原理,也用到了大量编程技巧和数据结构,通过这个练习可大大提高软件开发能力。(六)为了能设计好程序,注意以下事情:1. 模块设计:将程序分成合理的多个模块(函数),每个模块做具体的同一事情。2. 写出(画出)设计方案:模块关系简图、流程图、全局变量、函数接口等。3. 编程时注意编程风格:空行的使用、注释的使用、缩进的使用等。