编译原理实验指导书(新)

编译原理实验指导书75编译原理实验指导书周鹏杨亚会梅琴赵榕计算机技术实验中心编译原理实验指导书76前言编译原理是计算机科学与技术、软件工程等专业的主干课和必修课，由于这门课程相对抽象且内容较复杂，一直是比较难学的一门课程。在编译原理的学习过程中，实验非常重要，只有通过上机实验，才能使学生对比较抽象的课程内容产生一个具体的感性认识。但是，目前国内市场上很少有较详细且比较适合我院实际的实验指导书，为此，我们特编了这份指导书，希望能对我院的《编译原理》教学工作有所帮助。本书实验环境主要为C环境(由于兼容性问题，建议使用Turboc2.0)及一个词法分析器自动生成工具FLEX和一个语法分析器自动生成工具BISON。书中给出的参考源程序也是C源程序，但由于实验者熟悉精通的语言工具不尽相同，因而强求采用统一的编程语言编程是不现实的。实验者在掌握了编译程序各个阶段的功能和原理之后，不难借助使用其他自己熟悉的语言实现相关功能。实验者在实验过程中应该侧重写出自己在算法分析、设计思路、实现功能或程序代码等方面的特色，写出设计和实现过程中遭遇到的难点和解决办法，可以不拘泥于实验指导给出的参考性设计思路，尽可能在深度和广度上加以拓展。只有这种各具特色的实验报告，才将更有利于体现实验者在创新思维和动手能力上的差异。通过这些实验，能使学生对这些部份的工作机理有一个详细的了解，达到“知其然，且知其所以然”的目的。并可在C环境下对自动生成工具生成的词法、语法分析器进行编译调试。由于手工生成词法和语法分析器的工作量太大，在实际中常用自动生成工具来完成之。这些工具中最著名的当属贝尔实验室的词法分析器生成工具LEX和语法分析器生成工具YACC。它们现已成为UNIX的标准应用程序同UNIX一起发行。与此同时GNU推出与LEX完全兼容的FLEX，与YACC完全兼容的BISON。这两个程序都在Internet上以源代码的形式免费发行，所以很容易在其它操作系统下重新编译安装。我们实验采用的就是fordos的FLEX和BISON。本书有关的编译工具及其源程序例子，可到BISON的网站上下载。关于FLEX和BISON的用法简介，参见附录，如需更详细的介绍，请参阅编译工具中帮助文件。关于实验学时和安排，任课教师可根据实际情况，选做其中的一部份。由于这门课实验难度较大，所以希望任课教师在实验前安排好学生的预习工作，在上机前要求学生写好实验预习报告。本书中c程序均在Turboc2.0下调试通过.LEX和YACC源程序均在FLEX和BISON下调试通过.由于编者水平有限，本书中必然存在着不少缺点，在此恳请大家给予批评和指正，我们将尽力纠正。在此特对关心支持编写本书的院系领导表示感谢。本书中关于LEX和YACC的部份大量参考引用了何炎祥老师主编，华中理工大学出版社出版的《编译原理》一书，在此表示衷心的感谢。周鹏杨亚会梅琴赵榕2006年8月编译原理实验指导书77目录实验一词法分析器设计实验..............................................78实验二熟悉FLEX使用方法...............................................87实验三用FLEX自动生成PL/0词法分析器..................................88实验四用递归下降法分析表达式实验......................................95实验五用算符优先法分析表达式实验......................................98实验六利用BISON生成逆波兰表示计算器.................................102实验七利用BISON生成中缀表示计算器...................................103附录一词法分析器生成工具FLEX简介...................................104附录二语法分析器生成工具YACC简介...................................111参考文献...............................................................117《编译原理》实验指导书实验一词法分析器设计实验【实验目的】1．掌握生成词法分析器的方法，加深对词法分析原理的理解。2．掌握设计、编制并调试词法分析程序的思想和方法。3．本实验是高级语言程序设计、数据结构和编译原理中词法分析原理等知识的综合。【实验性质】综合性实验（学时数：4H）【实验内容及要求】1．选择一种熟悉的高级语言（如C语言，C++，VB或VC等），设计、编写、调试一个词法分析子程序。2．待分析的源程序为一个简单的C语言程序，如下所示：main(){intx,a,b;floaty,c,d;x=a+b;y=c/d;if(xy)x=10;elsey=100;}将该源程序的源文件经词法分析后输出以二元组形式表示的单词符号序列。3．编写的程序具有一定的查错能力。提交的实验报告中要有实验名称、实验目的、实验内容、实验程序清单、调试过程和运行结果，程序的主要部分做出功能说明，并有实验收获体会或改进意见等内容。4．实验前请仔细阅读实验预习提示，提示中程序仅供参考。5．本实验建议学时数为4学时。【实验预习提示】1.词法分析器的功能和输出格式词法分析器的功能是输入以字符串表示的源程序，输出单词符号或单词符号序列。词法分析器的单词符号常常表示成以下的二元组(单词的种别码，单词符号的属性值)。本实验中，采用的是一符一种种别码的方式。2.调试程序文法的EBNF（扩展巴科斯范式）表示如下程序::=main()语句串语句串::=语句{；语句}语句::=赋值语句|条件语句|循环语句赋值语句::=变量=表达式条件语句::=if条件then语句循环语句::=while条件语句串条件::=表达式关系运算符表达式编译原理实验指导书79表达式::=项{+项|—项}项::=因子{*因子|/因子}因子::=变量|无符号整数|表达式无符号整数::=数字{数字}变量::=标识符标识符::=字母{字母|数字|下划线}关系运算符::=||=|=|==|!=字母::=A|B|C|……|Z|a|b|c|……|z(要求不区分大小写)数字::=0|1|2|3|4|5|6|7|8|93.“超前搜索”方法词法分析时，常常会用到超前搜索方法。如当前待分析字符串为“a+”,当前字符为’’，此时，分析器倒底是将其分析为大于关系运算符还是大于等于关系运算符呢？显然，只有知道下一个字符是什么才能下结论。于是分析器读入下一个字符’+’，这时可知应将’’解释为大于运算符。但此时，超前读了一个字符’+’，所以要回退一个字符，词法分析器才能正常运行。在分析标识符，无符号整数等时也有类似情况。4.词法分析程序主程序的算法思想算法的基本思想是根据扫描到单词符号的第一个字符的种类，拼写出相应的单词符号，其实现的基本任务是从字符串表示的源程序中识别出相应的具有独立意义的单词符号。主程序示意图如图1.1所示。图1.1词法分析主程序示意图其中设置初始值包括两个方面：（1）关键字表的初值关键字作为特殊标识符处理，把它们预先安排在一张表中，称这张表为关键字表，当扫描程序识别出标识符时，查关键字表，若能查找到匹配的单词，则该单词是关键字，否则为一般标识符。关键字表为一个字符串数组，其描述为：char*KEY_WORDS[8]={“main”,”int”,”char”,”if”,”else”,”while”,”for”};（2）程序中需要用到的主要变量为syn，token和sum。5.参考部分源程序[1][1]globals.h/*本头文件定义分析器需要的一些数据结构和宏等*/#ifndef_GLOBALS_H初始化并设置初始值调用扫描子程序输出单词二元组输入串结束了吗？YN结束编译原理实验指导书80#define_GLOBALS_H#includestdio.h#includestdlib.h#includestring.h/*单词种别码*/#define_SYN_MAIN1#define_SYN_INT2#define_SYN_CHAR3#define_SYN_IF4#define_SYN_ELSE5#define_SYN_FOR6#define_SYN_WHILE7/*以上为关键字的单词种别码*/#define_SYN_ID10/*标识符的单词种别码*/#define_SYN_NUM11/*整数的单词种别码*/#define_SYN_PLUS13/*算术运算符“+”的单词种别码*/#define_SYN_MINUS14/*算术运算符“-”的单词种别码*/#define_SYN_TIMES15/*算术运算符“*”的单词种别码*/#define_SYN_DIVIDE16/*算术运算符“/”的单词种别码*/#define_SYN_ASSIGN17/*=*/#define_SYN_SEMICOLON18/*;*/#define_SYN_LT20/**/#define_SYN_NE21/*！=*/#define_SYN_LE22/*=*/#define_SYN_LG23/**/#define_SYN_ME24/*=*/#define_SYN_EQ25/*=*/#define_SYN_LPAREN28/*(*/#define_SYN_RPAREN29/*)*/#define_SYN_OVER0/*#即源程序结束标志*/#defineMAXLENGTH255/*一行允许的字符个数*/unionWORDCONTENT{/*存放单词内容的联合*/charT1[MAXLENGTH];intT2;charT3;};typedefstructWORD{/*单词二元组*/intsyn;unionWORDCONTENTvalue;}WORD;#endif编译原理实验指导书81[2]scan.h/*本头文件定义词法分析器的接口*/#ifndef_SCAN_H#define_SCAN_H#define_TAB_LEGNTH4/*一个TAB占用的空格数*/#define_KEY_WORD_ENDwaitingforexpanding/*关键字结束标志*/voidScaner(void);/*函数scaner得到源程序里的下一个单词符号*/#endif[3]Symbol.c#includebasedata.h#includesymbol.h#includeconio.h#includestring.h#includectype.hchar*WORD[WORDLEN]={BEGIN,CALL,CONST,DO,END,IF,ODD,PROCEDURE,READ,THEN,VAR,WHILE,WRITE};//保留字字符串表,用于将保留字种别码转为字符串输出SYMBOLWSYM[WORDLEN]={BEGINSYM,CALLSYM,CONSTSYM,DOSYM,ENDSYM,IFSYM,ODDSYM,PROCSYM,READSYM,THENSYM,VARSYM,WHILESYM,WRITESYM};//保留字种别码表char*SNAME[SYMBOLNUM]={NOL,IDENT,NUMBER,PLUS,MINUS,TIMES,SLASH,ODDSYM,EQL,NEQ,LSS,LEQ,GTR,GEQ,LPAREN,RPAREN,COMMA,SEMICOLON,PERIOD,BECOMES,BEGINSYM,E