《编译原理》实验指导书

编译原理实验指导书实验目的和内容编译原理实验的目的是使学生将编译理论运用到实际当中，实现一个简单语言集的词法、语法和语义分析程序，验证实际编译系统的实现方法，并加深对编译技术的认识。实验内容共需实现编译器的词法、语法和语义分析程序三个组成部分。要求学生必须完成每个实验的基本要求，并可尝试实验的扩展要求部分。实验报告要求每人针对每个实验上交一份实验报告，其中主要包括三方面内容：1、实验设计：实验采用的实现方法，如描述语言的文法，单词分类码表，状态转换图或状态矩阵等。具体的设计结果，应包括程序结构的描述，各部分主要功能的说明，以及所用数据结构的介绍等。2、程序代码：实验实现的源程序，要求符合一般的程序书写风格，并包括必要的注释。3、实验结果分析：程序的输入及输出，运行结果分析（至少包括一个正确和一个错误单词或语句的分析结果），改进设想等。注意事项1、电子版实验报告和源程序在最后一次机时后的一周内上交。（每个同学上交一个压缩文件，其命名格式为“学号_姓名.rar”，内含实验报告和一个命名为“源程序”的文件夹。注意：提交的源程序应是经过调试、测试成功的较为通用的程序，并应有相应的注释、运行环境和使用方法简介。）2、不接受不完整的实验报告和没有说明注释的源程序，或者说明与程序、运行结果不符合的作业。3、基本题是必须完成的，扩充部分可以选作。没有完成扩充部分的同学的上机实验的总成绩不高于90分；没有按时完成实验报告的同学的实验成绩不高于90分。实验一 词法分析程序实现一、实验目的与要求通过编写和调试一个词法分析程序，掌握在对程序设计语言的源程序进行扫描的过程中，将字符形式的源程序流转化为一个由各类单词符号组成的流的词法分析方法。二、实验内容根据教学要求并结合学生自己的兴趣和具体情况，从具有代表性的高级程序设计语言的各类典型单词中，选取一个适当大小的子集。例如，可以完成无符号常数这一类典型单词的识别后，再完成一个尽可能兼顾到各种常数、关键字、标识符和各种运算符的扫描器的设计和实现。输入：由符合或不符合所规定的单词类别结构的各类单词组成的源程序。输出：把单词的字符形式的表示翻译成编译器的内部表示，即确定单词串的输出形式。例如，所输出的每一单词均按形如（CLASS，VALUE）的二元式编码。对于变量和常数，CLASS字段为相应的类别码；VALUE字段则是该标识符、常数的具体值或在其符号表中登记项的序号（要求在变量名表登记项中存放该标识符的字符串；常数表登记项中则存放该常数的二进制形式）。对于关键字和运算符，采用一词一类的编码形式；由于采用一词一类的编码方式，所以仅需在二元式的CLASS字段上放置相应的单词的类别码，VALUE字段则为“空”。另外，为便于查看由词法分析程序所输出的单词串，要求在CLASS字段上放置单词类别的助记符。三、实现方法与环境词法分析是编译程序的第一个处理阶段，可以通过两种途径来构造词法分析程序。其一是根据对语言中各类单词的某种描述或定义（如BNF），用手工的方式（例如可用C语言）构造词法分析程序。一般地，可以根据文法或状态转换图构造相应的状态矩阵，该状态矩阵同控制程序便组成了编译器的词法分析程序；也可以根据文法或状态转换图直接编写词法分析程序。构造词法分析程序的另外一种途径是所谓的词法分析程序的自动生成，即首先用正规式对语言中的各类单词符号进行词型描述，并分别指出在识别单词时，词法分析程序所应进行的语义处理工作，然后由一个所谓词法分析程序的构造程序对上述信息进行加工。如美国BELL实验室研制的LEX就是一个被广泛使用的词法分析程序的自动生成工具。总的来说，开发一种新语言时，由于它的单词符号在不停地修改，采用LEX等工具生成的词法分析程序比较易于修改和维护。一旦一种语言确定了，则采用手工编写词法分析程序效率更高。四、基本实验题目1）题目1：试用手工编码方式构造识别以下给定单词的某一语言的词法分析程序。语言中具有的单词包括五个有代表性的关键字begin、end、if、then、else；标识符；整型常数；六种关系运算符；一个赋值符和四个算术运算符。参考实现方法简述如下。单词的分类：构造上述语言中的各类单词符号及其分类码表。表I 语言中的各类单词符号及其分类码表单词符号类别编码类别码的助记符单词值begin1BEGINend2ENDif3IFthen4THENelse5ELSE标识符6ID字母打头的字母数字串整常数7INT数字串8LT=9LE=10EQ11NE12GT=13GE:=14IS+15PL-16MI*17MU/18DI处理过程：在一个程序设计语言中，一般都含有若干类单词符号，为此可首先为每类单词建立一张状态转换图，然后将这些状态转换图合并成一张统一的状态图，即得到了一个有限自动机，再进行必要的确定化和状态数最小化处理，最后据此构造词法分析程序。在此为了使词法分析程序结构比较清晰，且尽量避免某些枝节问题的纠缠，假定要编译的语言中，全部关键字都是保留字，程序员不得将它们作为源程序中的标识符；在源程序的输入文本中，关键字、标识符、整常数之间，若未出现关系和算术运算符以及赋值符，则至少须用一个空白字符加以分隔。作了这些限制以后，就可以把关键字和标识符的识别统一进行处理。即每当开始识别一个单词时，若扫视到的第一个字符为字母，则把后续输入的字母或数字字符依次进行拼接，直至扫视到非字母、数字字符为止，以期获得一个尽可能长的字母数字字符串，然后以此字符串查所谓保留字表（此保留字表已事先造好），若查到此字符串，则取出相应的类别码；反之，则表明该字符串应为一标识符。采用上述策略后，针对表I中部分单词可以构造一个如图1所示的有限自动机（以状态转换图表示）。在图1中添加了当进行状态转移时，词法分析程序应执行的语义动作。根据图1，可用C语言编写出符合以上几项要求的一个相应的扫描器程序，如程序一所示。图1 识别表I所列语言中的部分单词的DFA及相关的语义过程图1及程序一中所出现的语义变量及语义函数的含义和功能说明如下。函数GETCHAR：每调用一次，就把扫描指示器当前所指示的源程序字符送入字符变量ch，然后把扫描指示器前推一个字符位置。字符数组TOKEN：用来依次存放一个单词词文中的各个字符。函数CAT：每调用一次，就把当前ch中的字符拼接于TOKEN中所存字符串的右边。函数LOOKUP：每调用一次，就以TOKEN中的字符串查保留字表，若查到，就将相应关键字的类别码赋给整型变量c；否则将c置为零。函数RETRACT：每调用一次，就把扫描指示器回退一个字符位置（即退回多读的那个字符）。函数OUT：一般仅在进入终态时调用此函数，调用的形式为OUT(c，VAL)。其中，实参c为相应单词的类别码或其助记符；当所识别的单词为标识符和整数时，实参VAL为TOKEN（即词文分别为字母数字串和数字串），对于其余种类的单词，VAL均为空串。函数OUT的功能是，在送出一个单词的内部表示之后，返回到调用该词法分析程序的那个程序。程序一 根据图1编写的扫描器# include # include # include # define ID 6# define INT 7# define LT 8# define LE 9# define EQ 10# define NE 11# define GT 12# define GE 13char TOKEN20；extern int lookup (char*);extern void out (int, char*);extern report_error (void);void scanner_example (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: report_error( ); break;return;提示：扫描器所用的若干函数以及主程序有待于具体编写，并需事先建立好保留字表，以备查询。另外，在扫描源程序字符串时，一旦识别出关键字、标识符、整常数以及运算符中之一，即以二元式形式（类别编码，值）输出单词。每次调用词法分析程序，它均能自动继续扫描下去，形成下一个单词，直至整个源程序全部扫描完毕，并形成相应的单词串形式的源程序。2）题目2：将表I单词集中的整常数改为无符号常数，修改题目1中已开发的扫描器。无符号常数的单词分类码助记符：UCON；其值为无符号常数的机内二进制表示。描述无符号数的BNF定义和状态转换图：无符号数的文法G如下：无符号数 d余留无符号数无符号数 小数部分无符号数 d余留无符号数 d余留无符号数余留无符号数 十进小数余留无符号数 E指数部分余留无符号数 d余留无符号数 十进小数 E指数部分十进小数 d十进小数十进小数 d小数部分 d十进小数小数部分 d指数部分 d余留整指数指数部分 +整指数指数部分 -整指数指数部分 d整指数 d余留整指数整指数 d余留整指数 d余留整指数余留整指数 d图2所示为上述文法的状态转换图，其中编号0、1、2、6分别代表非终结符号、及。图2 文法G的状态转换图实现无符号数识别的参考方法：在计算机内实现状态转换图的方法之一，是以状态图中的各个状态为行，以可能输入的各个输入符号为列，组成一个状态矩阵。其中，矩阵的元素用来指明下一个状态和扫描器应完成的语义动作（如拼接字符、数制转换、查填符号表以及输出单词的内部表示等）。由于在一个状态矩阵中，通常有许多状态都是出错状态，为了节省存放状态矩阵的存储空间，在具体实现时，常常采用更为紧凑和有效的数据结构。例如，对于文法G的状态转换图，可按表II的形式来存放其状态矩阵。表II中的第一列为各状态Si的编号，第二列分别列出了在每一状态下可能扫视到的输入符号aj（其中“other”是一个符号集合，用来表示在相应状态所属的那一栏中，除其前所列字符之外的全部其它字符），第三列指出当（Si,aj）出现时应执行的语义动作（通常用若干个语句来实现，若其后空，则表示不进行任何处理），最后一栏用来指明下一状态的编号（若其后NULL或“结束”则表示无后继状态）。状态矩阵中所嵌入的语义动作，其功能是在扫描源程序字符串的过程中，把识别出的字符串形式的无符号数，逐步转换为相应的二进制整数（ICON）或二进制浮点数（FCON）的内部形式，方法见教材第56页。（注：考虑能否采用C语言的库函数实现此语义处理工作。）表II 包含语义处理过程的识别无符号数的状态矩阵根据加入语义过程说明的状态转换图直接编写词法分析程序，部分实现代码如下：程序二 单词分类码为UCON的无符号数的识别程序1 #include 2 #include 3 #include 4 #define LETTER 05 #define DIGIT 16 #define POINT 27 #define OTHER 38 #define POWER 49 #define PLUS 510 #define MINUS 611 #define UCON 7 /Suppose the class number of unsigned constant is 712 #define ClassOther 20013 #define EndState -114 int w,n,p,e,d;15 int Class; /Used to indicate class of the word16 int ICON;17 float FCON;18 static int CurrentState; /Used to present current state, the initial value:01920 int GetChar (void);21 int EXCUTE (int,int)；22 int LEX (void)；23 int HandleOtherWord (void)24 return ClassOther;25 26 int HandleError (void)27 printf (Error!n); return 0;2829 int GetChar (void)30 31 int c;32 c=getchar ( );33 if(isdigit(c) d=c-0;return DIGIT;34 if (c=.) return POINT;35 if (c=E|c=e) return POWER;36 if (c=+) return PLUS;37 if (c=-) return MINUS;38 return OTHER;39 40 int EXCUTE (int state, int symbol)41 42 switch (state)43 44 case 0:switch (symbol)45 46 case DIGIT: n=0;p=0;e=1;w=d;CurrentState=1;Class=UCON;break;47 case POINT: w=0;n=0;p=0;e=1;CurrentState=3;Class=UCON;break;48 default: HandleOtherWord( );Class=ClassOther;49 CurrentState=EndState;50 51 break;52 case 1:switch (symbol)53 54 case DIGIT: w=w*10+d;break; /CurrentState=155 case POINT: CurrentState=2;break;56 case POWER: CurrentState=4;break;57 default: ICON=w;CurrentState=EndState;58 59 break；60 case 2:switch (symbol)61 62 case DIGIT: n+;w=w*10+d;break;63 case POWER: CurrentState=4;break;64 default: FCON=w*pow(10,e*p-n);CurrentState=EndState;65 66 break;67 case 3:switch (symbol)68 69 case DIGIT: n+;w=w*10+d;CurrentState=2;break;70 default: HandleError( )；CurrentState=EndState;71 72 break；73 case 4:switch (symbol)74 75 case DIGIT: p=p*10+d;CurrentState=6;break;76 case MINUS: e=-1;CurrentState=5;break;77 case PLUS: CurrentState=5;break;78 default: HandleError( );CurrentState=EndState;79 80 break；81 case 5:switch (symbol)82 83 case DIGIT: p=p*10+d;CurrentState=6;break;84 default: HandleError( );CurrentState=EndState;85 86 break;87 case 6:switch (symbol)88 89 case: DIGIT:p=p*10+d;break;90 default: FCON=w*pow(10,e*p-n);CurrentState=EndState;91 92 break;93 94 return CurrentState;95 96 int LEX (void)97 98 int ch;99 CurrentState=0;100 while (CurrentState!=EndState)101 102 ch=GetChar( );103 EXCUTE (CurrentState,ch);104 105 return Class;106 五、扩展要求1、在词法分析过程中建立变量名表和常数表，以备以后的编译过程（如语法分析）查询；扩充关键字的数目、增加单词类别（如逻辑运算符等）、将常数分成字符串常量、整型常量和实型常量等；添加词法分析中单词出错的位置和错误类型的检查。2、识别一个程序设计语言（如C语言或其大小适宜的一个子集）所有单词的词法分析程序设计。建议利用LEX系统。六、注意1、上机前的准备：完成词法分析程序的程序流图，并选择好相应的数据结构。2、编程：用C语言或你熟悉的其它高级程序设计语言编写一个规模适当的扫描器。3、调试：将各个模块连接成一个完整程序，并整体调试成功。4、测试：用于测试扫描器的实例源文件中应有词法正确的，也应有错误的字符串。5、输出结果：以文件形式输入的例子至少应包含两行以上的源代码，并以对照的形式将扫描器的分析结果输出，必要时给出正误信息。