Compilation principle knowledge points sorting

Select the judgment knowledge point record

• A compiler is a system software

• Split compiler “ All over ” It can make the compiler structure clear

• The work of each stage of the compiler involves table management and error handling

• BNF Is a widely used tool for describing grammar

• The object code generated by the compiler is not necessarily an executable program
  

• The result of any derivation of grammar recognition symbols is sentence pattern

• Lexical analysis is based on word formation rules

• In bottom-up parsing , It should be analyzed from the sentence

• The rules on which intermediate codes are generated are semantic rules

• Quaternion The intermediate code of is easy to optimize

• The connection between ternary expressions is realized through indicators , Quaternions are realized by temporary variables

• The advantage of the indirect ternary representation is the use of an indirect code table , Easy to optimize

• The advantage of quaternion expression is that it is easy to optimize , It is also convenient to change the watch

• The heap dynamic allocation application and the release of storage space comply with arbitrary principles

• Dynamic allocation storage allocation includes stack allocation and heap allocation

• Dynamic storage allocation , That is, dynamically allocate storage space for the amount in the source program during the running phase of the target program or operating system . Static storage is determined by the compiler

• FORTRAN Allocate by static storage ,C and Pascal The language adopts static and dynamic storage allocation strategies

• The purpose of storage organization and management in the running phase is to prepare for storage allocation in the running phase and improve the running speed of the target program

• The compiler uses the static hierarchy of procedures or functions that describe identifiers to distinguish the scope of identifiers

• Lexical analyzer as an independent stage makes the whole compiler structure more concise 、 clear , So lexical analyzer is better as a subroutine

• Backtracking must be avoided when using deterministic top-down analysis

• Compilers spend most of their time managing tables

• The characteristic of the interpreter is that the handler does not produce object code

• In the specification , Use handle to describe a conventionalized string

• The work of translating an assembler into an executable object program is done by the assembler

• During compilation , The task of the parser is ： Analyze how word strings form sentences and descriptions ; Analyze how statements and instructions form a program ; Analyze program structure

• If grammar G The language defined is an infinite set , Then the grammar must be recursive

• Source language the language used to write the compiled program

• The process of reading the entire input and processing it at each stage is called pass or lie

• NFA The initial state of can be multiple .DFA There is only one initial state of

• For any regular grammar G, There are regular expressions that define the same language r; For any regular expression r, There are regular grammars that generate the same language G

• Generally, it is not necessary to put all the basic work related to compilation in a single pass , It is not necessary to complete each basic work as an independent one , It is often the right combination

• To build effective top-down analyzers , Backtracking must be eliminated

• Operator priority analysis always specifies the leftmost prime phrase of the current sentence pattern , and LR The analytic method specifies a handle to the current sentence pattern

• LR The analysis method can find errors when scanning the input string from left to right , And can accurately point out the error location

• LR Parsing techniques can be applied to ambiguous grammars

• Attribute grammars that contain only comprehensive attributes are called S- Attributive grammar , It is L- A special case of attribute grammar

• DAG Figure shows the basic block , The flow graph reflects the relationship between basic blocks

Short answer

NFA And DFA The difference between
①NFA There can be several start States , and DFA Only one ;
②NFA Image of M Not a single valued function , and DFA The image of is a single valued function .

What is optimization ？ According to the program scope involved, it can be divided into several levels of optimization ？
Optimize ： Perform various equivalent transformations from the program , Starting from the transformed program , Can generate more effective object code
Local optimization ： Is an optimization done in a basic block , The quaternion sequence in a basic block can be completed ;
Global optimization ： It can only be completed on the basis of investigating the interrelationship and influence between the basic blocks .
Try to contact C Language , A brief description of the general compilation process of the source program , And briefly describe what technologies can be used ？
（1） Lexical analysis . Based on regular grammar , Scan the characters of the source program body from left to right , According to lexical rules, the minimum grammatical unit symbols with independent meanings are recognized , For the next phase of the parser to use .
（2） Syntax analysis . According to the given grammar rules , Identify each grammatical structure .
（3） Semantic analysis . Semantic analysis can determine the type 、 Type checking 、 Identify meaning and corresponding semantic processing ,
（4） Code optimization . Work to improve the quality of object code ., Change it into the same function 、 But more efficient optimized intermediate representation code .
（5） Target code generation . Transform the intermediate representation code into an equivalent object program , The target language code .

This paper briefly introduces the basic idea of writing lexical analysis program by hand
The basic idea of the manual implementation of lexical analysis program is :
(1) First, design attribute words based on a programming language ,
(2) Then design various forms ( Such as identifier table 、 Often scale . Symbol internal representation comparison table, etc ),
(3) Then draw the general control flow chart and the symbols 、 Program control flow chart of subroutines such as character fetching and identifier table checking ,
(4) Finally complete the programming and debugging .

There are several kinds of stored representations of grammar rules in computer memory ？

1. Replace symbols with integers , Replace the terminator with the sequence number in the terminator set , Use the sequence number in the nonterminal symbol set instead of the nonterminal symbol .
2. The grammar is designed as a data structure of chain representation .

This paper briefly introduces the basic work of semantic analysis
The semantic analysis phase analyzes the meaning of the source program , And make corresponding semantic processing .
(1) Determine the type . Determine the data type of the data object to which the identifier is associated .
(2) Type checking . According to the type rule of language , Check the type of the operation and the operation component .
(3) Identify meaning , And make corresponding semantic processing .
(4) Other static semantic checks . For example, control flow check .

Try to contact C The language describes the storage allocation policy at runtime
At runtime , Storage allocation strategies include static allocation strategies and dynamic storage allocation strategies .
Static allocation strategy ： The storage space requirements of each data target at runtime can be determined at compile time .
Dynamic storage allocation strategies include stack allocation strategy and heap allocation strategy .
Stack storage allocation , It is implemented by a stack like runtime stack , Contrary to static storage allocation , In a trestle storage scheme , The program's requirements for data areas are completely unknown at compile time , Only when it's running can we know , Stack storage allocation is based on the principle of "first in, last out" .
Heap storage allocation is specifically responsible for the memory allocation of the data structure that cannot be determined at the entrance of the module during compilation or runtime , Such as variable length strings and object instances . The heap is made up of large pieces of available or free blocks , The memory in the heap can be allocated and released in any order .

Try to explain the function of intermediate code （ advantage ） And its form .

Intermediate code is the product of analyzing the meaning of structural elements of programming language ,
(1) Usually not related to the machine , One semantic analyzer can be applied to multiple object code generators ;
(2) It is optimized independently of the machine , It helps to improve the quality of the object code ;
(3) Phased implementation reduces the development complexity of each stage , It is beneficial to the development of compiler itself .
form ： Abstract syntax tree 、 Anti Polish means 、 Quaternion sequence 、 Ternary sequence
Try to briefly describe the concept and classification of code optimization .
Concept ： Code optimization refers to all the work done at compile time to improve the quality of the target program .
classification ： To the extent relevant to the machine , It can be divided into machine related optimization and machine independent optimization .
From the perspective of optimization scope , It can be divided into local optimization and global optimization .
From the perspective of optimizing language level , Code optimization can be divided into optimization of intermediate presentation code and optimization of target language code .