编译原理编译原理编译原理 (6).ppt

Chapter 1 Introduction Bootstrapping and PortingThere is a strong interaction between the algorithms used by the phases of a compiler and the data structures that support these phases.Algorithms need to be implemented in efficient manner.The choice of data structures is importantCompilerS2Major Data Structures in CompilerCompilerS3Temporary FilesIntermediate CodeThe Literal TableThe Symbol TableThe Syntax TreeTokensData StructuresWhen a scanner collects characters into a token,it represents the token symbolically as a value of an enumerated data type representing a set of tokens of the source languageSometimes,it is necessary to preserve the character string itself or other information derived from itThe name associated with an identifier tokenThe value of a number tokenIn most languages the scanner needs to generate one token at a time(single symbol lookahead)A single global variable can be used to hold the token information.CompilerS4TokensThe syntax tree is constructed as a standard pointer-based structure that is dynamically allocated as parsing proceeds.The tree can be kept as a single variable pointing to the root node.Each node is a record.Its fields represent the information collected by the parser and the semantic analyzer.Sometimes these fields are dynamically allocatedCompilerS5The Syntax TreeThis data structure keeps information associated with identifiers,functions,variables,constants,and data types.The symbol table interacts with almost every phase of the compiler.The insertion,deletion access operations need to be efficient.A standard data type for this purpose is the hash table.CompilerS6The Symbol TableStores constants and strings used in the program.Quick insertion and lookup are essential.Need not allow deletions.CompilerS7The Literal TableDepending on the kind of intermediate code,it may be kept as An array of text stringsA temporary text fileLinked list of structuresCompilerS8Intermediate CodeComputers did not possess enough memory for an entire program to be kept in memory during compilation.This was solved by using temporary files to hold the products of intermediate steps.Memory constrains are now much smaller problem.Occasionally,compilers generate intermediate files during some of the steps.CompilerS9Temporary Files