...menustart
...menuend
- analysis
- The analysis part breaks up the source program into constituent pieces and imposes a grammatical structure on them
- It then uses this structure to create an intermediate representation of the source program.
- If it detects that the source program is either syntactically ill formed or semantically unsound, then it must provide informative messages
- The analysis part also collects information about the source program and stores it in a data structure called a symbol table, which is passed along with the intermediate representation to the synthesis part.
- synthesis
- The synthesis part constructs the desired target program from the intermediate representation and the information in the symbol table.
- The symbol table, which stores information about the entire source program, is used by all phases of the compiler.
- The analysis part is often called the front end of the compiler; the synthesis part is the back end.
- The first phase of a compiler is called lexical analysis or scanning
- lexical analysis groups source code characters into meaningful sequences called lexemes.
- For each lexeme, the lexical analyzer produces as output a token of the form
- < token-name, attribute-value >
- the 1st component token-name is an abstract symbol that is used during syntax analysis
- the 2nd component attribute-value points to an entry in the symbol table for this token
- Information from the symbol-table entry is needed for semantic analysis and code generation
For example:
position = initial + rate * 60
- position is a lexeme that would be mapped into a token < id, 1 >, where id is an abstract symbol standing for identifier and 1 points to the symbol table entry for position.
- The symbol-table entry for an identifier holds information about the identifier, such as its name and type.
- The assignment symbol = is a lexeme that is mapped into the token < = > . Since this token needs no attribute-value, we have omitted the second component.
- We could have used any abstract symbol such as assign for the token-name, but for notational convenience we have chosen to use the lexeme itself as the name of the abstract symbol.
- initial is a lexeme that is mapped into the token < id,2 > , where 2 points to the symbol-table entry for initial.
-
- is a lexeme that is mapped into the token < + >.
- rate is a lexeme that is mapped into the token < id, 3 > , where 3 points to the symbol-table entry for rate.
- * is a lexeme that is mapped into the token < * >.
- 60 is a lexeme that is mapped into the token < 60 >
- Technically speaking, for the lexeme 60 we should make up a token like < number, 4 > , but we shall defer the discussion of tokens for numbers until Chapter 2.
Blanks separating the lexemes would be discarded by the lexical analyzer.
After lexical analysis as the sequence of tokens
<id, 1> <=> <id, 2> <+> <id, 3> <*> <60>
The second phase of the compiler is syntax analysis or parsing.
- The parser create a tree-like intermediate representation that depicts the grammatical structure of the token stream.
- by using the first components of the tokens produced by the lexical analyzer
- A typical representation is a syntax tree
- in which each interior node represents an operation
- and the children of the node represent the arguments of the operation.
- A syntax tree for the token stream is shown as :
This tree shows the order in which the operations in the assignment position = initial + rate * 60 are to be performed.
- The tree has an interior node labeled * with (id, 3) as its left child and the integer 60 as its right child.
- The node (id, 3) represents the identifier rate.
- The node labeled * makes it explicit that we must first multiply the value of rate by 60.
- The node labeled + indicates that we must add the result of this multiplication to the value of initial.
- The root of the tree, labeled =, indicates that we must store the result of this addition into the location for the identifier position.
- This ordering of operations is consistent with the usual conventions of arithmetic which tell us that multiplication has higher precedence than addition, and hence that the multiplication is to be performed before the addition.
The subsequent phases of the compiler use the grammatical structure to help analyze the source program and generate the target program.
- context-free grammars
- syntax-directed definitions
- The semantic analyzer checks the source program for semantic consistency with the language definition.
- by using the syntax tree and the information in the symbol table
- It also gathers type information and saves it in either the syntax tree or the symbol table
- for subsequent use during intermediate-code generation.
- An important part of semantic analysis is type checking, where the compiler checks that each operator has matching operands.
- For example, many programming language definitions require an array index to be an integer the compiler must report an error if a floating-point number is used to index an array.
- The language specification may permit some type conversions called coercions (强制转换).
- For example, a binary arithmetic operator may be applied to either a pair of integers or to a pair of floating-point numbers.
- If the operator is applied to a floating-point number and an integer, the compiler may convert or coerce the integer into a floating-point number.
- Suppose that position, initial, and rate have been declared to be floating-point numbers
- and that the lexeme 60 by itself forms an integer
- The type checker discovers that the operator * is applied to a floating-point number rate and an integer 60
- In this case, the integer may be converted into a floating-point number
- notice that the output of the semantic analyzer has an extra node for the operator inttofloat, which explicitly converts its integer argument into a floating-point number
- In the process of translating a source program into target code, a compiler may construct one or more intermediate representations
- which can have a variety of forms.
- Syntax trees are a form of intermediate representation;
- they are commonly used during syntax and semantic analysis.
- After syntax and semantic analysis of the source program, many compiliers generate an explicit low-level or machine-like intermediate representation
- which we can think of as a program for an abstract machine.
- This intermediate representation should have two important properties:
- it should be easy to produce and it should be easy to translate into the target machine.
- In Chapter 6, we consider an intermediate form called three-address code which consists of a sequence of assembly-like instructions with 3 operands per instruction.
- Each operand can act like a register.
There are several points worth noting about three-address instructions.
- First, each three-address assignment instruction has at most one operator on the right side.
- Thus, these instructions fix the order in which operations are to be done;
- the multiplication precedes the addition in the source program.
- Second, the compiler must generate a temporary name to hold the value computed by a three-address instruction.
- Third, some "three-address instructions" like the first and last , have fewer than three operands.
- The machine-independent code-optimization phase attempts to improve the intermediate code so that better target code will result.
- Usually better means faster, but other objectives may be desired, such as shorter code, or target code that consumes less power.
- A simple intermediate code generation algorithm followed by code optimization is a reasonable way to generate good target code.
- The optimizer can deduce that the conversion of 60 from integer to floating point can be done once and for all at compile time
- so the inttofloat operation can be eliminated by replacing the integer 60 by the floating-point number 60.0.
- Moreover, t3 is used only once to transmit its value to id1 so the optimizer can transform into the shorter sequence.
- The code generator takes as input , an intermediate representation of the source program
- and maps it into the target language.
- If the target language is machine code, registers or memory locations are selected for each of the variables used by the program.
- Then, the intermediate instructions are translated into sequences of machine instructions that perform the same task.
- A crucial aspect of code generation is the judicious assignment of registers to hold variables.
For example, using registers R1 and R2.
- The first operand of each instruction specifies a destination.
- The F in each instruction tells us that it deals with floating-point numbers.
- The code loads the contents of address id3 into register R2,
- then multiplies it with floating-point constant 60.0.
- The # signifies that 60.0 is to be treated as an immediate constant.
- The third instruction moves id2 into register R1
- and the fourth adds to it the value previously computed in register R2.
- Finally, the value in register R1 is stored into the address of id1
This discussion of code generation has ignored the important issue of storage allocation for the identifiers in the source program. As we shall see in Chapter 7, the organization of storage at run-time depends on the language being compiled. Storage-allocation decisions are made either during intermediate code generation or during code generation.
-
An essential function of a compiler is to record the variable names used in the source program and collect information about various attributes of each name.
-
These attributes may provide information about the storage allocated for a name
- its type, its scope (where in the program its value may be used), and in the case of procedure names,
- such things as the number and types of its arguments,
- the method of passing each argument (for example, by value or by reference), and the type returned.
-
The symbol table is a data structure containing a record for each variable name, with fields for the attributes of the name.
- The data structure should be designed to allow the compiler to find the record for each name quickly
- and to store or retrieve data from that record quickly.
-
The discussion of phases deals with the logical organization of a compiler.
-
In an implementation, activities from several phases may be grouped together into a pass that reads an input file and writes an output file.
- For example, the front-end phases of lexical analysis, syntax analysis, semantic analysis, and intermediate code generation might be grouped together into one pass.
- Code optimization might be an optional pass.
- Then there could be a back-end pass consisting of code generation for a particular target machine.
-
Some compiler collections have been created around carefully designed in termediate representations that allow the front end for a particular language to interface with the back end for a certain target machine.
-
With these collections, we can produce compilers for different source languages for one target machine by combining different front ends with the back end for that target machine.
-
Similarly, we can produce compilers for different target machines, by combining a front end with back ends for different target machines.
These tools use specialized languages for specifying and implementing specific components, and many use quite sophisticated algorithms.
The most successful tools are those that hide the details of the generation algorithm and produce components that can be easily integrated into the remainder of the compiler. Some commonly used compiler-construction tools include:
- Parser generators that automatically produce syntax analyzers from a grammatical description of a programming language.
- Scanner generators that produce lexical analyzers from a regular-expression description of the tokens of a language.
- Syntax-directed translation engines that produce collections of routines for walking a parse tree and generating intermediate code.
- Code-generator generators that produce a code generator from a collection of rules for translating each operation of the intermediate language into the machine language for a target machine.
- Data-flow analysis engines that facilitate the gathering of information about how values are transmitted from one part of a program to each other part. Data-flow analysis is a key part of code optimization.
- Compiler-construction toolkits that provide an integrated set of routines for constructing various phases of a compiler.