《编译原理》实验指导书.doc

编译原理课程实验指导书（Compiler Principle）软件工程专业2014孙金庆 编写华信软件学院2017年4月目录序言1实验安排2第一次实验：编译器的词法分析器2第二次实验：编译器的语法分析器10序言本编译原理实验指导，其目的是让大家动手设计和实现规模适中的语言的词法分析器、语法分析器和编译代码生成器，该编译器不仅涉及编译程序的各个阶段，而且也强调了编译的总体设计、各个阶段的接口安排等等。通过上机实践，来设计这个相对完整的编译器，一方面可以使同学们增加对编译程序的整体认识和了解巩固编译原理课程所学知识，另一方面，通过上机练习，学生也可以学到很多程序调试技巧和设计大型程序一般的原则，如模块接口的协调，数据结构的合理选择等等。实验安排第一次实验：编译器的词法分析器（学时：4）词法分析器实验样本C1.1 实验目的设计、编制并调试一个词法分析程序，加深对词法分析原理的理解。C1.2实验要求C1.2.1待分析的简单语言的词法（1）关键字： bengin if then while do end 所有的关键字都是小写。（2）运算符和界符：（3）其他单词是标志符（ID）和整形常数（NUM），通过以下正规式定义： ID=letter（letter|digit）* NUM=digit digit*（4）空格由空白、制表符和换行符组成。空格一般用来分隔ID、NUM、运算符、界符和关键字，词法分析阶段通常被忽略。C1.2.2各种单词符号对应的种别码单词符号种别码单词符号种别码begin1：17if2：=18then3<20while4<>21do5<=22end6>23Letter(letter|digit) 10>=24digit digit *11=25+13;26-14(27* 15)28/16#0C1.2.3词法分析程序的功能输入：所给文法的源程序字符串。输出：二元组（syn，token或sum）构成的序列。其中：syn为单词种别码； token为存放的单词自身字符串； sum为整形常数。例如：对源程序 begin x:=9; if x>0 then x:= 2*x+1/3; end #的源文件，经词法分析后输出如下序列：（1， begin）（10，x）(18,:=) ( 11,9) (26,;) (2,if) 功能测试：（1） 输入字符串begin x:=9; if x>0 then x:= 2*x+1/3; end #其结果如下图所示：（2）输入字符串if x>2; y=3; end #其结果如下图所示：（3）输入字符串where#其输出结果如下图所示：（4）输入字符串1234#其结果显示如下：C1.3 词法分析程序的基本思想算法的基本任务是从字符串表示的源程序中识别出具有独立意义的单词符号，其基本思想示根据扫描到单词符号的第一字符的种类，拼出相应的单词符号。1. 主程序示意图主程序示意图如图C。1所示。其中初值包括如下两个方面：（1） 关键字表的初值。 关键字作为特殊标识符处理，把它们预先安排在一张表格中（称为关键字表），当扫描程序识别出标识符时，查关键字表。如能查到匹配的单词，则该单词为关键字，否则为一般标识符。关键字表为一个字符串数组，其描述如下： char * rwtab6“begin ”,”if”,”then”,”while”,”do”,”end”; 图C.1 词法分析主程序示意图（2） 程序中需要用到的主要变量为syn，token和sum。2. 扫描子程序的算法思想首先设置3个变量：a.token用来存放构成单词符号的字符串；b.sum用来存放整形单词；c.syn用来存放单词符号的种别码。扫描子程序主要部分流程如图C.2所示。 图C.2 词法分析程序流程C.1.4 词法分析程序源代码#include<stdio.h>#include<string.h>char prog80,token6;char ch;int syn,p,m,n,sum;char * rwtab6="begin","if","then","while","do","end"main() p=0; printf("nplease intput string:");do ch=getchar(); progp+=ch;while(ch!='#');p=0;do scaner(); switch(syn) case 11:printf("(%d,%d)",syn,sum);break; case -1:printf("input errorn"); break; default:printf("(%d,%s)",syn,token);while(syn!=0);getch();/*词法扫描程序：*/scaner() for(n=0;n<8;n+) tokenn=NULL; m=0; ch=progp+; while(ch=' ')ch=progp+; if(ch<='z'&&ch>='a')|(ch<='Z'&&ch>='A') while(ch<='z'&&ch>='a')|(ch<='Z'&&ch>='A')|(ch<='9'&&ch>='0') tokenm+=ch; ch=progp+; tokenm+='0' ch=prog-p; syn=10; for(n=0;n<6;n+) if(strcmp(token,rwtabn)=0) syn=n+1; break; else if(ch<='9'&&ch>='0') sum=0; while(ch<='9'&&ch>='0') sum=sum*10+ch-'0' ch=progp+; ch=prog-p; syn=11; else switch(ch) case '<':m=0;tokenm+=ch; ch=progp+; if(ch='>') syn=21; tokenm+=ch; else if(ch='=') syn=22; tokenm+=ch; else syn=20; ch=prog-p; break; case '>':tokenm+=ch; ch=progp+; if(ch='=') syn=24; tokenm+=ch; else syn=23; ch=prog-p; break; case ':':tokenm+=ch; ch=progp+; if(ch='=') syn=18; tokenm+=ch; else syn=17; ch=prog-p; break; case '+':syn=13;token0=ch;break; case '-':syn=14;token0=ch;break; case '*':syn=15;token0=ch;break; case '/':syn=16;token0=ch;break; case ':=':syn=18;token0=ch;break; case '<>':syn=21;token0=ch;break; case '<=':syn=22;token0=ch;break; case '>=':syn=24;token0=ch;break; case '=':syn=25;token0=ch;break; case '':syn=26;token0=ch;break; case '(':syn=27;token0=ch;break; case ')':syn=28;token0=ch;break; case '#':syn=0;token0=ch;break; default:syn=-1;C1.5 实验心得体会：第二次实验：编译器的语法分析器（学时：4）词法分析器实验样本1.2预期目标熟练掌握运用VC+建立工程，并用VC+语言进行程序编写，掌握编程思想和算法。熟练掌握LL(1) 文法的分析方法，利用FIRST集合、FOLLOW集合以及SELECT集合得到预测分析表，并且各集合的计算方法也是设计的目标。1.3解决问题(1)对于一个输入文法，消除文法的左递归；(2)理解计算FIRST、FOLLOW集合和SELECT集合的方法；(3)理解文法分析表的构造。2 系统分析 2.1涉及的知识基础2.1.1 LL(1)文法LL(1)文法是一类可以进行确定的自顶向下语法分析的文法。一个用来描述语言语法结构的文法G2可形式地定义如下：一个文法GS可表示成形如(VN，VT，P，S)的四元式。其中VN，VT，P均为非空的有限集，分别称为非终结符集、终结符集和产生式集。具体来说：VN，一系列需要定义的语法范畴。VT，若干基本符号，不需要进一步定义。P，用“->“连接起来的有序对(A,)的集合，称为规则，也叫产生式。其中A是一个非终结符，是一个由终结符或非终结符组成的符号串，即(VNVT)*。S， 是文法的开始符号。SVN此外 ，我们还将出现在产生式左、右侧的全部符号的集合称为词汇表，记为V。显然：V=VNVT；VNVT =。更确切地说，上面给出的是上下文无关文法的定义。这是因为由符号串a去替换A时，并不考虑A所处的环境，即与A的上下文无关。除非另做说明，我们以后所说的文法均指上下文无关文法。LL(1)的含义：l 第一个L表示从左至右扫描输入符号串l 第二个L表示生成输入串的一个最左推导l 1表示在决定分析程序的每步动作时，向前看一个符号2.1.2确定的自顶向下分析思想LL(1)文法是一类可以进行确定的自顶而下语法分析的文法。而自顶而下分析法的基本思想是从文法的开始符号出发采用最左推导，根据当前的输入符号(单词符号)惟一地确定选用哪个产生式替换相应非终结符以下推导。这种分析过程实质是一种试探过程，是反复使用不同产生式匹配输入符号串的过程。若有文法：S->cAdA->ab|a输入串W=cad。为建立分析树，首先建立只有标记S单个结点树，输入指针指向W的第一个符号c。然后用S的第一个产生式来扩展该树，得到的树如图2.1所示：ScAdScAdSabScAda(a)(b)(c)图2.1.1语法分析树最左边的叶子标记为c，匹配W的第一个符号。于是，推进输入指针到W的第二个符号a，并考虑下一个标记为A的叶子。用A的第一个选择来扩展A，得到如图(b)的树。现在匹配第二个输入符号a，再推进输入指针到d，把它和下一个标记为b的叶子比较。因为b和d不匹配，报告失败，回到A，看它是否还有别的选择尚未尝试。在回到A时，必须重置指针于第二个符号，即第一次进入A的位置。现在尝试A的第二个选择，得到图(c)的分析树。叶子a匹配W的第二个符号，叶子d匹配W的第三个符号。这样，产生了W的分析树，从而宣告分析完全成功。2.1.3 左递归的消除直接消除产生式中的左递归是比较容易的。假定关于非终结符P的规则为P->Pa|b其中，P是开头。那么我们可以把P的规则改写为如下的非直接左递归形式：P->bRR->aR| (为空字)这种形式和原来的形式是等价的，也就是说，从P推出的符号串是相同的。一般而言，假定P关于的全部产生式是P->P1|P2|Pm|1| 2|n其中，每个i(1im)都不等于，1n都不以P开头，那么消除P的直接左递归就是把这些规则改写成：  P->1R| 2R| nR                R->1R|2R|mR|使用这个方法，我们容易把见诸于表面的所有直接左递归都消除掉，也就是说，把直接左递归都改成直接右递归。对于间接左递归的消除需先通过产生式非终结符置换，把间接左递归变成直接左递归。例如有文法：S->A|     (1)            A->S      (2)因为S=>A=>S，所以S是一个间接递归的非终结符。为了消除这种间接左递归将(2)式代人(1)式，即可得到与原方法等价的方法: S->S| (3)(3)式是直接左递归的，可以采用消除直接左递归的方法对文法进行改写，可的文法：S->S       S->S|由此可见，为了消除间接左递归，可首先查出那些具有左递归的非终结符号，然后对以这些非终结符为左部的产生式，通过逐步置换有关产生式的方法将它们化为直接左递归的产生式。最后在消除其中的全部直接左递归。2.1.4消除回溯、提左因子   为了消除回溯就必须保证：对文法的任何非终结符，当要它去匹配输入串时，能够根据它所面临的输入符号准确地指派它的一个侯选去执行任务，并且次侯选的工作结果是确信无疑的。也就是说，若此侯选获得成功匹配，那么，这种匹配不会是虚假的；若此侯选无法完成任务，则任何其它侯选也肯定也无法完成任务。换句话说，假定现在轮到非终结符A去执行匹配任务，A共有n个侯选1，2，n,即A->1|2|n。A能够根据不同的输入符号指派相应的i作为全权代表去执行任务，那就肯定无需回溯了。在这里A已不再是让某个侯选去试探地执行任务，而是根据所面临的输入符号准确地指派唯一的一个侯选。其次，被指派侯选的工作成败也完全代表了A。2.1.5 计算FIRST集合、FOLLOW集合和SELECT集合FIRST集合：令GS=(VT,VN,S,P),则 FIRST(a)= a | a Þ * ab,aVT ,a、bV*、若a Þ* ，则FIRST(a)对每以文法符号X，计算FIRST(X)过程如下： (a)若XVT ,则FIRST(X)=X；(b)若XVN,且有产生式X®a,aVT,则把a加入到FIRST(X)中；(c)若XVN ,若X®e也是一条产生式,则把e也加到FIRST(X)中；(d)若XVN,有产生式X®Y1Y2Yn,Y1,Yi都是非终结符，对于任何j，1ji-1，FIRST(Yj)都含有，则把FIRST(Yj)中的所有非元素都加到FIRST(X)中； FIRST(Yi)的元素加入到FIRST(X)特别地，若所有的FIRST(Yj , j=1,2,n)均含有e,则把e ,FIRST(Yj)中的所有非元素都加到FRIST(X)中。FOLLOW集合：设GS=(VT,VN,S,P)是上下文无关文法, (a)设S为开始符号,则#FOLLOW(S)(b)若有产生式A® aBb，b *Þ 则FIRST(b)ÌFOLLOW(B)(C)若b Þ (可理解为A® aB)则FIRST(b)-FOLLOW(A)Ì FOLLOW(B)SELECT集合：A® a的可选集SELECT aÞ，则SELECT(A®a)=FIRST(a)aÞ，则SELECT(A®a)=(FIRST(a)-) FOLLOW(A)2.2 解决问题的基本思路首先根据一定的规则输入一个合法的文法，化简成LL(1)文法，利用一定的算法消除文法中的左递归，然后再利用首先预定的规则计算出FIRST和FOLLOW集合，以及算出SELECT集合，然后就是显示出LL(1)文法的分析表。最后一步是输入一串字符串，然后对字符串进行分析，输出分析过程表，这样系统就成形了。2.3 功能模块框图初始数据产生式处理计算机FOLLOW集合显示预测分析表图2.3 功能模块框图输入文法3 系统设计语法分析是编译过程的核心部分。他的任务是在词法分析识别单词符号串的基础上，分析并判断程序的的语法结构是否符合语法规则。语言的语法结构是用上下文无关文法描述的。因此语法分析器的工作的本质上就是按文法的产生式，识别输入符号串是否为一个句子。对于一个文法，当给你一串符号是，如何知道它是不是该文法的一个句子，这是这个课程设计所要解决的一个问题。其实要知道一串符号是不是该文法的一个句子，只要判断是否能从文法的开始符号出发推导出这个输入串。语法分析可以分为两类，一类是自上而下的分析法，一类是自下而上的分析法。自上而下的主旨是，对任何输入串，试图用一切可能的办法，从文法开始符号出发，自上而下的为输入串建立一棵语法树。或者说，为输入串寻找一个最左推倒，这种分析过程的本质是一种试探过程，是反复使用不同产生式谋求匹配输入串的过程我主要是自上而下的过程。3.1 LL(1)文法输入设计标准的文法有一定的规则，若在设计过程中，输入的文法不正确，则不能正确的实现程序功能，所以首先在编写程序时，要对输入文法进行限制，规则如下：(1) 大写英文字母表示非终结符，所以产生式左部一定要输入大写字母；(2) e表示空产生式；(3) 除大写字母、#、'、| 外的单字符表示终结符，所以产生右部不能包括以上几个字符；(4) 不能出现递归文法。(如 S->S或S->A, A->S;)；(5) 不能出现多余文法规则。(如 S->A，A不是非终结符)； (6) 文法产生式长度不超过10个字符。3.2 LL(1)语法分析详细流程图我们知道一个文法要能进行LL（1）分析，那么这个文法应该满足：无二义性，无左递归，无左公因子。当文法满足条件后，再分别构造文法每个非终结符的FIRST和FOLLOW集合，然后根据FIRST和FOLLOW集合构造LL（1）分析表，最后利用分析表，根据LL(1)语法分析构造一个分析器。LL（1）的语法分析程序包含了三个部分，总控程序，预测分析表函数，先进先出的语法分析栈，本程序也是采用了同样的方法进行语法分析，其结构图如图3.2。开始操作读源程序字符常数分析程序关键字标识符分析程序其它单词分析程序输出单词内部表示开始结束是字母?有字符?是数字?YYYNNN图3.2 LL(1)语法分析详细流图3.3算法描述3.3.1 消除左递归的算法(1) 把文法G的所有非终结符按任一种顺序排列成P1，P2,Pn;按此顺序执行； (2)  FOR  i:=1  TO   n    DOBEGIN          FOR  j:=1   TO   i-1   DO                把形如Pi->Pj产生式变为Pj->1|2|k关于Pj的所有规则消除关于Pi规则的直接左递归性       END(3) 化简由(2)所得的文法。即去除那些从开始符号出发永远也无法到达的非终结符的产生规则。3.4系统流程图整个程序可分为如下几步：(1) 读入文法；(2) 判断正误；(3) 若无误，判断是否为LL(1)文法；(4) 若是，构造分析表；(5) 由总控算法判断输入符号串是否为该文法的句型。 图3.4.1 程序主流程图 图3.4.2消除左递归流程图4 代码编写4.1相关代码 分解含有左递归的产生式void recur(char *point)/*完整的产生式在point中*/ int j,m=0,n=3,k;char temp20,ch;ch=c();/*得到一个非终结符*/k=strlen(non_ter); /*非终结符号长度*/non_terk=ch;/得到最后一个非终结符号non_terk+1='0'for(j=0;j<=strlen(point)-1;j+)if(pointn=point0) /*如果|后的首符号和左部相同，含直接左递归*/for(j=n+1;j<=strlen(point)-1;j+) while(pointj!='|'&&pointj!='0') tempm+=pointj+;leftcount=ch;memcpy(rightcount,temp,m);rightcountm=ch;rightcountm+1='0'm=0;count+;if(pointj='|')n=j+1;break;else /*如果|后的首符号和左部不同*/leftcount=ch;rightcount0=''rightcount1='0'count+;for(j=n;j<=strlen(point)-1;j+) if(pointj!='|') tempm+=pointj; else leftcount=point0; memcpy(rightcount,temp,m); rightcountm=ch; rightcountm+1='0'printf(" count=%d ",count);m=0; count+; leftcount=point0; memcpy(rightcount,temp,m); rightcountm=ch; rightcountm+1='0'count+; m=0; 分解不含有左递归的产生式void non_re(char *point) int m=0,j;char temp20;for(j=3;j<=strlen(point)-1;j+) if(pointj!='|') tempm+=pointj;else leftcount=point0; memcpy(rightcount,temp,m); rightcountm='0'm=0;count+; leftcount=point0; memcpy(rightcount,temp,m); rightcountm='0' count+;m=0; 总控算法void syntax()int i,j,k,m,n,p,q; char ch;char S50,str50; printf("请输入该文法的句型：");scanf("%s",str);getchar();i=strlen(str);stri='#'stri+1='0'S0='#'S1=start;S2='0'j=0;ch=strj; while(1)if(in(Sstrlen(S)-1,termin)=1) if(Sstrlen(S)-1!=ch)printf("该符号串不是文法的句型！"); return;else if(Sstrlen(S)-1='#') printf("该符号串是文法的句型."); return;else Sstrlen(S)-1='0'j+;ch=strj;else for(i=0;i+)if(non_teri=Sstrlen(S)-1)break;for(k=0;k+)if(termink=ch)break;if(k=strlen(termin)printf("词法错误！");return;if(Mik=-1)printf("语法错误！");return;else m=Mik; if(rightm0='')Sstrlen(S)-1='0'else p=strlen(S)-1; q=p; for(n=strlen(rightm)-1;n>=0;n-) Sp+=rightmn; Sq+strlen(rightm)='0' printf("符号栈:%s 剩余字符串:",S);for(p=j;p<=strlen(str)-1;p+)printf("%c",strp);printf(" n");4.2运行结果编译调试，运行程序。输入文法，如图4.2.1，按回车键得到分析结果，如图4.2.2，判断其是否为LL(1)文法，并得到该文法的分析表；输入该文法的句型，回车得到句型的预测分析过程，如图4.2.3，再次输入不是该文法的句型，如图4.2.4图4.2.1图4.2.2图4.2.3图4.2.4C1.5 实验心得体会：