城市学院编译原理试验参考指导书

《编译原理》试验指导书适用试验课时：30适用对象：城市学院计算机系

试验目标和内容编译原理试验目标是使学生将编译理论利用到实际当中，实现一个简单语言集词法分析程序、语法分析程序和简单语义处理程序，验证实际编译系统实现方法，并加深对编译理论认识。基础试验分为三个部分，试验一识别无符号数词法分析器设计实现、试验二无符号数算术四则运算LR语法分析器设计实现，试验三是无符号数算术四则运算语义处理程序实现，总试验课时为30课时。要求每个学生独立完成全部试验要求。每部分基础试验还包含若干扩展试验，供编程能力较强学生自愿进行。

试验一词法分析程序实现一、试验目标和要求经过编写和调试一个词法分析程序，掌握在对程序设计语言源程序进行扫描过程中，将字符形式源程序流转化为一个由各类单词符号组成流词法分析方法。二、试验内容选择无符号数算术四则运算中各类单词为识别对象，要求将其中各个单词识别出来。输入：由无符号数和+，－，*，/,(,)组成算术表示式，如1.5E+2－100。输出：对识别出每一单词均单行输出其类别码（无符号数值暂不要求计算）。三、实现方法和环境1、首先设计识别各类单词状态转换图。描述无符号常数确实定、最小化状态转换图图1所表示。其中编号0，1，2，…，6代表非终止符号<无符号数>、<余留无符号数>、<十进小数>、<小数部分>、<指数部分>、<整指数>及<余留整指数>，1，2和6为终态，分别代表整数、小数和科学计数识别结束状态。图1文法G[<无符号数>]状态转换图其中编号0，1，2，…，6代表非终止符号<无符号数>、<余留无符号数>、<十进小数>、<小数部分>、<指数部分>、<整指数>及<余留整指数>，1，2和6为终态，分别代表整数、小数和科学计数识别结束状态。在一个程序设计语言中，通常全部含有若干类单词符号，为此可首先为每类单词建立一张状态转换图，然后将这些状态转换图合并成一张统一状态图，即得到了一个有限自动机，再进行必需确实定化和状态数最小化处理，最终据此结构词法分析程序。四则运算算术符号识别很简单，直接在状态图0状态分别引出对应标识矢线至一个新终态即可。依据自己习惯，也能够将其转换为状态矩阵形式。2、词法分析程序编写依据描述语言中各类单词文法状态转换图或状态矩阵，利用某种语言（C语言或JAVA语言）直接编写词法分析程序。3、词法分析程序测试用于测试扫描器实例源文件中应有词法正确，也应有错误字符串，对于输入测试用例源程序文件，以对照形式将扫描器分析结果信息在输出文件中表示出来。四、参考资料实现无符号数识别参考方法：将设计状态转换图直接转化为一张程序步骤图，并在外层再增加一个以EOF为循环终止条件while循环，即形成能连续识别各类单词词法分析程序。各类单词编码提议如表1。表1单词内部编码单词符号类别码（CLASS）单词值（VALUE）无符号数1数字值+2无值－3无值*4无值/5无值(6无值)7无值五、扩展试验1、试对基础试验识别单词种类进行扩充，结构识别以下单词词法分析程序。语言中含有单词包含五个有代表性关键字begin、end、if、then、else；标识符；整型常数；六种关系运算符；一个赋值符和四个算术运算符。参考实现方法简述以下。表2扩展单词分类码表单词符号类别编码类别码助记符单词值begin1BEGINend2ENDif3IFthen4THENelse5ELSE标识符6ID字母打头字母数字串整常数7INT数字串<8LT<=9LE=10EQ<>11NE>12GT>=13GE:=14IS+15PL-16MI*17MU/18DI处理过程：在此为了使词法分析程序结构比较清楚，且尽可能避免一些枝节问题纠缠，假定要编译语言中，全部关键字全部是保留字，程序员不得将它们作为源程序中标识符；在源程序输入文本中，关键字、标识符、整常数之间，若未出现关系和算术运算符和赋值符，则最少须用一个空白字符加以分隔。作了这些限制以后，就能够把关键字和标识符识别统一进行处理。即每当开始识别一个单词时，若扫视到第一个字符为字母，则把后续输入字母或数字字符依次进行拼接，直至扫视到非字母、数字字符为止，以期取得一个尽可能长字母数字字符串，然后以此字符串查所谓保留字表（此保留字表已事先造好），若查到此字符串，则取出对应类别码；反之，则表明该字符串应为一标识符。采取上述策略后，针对表2中部分单词能够结构一个图2所表示有限自动机（以状态转换图表示）。在图2中添加了当进行状态转移时，词法分析程序应实施语义动作。依据图2，可用C语言编写出符合以上几项要求一个对应扫描器程序，如程序一所表示。图2识别表I所列语言中部分单词DFA及相关函数图2所出现变量及函数含义和功效说明以下：函数GETCHAR：每调用一次，就把扫描指示器目前所指示源程序字符送入字符变量ch，然后把扫描指示器前推一个字符位置。字符数组TOKEN：用来依次存放一个单词词文中各个字符。函数CAT：每调用一次，就把目前ch中字符拼接于TOKEN中所存字符串右边。函数LOOKUP：每调用一次，就以TOKEN中字符串查保留字表，若查到，就将对应关键字类别码赋给整型变量c；不然将c置为零。函数RETRACT：每调用一次，就把扫描指示器回退一个字符位置（即退回多读那个字符）。函数OUT：通常仅在进入终态时调用此函数，调用形式为OUT(c，VAL)。其中，实参c为对应单词类别码或其助记符；当所识别单词为标识符和整数时，实参VAL为TOKEN（即词文分别为字母数字串和数字串），对于其它种类单词，VAL均为空串。函数OUT功效是，在送出一个单词内部表示以后，返回到调用该词法分析程序那个程序。参考程序：#include<stdio.h>#include<ctype.h>#include<string.h>#defineID6#defineINT7#defineLT8#defineLE9#defineEQ10#defineNE11#defineGT12#defineGE13charTOKEN[20]；externintlookup(char*);externvoidout(int,char*);externreport_error(void);voidscanner_example(FILE*fp){charch;inti,c;ch=fgetc(fp);if(isalpha(ch))/*itmustbeaidentifer!*/{TOKEN[0]=ch;ch=fgetc(fp);i=1;while(isalnum(ch)){TOKEN[i]=ch;i++；ch=fgetc(fp);}TOKEN[i]=′＼0′fseek(fp,-1,1);/*retract*/c=lookup(TOKEN);if(c==0)out(ID,TOKEN);elseout(c,"")；}elseif(isdigit(ch)){TOKEN[0]=ch;ch=fgetc(fp);i=1;while(isdigit(ch)){TOKEN[i]=ch;i++;ch=fgetc(fp);}TOKEN[i]=′＼0′；fseek(fp,-1,1);out(INT,TOKEN);}elseswitch(ch){case′＜′:ch=fgetc(fp);if(ch==′=′)out(LE,"");elseif(ch==′＞′)out(NE,"");else{fseek(fp,-1,1);out(LT,"");}break;case′=′:out(EQ,"");break;case′＞′:ch=fgetc(fp);if(ch==′=′)out(GE,"");else{fseek(fp,-1,1);out(GT,"");}break;default:report_error();break;}return;}提醒：扫描器所用若干函数和主程序有待于具体编写，并需事先建立好保留字表，以备查询。比如：/*建立保留字表*/#defineMAX_KEY_NUMBER20/*关键字数量*/#defineKEY_WORD_END“waitingforyourexpanding”/*关键字结束标识*/char*KeyWordTable[MAX_KEY_NUMBER]={“begin”,“end”,“if”,“then”,“else”,KEY_WORD_END};/*查保留字表，判定是否为关键字*/intlookup(char*token){inti=0;while(strcmp(KeyWordTable[n],KEY_WORD_END))/*strcmp比较两串是否相同，若相同返回0*/{if(!strcmp(KeyWordTable[n],token))/*比较token所指向关键字和保留字表中哪个关键字相符*/{returnn+1;/*设置正确关键字类别码，并返回这类别码值*/break;}n++;}return0;/*单词不是关键字，而是标识符*/}另外，在扫描源程序字符串时，一旦识别出关键字、标识符、整常数和运算符中之一，即以二元式形式（类别编码，值）输出单词到指定文件中。每次调用词法分析程序，它均能自动继续扫描下去，形成下一个单词，直至整个源程序全部扫描完成，并形成对应单词串形式源程序。2、在词法分析过程中建立变量名表和常数表，以备以后编译过程（如语法分析）查询；扩充关键字数目、增加单词类别（如逻辑运算符等）、将常数分成字符串常量、整型常量和实型常量等；添加词法分析中单词犯错位置、错误类型检验，和删除注释部分等。

试验二语法分析程序实现一、试验目标和要求经过设计、编制、调试经典SLR（1）语法分析程序，实现对试验一所得词法分析程序所提供单词序列进行语法检验和结构分析，深入掌握常见语法分析方法。二、试验内容选择对多种常见高级程序设计语言全部较为通用语法结构无符号数算术四则运算作为分析对象，给出其文法描述（注意应和所采取语法分析方法比较贴近），设计并实现一个完整语法分析程序。输入：由试验一输出单词类别串，如1，3，1。输出：对于所输入源程序，假如输入符号串是给定文法定义正当句子，则输出“RIGHT”，而且给出每一步归约过程；假如不是句子，即输入串有错误，则输出“ERROR”，而且显示已经归约出各个文法符号，和必需犯错说明信息。三、实现方法和环境首先依据算术四则运算语法定义，结构SLR（1）分析表。无符号数算术四则运算语法可表示为：E->E+T|E-T|TT->T*F|T/F|FF->(E)|i2、语法分析程序编写设置输入缓冲区、状态栈、符号栈，并依据SLR（1）分析表利用某种语言（C语言或JAVA语言）直接编写移进、归约、接收子程序，编写语法分析程序。3、语法分析程序测试用于测试实例源文件中应有语法正确，也应有语法错误符号串，以对照形式将分析结果信息在输出文件中表示出来。四、扩展试验1、对以下复合语句进行语法分析器设计和实现。G[<复合语句>]：<复合语句>→begin<语句表>end<语句表>→<语句>|<语句>;<语句表><语句>→<赋值语句><赋值语句>→<变量>:=<算术表示式><算术表示式>→<项>|<算术表示式>+<项>|<算术表示式>-<项><项>→<因式>|<项>*<因式>|<项>/<因式><因式>→<变量>|<常数>|(<算术表示式>)<变量>→<标识符><标识符>→<标识符><字母>|<标识符><数字>|<字母><常数>→<整数>|<浮点数><整数>→<数字>|<数字><整数><浮点数>→•<整数>|<整数>•<整数><字母>→A|B|C|…|X|Y|Z|a|b|c|…|x|y|z<数字>→0|1|2|…|92、增强语法检验功效，对犯错位置、错误类型给提醒。

试验三语义分析程序实现一、试验目标和要求经过设计、编制、调试一个简单语义处理分析程序，实现对试验一和试验二所得单词和语句语义信息简单处里，深入掌握语义处理内容和简单方法。二、试验内容对试验一进行扩展，对识别无符号数进行计值，并将输出形式改为（类别码，值）二元式形式。对试验二进行扩展，在语法分析基础上，增加语义操作来实现语法制导翻译。对于给定文法中每一产生式，编写对应语义子程序。在语法分析过程中，每当用一产生式进行推导或归约时，语法分析程序除实施对应语法分析动作之外，还要调用对应语义子程序，计算并输出算术表示式值。将试验一和试验二程序合并，以能对完整输入源文件进行词法分析生成中间文件，然后进行语法制导翻译，输出最终翻译结果。输入：由无符号数和+，—，*，/,(,)组成算术表示式。输出：假如输入单词串是正当无符号数算术四则运算，输出运算结果，而且给出每一步分析过程；假如不是无符号数算术四则运算，输出“非法四则运算表示式”。三、基础试验题目对试验一中每个无符号数识别状态插入计值处理，最终取得无符号数取值。对试验二进行扩展，在归约（分析表中归约动作已经反应了运算优先级）处理子程序中加入计值处理，接收子程序中加入输出算数表示式值处理。四、参考资料和无符号数状态转换图对应包含语义处理过程（据此可计算求得无符号数数字值）状态矩阵和参考程序以下所表示。表3包含语义处理过程识别无符号数状态矩阵依据加入语义过程说明状态转换图直接编写词法分析程序，部分实现代码以下：1#include<stdio.h>2#include<ctype.h>3#include<math.h>4#defineLETTER05#defineDIGIT16#definePOINT27#defineOTHER38#definePOWER49#definePLUS510#defineMINUS611#defineUCON7//Supposetheclassnumberofunsignedconstantis712#defineClassOther20013#defineEndState-114intw,n,p,e,d;15intClass;//Usedtoindicateclassoftheword16intICON;17floatFCON;18staticintCurrentState;//Usedtopresentcurrentstate,theinitialvalue:01920intGetChar(void);21intEXCUTE(int,int)；22intLEX(void)；23intHandleOtherWord(void)24{returnClassOther;25}26intHandleError(void)27{printf("Error!＼n");return0;}2829intGetChar(void)30{31intc;3233if(isdigit(c)){d=c-′0′;returnDIGIT;}34if(c==′.′)returnPOINT;35if(c==′E′||c==′e′)returnPOWER;36if(c==′+′)returnPLUS;37if(c==′-′)returnMINUS;38returnOTHER;39}40intEXCUTE(intstate,intsymbol)41{42switch(state)43{44case0:switch(symbol)45{46caseDIGIT:n=0;p=0;e=1;w=d;CurrentState=1;Class=UCON;break;47casePOINT:w=0;n=0;p=0;e=1;CurrentState=3;Class=UCON;break;48default:HandleOtherWord();Class=ClassOther;49CurrentState=EndState;50}51break;52case1:switch(symbol)53{54caseDIGIT:w=w*10+d;break;//CurrentState=155casePOINT:CurrentState=2;break;56casePOWER:CurrentState=4;break;57default:ICON=w;CurrentState=EndState;58}59break；60case2:switch(symbol)61{62caseDIGIT:n++;w=w*10+d;break;63casePOWER:CurrentState=4;break;64default:FCON=w*pow(10,e*p-n);CurrentState=EndState;65}66break;67case3:switch(symbol)68{69caseDIGIT:n++;w=w*10+d;CurrentState=2;break;70default:HandleError()；CurrentState=EndState;71}72break；73case4:switch(symbol)74{75caseDIGIT:p=p*10+d;CurrentState=6;break;76caseMINUS:e=-1;CurrentState=5;break;77casePLUS:CurrentState=5;break;78default:HandleError();CurrentState=EndState;79}80break；81case5:switch(symbol)82{83caseDIGIT:p=p*10+d;CurrentState=6;break;84default:HandleError();CurrentState=EndState;85}86break;87case6:switch(symbol)88{89case:DIGIT:p=p*10+d;break;90default:FCON=w*pow(10,e*p-n);CurrentState=EndState;91}92break;93}94returnCurrentState;95}96intLEX(void)97{98intch;99CurrentState=0;100whi