A Design And Practice Of Pointer Type Compiler In CML Language

This paper mainly introduced how to implement pointer type in CML language.Pointer type implemented in compiler involves syntax analysis, semantic analysis, intermediate code generation and storage-space manager.There are three general types of parsers for grammar. Universal parsing methods such as the Cocke-Younger-Kasami algorithm and Earley's algorithm can parse any grammar. These methods, however, are too inefficient to use in production compilers. The methods commonly used in compilers are classified as being either top-down or bottom-up. As indicated by their names, top-down parsers build parse trees from the top(root) to the bottom(leaves), while bottom-up parsers start from the leaves and work up to the root. In both cases, the input to the parser is scanned from left to right, one symbol at a time. In this paper, we use recursive-descent parsing method, a method of top-down method.In compiler syntax analysis phase, pointer type analysis only can complete pointer type defined and used is correct or not in grammar, but it can not do more analysis, more analysis need work in semantic-analysis and type check phase. So mainly work in syntax analysis phase for pointer type is:Check pointer type defined in syntaxCheck pointer variable used in syntaxThe analysis for pointer type defined based on ordinary types, process rules is very simple. If type defined is pointer type, foreword token must to be identifier (ID). Pointer variable used analysis is a bit difficult. The token before this variable must to be a identifier, in spite of variable identifier or field identifier. Variable identifier and field identifier only define this pointer variable is a simple pointer type or a entry of array type.After lexical analysis and syntax analysis, the compiler mainly wok is semantic analysis phase. In this phase, compilers will use all kinds of symbol table technique for search. To determine the correction of pointer type in semantic, mainly problem is:Check pointer type defined in semanticCheck pointer variable used in semanticMain work for checking pointer type defined in semantic is checking this variable is pointer type? If yes, the used of this variable is corrected in semantic? The first question is so simple, we can do it just searching in symbol table, if searched it and its 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 for ordinary type, because the pointer is mainly used in assign statement and as for arguments for procedures. First determine it is a pointer type, and then compare their target type. if equal, it is right, otherwise wrong.The based question of dynamic-space manager is how to reply the user's request for allocing memory, and how to dealloc the memory that user not used for the new request for allocing memory. First questi on is simply, we only return a space that is free and size bigger enough, for deallocing, we must do more. We need combine adjacent free-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. In this case ,we combine this block and it's right block to a block.4. The left block and right block are free. We need combine the three blocks into a block. The way is increasing the capacity of the most left block size, and deletes the right block node.This paper not involve is garbage collection. GC is character of the modern language, such as JAVA and C#. A great deal of work has been done in the area of garbage collection algorithms. Any garbage collection algorithm must do two basic things. First, it must detect garbage objects; second, it must reclaim the heap space used by the garbage objects and make it available to the program. Garbage detection is ordinarily accomplished by defining a set of roots and determining reachability from the roots. And object is reachable if there is some path of references from the roots. An object is reachable if there is some path of references from the roots by which the executing program can access the object. The roots are always accessible to the program. Any objects that are reachable from the roots are considered live. Objects that are not reachable are considered garbage, because them can no longer affect the future course of program execution. Two basic approaches to distinguishing live objects from garbage are reference counting and tracing. Reference counting garbage collectors distinguish live objects from garbage objects by keeping a count for each object on the heap. The count keeps track of the number of references to that object. Tracing garbage collectors, on the other hand, actually trace out the graph of references starting with the root nodes. Objects that are encountered during the track are marked in some way. After the trace is complete, unmarked objects are known to be unreachable and can be garbage collected.