《编译原理》实验指导书

《编译原理》实验指导书主编：王春霞软件学院编译原理课程组2008年8月20日前言本实验指导书是《编译原理》课程的配套实验指导书。本课程的总体目标是：通过实验学习编译程序调试技巧和设计编译程序的一般原则，加深对词法分析、语法分析、语义分析和中间代码生成等编译阶段及实用编译系统的认识，初步掌握编译程序构造的基本原理与技术,从形式语言理论的角度进一步认识与理解程序设计语言。通过编译程序的编写和调试能力的训练，激发学生进一步思考问题，培养学生的学习兴趣和创新能力。并进一步培养学生的抽象思维能力，进一步巩固《编译原理》课程所学知识。书中共设计了2个实验，共计8学时，均为验证型实验。该指导书在算法提示上采取从有到无、从多到少的方式，实验内容将针对我院学生的实际情况，做到难易适中。本指导书使用伪语言来描述和实现相关算法，实验环境是VC6.0语言。编译原理实验指导书实验一词法分析一、实验目的：通过设计编制调试一个具体的词法分析程序，加深对词法分析原理的理解。并掌握在对程序设计语言源程序进行扫描过程中将其分解为各类单词的词法分析方法。编制一个读单词过程，从输入的源程序中，识别出各个具有独立意义的单词，即基本保留字、标识符、常数、运算符、分隔符五大类。并依次输出各个单词的内部编码及单词符号自身值。（遇到错误时可显示“Error”，然后跳过错误部分继续显示）二、实验预习提示1、词法分析器的功能和输出格式词法分析器的功能是输入源程序，输出单词符号。词法分析器的单词符号常常表示成以下的二元式(单词种别码，单词符号的属性值)。本实验中，采用的是一类符号一种别码的方式。2、单词的BNF表示<标识符>-><字母><字母数字串><字母数字串>-><字母><字母数字串>|<数字><字母数字串>|<下划线><字母数字串>|ε<无符号整数>-><数字><数字串><数字串>-><数字><数字串>|ε<加法运算符>->+<减法运算符>->-<大于关系运算符>->><大于等于关系运算符>->>=3、“超前搜索”方法词法分析时，常常会用到超前搜索方法。如当前待分析字符串为“a>+”,当前字符为’>’，此时，分析器倒底是将其分析为大于关系运算符还是大于等于关系运算符呢？显然，只有知道下一个字符是什么才能下结论。于是分析器读入下一个字符’+’，这时可知应将’>’解释为大于运算符。但此时，超前读了一个字符’+’，所以要回退一个字符，词法分析器才能正常运行。在分析标识符，无符号整数等时也有类似情况。缓冲区扫描一个字符缓冲区扫描一个字符主函数main()N输入文件名，判断能否打开文件Y缓冲区中是否还有字符Y结束取单词扫描一个字符调用返回输出N三、实验过程和指导：（一）准备：1.阅读课本有关章节，明确语言的语法，写出基本保留字、标识符、常数、运算符、分隔符和程序例。2.初步编制好程序。3.准备好多组测试数据。（二）上课上机：将源代码拷贝到机上调试，发现错误，再修改完善。第二次上机调试通过。（三）程序要求：程序输入/输出示例：（1（1，”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，”}“）main(){inta,b;a=10; b=a+20;}要求输出如右图。要求：一、将单词分为五种识别关键字：main、if、int、for、while、do、return、break、continue；单词种别码为1。标识符；单词种别码为2。常数为无符号整形数；单词种别码为3。运算符包括：+、-、*、/、=、>、<、>=、<=、!=；单词种别码为4。分隔符包括：,、;、{、}、(、)；单词种别码为5。二、使用一符一种的分法关键字、运算符和分界符可以每一个均为一种标识符和常数仍然一类一种以上两个选择任选其一以上为参考，具体可自行增删。（四）程序思路（仅供参考）：这里以开始定义的C语言子集的源程序作为词法分析程序的输入数据。在词法分析中，自文件头开始扫描源程序字符，一旦发现符合“单词”定义的源程序字符串时，将它翻译成固定长度的单词内部表示，并查填适当的信息表。经过词法分析后，源程序字符串（源程序的外部表示）被翻译成具有等长信息的单词串（源程序的内部表示），并产生两个表格：常数表和标识符表，它们分别包含了源程序中的所有常数和所有标识符。1.定义部分：定义常量、变量、数据结构。2.初始化：从文件将源程序全部输入到字符缓冲区中。3.取单词前：去掉多余空白。4.取单词后：去掉多余空白（可选，看着办）。5.取单词：利用实验一的成果读出单词的每一个字符，组成单词，分析类型。（关键是如何判断取单词结束？取到的单词是什么类型的单词？）6.显示结果。（五）练习该实验的目的和思路：程序开始变得复杂起来，可能是大家目前编过的程序中最复杂的，但相对于以后的程序来说还是简单的。因此要认真把握这个过渡期的练习。本实验和以后的实验相关。通过练习，掌握对字符进行灵活处理的方法。（六）为了能设计好程序，注意以下事情：1.模块设计：将程序分成合理的多个模块（函数），每个模块做具体的同一事情。2.写出（画出）设计方案：模块关系简图、流程图、全局变量、函数接口等。3.编程时注意编程风格：空行的使用、注释的使用、缩进的使用等。（七）部分代码示例：#include<string.h>#include<stdio.h>#include<stdlib.h>#include<ctype.h>char*table[7]={"","main","int","if","then","else","return"},TOKEN[20],ch;

//定义关键字intlookup(char*TOKEN){

//关键字匹配函数

intm,i;

for(i=1;i<6;i++){

if((m=strcmp(TOKEN,table[i]))==0)

return(i);

}

return(0);}voidout(intc,char*TOKEN){

//输出函数

printf("(%d,%s)\n",c,TOKEN);}voidscanner(FILE*fp){

//扫描函数

charTOKEN[20]={'\0'};

charch;

inti;

ch=fgetc(fp);

//获取字符，指针fp并自动指向下一个字符

if(zimu(ch)){

//判断该字符是否是字母

TOKEN[0]=ch;

ch=fgetc(fp);

i=1;

while(zimu(ch)||shuzi(ch)){

//判断该字符是否是字母或数字}main(){

FILE*fp;

if((fp=fopen("E:\\222.txt","r"))==NULL){

//读取文件内容，并返回文件指针，该指针指向文件的第一个字符

fprintf(stderr,"erroropening.\n");

exit(1);

}

do{

ch=fgetc(fp);

if(ch=='#')

//文件以#结尾，作为扫描结束条件

break;

if(ch=='')

//如果是空格，自动跳到下个字符

scanner(fp);

else{

fseek(fp,-1,1);

//如果不是空格，则回退一个字符并扫描

scanner(fp);

}

}while(ch!='#');

return(0);}函数说明1.intlookup(char*TOKEN)

关键字匹配函数,查询所述程序中的关键字2.voidout(intc,char*TOKEN)

输出函数3.voidscanner(FILE*fp)

扫描函数，扫描程序中的字符串并调用lookup函数检查是否是关键字，再调用out函数输出二元组4.fseek（fp，-1，1）回退一个字符5.isletter（ch）字母判断函数，若ch指的是字母，返回非0，否则返回06.isnumber（ch）数字判断函数，若ch指的是数字，返回非0，否则返回07.fgetc（fp）从数据流中区下一个字符8.fopen

文件打开函数，返回指向文件第一个字符的指针四、上交：1.程序源代码（上交软盘）；2.已经测试通过的测试数据3组；3.实验报告包含：实验名称实验目的和要求（一）实验内容（1）功能描述：该程序具有什么功能？（2）程序结构描述：函数调用格式、参数含义、返回值描述、函数功能；函数之间的调用关系图。（3）程序总体执行流程图（二）实验过程记录：出错次数、出错严重程度、解决办法摘要。（三）实验总结：你在编程过程中花时多少？多少时间在纸上设计？多少时间上机输入和调试？多少时间在思考问题？遇到了哪些难题？你是怎么克服的？你对你的程序的评价？你的收获有哪些？

实验二：自上而下语法分析一、实验目的：1、根据某一文法编制调试递归下降分析程序，以便对任意输入的符号串进行分析。（选做）2、根据某一文法编制调试LL（1）分析程序，以便对任意输入的符号串进行分析。（必做）3、本次实验的目的主要是加深对自上而下分析法的理解。二、实验预习提示1、自下而上分析法的前提改造文法：消除二义性、消除左递归、提取左因子，判断是否为LL（1）文法A．递归下降1、递归下降分析法的功能词法分析器的功能是利用函数之间的递归调用模拟语法树自上而下的构造过程。2、递归下降分析法实验设计思想及算法为G的每个非终结符号U构造一个递归过程,不妨命名为U。U的产生式的右边指出这个过程的代码结构：(1)若是终结符号，则和向前看符号对照，若匹配则向前进一个符号；否则出错。(2)若是非终结符号，则调用与此非终结符对应的过程。当A的右部有多个产生式时,可用选择结构实现。具体为：（1）对于每个非终结符号U->u1|u2|…|un处理的方法如下：U(){ch=当前符号;if(ch可能是u1字的开头)处理u1的程序部分;elseif(ch可能是u2字的开头)处理u2的程序部分;…elseerror()}（2）对于每个右部u1->x1x2…xn的处理架构如下：处理x1的程序；处理x2的程序；…处理xn的程序；（3）如果右部为空，则不处理。（4）对于右部中的每个符号xi=1\*GB3①如果xi为终结符号：if(xi==当前的符号){NextChar()；return;}else出错处理=2\*GB3②如果xi为非终结符号，直接调用相应的过程xi()说明：NextChar为前进一个字符函数。B．LL（1）分析法1、LL（1）分析法的功能LL（1）分析法的功能是利用LL（1）控制程序根据显示栈栈顶内容、向前看符号以及LL（1）分析表，对输入符号串自上而下的分析过程。2、LL（1）分析法实验设计思想及算法‘#’‘S’‘#’‘S’进栈，当前输入符送a上托栈顶符号放入上托栈顶符号放入X是是X∈V是是X∈VTX=a读入下一个符号若产生式为X若产生式为XX1X2…Xn按逆序即Xn…X2X1入栈否否X=’#'否X=’#'否否是X∈VN是X∈VNM[X,a]是产生式吗M[X,a]是产生式吗是是否否否X=a出错否X=a出错出错是出错是结束结束三、实验过程和指导：（一）准备：1.阅读课本有关章节，2.考虑好设计方案；3.设计出模块结构、测试数据，初步编制好程序。（二）上课上机：将源代码拷贝到机上调试，发现错误，再修改完善。第二次上机调试通过。（三）程序要求：程序输入/输出示例：对下列文法，用两种分析法对任意输入的符号串进行分析：（1）E->TG（2）G->+TG（3）G->ε（4）T->FS（5）S->*FS（6）S->ε（7）F->(E)（8）F->i输出的格式如下：(1)递归下降分析程序输入一以#结束的符号串(包括+—*/（）i#)：在此位置输入符号串例如：i+i*i#输出结果：i+i*i#为合法符号串备注：输入一符号串如i+i*#,要求输出为“非法的符号串”。(2)LL（1）分析：输入一以#结束的符号串(包括+—*/（）i#)：在此位置输入符号串例如：i+i*i#输出结果：i+i*i#为合法符号串注意：1.表达式中允许使用运算符（+-*/）、分割符（括号）、字符I，结束符#；2.如果遇到错误的表达式，应输出错误提示信息（该信息越详细越好）；3.对学有余力的同学，可以详细的输出推导的过程，即详细列出每一步使用的产生式。分析栈剩余输入串所用产生式Ei+i*i#E->TG4.与读文件有关的函数：FILE*fp;

if((fp=fopen("E:\\222.txt","r"))==NULL){

//读取文件内容，并返回文件指针，该指针指向文件的第一个字符

fprintf(stderr,"erroropening.\n");

exit(1);

}fgetc（fp）从数据流中区下一个字符fopen

文件打开函数，返回指向文件第一个字符的指针（四）程序思路（仅供参考）：递归下降分析法：1、定义部分：定义常量、变量、数据结构。2、初始化：从文件将输入符号串输入到字符缓冲区中。3、利用递归下降分析法分析，对每个非终结符编写函数，在主函数中调用文法开始符号的函数。LL（1）分析法：模块结构：1、定义部分：定义常量、变量、数据结构。2、初始化：设立LL(1)分析表、初始化变量空间（包括堆栈、结构体等）；3、运行程序：让程序分析一个text文件，判断输入的字符串是否符合文法定义的规则；4、利用LL(1)分析算法进行表达式处理：根据LL(1)分析表对表达式符号串进行堆栈（或其他）操作，输出分析结果，如果遇到错误则显示简单的错误提示。参考代码示例（C语言）：#include<stdio.h>#include<stdlib.h>#include<string.h>#include<dos.h>structStack{chars[30];inttop;/*栈顶指针*/}S1;charv1[6]={'i','+','*','(',')','#'};/*终结符*/charv2[5]={'E','G','T','S','F'};/*非终结符*//*用二维数组保存预测分析表，可用符号^来代替ε，注意字符串结束位自动加'\0'*/chartable[5][6][4]={{“TG”,””,””,””,”TG”,””},{…},{…},{…},{…}}voidprint()/*输出分析栈*/{ inta;/*指针*/ for(a=0;a<S1.top;a++) cout<<S1.s[a]; cout<<endl;}/*print*/voidintialstack(){S1.top=0;}voidpush(charch){S1.s[S1.top]=ch;S1.top++;}charpop(){S1.top--;returnS1.s[S1.top];}voidjinzhan(inthang,intlie){…….}intiszhongjie(charX){…..}/*判断X是否为终结符，返回下标*/boolchabiao(charX,charsym){……}/*判断X是否为非终结符，sym是否为终结符，若是查找预测表对应表格是