【作者】 赵勇；

【导师】 刘磊；

【作者基本信息】 吉林大学 ， 计算机系统结构， 2005， 硕士

【摘要】 编译程序是计算机系统不可缺少的部分,是程序设计者的必备工具。学习并掌握编译程序的构造原理和实现技术,能够提高对程序设计语言的理解,提高程序设计,尤其是大型软件的设计能力。本文重点在于在SNL 语言中实现指针类型。指针类型作为现代语言的一个重要特征,在实际中得到了广泛的应用,对于它的实现无论对于掌握编译原理和对于构造一个实际的编译器都有着重要的意义。对于指针类型的实现本文主要从以下语法分析、语义分析、中间代码生成以及运行时存储空间的管理等方面进行说明。其中对语义分析和运行时空间的管理,特别是堆区的管理进行了重点介绍。运行时空间的管理,特别是堆区的管理,对于指针的实现起着关键的作用,本文对其进行了详细的探讨,并给出一个具体的实现来进行说明。更多还原

【Abstract】 This paper mainly introduced how to implement pointer type inSNL language.Pointer type implemented in compiler involves syntaxanlysis,semantic analysis,intermediate code generation andstorage-space manager.There are three general types of parsers for grammer.Universalparsing methods such as the Cocke-Younger-Kasami algorithm andEarley’s algorithm can parse any grammer.These methods, however,are too inefficient to use in production compilers. The methodscommonly used in compilers are classified as being either top-down orbottom-up.As indicated by their names, top-down parsers build parsetrees from the top(root) to the bottom(leaves), while bottom-up parsersstart from the leaves and work up to the root. In both cases, the inputto the parser is scanned from left to right, one symbol at a time. In thispaper, we use recursive-descent parsing method,a method of top-downmethod.In compiler syntax analysis phase, pointer type analysised onlycan complete pointer type defined and used is correct or not ingrammer,but it can not do more analysises, more analysises need workin semantic-analysis and type check phase. So mainly work in syntaxanalysis phase for pointer type is:Check pointer type defined in syntaxCheck pointer variable used in syntaxThe analysis for pointer type defined based on ordinarytypes,process rules is very simple. If type defined is pointer type,foreword token must to be identifier(ID). Pointer variable usedanalysis is a bit difficult. The token before this variable must to be aidentifier, in spite of variable identifier or field identifier. Variableidentifier and field identifier only define this pointer variable is asimple pointer type or a entry of record type.After lexical analysis and syntax analysis, the compiler mainlywok is semantic analysis phase. In this phase, compilers will use allkinds of symbol table technique for search. To determine thecorrection of pointer type in semantic, mainly problem is: Check pointer type defined in semantic Check pointer variable used in semantic Main work for checking pointer type defined in semantic is checking this variable is pointer type ? if yes, the usage of this variable is correct in semantic? The first question is so simple, we can do it just searching in symbol table, if searched it and it’s type is pointer type, express it is right, other is wrong. We must use iterate algorithm to process checking pointer variable used in semantic, as well as consumed a caret(^) notation at a loop statement, and checked it is pointer type in symbol table. In this phase , we also need involve foreword declaration and fill-back technique. The type checking for pointer, is analogue type checking forordinary type, because the pointer is mainly used in assign statementand as for arguments for procedures. First determine it is a pointer type,then compare their target type. if equal, it is right, otherwise wrong. The based question of dynamic-space manager is how to reply theuser’s request for allocing memory, and how to dealloc the memorythat user not used for the new request for allocing memory. firstquestion is simply, we only return a space that is free and size biggerenough, for deallocing, we must do more. We need combine adjacentfree-space, it can help to shrink fragment. There are 4 cases: 1. the left and right adjacent block is not free, in this case, we only release it and don’t do more. 2. the left block is free, but right is not. In this case, we combine this block and it’s left block to a block. 3. the right block is free but left is not. We do it as case 2. 4. the left block and right block are free. We need combine the three blocks into a block. The way is increasing the capacityp of the most left block size, and delete the right block node. This paper not involve is garbage collection. GC is character ofthe modern language,such as JAVA and C#. a great deal of work hasbeen done in the area of garbage collection algorithms. Any garbagecollection algorithm must do two basic things. First, it must detectgarbage objects, Second, it must reclaim the heap space used by thegarbage objects and make it avaiable to the program. Garbagedetection is ordinarily accomplished by defining a set of roots and更多还原