编译原理实验指导书2015.doc
LIAOCHENG UNIVERSITY编译原理实验指导书聊城大学计算机学院2011年3月目录编译原理课程实验教学大纲1实验一词法分析器的设计3基本信息3实验目的3实验内容3实验扩充5实验说明5实验考核方式5实验辅导5实验二语法分析器的设计10基本信息10实验目的10实验内容10实验说明：10实验考核方式：10实验辅导11能力扩展19附录19编译原理课程实验教学大纲课程名称：编译原理英文名称：Compile principles设置形式：非独立设课课程模块：专业方向课实验课性质：专业实验课程编号：509615课程负责人：姜华大纲主撰人：姜华大纲审核人：左风朝一、学时、学分 课程总学时：72实验学时：8课程学分：4二、适用专业及年级计算机科学与技术、软件工程三年级三、课程目标与基本要求编译原理课程是计算机专业的核心课程，是培养计算机技术高级人才的必修课程。该课程通过程序设计语言和语言处理软件的理论与技术的教学，培养学生利用计算机语言处理技术进行系统分析和软件设计的能力。<<编译原理>>是理论与实践并重的课程，这门实验课要综合运用一、二、三年级所学的多门课程的内容。实验目标与要求； 1学会用高级程序设计语言设计词法分析器。 2学会用高级程序设计语言设计语法分析器。四、主要仪器设备Windows操作系统，编程语言采用C、C+，集成调试环境采用TC或Microsoft Visual Studio 6五、实验项目及教学安排序 号实验项目名称实 验 内 容学时要求性质类别所用主要仪器及台套数所在实验室1用C或者 C+ 语言设计一个词法分析器1. 确定编译中使用的表格、词法分析器的输出形式、标识符与关键字的区分方法。2. 把词法分析器设计成一个独立的过程。4必做设计综合型微机，每人一台。计算机学院实验中心2用C或者 C+语言设计一个语法分析器。1. 词法分析和语法分析在一起实现。2. 把语法分析器设计成一个独的过程。4必做设计综合型微机，每人一台。计算机学院实验中心六、考核方式及成绩评定根据学生实验出勤情况、实验态度、实验报告成绩等方面评定实验成绩。实验报告平均成绩（含实验理论）占实验成绩的50%，实验技能平均成绩（含实验态度）占实验成绩的50%。 实验成绩占该课程考试总成绩的1020%。在机器上将程序及运行结果上传至服务器，由实习教师给出优、良、中、及格、不及格。七、实验教科书、参考书1实验教科书自编实验指导书。 2实验参考书实验一词法分析器的设计基本信息实验课程：编译原理设课形式：非独立课程学分：4实验项目：词法分析器的设计项目类型：设计项目学时：4实验目的1. 掌握词法分析的原理；2. 熟悉符号表的建立与单词的分类方法；3. 掌握词法分析器的设计与调试；实验内容1. 分析如表1所定义的PASCAL语言子集的语法，找出所有单词的组成及类别；2. 完成单词的分类及其编码；3. 完成保留字表、变量名表和常数表的结构设计；4. 建立识别单词符号集合的DFA；5. 由DFA设计词法分析程序；6. 调试并运行词法分析程序；7. 实验结果分析。分析结果含义并写出自己的心得体会。表1.PASCAL语言子集的语法定义程序变量说明BEGIN语句表END.变量说明VAR变量表：类型；|空变量表变量表，变量|变量类型INTEGER语句表语句表；语句|语句语句赋值语句|条件语句|WHILE语句|复合语句|过程定义赋值语句变量=算术表达式条件语句IF关系表达式THEN语句ELSE语句WHILE语句WHILE关系表达式DO语句复合语句BEGIN语句表END过程定义PROCEDURE标识符参数表；BEGIN语句表END参数表(标识符表)|空标识符表标识符表，标识符|标识符算术表达式算术表达式+项|项项项*初等量|初等量初等量(算术表达式)|变量|无符号数关系表达式算术表达式关系符算术表达式变量标识符标识符标识符字母|标识符数学|字母无符号数无符号数数字|数字关系符=|=|=|字母A|B|C|X|Y|Z数字0|1|2|8|9空提示： (1) 单词的分类。 可将所有标识符归为一类；将常数归为另一类；保留字和分隔符则可采取一词一类。 (2) 符号表的建立。 可事先建立一保留字表，以备在识别保留字时进行查询。变量名表及常数表则在词法分析过程中建立。 (3) 单词串的输出形式。 所输出的每一单词，均按形如 (CLASS，VALUE)的二元式编码。对于变量标识符和常数，CLASS字段为相应的类别码，VALUE字段则是该标识符、常数在其符号表中登记项的序号 (要求在变量名表登记项中存放该标识符的字符串，其最大长度为四个字符；常数表登记项中则存放该整数的二进制形式)。对于保留字和分隔号，由于采用一词一类的编码方式，所以仅需在二元式的CLASS字段上放置相应的单词的类别码，VALUE字段则为“空”。不过，为便于查看由词法分析程序所输出的单词串，也可以在CLASS字段上直接放置单词符号串本身。 测试用输入：测试用输入程序为。 Procedure program1(a, b)；BeginVar xyz=50;While a>b do beginIf xyz=0 then xyz=50; xyz:=xyz-a; a:=a-1; endEnd实验扩充构造语言的词法分析程序，要求识别出变量类型并记录相关信息。实验说明实验环境：WINDOWS下，工具为Turbo C2.0或Visual C 6.0。实验考核方式1提交实验报告2演示程序和答辩（抽查）实验辅导1. 词法分析程序的功能词法分析程序又称为扫描器，其功能在于依次扫视字符串形式源程序中的各个字符，逐个识别出其中的单词，并将其转换为内部编码形式的单词符号串作确为输出。通常，可采用二元式（class，value）来表示一个单词符号的内部编码，其中：class为一整数码，用于表示该单词的类别；value则是该单词之值（如变量名在符号表中序号，常数的二进制表示，以及运算符和分隔符的编码等等）。概括地说，扫描器在其工作过程中，一般应完成下列的任务：（1）识别出源程序中的各个单词符号，并将其转换为内部编码形式；（2）删除无用的空白字符、回车字符以及其它非实质性字符；（3）删除注释；（4）进行词法检查，报告所发现的错误。此外，视编译工作流程的组织，一些编译程序在进行词法分析时，还要完成将所识别出的标识符登录到符号表的工作。 2. 实例分析对于表2所列的各类单词符号，词法分析程序可按图1所示的状态转换图来构造。表2 一个语言的单词符号及分类码表图1识别表2所列语言单词的DFA及相关的语义过程相关变量和子程序说明如下：u 函数GETCHAR每调用一次，就把扫描指示器当前所指示的源程序字符送入字符变量ch，然后把扫描指示器前推一个字符位置。u 字符数组TOKEN用来依次存放一个单词词文中的各个字符。u 函数CAT每调用一次，就把当前ch中的字符拼接于TOKEN中所存字符串的右边。u 函数LOOKUP每调用一次，就以TOKEN中的字符串查保留字表，若查到，就将相应关键字的类别码赋给整型变量c；否则将c置为零。u 函数RETRACT每调用一次，就把扫描指示器回退一个字符位置 (即退回多读的那个字符)。u 函数OUT一般仅在进入终态时调用此函数，调用的形式为OUT (c，VAL)。其中，实参c为相应单词的类别码或其助记符；当所识别的单词为标识符和整数时，实参VAL为TOKEN (即词文分别为字母数字串和数字串)，对于其余种类的单词，VAL均为空串。函数OUT的功能是，在送出一个单词的内部表示之后，返回到调用该词法分析程序的那个程序。可参考的C语言源程序如下：# include <stdio.h># include <ctype.h># include <string.h># define ID6# define INT7# define LT8# define LE9# define EQ10# define NE11# define GT12# define GE13char TOKEN20；extern int lookup (char*);extern void out (int, char*);extern reporterror (void);void scannerexample (FILE*fp)char ch;int i, c;ch=fgetc (fp);if (isalpha (ch)/*it must be a identifer!*/TOKEN0=ch;ch=fgetc (fp);i=1;while (isalnum (ch)TOKENi=ch;i+；ch=fgetc (fp);TOKENi=0fseek(fp,-1,1);/* retract*/c=lookup (TOKEN);if (c=0) out (ID,TOKEN);else out (c," ")；Elseif(isdigit(ch)TOKEN0=ch;ch=fgetc(fp);i=1;while(isdigit(ch)TOKENi=ch;i+;ch=fgetc(fp);TOKENi=0；fseek(fp,-1,1);out(INT,TOKEN);Elseswitch(ch)case :ch=fgetc(fp);if(ch=)out(LE," ");else if(ch=) out (NE," ");elsefseek (fp,-1,1);out (LT," ");break;case =:out(EQ, " ");break;case :ch=fgetc(fp);if(ch=)out(GE," ");elsefseek(fp,-1,1);out(GT," ");break;default: reporterror( );break;return;实验二语法分析器的设计基本信息实验课程：编译原理设课形式：非独立课程学分：4实验项目：语法分析器的设计项目类型：设计项目学时：4实验目的1. 掌握自上而下语法分析的基本思想；2. 掌握利用预测分析法进行语法分析的原理和过程；3. 熟悉文法的机内表示；4. 掌握语法分析器的设计与调试，提高编程能力、动手能力以及独立分析问题、解决问题的能力和综合运用所学知识的能力。实验内容1. 输入任意文法，改写文法使其成为LL(1)文法。 Ø2. 构造文法的预测分析表；3. 设计堆栈和预测分析表的机内表示；4. 设计并书写语法分析程序；5. 调试并运行语法分析程序；6. 实验结果分析l 分析程序中文法存储所采用的数据结构l 分析结果并写出自己的心得体会提示： 对于所选定的分析方法，如有需要，应选择一种合适的数据结构，以构造所给文法的机内表示。 实验说明：实验环境：WINDOWS下，工具为Turbo C2.0或Visual C 6.0。实验考核方式：1. 提交实验报告2. 演示程序和答辩（抽查）实验预习实验辅导1. 设计原理及算法描述 所谓LL（1）分析法，就是指从左到右扫描输入串（源程序），同时采用最左推导，且对每次直接推导只需向前看一个输入符号，便可确定当前所应当选择的规则。实现LL（1）分析的程序又称为LL（1）分析程序或LL1（1）分析器。 一个文法要能进行LL（1）分析，那么这个文法应该满足：无二义性，无左递归，无左公因子。当文法满足条件后，再分别构造文法每个非终结符的FIRST和FOLLOW集合，然后根据FIRST和FOLLOW集合构造LL（1）分析表，最后利用分析表，根据LL(1)语法分析构造一个分析器。2. 分析过程LL（1）的语法分析程序包含了三个部分，总控程序，预测分析表函数，先进先出的语法分析栈，本程序也是采用了同样的方法进行语法分析，该程序是采用了C语言来编写，其逻辑结构图如图2所示。 图2 LL(1)语法分析逻辑结构图 LL（1）预测分析程序的总控程序在任何时候都是按STACK栈顶符号X和当前的输入符号a做哪种过程的。对于任何（X，a）总控程序每次都执行下述三种可能的动作之一： （）若X = a =#，则宣布分析成功，停止分析过程。 （）若X = a #，则把X从STACK栈顶弹出，让a指向下一个输入符号。 （）若X是一个非终结符，则查看预测分析表M。若MA，a中存放着关于X的一个产生式，那么，首先把X弹出STACK栈顶，然后，把产生式的右部符号串按反序一一弹出STACK栈（若右部符号为，则不推什么东西进STACK栈）。若MA，a中存放着“出错标志”，则调用出错诊断程序ERROR。 事实上，LL（1）的分析是根据文法构造的，它反映了相应文法所定义的语言的固定特征，因此在LL（1）分析器中，实际上是以LL（1）分析表代替相应方法来进行分析的。 3. 构造LL(1)分析表 例如考查文法GE： EE+T | T TT*F | F F( E ) | i | 我们容易看出此文法没有左公因子也没有二义性，但却存在两个直接左递归，这里我们利用引入新非终结符的方法来消除它使方法满足要求，即： (1) 改写文法。对形如：UUx|y的产生式（其中x,y V+ ，y不以U开头），引入一个新的非终结符U后，可以等价地改写成为： UyU Ux U| 显然改写后，U和U都不是左递归的非终结符。因此文法GE按上述方法消去左递归后可等价地写成： ETP P+TP | TFQ Q*FQ | F( E ) | i (2) FIRST和FOLLOW集合构造。在构造LL(1)预测分析表之前，首先要构造该文法的每个非终结符的FIRST和FOLLOW集合，按照下面描述的算法来构造这两个集合。 FIRST集合的构造算法： l 若XVT，则FIRST（X）=X。 l 若XVN，且有产生式Xa，则把a加入到FIRST(X)中；若X也是一条产生式，则把也加到FIRST(X)中。 l 若XY是一个产生式且YVN，则把FIRST(Y)中的所有非-元素都加到FIRST(X)中；若XY1Y2Yk是一个产生式，Y1，Yi-1都是非终结符，而且，对于任何j，1ji-1，FIRST(Yj)都含有（即Y1Yi-1* ），则把FIRST(Yj)中的所有非-元素都加到FIRST(X)中；特别是，若所有的FIRST(Yj)均含有，j=1,2,，k，则把加到FIRST(X)中。连续使用上面的规则，直至每个集合FIRST不再增大为止。 FOLLOW集合的构造算法： l 对于文法的开始符号S，置#于FOLLOW(S)中； l 若AB是一个产生式，则把FIRST()| 加至FOLLOW(B)中； l 若AB是一个产生式，或AB是一个产生式而ð（即FIRST()），则把FOLLOW(A)加至FOLLOW(B)中。 连续使用上面的规则，直至每个集合FOLLOW不再增大为止。 算法中利用二维数组分别表示各产生式右部的FIRST和左部的FOLLOW集合(3)预测分析表构造。构造GE的LL（1）预测分析表。预测分析表MA, a是如下形式的一个矩阵。A为非终结符，a是终结符或#。矩阵元素 MA, a中存放这一条关于A的产生式，指出当A面临输入符号a是所应采用的规则。MA, a也可能存放一条“出错标志”，指出当A根本不该面临输入符号a。算法中利用二维数组存储分析表。 4. 利用分析表进行预测分析 (1) 总控程序的流程图LL(1)分析法总控程序流程图如图3所示。图3 LL(1)分析法总控程序流程图(2) 总程序的算法描述如下：BEGIN 首先把#然后把文法开始符号推进STACK栈；把第一个输入符号读进a; FLAG:=TRUE; WHILE FLAG DO BEGIN 把栈顶符号出栈到X中； IF X in VT THEN IF X =a THEN 把下一输入符号读进a ELSE ERROR ELSE IF X= # THEN IF X=a THEN FLAG:=FALSE ELSE ERROR ELSE IF MA, a=Xx1x2xk THEN 把xk, xk1, x1依次进栈 /*若x1, x2 xk=e，则不进栈*/ ELSE ERROREND OF WHILE; STOP /*分析成功，过程结束*/ END (5) 实例分析 实例考查文法GE： EE+T | T TT*F | F F( E ) | i | 文法改造为LL(1)文法为测试文法GE: ETG G+TG | TFS S*FS | F( E ) | i分析例句：i*(i)# , i+i#输入：串w和文法G的分析表M。输出：如果W属于L（G），则输出W的最左推导，否则报告错误。方法：开始时，#S在分析栈中，其中S是文法的开始符号，在栈顶；令指针ip指向W#的第一个符号； 主要数据结构描述 char termin50; /*终结符号*/ char non_ter50; /*非终结符号*/ char v50; /*所有符号*/ char left50; /*左部*/ char right5050; /*右部*/ int M2020; /*二维数组存储分析表*/ 栈T用来存放产生式的右边 Str数组存放要分析的句子串 可参考的C语言源程序V/*LL(1)分析法源程序，只能在VC+中运行 */#include<stdio.h>#include<stdlib.h>#include<string.h>#include<dos.h>char A20;/*分析栈*/char B20;/*剩余串*/char v120='i','+','*','(',')','#'/*终结符 */char v220='E','G','T','S','F'/*非终结符 */ int j=0,b=0,top=0,l;/*L为输入串长度 */ typedef struct type/*产生式类型定义 */ char origin;/*大写字符 */ char array5;/*产生式右边字符 */ int length;/*字符个数 */type; type e,t,g,g1,s,s1,f,f1;/*结构体变量 */type C1010;/*预测分析表 */ void print()/*输出分析栈 */ int a;/*指针*/ for(a=0;a<=top+1;a+) printf("%c",Aa); printf(""t"t");/*print*/ void print1()/*输出剩余串*/ int j; for(j=0;j<b;j+)/*输出对齐符*/ printf(" "); for(j=b;j<=l;j+) printf("%c",Bj); printf(""t"t"t");/*print1*/void main() int m,n,k=0,flag=0,finish=0; char ch,x; type cha;/*用来接受Cmn*/ /*把文法产生式赋值结构体*/ e.origin='E' strcpy(e.array,"TG"); e.length=2; t.origin='T' strcpy(t.array,"FS"); t.length=2; g.origin='G' strcpy(g.array,"+TG"); g.length=3; g1.origin='G' g1.array0='' g1.length=1; s.origin='S' strcpy(s.array,"*FS"); s.length=3; s1.origin='S' s1.array0='' s1.length=1; f.origin='F' strcpy(f.array,"(E)"); f.length=3; f1.origin='F' f1.array0='i' f1.length=1; for(m=0;m<=4;m+)/*初始化分析表*/ for(n=0;n<=5;n+) Cmn.origin='N'/*全部赋为空*/ /*填充分析表*/ C00=e;C03=e; C11=g;C14=g1;C15=g1; C20=t;C23=t; C31=s1;C32=s;C34=C35=s1; C40=f1;C43=f; printf("提示:本程序只能对由'i','+','*','(',')'构成的以'#'结束的字符串进行分析,n"); printf("请输入要分析的字符串:"); do/*读入分析串*/ scanf("%c",&ch); if (ch!='i') &&(ch!='+') &&(ch!='*')&&(ch!='(')&&(ch!=')')&&(ch!='#') printf("输入串中有非法字符n"); exit(1); Bj=ch; j+; while(ch!='#'); l=j;/*分析串长度*/ ch=B0;/*当前分析字符*/ Atop='#' A+top='E'/*'#','E'进栈*/ printf("步骤tt分析栈 tt剩余字符 tt所用产生式 n"); do x=Atop-;/*x为当前栈顶字符*/ printf("%d",k+); printf("tt"); for(j=0;j<=5;j+)/*判断是否为终结符*/ if(x=v1j) flag=1; break; if(flag=1)/*如果是终结符*/ if(x='#') finish=1;/*结束标记*/ printf("acc!n");/*接受 */ getchar(); getchar(); exit(1); /*if*/ if(x=ch) print(); print1(); printf("%c匹配n",ch); ch=B+b;/*下一个输入字符*/ flag=0;/*恢复标记*/ /*if*/ else/*出错处理*/ print(); print1(); printf("%c出错n",ch);/*输出出错终结符*/ exit(1); /*else*/ /*if*/ else/*非终结符处理*/ for(j=0;j<=4;j+) if(x=v2j) m=j;/*行号*/ break; for(j=0;j<=5;j+) if(ch=v1j) n=j;/*列号*/ break; cha=Cmn; if(cha.origin!='N')/*判断是否为空*/ print(); print1(); printf("%c->",cha.origin);/*输出产生式*/ for(j=0;j<cha.length;j+) printf("%c",cha.arrayj); printf("n"); for(j=(cha.length-1);j =0;j-)/*产生式逆序入栈*/ A+top=cha.arrayj; if(Atop='')/*为空则不进栈*/ top-; /*if*/ else/*出错处理*/ print(); print1(); printf("%c出错n",x);/*输出出错非终结符*/ exit(1); /*else*/ /*else*/ while(finish=0);/*main*/ 运行结果（略）能力扩展实验完成达到实习目的之后，若尚有余力者，可进行如下能力扩展的训练： （1）对输入文法，它能判断是否为LL(1)文法，若是，则转（2）；否则报错并终止； （2）输入已知文法，由程序自动生成它的LL(1)分析表； （3）对于给定的输入串，应能判断识别该串是否为给定文法的句型。也可以对所选子集适当扩大或是增加相应功能如：扩充界符和保留字数目；允许实型常数；进行词法错误检查；最大范围扩充以至PASCAL语言所有字符的集合。附录预测分析程序（语法分析程序），分析对象为C语言源程序文件。 该分析程序有18部分组成：1首先定义各种需要用到的常量和变量；2判断一个字符是否在指定字符串中；3得到一个不是非终结符的符号；4分解含有左递归的产生式；5分解不含有左递归的产生式；6读入一个文法；7将单个符号或符号串并入另一符号串；8求所有能直接推出的符号；9求某一符号能否推出 ；10判断读入的文法是否正确；11求单个符号的FIRST；12求各产生式右部的FIRST；13求各产生式左部的FOLLOW；14判断读入文法是否为一个LL(1)文法；15构造分析表M；16总控算法；17一个用户调用函数；18主函数；头部定义#include<stdlib.h>#include<stdio.h>#include<string.h>int count=0; /*分解的产生式的个数*/int number; /*所有终结符和非终结符的总数*/char start; /*开始符号*/char termin50; /*终结符号*/char non_ter50; /*非终结符号*/char v50; /*所有符号*/char left50; /*左部*/char right5050; /*右部*/char first5050,follow5050; /*各产生式右部的FIRST和左部的FOLLOW集合*/char first15050; /*所有单个符号的FIRST集合*/char select5050; /*各单个产生式的SELECT集合*/char f50,F50; /*记录各符号的FIRST和FOLLOW是否已求过*/char empty20; /*记录可直接推出的符号*/char TEMP50; /*求FOLLOW时存放某一符号串的FIRST集合*/int validity=1; /*表示输入文法是否有效*/int ll=1; /*表示输入文法是否为LL(1)文法*/int M2020; /*分析表*/char choose; /*用户输入时使用*/char empt20; /*求_emp()时使用*/char fo20; /*求FOLLOW集合时使用*/
