编译原理实验指导

1、.编译原理实验指导书主编：徐静 李娜 信息与电气工程学院2010年3月概 述一、本课程实验的目的和任务 编译原理是一门实践性很强的课程，只有通过实践，才能真正掌握。实际的编译程序是十分复杂的，有时由多达十几万条指令组成。为此，编译原理的实践教学，采用简化编译过程的办法，选择最关键的3个环节词法分析、语法分析（包括语义处理、产生无优化的目标指令）、连接调试，进行编程和调试训练。每个环节作为一个实践课题。先分别编程调试，再连接在一起总调。 二、实验方法 任何一个实用的高级语言，其语法都比较复杂，如选其作为源语言，很难实践全过程。故本实验将定义一个简化的语言 C语言的一个子集作为源语言，设计调试出它

2、的编译程序。前后贯穿这一条主线进行实践。每次都可利用课余时间编程，利用上机时间进行输入和调试。 三、实验报告的规范和要求 每个实验完成后写出实验报告。实验报告的内容包括如下内容：一、 实验目的二、 程序设计时采用的算法和方法三、 输入的源程序四、 词法分析程序清单和输出结果。 五、 心得体会实验一 词法分析一、实验目的： （1）通过设计编制调试一个具体的词法分析程序，理解词法分析在编译程序中的作用。（2）加深对有穷自动机模型的理解。（3）掌握词法分析程序的实现方法和技术。（4）用C语言对一个简单语言的子集编制一个一遍扫描的程序，以加深对编译原理的理解，掌握编译程序的实现方法和技术。编制一个读单

3、词过程，从输入的源程序中，识别出各个具有独立意义的单词，即基本保留字、标识符、常数、运算符、分隔符五大类。并依次输出各个单词的内部编码及单词符号自身值。（遇到错误时可显示“Error”，然后跳过错误部分继续显示） 。二、实验预习提示 1. 词法分析器的功能和输出格式词法分析器的功能是输入源程序，输出单词符号。词法分析器的单词符号常常表示成以下的二元式（单词种别码，单词符号的属性值）。本实验中，采用的是一类符号一种别码的方式。2. 单词的BNF表示 | | | + - =3. “超前搜索”方法词法分析时，常常会用到超前搜索方法。如当前待分析字符串为“a+”,当前字符为“ ”，此时，分析器到底是将

4、其分析为大于关系运算符还是大于等于关系运算符呢？显然，只有知道下一个字符是什么才能下结论。于是分析器读入下一个字符“+”，这时可知应将“ ”解释为大于运算符。但此时，超前读了一个字符“+”，所以要回退一个字符，词法分析器才能正常运行。在分析标识符，无符号整数等时也有类似情况。4. 模块结构YNYN调用返回输出缓冲区中是否还有字符取单词扫描一个字符结束主函数main（）输入文件名判断能否打开文件缓冲区扫描一个字符三、实验过程和指导： （一）准备： 1.阅读课本有关章节，明确语言的语法，写出基本保留字、标识符、常数、运算符、分隔符和程序例。2.初步编制好程序。3.准备多组测试数据。（二）上课上机：

5、 将源代码拷贝到机上调试，发现错误，再修改完善。第二次上机调试通过。（三）程序要求：程序输入/输出示例：如源程序为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

6、、continue；单词种别码为1。2. 其他的都识别为标识符；单词种别码为2。3. 常数为无符号整型数；单词种别码为3。4. 运算符包括：+、-、*、/、=、=、=、!= ；单词种别码为4。5. 分隔符包括：,、;、(、)； 单词种别码为5。以上为参考，具体可自行增删。（四）程序思路（仅供参考）：这里以开始定义的C语言子集的源程序作为词法分析程序的输入数据。在词法分析中，自文件头开始扫描源程序字符，一旦发现符合“单词”定义的源程序字符串时，将它翻译成固定长度的单词内部表示，并查填适当的信息表。经过词法分析后，源程序字符串（源程序的外部表示）被翻译成具有等长信息的单词串（源程序的内部表示），并

7、产生两个表格：常数表和标识符表，它们分别包含了源程序中的所有常数和所有标识符。0. 定义部分：定义常量、变量、数据结构。1. 初始化：从文件将源程序全部输入到字符缓冲区中。2. 取单词前：去掉多余空白。3. 取单词后：去掉多余空白。4. 取单词：读出单词的每一个字符，组成单词，分析类型。（关键是如何判断取单词结束？取到的单词是什么类型的单词？）5. 显示结果。（五）练习该实验的目的和思路：程序开始变得复杂起来，可能是大家目前编过的程序中最复杂的，但相对于以后的程序来说还是简单的。因此要认真把握这个过渡期的练习。本实验和以后的实验相关。通过练习，掌握对字符进行灵活处理的方法。（六）为了能设计好程

8、序，注意以下事情：1. 模块设计：将程序分成合理的多个模块（函数），每个模块做具体的同一事情。2. 写出（画出）设计方案：模块关系简图、流程图、全局变量、函数接口等。3. 编程时注意编程风格：空行的使用、注释的使用、缩进的使用等。 （七）程序框架：#include#includechar program80,token8; /*数组program存放的为源程序所有字符，数组token为存放的单词自身字符串*/char ch;int syn,p,m,n,row; /*syn为单词种别码*/long int num; /*sum为整型常数*/char *key 8= if,int,for,whil

9、e,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+;bre

10、ak; default: printf(n(%d, %s),syn,token);break; while(syn!=0);getch( );scaner( ) for(n=0;n8;n+) tokenn=NULL; m=0; ch=programp+; while(ch= ) ch=programp+; /*分类判断1.识别标识符（包括保留字）。建议：关键字作为特殊标识符处理，把它们预先安排在一张表格中（保留字表），当扫描程序识别标识符时，查关键字，否则为一般标识符。注意：识别保留字：if、int、for、while、do、return、break、continue；单词种别码为1。其他的都

11、识别为标识符；单词种别码为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语句）运算符包括：+、-、*、/、=、=、0 ActionA,a=acc把a和s分别压入符号栈和状态栈；使ip前进到下一个字符结束处理是是是否否否三、实验过程和指导： （一）准备： 1.阅读课本有关章节，2.考

12、虑好设计方案；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在“所用产生式”一列中如

13、果对应有推导则写出所用产生式；如果为匹配终结符则写明匹配的终结符；如分析异常出错则写为“分析出错”；若成功结束则写为“分析成功”。B 在此位置输入符号串为用户自行输入的符号串。注意：1. 表达式中允许使用运算符（+-*/）、分割符（括号）、字符i、结束符#； 2. 如果遇到错误的表达式，应输出错误提示信息（该信息越详细越好）；3. 对学有余力的同学，测试用的表达式事先放在文本文件中，一行存放一个表达式，同时以分号分割。同时将预期的输出结果写在另一个文本文件中，以便和输出进行对照；（四）程序思路（仅供参考）：模块结构：（1）定义部分：定义常量、变量、数据结构。（2）初始化：设立LR(1)分析表、初始化变量空间（包括堆栈、结构体、数组、临时变量等）；（3）控制部分：从键盘输入一个表达式符号串；（4）利用LR(1)分析算法进行表达式处理：根据LR(1)分析表对表达式符号串进行堆栈（或其他）操作，输出分析结果，