compile

lexical analysis

The task of lexical analysis is to process words composed of characters, scan the source program character by character from left to right, generate word symbols one by one, and transform the source program as a character string into an intermediate program of word symbol strings. The program that performs lexical analysis is called a lexical analysis program or scanner.

The word symbols in the source program are analyzed by the scanner and generally produce a binary type: word type; the value of the word itself. Word categories are usually coded with integers. If a category contains only one word symbol, then for this word symbol, the category code completely represents its own value. If a category contains many word symbols, then for each word symbol, in addition to the category code, it should also give its own value.

The lexical analyzer generally has two methods of construction: manual construction and automatic generation. The manual construction can use the state diagram to work, and the automatic generation is realized by using the limited finite automaton.

Parsing

The grammar analyzer of the compiler takes word symbols as input, analyzes whether the word symbol strings form grammatical units that conform to the grammar rules, such as expressions, assignments, loops, etc. Finally, to see if they form a program that meets the requirements, according to the grammar used in the language Rule analysis checks whether each statement has the correct logical structure, and the program is the final grammatical unit. The grammar rules of the compiler can be described by context-free grammars.

There are two methods of grammatical analysis: top-down analysis and bottom-up analysis. From top to bottom is to start from the beginning of the grammar, deduce downward, and deduce sentences. The bottom-up analysis method uses the shift-in reduction method. The basic idea is: use a registered symbol to advance the stack, move the input symbols into the stack one by one, when the top of the stack forms a production one In the case of a candidate, this part of the top of the stack is reduced to the left-most symbol of the production.

Intermediate code

Intermediate code is an internal representation of the source program, or intermediate language. The role of the intermediate code is to make the structure of the compiler more logically simple and clear, especially to make the optimization of the target code easier to implement the intermediate code, that is, the intermediate language program, the complexity of the intermediate language is between the source language and Between machine languages. Intermediate languages come in many forms, common ones are inverse Polish notation, quaternary, ternary, and tree.

Code optimization

Code optimization refers to multiple equivalent transformations of the program, so that starting from the transformed program, a more effective target code can be generated. The so-called equivalence means that the running result of the program is not changed. The so-called effective mainly refers to the short running time of the target code and the small storage space occupied. This transformation is called optimization.

There are two types of optimization: one is to optimize the intermediate code after the syntax analysis, it does not depend on the specific computer; the other is to generate the target code, which depends to a large extent on the specific computer. For the former type of optimization, it can be divided into three different levels of local optimization, loop optimization and global optimization according to the scope of the program involved.

Object code

Object code generation is the final stage of compilation. The target code generator transforms the grammatically analyzed or optimized intermediate code into target code. The target code has three forms:

① Machine language code that can be executed immediately, all addresses are relocated;

② The machine language modules to be assembled, when they need to be executed, are connected by the connection loader to some running programs and converted into executable machine language codes;

③ Assembly language code must be assembled by an assembler to become an executable machine language code.

The target code generation stage should consider three issues that directly affect the speed of the target code: first, how to generate shorter target code; second, how to make full use of the registers in the computer to reduce the number of times the target code accesses the storage unit; third, how to fully Use the characteristics of the computer command system to improve the quality of the target code.

Form management

Various information of the source program is kept in various tables during the compilation process, and the work of each stage of compilation involves constructing, searching, or updating the related tables.

The common auxiliary part of the compiler. Manage various quantities in the source program and register in the corresponding table. Obtain the required information by looking up the table when the compiler is processed.

Error handling

If errors are found in the source program during compilation, the compiler should report the nature of the error and the location of the error, and limit the impact of the error to the smallest possible range so that the rest of the source program can continue to be compiled Going forward, some compilers can automatically correct errors, and these tasks are completed by the error handler.

It should be noted that, generally speaking, the compiler only does syntax check and the simplest semantic check, but does not check the logic of the program.