第五章符号表

第五章符号表编译器的语义分析阶段的任务是：将变量的定义与它们的各个使用联系起来，检查每一个表达式是否有正确的类型，并将抽象语法转换为更简单的、适合于生成机器代码的表示。语义分析阶段的一个主要的工作是符号表的管理，符号表（symboltable）也称为环境（environment），其作用是将标识符映射到它们的类型和存储位置。在处理类型、变量和函数的声明时，这些标识符便与其在符号表中的“含义”相绑定。每当发现标识符的使用（即非声明性出现）时，便在符号表中查看它们的含义（即类型检查）。编译器的一个基本功能是记录源程序中使用的标识符并收集与每个标识符相关的各种属性信息。标识符的属性信息表明了该标识符的存储位置，类型，作用域（在哪段程序中有效）等信息。当一个标识符是过程名时，它的属性信息还包括诸如参数的个数与类型，每个参数的传递方法（如传地址方式）以及返回值的类型等信息。符号表是一个数据结构。每个标识符在符号表中都有一条记录，记录的每个域对应于该标识符的一个属性。这种数据结构允许我们快速地找到每个标识符的记录，并在该记录中快速地存储和检索信息。当源程序中的一个标识符被词法分析器识别出来时，词法分析器将在符号表中为该标识符建立一条记录。但是标识符的属性一般不能在词法分析中确定。例如，在如下的Pascal源程序的声明varposition,initial,rate:real;中，当position,initial,rate被词法分析器识别时，它们的数据类型（real）还是未知的。标识符的属性信息将由词法分析以后的各阶段陆续写入符号表，并以各种方式被使用。例如，当进行语义分析和中间代码生成时，我们需要知道标识符是哪种类型，以便检查源程序是否正确地使用了这些标识符，并在它们之上生成正确的操作。代码生成器将赋予标识符的存储位置信息写入符号表，而且代码生成器还要使用符号表中标识符的存储位置信息。在这一章中我们主要针对简单C语言的编译器给出符号表的设计及实现。5.1符号类型与定义1．VarInfo名称类型说明var_namestring变量名var_typestring变量类型（只支持int和用户自定义类型）var_modifierstring变量修饰符。0:protected1:public2:privateisarrayint数组标记。0表示简单变量，1表示数组变量arraysizeint数组大小。仅当isarray等于1时有效rvaint含义较复杂，请见下面的说明表5.1VarInfo的设计Rva:是Relativevirtualaddress的简写。在不同的上下文中有不同的含义，如表所示。全局变量相对于全局变量起始位置偏移(全局变量一般从0开始)局部变量局部变量声明相对于第一个的偏移(函数的第一个局部变量rva为0)函数参数参数声明相对于第一个的偏移(函数的第一个参数rva从0开始)catch块参数无意义①成员变量成员变量声明相对于第一个成员(包括从父类继承来的成员)的偏移，从0开始表5.2rva在不同上下文中的含义2．FunInfoFunInfo是全局函数和成员函数的主类。函数声明包括：函数名、返回类型、参数个、参数列表、局部变量的个数（这里同时可以表示出局部变量所占空间的大小）以及局部变量列表入口地址（需要在代码生成的时候进行填写）。名称类型说明fun_idint函数标识符fun_namestring函数名ret_typestring0:void1:int2:user_defined_typepara_sizeint这里表示的是所有局部变量所占空间的大小；数组的时候可能占多个空间paravar_listHashtable用来列出所有的参数变量的位置local_sizeintHashtablelocalvar_listentry_addrint入口地址表5.3FunInfo的设计①实际上由于catch块参数当作局部变量处理了，catch块参数rva是从当前函数最后一个局部变量的rva+1处开始编号。5.2符号表的生成1．准备工作---生成语法分析树在前面已经介绍了符号类型与定义，在这个部分里面我们还要讨论的问题是如何根据输入的抽象语法树生成符号表。为了讨论的方便，我们采用自顶向下，逐步求精的方法，逐步介绍各个生成符号表中比较重要的模块。首先要介绍的是analyze.cs这个文件，Analyze.Main这个函数是analyze的主入口，它的流程如下所示：Input:abstractsyntaxtreefile(anvalidXMLfile)nameArgumentsarg[0](string)Output:Symboltablefile(anvalidXMLfile),FilesourceFileName_SymbolTable.xmlProcedureMainBeginvarinputfile:=arg[0];ifinputfile=nullthen{complainingerrorsandreturn}Varpr:=newParser.ParserReader(inputfile);pr.ReadXML();Varroot:=pr.GetRoot();Varsymtable:=newAnalyzerLib.SymbolTable(inputfile);//BuildaParser.TreeNodetypeTreerepresentationofsyntaxtree.Ifrootnullthensymtable.BuildSymbolTable(root);Else{codesforprintingerrormessage}//DoingtypecheckongeneratedsymboltableVartc=AnalyzerLib.typeCheck(inputfile,symtable);Tc.DoTypeCheck();End下面介绍一下ParserLib.ParserReader.ReadXML,这个函数主要做的是从XML文档中定为第一个元素名为tree的点，并由此生成表示抽象语法树(ParserLib.TreeNode)形式的一棵树。Input:abstractsyntaxtreefile(anvalidXMLfile)name,MemberParserLib.ParserReader.parserfile(XmlDocument)Output:TreeNodeTypeobjectthatrepresentsabstractsyntaxtree,MemberParserLib.ParserReader.root(TreeNode)ProcedureParserLib.ParserReader.ReadXML()BeginXnode:=thefirstchildelementofparserfilewithtagname“tree”;Whilexnode.name“tree”doXnode:=xnode.FirstChild;Root:=GetNode(xnode);End;接着要说的是ParserLib.ParserReader.GetNode,这个函数根据一个XmlNode类型的XML元素(element)转化生成一个TreeNode类型的树结构。ProcedureParserLib.ParserReader.GetNode(XmlNodecurNode)Input:AXMLnodeinfileParserLib.ParserReader.parserfile,ParcurNode(XmlNode)Output:AParserLib.TreeNodeobjectrepresentingtheXmlelementsVarreturnNode(TreeNode)FunctionGetNode(curNode:XmlNode)BeginIfcurNode=nullthenreturn;ifcurNode.Name=“tree”thenbeginreturnNode:=ParserLib.ParserReader.GenTreeNode();/*ceachingGenTreeNodetoconvertanXmlnodetoParserLib.TreeNode,thenassigntoreturnNode*/ifcurNodehassiblingthen{buildingreturnNode.siblingwithiterativeceachoncurNode.sibling}IfcurNodehaschildthenForeachchildxi∈curNode’schildrendo{buildingreturnNode.child[i]withiterativeceachonxi}EndElseifcurNode.Name=“child”then{buildingandreturingcurNode.FirstChildwithiterativeceach}End;前面的GetNode中出现了一个函数GenTreeNode，该函数的作用是将一个Xml节点转化为一个ParserLib.ParserReader.TreeNode节点。其逻辑相对来说比较简单，这里就不再赘述了。自此，扫描语法分析文件，并生成一棵ParserLib.TreeNode类型语法树的工作就已完成。2．由抽象语法树生成符号表(1).符号表类SymTable首先要介绍的是表示符号表的类AnalyzeLib.SymTable。下面就Analyze.SymTable各字段含义介绍如下：globalSymTable：全局变量符号表，这是一个哈希表结构，它的键(key)是全局变量名，值(value)是该全局变量对应的AnalyzeLib.VarInfo②对象引用。funSymTable：全局函数符号表，哈希表结构，它的键是全局函数名，值是该全局函数对应的AnalyzeLib.FunInfo对象引用。classSymTable：类符号表，哈希表结构，它的键是类名，值是该类对应的AnalyzeLib.ClassInfo对象引用。extype_table：异常符号表，哈希表结构，它的键是异常类型名，值是该异常对象对应的analyzeLib.ExTypeItem对象引用。Sw：符号表输出对象，AnalyzeLib.SymtableWriter类型，作用是将符号表输出到一个有效的、命名为sourceFileName_SymbolTable.xml的文档中。fun_ID,try_ID,catch_ID,globalRva：分别用来记录函数Id,try块Id，catch块Id,和全局变量的偏移量。由于fun_ID,try_ID,catch_Id,globalRva对于每个函数，try块，catch块和全局变量都有唯一的值，因此，这4个字段都定义为静态变量，从0开始计数。(2).buildSymTable注意到，前面介绍Analyze.Main函数的时候，有一步作的符号表的生成，其入口函数时AnalyzeLib.SymTable.buildSymTable,现就将buildSymTable介绍如下:Input:rootofanabstractsyntaxtree,oftypeTreeNodeParr(TreeNode)Output:XMLfilerepresentingthesymboltablederivedfromabstractsyntaxtreeFilesourceFileName_SymbolTable.xmlFunctionbuildSymTable(r:TreeNode);BeginWhilernulldoBeginCaser.NodeTypeofClassDecl:Begin{ProcessclassdeclarationwithmethodProcessClass}{addpairofclass_name,ClassInfo_refpro