编译原理实验三.doc

2001编译原理实验三(pp3)说明文档实验目的实验三的目的是在实验一、二的基础上进行语义分析。要求对Decaf源程序进行类型检查和作用域检查。实验参考文档做实验之前，请仔细阅读一下材料：Decaf语法规范，Semantic Analysis(英文pdf文档)，如果你对Bison的部分使用方法不熟悉，请仔细阅读教材附录和bison附的帮助。软件工具和文档说明我们所使用的工具和实验二相同，主要文件列表如下：scanner.l/h词法分析器parser.y/h语法分析器需要修改hashtable.h/cpp我们提供的哈希表declaration.h/cpp我们提供的变量声明类decllist.h我们提供的list of declaration类scope.h/cpp变量作用域类需要修改type.h/cpp变量类型类typelist.h我们提供的list of type类loopstack.h/cpp函数嵌套栈utility.h/cpp实用工具semantic.h/cpp语义分析所用函数需要修改main.cmain函数test.decaf调试用例flex.exeflex工具bison.exe/simplebison工具fix.exe同pp1，修正头函数定义debug.bat完成flex，bison编译的批处理文件。pp3.dsp/dswpp3工程文件程序运行的方法以及sample目录和pp2一样。实验实现方法1 与pp2相比，pp3的每个语法符号都有相应的语义值，例如Variable是decl类型的。具体的赋值方法和定义方法可以参看教材附录C.3.6和bison说明相应部分。2 语义分析。在pp3的实验中，语义分析可以大致分为两个部分：类型检查和作用域检查。(参见semantic analysis)A. 类型检查。类型检查是检查程序是否符合程序语言的类型规范。例如，把一个字符串常量赋给了一个整形变量，在Decaf中就会导致类型不匹配。Decaf的类型包括base type和compound types。（Decaf语言规范）base types ：int, double, bool, stringcompound types ：arrays and classes. In Decaf, two base types are equivalent if and only if they are the exactly the same type. Two array types are equivalent if and only if they have the same element type(which it self may be a array). Two class types are equivalent if and only if they are the same exact type (即使两个类结构相同，也认为他们不是equivalent的)。在什么情况下需要注意类型匹配(equivalent)呢？ 变量赋值、函数传参、函数返回值都需要检查类型匹配。注：Decaf中函数返回值可以为void, 也可以为某个base type，相应的return语句也有两种，我们在检查的时候要检查以下3种情况：如果函数声明为void，则return语句不能跟参数，如果函数声明有某种类型，则函数体内必须有return语句且return语句必须返回相应的类型。对于函数声明了某种类型，但是在函数体内没有return语句这种情况，我们不做基本要求，供有兴趣的同学实现，另外两种要求实现。B. 作用域检查。Decaf的作用域规则（Decaf语言规范）： all variables, functions, and classes must be declared to prior to use identifiers within a scope must be unique (i.e. cannot have two functions of same name, a global variable and function of the same name, a global variable and a class of the same name, etc.) identifiers re-declared or re-defined with a nested scope shadow the version in the outer scope (i.e. it is legal to have a local variable with the same name as a global variable, a function within a class can have the same name as a global function, and so on.) declarations in the global scope are accessible anywhere in the program (unless they areshadowed by another use of the identifier) declarations in closed scopes are inaccessibleDecaf语言有四种scope：global scope, class scope, local scope for functions parameters and local scope for functions body。C. 类和继承。Decaf支持简单的继承（Decaf语言规范）。在pp3中我们仅仅纪录下子类的父类类型，此外this是每一个类的第一个成员变量。需要注意的是，class会给你带来一些小麻烦，例如，在识别出一个函数A后，我们要首先查找以前是否已经有A的定义，一般来说，如果前面已经有A的定义，则认为是重定义了，但是注意，它还有可能是子类对父类某个函数的的继承，这种情况下，我们认为它是正确的。D. 其他。除了以上的类型检查外，还有一些细小的地方需要检查，例如数组的越界检查，数组的index必须是integer型等，这些在Decaf语言规范中都有详细讲述。3 实验要求。这个实验比较难，是整个Decaf实验中最重要的部分，希望同学能够提早动手，以免无法按时完成。基本要求同学能实现Decaf语言的基本规范。扩展不做基本要求，仅供有兴趣且有余力的同学完成。Decaf语言的基本规范在英文文档Decaf语言基本规范中有具体描述，英文文档semantic analysis中讲述了一些语义分析的基本知识，对于进一步了解语义分析的知识和做扩展有很大帮助。Pp3/pp4同时交给同学们（好像没法同步了），文档和start files都放置在九号楼的ftp服务器上。提交的时候注意事项和pp2相同，就不再赘述了。4 Start files说明。Start files中declaration等只是一个近似的实现，如hashtable只是使用数组实现，所以同学们完全可以使用以前自己编的文件代替，但是需要注意的是由于hashtable的不同实现方法会导致最终输出结果的不同，所以hashtable就让它那样吧JSpecial Hints：Scope类的说明：在pp3中，只有一个全局变量scope，（我怎么找不到？hehe，scope类里面有一个static Scope* stackMaxNestLevel，就是它啦。）作用类似于符号表，记录着当前的