编译原理实验指导

编译原理实验指导书主编：徐静李娜信息与电气工程学院2010年3月编译原理实验指导书1概述一、本课程实验的目的和任务编译原理是一门实践性很强的课程，只有通过实践，才能真正掌握。实际的编译程序是十分复杂的，有时由多达十几万条指令组成。为此，编译原理的实践教学，采用简化编译过程的办法，选择最关键的3个环节──词法分析、语法分析（包括语义处理、产生无优化的目标指令）、连接调试，进行编程和调试训练。每个环节作为一个实践课题。先分别编程调试，再连接在一起总调。二、实验方法任何一个实用的高级语言，其语法都比较复杂，如选其作为源语言，很难实践全过程。故本实验将定义一个简化的语言──C语言的一个子集作为源语言，设计调试出它的编译程序。前后贯穿这一条主线进行实践。每次都可利用课余时间编程，利用上机时间进行输入和调试。三、实验报告的规范和要求每个实验完成后写出实验报告。实验报告的内容包括如下内容：一、实验目的二、程序设计时采用的算法和方法三、输入的源程序四、词法分析程序清单和输出结果。五、心得体会编译原理实验指导书2实验一词法分析一、实验目的：（1）通过设计编制调试一个具体的词法分析程序，理解词法分析在编译程序中的作用。（2）加深对有穷自动机模型的理解。（3）掌握词法分析程序的实现方法和技术。（4）用C语言对一个简单语言的子集编制一个一遍扫描的程序，以加深对编译原理的理解，掌握编译程序的实现方法和技术。编制一个读单词过程，从输入的源程序中，识别出各个具有独立意义的单词，即基本保留字、标识符、常数、运算符、分隔符五大类。并依次输出各个单词的内部编码及单词符号自身值。（遇到错误时可显示“Error”，然后跳过错误部分继续显示）。二、实验预习提示1.词法分析器的功能和输出格式词法分析器的功能是输入源程序，输出单词符号。词法分析器的单词符号常常表示成以下的二元式（单词种别码，单词符号的属性值）。本实验中，采用的是一类符号一种别码的方式。2.单词的BNF表示标识符→字母字母数字串字母数字串→字母字母数字串|数字字母数字串|下划线字母数字串|ε无符号整数→数字数字串数字串→数字数字串|ε加法运算符→+减法运算符→-大于关系运算符→大于等于关系运算符→=3.“超前搜索”方法编译原理实验指导书3词法分析时，常常会用到超前搜索方法。如当前待分析字符串为“a+”,当前字符为“”，此时，分析器到底是将其分析为大于关系运算符还是大于等于关系运算符呢？显然，只有知道下一个字符是什么才能下结论。于是分析器读入下一个字符“+”，这时可知应将“”解释为大于运算符。但此时，超前读了一个字符“+”，所以要回退一个字符，词法分析器才能正常运行。在分析标识符，无符号整数等时也有类似情况。4.模块结构三、实验过程和指导：（一）准备：1.阅读课本有关章节，明确语言的语法，写出基本保留字、标识符、常数、运算符、分隔符和程序例。2.初步编制好程序。3.准备多组测试数据。（二）上课上机：YNYN调用返回输出缓冲区中是否还有字符取单词扫描一个字符结束主函数main（）输入文件名判断能否打开文件缓冲区扫描一个字符编译原理实验指导书4将源代码拷贝到机上调试，发现错误，再修改完善。第二次上机调试通过。（三）程序要求：程序输入/输出示例：如源程序为C语言。输入如下一段：main(){inta,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。以上为参考，具体可自行增删。（四）程序思路（仅供参考）：编译原理实验指导书5这里以开始定义的C语言子集的源程序作为词法分析程序的输入数据。在词法分析中，自文件头开始扫描源程序字符，一旦发现符合“单词”定义的源程序字符串时，将它翻译成固定长度的单词内部表示，并查填适当的信息表。经过词法分析后，源程序字符串（源程序的外部表示）被翻译成具有等长信息的单词串（源程序的内部表示），并产生两个表格：常数表和标识符表，它们分别包含了源程序中的所有常数和所有标识符。0.定义部分：定义常量、变量、数据结构。1.初始化：从文件将源程序全部输入到字符缓冲区中。2.取单词前：去掉多余空白。3.取单词后：去掉多余空白。4.取单词：读出单词的每一个字符，组成单词，分析类型。（关键是如何判断取单词结束？取到的单词是什么类型的单词？）5.显示结果。（五）练习该实验的目的和思路：程序开始变得复杂起来，可能是大家目前编过的程序中最复杂的，但相对于以后的程序来说还是简单的。因此要认真把握这个过渡期的练习。本实验和以后的实验相关。通过练习，掌握对字符进行灵活处理的方法。（六）为了能设计好程序，注意以下事情：1.模块设计：将程序分成合理的多个模块（函数），每个模块做具体的同一事情。2.写出（画出）设计方案：模块关系简图、流程图、全局变量、函数接口等。3.编程时注意编程风格：空行的使用、注释的使用、缩进的使用等。编译原理实验指导书6（七）程序框架：#includestdio.h#includestring.hcharprogram[80],token[8];/*数组program存放的为源程序所有字符，数组token为存放的单词自身字符串*/charch;intsyn,p,m,n,row;/*syn为单词种别码*/longintnum;/*sum为整型常数*/char*key[8]={if,int,for,while,do,return,break,continue};/*保留字*/voidmain(){p=0;row=1;printf(\npleaseinputstring:\n);do/*从文件将源程序全部输入到字符缓冲区中*/{ch=getchar();program[p++]=ch;}while(ch!='#');p=0;do{scaner();switch(syn){编译原理实验指导书7case3:printf(\n(%d,%d),syn,num);break;case-1:printf(\nFOUNDERRORINROW%d,row);break;case-2:row=row++;break;default:printf(\n(%d,%s),syn,token);break;}}while(syn!=0);getch();}scaner(){for(n=0;n8;n++)token[n]=NULL;m=0;ch=program[p++];while(ch==''){ch=program[p++];}/*分类判断编译原理实验指导书8*/}4.识别界符。分隔符包括：,、;、{、}、(、)单词种别码为5。（switch语句）3.识别运算符。注意：区分两个运算符和=。（switch语句）运算符包括：+、-、*、/、=、、、=、=、!=单词种别码为4。2.识别常数。注意：常数的有效范围，如果产生溢出则设置syn的值，与主函数的代码呼应。case3:printf(\n(%d,%d),syn,num);break;case-1:printf(\nFOUNDERRORINROW%d,row);break;常数为无符号整型数；单词种别码为3。1.识别标识符（包括保留字）。建议：关键字作为特殊标识符处理，把它们预先安排在一张表格中（保留字表），当扫描程序识别标识符时，查关键字，否则为一般标识符。注意：识别保留字：if、int、for、while、do、return、break、continue；单词种别码为1。其他的都识别为标识符；单词种别码为2。编译原理实验指导书9实验二递归下降分析法一、实验目的：根据某一文法编制调试递归下降分析程序，以便对任意输入的符号串进行分析。本次实验的目的主要是加深对递归下降分析法的理解。二、实验预习提示1．递归下降分析法的功能词法分析器的功能是利用函数之间的递归调用模拟语法树自上而下的构造过程。2．递归下降分析法的前提改造文法：消除二义性、消除左递归、提取左因子，判断是否为LL（1）文法。3．递归下降分析法实验设计思想及算法为G的每个非终结符号U构造一个递归过程，不妨命名为U。U的产生式的右边指出这个过程的代码结构：(1)若是终结符号，则和向前看符号对照，若匹配则向前进一个符号；否则出错。(2)若是非终结符号，则调用与此非终结符对应的过程。当A的右部有多个产生式时，可用选择结构实现。具体为：①对于每个非终结符号U→u1|u2|…|un处理的方法如下：U(){ch=当前符号；if(ch可能是u1字的开头)处理u1的程序部分；elseif(ch可能是u2字的开头)处理u2的程序部分；…elseerror()；}②对于每个右部u→x1x2…xn的处理架构如下：处理x1的程序；处理x2的程序；…编译原理实验指导书10处理xn的程序；③如果右部为空，则不处理。④对于右部中的每个符号xi。A．如果xi为终结符号：if(xi==当前的符号){NextChar()；Return；}else出错处理B．如果xi为非终结符号，直接调用相应的过程xi()。说明：NextChar为前进一个字符函数。三、实验过程和指导：（一）准备：1.阅读课本有关章节，2.考虑好设计方案；3.设计出模块结构、测试数据，初步编制好程序。（二）上课上机：将源代码拷贝到机上调试，发现错误，再修改完善。第二次上机调试通过。（三）程序要求：程序输入/输出示例：对下列文法，用递归下降分析法对任意输入的符号串进行分析：（1）E→TG（2）G→+TG|—TG（3）G→ε（4）T→FS（5）S→*FS|/FS（6）S→ε编译原理实验指导书11（7）F→(E)（8）F→i输出的格式如下：(1)递归下降分析程序，编制人：姓名，学号，班级(2)输入一以#结束的符号串(包括+—*/（）i#)：在此位置输入符号串例如：i+i*i#(3)输出结果：i+i*i#为合法符号串备注：输入一符号串如i+i*#,要求输出为“非法的符号串”。注意：1.表达式中允许使用运算符（+-*/）、分割符（括号）、字符I，结束符#；2.如果遇到错误的表达式，应输出错误提示信息（该信息越详细越好）；3.对学有余力的同学，可以详细的输出推导的过程，即详细列出每一步使用的产生式。（四）程序思路（仅供参考）：0.定义部分：定义常量、变量、数据结构。1.初始化：从文件将输入符号串输入到字符缓冲区中。2.利用递归下降分析法分析，对每个非终结符编写函数，在主函数中调用文法开始符号的函数。（五）练习该实验的目的和思路：程序开始变得复杂起来，需要利用到程序设计语言的知识和大量编程技巧，递归下降分析法是一种较实用的分析法，通过这个练习可大大提高软件开发能力。通过练习，掌握函数间相互调用的方法。（六）为了能设计好程序，注意以下事情：1.模块设计：将程序分成合理的多个模块（函数），每个模块做具体的同一事情。2.写出（画出）设计方案：模块关系简图、流程图、全局变量、函数接口等。3.编程时注意编程风格：空行的使用、注释的使用、缩进的使用等。编译原理实验指导书12实验三LL(1)分析法一、实验目的：根据某一文法编制调试LL（1）分析程序，以便对任意输入的符号串进行分析。本次实验的目的主要是加深对预测分析LL（1）分析法的理解。二、实验预习提示1、LL（1）分析法的功能LL（1）分