2011城市学院“编译原理”实验指导书.docVIP

《编译原理》实验指导书 适用实验课时：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=10EQ11NE12GT=13GE:=14IS+15PL-16MI*17MU/18DI处理过程：在此为了使词法分析程序结构比较清晰，且尽量避免某些枝节问题的纠缠，假定要编译的语言中，全部关键字都是保留字，程序员不得将它们作为源程序中的标识符；在源程序的输入文本中，关键字、标识符、整常数之间，若未出现关系和算术运算符以及赋值符，则至少须用一个空白字符加以分隔。作了这些限制以后，就可以把关键字和标识符的识别统一进行处理。即每当开始识别一个单词时，若扫视到的第一个字符为字母，则把后续输入的字母或数字字符依次进行拼接，直至扫视到非字母、数字字符为止，以期获得一个尽可能长的字母数字字符串，然后以此字符串查所谓保留字表（此保留字表已事先造好），若查到此字符串，则取出相应的类别码；反之，则表明该字符串应为一标识符。采用上述策略后，针对表2