Compiling principle questions - with answers

One 、 Judgment questions （）
1． One LL(l) Grammar must be unambiguous . ( N)
2． Any language produced by formal grammar can be described by context free grammar . ( N)
3． A transition graph contains only a finite number of States , One of them is considered to be the initial state , There is at most one final state . ( Y)
4． When object code is generated , We should consider how to make full use of the registers of the computer . ( N)
5． The expression expressed by the inverse Polish method is also known as the prefix . (Y )
6． If a grammar has a sentence corresponding to two different grammar trees , Call this grammar ambiguous . (Y )
7．LR Method is a top-down grammar analysis method . ( N)
8． The address calculation of array elements is related to the storage mode of the array .( N)
9． The operator priority relation table does not necessarily have a corresponding priority function . (N )
10． Storage allocation of data space , FORTRAN Adopt dynamic storage allocation strategy . (N )
Refer to the answer ：
1、× 2、× 3、√ 4、× 5、√
6、√ 7、× 8、× 9、× 10、×

Two ． Completion （ Every empty 2 branch , common 20 branch ）

1. Different compilers may have different storage allocation strategies for data space , However, there are two schemes used in most compilers ： Static storage allocation scheme and dynamic storage allocation scheme , The latter is divided into （1） and （2） .
2. Norms and regulations are the most important （3） Statute .
3. The working process of compiler is generally divided into 5 Stages ： Lexical analysis 、（4） 、 Semantic analysis and intermediate code generation , Code optimization and （5） . And then there is （6） And error handling .
   4． expression x+yz/(a+b) The suffix of is （7） .
   5． The attributes of grammatical symbols include comprehensive attributes and （8）.
   6． Suppose a binary array is stored in rows , And each element occupies a storage unit , The array a[1…15,1…20] Some element a[i,j] The address calculation formula is （9）.
   7． Local optimization is limited to one （10） An optimization within the scope .
   answer ：
   (1) Stack dynamic storage allocation
   (2) Heap dynamic storage allocation
   (3) Left
   (4) Syntax analysis
   (5) Target code generation
   (6) Form management
   (7) xyzab+/+
   (8) Inheritance attribute
   (9) a+(i-1)*20+j-1
   (10) Basic block

3、 ... and ． choice question （ Every question 2 branch , common 20 branch ）

1. A context free grammar G There are four components ： A set of terminators , A set of non terminators , One （C ）, And a group of Generative formula .
   A． character string B． Generative formula C． Start symbol D． Grammar

2. The basic block of a program is （D ）.
A． A subroutine B． A statement with only one entry and one exit
C． A program segment without nesting D． A set of sequentially executed program segments , There is only one entrance and one exit

3. In the common syntax analysis methods of high-level language compiler , Recursive descent analysis belongs to （ B） Analysis method .
   A． From left to right B． The top-down C． Bottom up D． From right to left

4． In common parsing methods ,（A ） It is especially suitable for the analysis of expressions .
A． Operator first analysis B． LR analysis
C． Recursive descent analysis D． LL（1） analysis

5． After compiling, the target program is （ D）.
A． Quaternion sequence B． Indirect ternary sequence
C． Binary sequence D． Machine language program or assembly language program
6. With grammar G[I]： I I → I1|I0|Ia|Ic|a|b|c
In the following symbol string is the of the grammar sentence （ B）.
① ab0 ② a0c01 ③ aaa ④ bc10
The options are ：
A． ① B．②③④ C．③④ D．①②③④
7. The basic block of a program is （ D）.
A． A subroutine B． A statement with only one entry and one exit
C． A program segment without nesting D． A set of sequentially executed program segments , There is only one entrance and one exit
8. In the common syntax analysis methods of high-level language compiler , Recursive descent analysis belongs to （B ） Analysis method .
A． From left to right B． The top-down C． Bottom up D． From right to left
9． After compiling, the target program is （ D）.
A． Quaternion sequence B． Indirect ternary sequence
C． Binary sequence D． Machine language program or assembly language program
10． The purpose of storage organization and management in the operation stage is （ C）.
① Improve the running speed of the compiler ② Save compiler storage space
③ Improve the running speed of the target program ④ Prepare for storage allocation during run-time
The options are ：
A. ①② B. ②③ C. ③④ D. ④②
Four 、 Short answer （ Each question 10 branch , common 30 branch ）

1. Known grammar G[S] by ：
   S→dAB
   A→aA|a
   B→Bb|ε
   G[S] What is the resulting language ？
   Refer to the answer ：
   answer ：G[S] The resulting language is L(G[S])={danbm│n≥1,m≥0}.

2. sketch DFA And NFA What's the difference ?
   Refer to the answer ：
   answer ：DFA And NFA There are two differences between : One is NFA There can be several start States , and DFA Only one start state . On the other hand ,DFA Mapping of M It's from K×∑ To K, and NFA Mapping of M It's from K×∑ To K Subset , Namely mapping M Will produce a set of States （ May be an empty set ）, Instead of a single state .

3. What is optimization ？ According to the program scope involved, which levels of optimization can be divided into ？
   Refer to the answer ：
   (1) Optimize ： Perform various equivalent transformations on the program , Starting from the transformed program , Can produce more effective object code .　　　 　　　　　
   (2) Three levels ： Local optimization 、 Cycle optimization 、 Global optimization .

5、 ... and 、 Calculation questions （ common 20 branch ）
Consider the following grammar :
D →　T V
T →　int | float
V → id ,V | id
The left common factor is extracted from the grammar .
Construct a non terminator for the resulting grammar First The collection and Follow aggregate .
Explain that the grammar obtained is LL(1) Grammar .
Construct... For the resulting grammar LL(1) Analysis of the table
Suppose there is an input string int x,y,z Write the corresponding LL(1) Program action analysis
answer ：
a. Grammar has left common factor , The grammar after extracting the left common factor is ：
　　 D →　T V
T →　int | float
V → id V’
V’→ ,V |ε

b.
non-terminal
First aggregate
Follow aggregate

D
{ int , float }
{ $ }

T
{ int , float }
{ id }

V
{ id }
{ $ }

V’
{ , , ε }
{ $ }

c. (1) First ( TV ) = { int , float }
First(int) ∩ First(float)={int}∩{float}=φ;
First(id V’)={id};
First(,V) ∩First(ε)={,} ∩{ ε}}=φ;
(2) V’=>ε,
First(V’)∩Follow(V’)= { , , ε }∩{ $ }=φ
according to LL(1) The definition and judgment of grammar , This grammar is LL(1) Grammar ;