搜索
《编译原理》实验指导书实验目的和内容编译原理实验的目的是使学生将编译理论运用到实际当中，实现一个简单语言集的词法、语法和语义分析程序，验证实际编译系统的实现方法，并加深对编译技术的认识。实验内容共需实现编译器的词法、语法和语义分析程序三个组成部分。要求学生必须完成每个实验的基本题目要求，有余力的同学可尝试实验的扩展要求部分。实验报告要求每人针对所完成的实验内容上交一份实验报告，其中主要包括三方面内容：1、实验设计：实验采用的实现方法和依据（如描述语言的文法及其机内表示，词法分析的单词分类码表、状态转换图或状态矩阵等，语法分析中用到的分析表或优先矩阵等，语法制导翻译中文法的拆分和语义动作的设计编写等）；具体的设计结果（应包括整体设计思想和实现算法，程序结构的描述，各部分主要功能的说明，以及所用数据结构的介绍等）。2、程序代码：实验实现的源程序，要求符合一般的程序书写风格，并包括必要的注释。3、实验结果分析：自行编写若干源程序作为测试用例，对所生成的编译程序进行测试（编译程序的输入与输出以文件的形式给出）；运行结果分析（至少包括一个正确和一个错误单词或语句的运行结果）；以及改进设想等。另外，在实验报告的最后，欢迎每位同学写上对每个实验的收获、体会，特别是希望和建议，以利于今后不断改进教学，积累经验。注意事项1、电子版实验报告和源程序在最后一次机时后的一周内上交。（每个同学上交一个压缩文件，其命名格式为“学号_姓名.rar”，内含实验报告和一个命名为“源程序”的文件夹。注意提交的源程序应是经过调试、测试成功的较为通用的程序，并应有相应的注释、运行环境和使用方法简介。）2、不接受不完整的实验报告和没有说明注释的源程序，或者说明与程序、运行结果不符合的作业。特别鼓励：扩展题目1、为亲身经历一个小型编译器的开发全过程，触摸一下与实际编译器开发相关的工作，大家可以自由组成3人左右的小组，推举组长，模拟一个团队分工协作开发大型软件的实战环境，融入软件工程的思想规范和一般理论方法，初步体验从系统分析设计、编码测试到交付维护的一个完整编译器软件的开发过程。要求组长为每个小组成员分配主要负责的任务，完成相应的分析设计员、程序员和测试员等角色的工作，并以小组为单位提交一份实验报告和源程序，在报告封面上写明每个同学主要完成和负责的部分。2、以组为单位完成的实验内容至少必须整合词法、语法和语义三个部分的实验，对于选定的适当规模的文法（如C语言的一个大小适宜的子集），进行系统的总体设计、功能分析、编码测试等工作。完成一个从对源程序的词法分析开始，到中间代码生成的完整的编译器前端的开发，使所涉及到的编译系统的各个组成模块有机地衔接在一起，提交一份完整的实验报告和源程序，并将以下几个方面描述清楚：1）任务概述2）系统的设计3）系统实现（包括框图，各.h和.c文件说明，所有函数功能的说明，数据结构、各种表格、变量等的说明，以及函数调用关系图等）4）系统工作过程及运行说明（使用操作指南）5）源程序清单（要求有详细注释）和实例程序运行结果6）体会和讨论3、实验题目1）参考题目：在词法、语法和语义三个基本实验题目的基础上，完成以下扩展部分的要求：实验一：（1）扩充关键字的数目、增加单词类别（如分界符、逻辑运算符等）、将常数分成字符串常量、整型常量和实型常量等；添加词法分析中单词出错的位置、加细错误类型的检查以及删除注释部分等；并考虑如何在词法分析阶段建立变量名表和常数表，以备后续的编译过程查询。（2）选作：识别一个程序设计语言（如C语言）所有单词的词法分析程序设计。建议自学LEX系统。实验二：（1）至少完成文法G2[复合语句]的两种典型的语法分析程序的设计与实现。（2）在所给文法G2[复合语句]的基础上，适当扩大分析对象，增加功能。如赋值语句的左部不再只局限于简单变量和常数，可以是下标变量等；右部的算术表达式中可以包括函数调用、数组元素等。除赋值语句外，还可进一步选择高级语言的其它语法结构类型，如流程控制语句、子程序结构语句、说明语句等。语法分析的结果以语法树的形式输出，并显示分析过程的信息（如分析栈、符号栈、当前应被归约的最左子串、归约后所得的符号等）。（3）增强错误检查和处理能力。例如，当输入的源程序存在错误时，把所发现的每一处错误的性质（错误编码）和位置填入一张表中，以备以后输出之用；同时再跳过错误所在的语法范畴（如单词、表达式、语句等），继续对输入串的后续部分进行编译。至于对错误的具体处理措施应结合所采用的语法分析方法，以LR分析为例，可对LR分析表中的空白单元进行出错原因分析，填入一个指向出错处理子程序的指示字。（4）选作：学习编译器的自动生成工具LEX、YACC（或其它类似工具）的使用方法，运用LEX和YACC编写并生成以下文法G[程序]所定义语言的词法和语法分析程序。G[程序]：程序→PROGRAM标识符;分程序分程序→变量说明BEGIN语句表END.变量说明→VAR变量说明表;变量说明表→变量表:类型|变量表:类型;变量说明表类型→INTEGER|REAL变量表→变量|变量,变量表语句表→语句|语句;语句表语句→赋值语句|条件语句|WHILE语句|复合语句赋值语句→变量:=算术表达式条件语句→IF关系表达式THEN语句ELSE语句WHILE语句→WHILE关系表达式DO语句复合语句→BEGIN语句表END算术表达式→项|算术表达式+项|算术表达式-项项→因式|项*因式|项/因式因式→变量|常数|(算术表达式)关系表达式→算术表达式关系符算术表达式变量→标识符标识符→标识符字母|标识符数字|字母常数→整数|浮点数整数→数字|数字整数浮点数→•整数|整数•整数关系符→|=|=||=|字母→A|B|C|…|X|Y|Z|a|b|c|…|x|y|z数字→0|1|2|…|9实验三：（1）增加语义分析的范围，如进一步完成布尔表达式（参见教材P200）、常见程序流程控制语句（参见教材P205）等的翻译。（2）语法制导翻译过程的可视化处理，选择编译各阶段用到的典型算法实现其动态演示。（3）选作：完成实验二中文法G[程序]所定义的语言的语法制导翻译程序。2）自拟题目：根据小组成员的兴趣自主选择或自定实验题目。要求先提交一份申请文档，说明所选题目、实现方案和技术路线；然后小组成员再与教师就题目的难易程度和工作量具体讨论调整，细化课程设计内容，最终确定要完成的主要工作；在得到老师的认可之后方可继续进行。实验一词法分析程序实现一、实验目的与要求通过编写和调试一个词法分析程序，掌握在对程序设计语言的源程序进行扫描的过程中，将字符形式的源程序流转化为一个由各类单词符号组成的流的词法分析方法。二、实验内容根据教学要求并结合学生自己的兴趣和具体情况，从具有代表性的高级程序设计语言的各类典型单词中，选取一个适当大小的子集。例如，可以完成无符号常数这一类典型单词的识别后，再完成一个尽可能兼顾到各种常数、关键字、标识符和各种运算符的扫描器的设计和实现。输入：由符合和不符合所规定的单词类别结构的各类单词组成的源程序文件。输出：把单词的字符形式表示翻译成编译器的内部表示，确定单词串的输出形式，并将其结果放到某个文件中。要求所输出的每一单词均按形如（CLASS，VALUE）的二元式编码。对于变量和常数，CLASS字段为相应的类别码；VALUE字段则是该标识符、常数的具体值或在其符号表中登记项的序号（要求在变量名表登记项中存放该标识符的字符串；常数表登记项中则存放该常数的二进制形式）。对于关键字和运算符，采用一词一类的编码形式；由于采用一词一类的编码方式，所以仅需在二元式的CLASS字段上放置相应的单词的类别码，VALUE字段则为“空”。不过，为便于查看由词法分析程序所输出的单词串，要求在CLASS字段上放置单词类别的助记符。三、实现方法与环境词法分析是编译程序的第一个处理阶段，可以通过两种途径来构造词法分析程序。其一是根据对语言中各类单词的某种描述或定义（如BNF），用手工的方式（例如可用C语言）构造词法分析程序。一般地，可以根据文法或状态转换图构造相应的状态矩阵，该状态矩阵连同控制程序一起便组成了编译器的词法分析程序；也可以根据文法或状态转换图直接编写词法分析程序。构造词法分析程序的另外一种途径是所谓的词法分析程序的自动生成，即首先用正规式对语言中的各类单词符号进行词型描述，并分别指出在识别单词时，词法分析程序所应进行的语义处理工作，然后由一个所谓词法分析程序的构造程序对上述信息进行加工。如美国BELL实验室研制的LEX就是一个被广泛使用的词法分析程序的自动生成工具。总的来说，开发一种新语言时，由于它的单词符号在不停地修改，采用LEX等工具生成的词法分析程序比较易于修改和维护。一旦一种语言确定了，则采用手工编写词法分析程序效率更高。四、基本实验题目题目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：一般仅在进入终态时调用此函数，调用的形