Key points of compilation principle examination in 2021-2022 academic year [overseas Chinese University]

2021-2022 Key points of compilation principle examination in the academic year

notes ： Please refer to Compile the principle experiment report

A term is used to explain

• compiler ： Compile phase , User input source program , The target program is translated by the compiler , The target program accepts input data at run time , Get data output

• Interpreter ： Combine the translation of the source program with the operation of the target program , Translate a source program , Then execute it , This way is called interpretation

  memory ： The function of compiler and interpreter is to translate and run the target program , The compiler separates the two , The interpreter performs translation and operation at the same time .

• Lexical analysis ： According to lexical rules , Identify each mark in the source program （token）, Every token Represents a class of words （lexeme）

• Syntax analysis ： According to the rules of grammar , Identify the grammatical structure in the token stream , And construct a parsing tree that reflects the structure

• Semantic analysis ： According to semantic rules , Static semantic check of syntax tree , Ensure that the sentences with correct structure are also semantically correct

• Intermediate code generation ： According to the results of semantic analysis, intermediate code independent of specific machine is generated , Then the intermediate code is interpreted and executed according to the specific machine

• Intermediate code optimization ： The generation of intermediate code is mechanical and fixed , Equivalent transformation of intermediate code , Improve the time and space efficiency of code

• Target code generation ： Transform intermediate code into instruction code running on a specific machine

• The symbol table ： Record information about symbols in the source program , After reasonable organization , Fast at all stages of the compiler 、 Accurate addition, deletion, modification, query and other operations

• Error handling ： It is irresponsible to make the compiler stop working when encountering an error , Therefore, the compiler should have a wide range of error checking capabilities , Accurately report the type and location of errors

• Language ： Language $L$ Is a finite alphabet $\Sigma$ Set of finite length symbol strings on

• Normal form ： Limited alphabet $\Sigma$ Normal forms and normal sets on $L$ For the definition of

  1. $ϵ$ It's normal ,$L(ϵ)=\{ϵ\}$
  2. $a\in \Sigma$,$a$ It's normal ,$L(a)=\{a\}$
  3. $r,s$ It's normal , Corresponding to normal set $L(r),L(s)$, be
     1. $r|s$ It's normal ,$L(r|s)=L(r)\cup L(s)$
     2. $rs$ It's normal ,$L(rs)=L(r)L(s)$
     3. $r^{\ast }$ It's normal ,$L(r^{\ast })=(L(r){)}^{\ast }$
     4. $(r)$ It's normal ,$L((r))=L(r)$

  memory ： Define the normal form on the finite alphabet and its corresponding normal set , First $ϵ$ It's normal , Its normal set is $\{ϵ\}$. secondly , Each letter in the alphabet forms a normal form , The corresponding normal set is the set of this letter . Then define the basic operation of normal form ： Or operations 、 Join operation 、 Closure operations 、 Brackets specify priority .

• Pattern ： Rules for generating and recognizing words

• mark ： According to some rules （ Pattern ） Identified elements

• NFA：Nondeterministic Finite Automata（ Indefinite finite state machine ） It's a quintuple $(Q,\Sigma ,\delta ,S,F)$, among

  1. $Q$ Is a set of finite states
  2. $\Sigma$ Is a finite alphabet , Include $ϵ$
  3. $\delta$ Is the state transition function ,$\delta$ Is a multivalued function , The definition is as follows ：
     $$\delta :Q\times \Sigma \to 2^Q$$
     among ,$2^Q$ yes $Q$ Power set of .
  4. $S$ Is the initial state set ,$S\subseteq Q$
  5. $F$ Is the final state set ,$F\subseteq Q$

• DFA：Deterministic Finite Automata（ Deterministic finite state machine ） It's a quintuple $(Q,\Sigma ,\delta ,S,F)$, among

  1. $Q$ Is a set of finite states
  2. $\Sigma$ Is a finite alphabet
  3. $\delta$ Is the state transition function ,$\delta$ Is a single valued function , The definition is as follows ：
     $$\delta :Q\times \Sigma \to Q$$
  4. $S$ Is the only initial state ,$S\in Q$
  5. $F$ Is the final state set ,$F\subseteq Q$

  memory ： And NFA comparison ,DFA With certainty , therefore DFA Of $\Sigma$ It doesn't contain $ϵ$、$\delta$ Is a single valued mapping function 、$S$ Is the only initial state .

• Context-free grammar ： Four tuple $(V_N,V_T,P,S)$, among

  1. $V_N$ Is a finite set of non terminators
  2. $V_T$ Is a finite set of terminators
  3. $P$ Is a finite set of production , Each production type is like $A\to \alpha$,$\alpha \in (V_N\cup V_T{)}^{\ast }$
  4. $S$ Is the starting sign of grammar

• Terminator ： The inseparable basic symbols that make up a language

• non-terminal ： The left part of the production can derive the symbol or symbol string

• Grammar production ： Recursively describe the sentence pattern composed of terminator and non terminator . The general form is ：$\alpha \to \beta$. among ,$\alpha ,\beta \in (V_N\cup V_T{)}^{\ast }$, And $\alpha$ Contains at least one non terminator

• deduction ： Start with grammar symbols $S$ Start , Use production repeatedly , Replace the left nonterminal character of the production with the right grammatical symbol sequence , Until you get a terminator sequence

• reduction ： Is the inverse process of derivation , Replace the right part with the left part of production repeatedly , Until the input string analysis is completed

• Sentence patterns and sentences ： Constructive law $G[S]$, if $S\stackrel{\ast }{\Rightarrow }x,x\in (V_N\cup V_T{)}^{\ast }$, be $x$ A sentence pattern called this grammar . if $S\stackrel{\ast }{\Rightarrow }x,x\in V_T^{\ast }$, be $x$ A sentence called this grammar

• Two senses ： If a grammar has a sentence corresponding to two different grammar trees , That is, it has different leftmost （ The most right ） deduction , This grammar is ambiguous

• Pushdown automaton ： Expand DFA Make it possible to access a stack , It is called push down stack . Enter a string of token streams , The pushdown automaton will be based on “ Finite state transition control ”, Decide whether to accept the token stream

• First Set ：$First(\alpha )=\{a|\alpha \stackrel{\ast }{\Rightarrow }a\dots anda\in V_T\}$, if $\alpha \stackrel{\ast }{\Rightarrow }ϵ$, be $ϵ\in First(\alpha )$

• Follow Set ：$Follow(A)=\{a|S\stackrel{\ast }{\Rightarrow }\dots Aa\dots ,a\in V_T\}$, if $S\stackrel{\ast }{\Rightarrow }\dots A$, be $\#\in Follow(A)$

• Live prefix ： Standardize sentence pattern prefix , Without any symbols after the handle . if $S\stackrel{\ast }{\Rightarrow }\delta A\omega$, And we can continue to deduce $S\stackrel{\ast }{\Rightarrow }\delta \alpha \beta \omega$, among ,$\delta \in V^{\ast },A\in V_N,\omega \in V_N^{\ast },\alpha \in V^{+}$, be $\alpha \beta$ yes $\delta \alpha \beta \omega$ The handle of ,$\delta \alpha \beta$ Any prefix of is $\delta \alpha \beta \omega$ Live prefix of

• Move into statute conflict ： A project set , Existing move in project , There are also statute projects , At this time, it cannot be decided whether to generate the move in action or the Convention action

• Grammar guided translation ： Match each production with corresponding semantic rules , In the process of derivation or specification, the corresponding semantic actions are executed according to the semantic rules of production

• Comprehensive attributes ： if $A\to \alpha ,b:=f(c_1,c_2,\dots ,c_k)$, among ,$b$ yes $A$ Properties of ,$c_1,c_2,\dots ,c_k$ yes $\alpha$ The attribute of some grammatical symbols in or $A$ Other properties of , be $b$ It is a comprehensive attribute

• Inheritance attribute ： if $A\to \alpha ,b:=f(c_1,c_2,\dots ,c_k)$, among ,$b$ yes $\alpha$ The attribute of a grammatical symbol in ,$c_1,c_2,\dots ,c_k$ yes $A$ The property of or $\alpha$ Properties of other grammatical symbols in , be $b$ Is an inherited property

  memory ： Comprehensive attributes “ Bottom up , Include yourself ”; Inheritance attribute “ From top to bottom , Including brothers ”.

• Three address codes ： Each code contains an operation and three addresses , for example $x=yopz$, operation op, Two addresses $y,z$ Used to store operands , Address $x$ Used to store operation results

• Quaternion ：$(op,arg1,arg2,result)$, Quaternion is a record structure with four fields , Its meaning is arg1 and arg2 Conduct op Specified operation , The results are stored in result in

• Zipper and backfill ： When the steering in the three address code is uncertain , Pull all three address codes that turn to the same address into a chain , Once the turn address is determined , Backfill the steering address along this chain

Short answer

• Comparison between compiler and interpreter ：
  The function of compiler and interpreter is to translate and run the target program , From the perspective of translation , The two are similar , But the compiler separates the translation of the source program from the operation of the object code , The interpreter performs translation and operation at the same time .
  The advantages of an interpreter ：

  1. It has good dynamic characteristics . When the target program runs , Control is in the interpreter , Users can dynamically modify the source program ;
  2. It has good portability . Recompile the interpreter , You can make it run in different environments .

  Disadvantages of the interpreter ：

  1. Time lost . The interpreter needs to translate 、 Running at the same time , It takes time to check the source program at runtime ;
  2. Large space loss . The operation of the interpreter also needs to occupy memory space .

  memory ：（ identical ） The translation process is similar .（ difference ） The compiler translates and runs separately , The interpreter performs at the same time .（ Advantages and disadvantages of interpreter ）“ Mobile spacetime ”——（ optimal ） Portability 、 Dynamic characteristics ,（ Lack of ） Great loss of time and space 、 Low operating efficiency .

• The general process of compilation ：

  • Input ： Source program
  • Output ： Target program
  • The process —— Lexical analysis 、 Syntax analysis 、 Semantic analysis 、 Intermediate code generation 、 Code optimization 、 Target code generation
  • rely on —— Symbol table management 、 Error handling

• Comparison between multi pass scanning and one pass scanning ：

  • Definition —— logically , Every stage of compiler work , The program should be completely scanned and analyzed , It is called multi pass scanning . But actually , Compilers often combine several stages of work , Do a scan . In principle, , I hope the fewer times you scan, the better .
  • Advantages of one pass scanning —— Avoid repeated scanning , Improve compilation speed ;
  • Disadvantages of one pass scanning —— Algorithm logic is not clear 、 It is not convenient for code optimization 、 When grammatical and semantic errors occur, the preliminary work is invalid

  memory ：（ Definition ） Multi pass scanning refers to the complete scanning and analysis of the source program for multiple times during the compiler compilation process , One pass scanning refers to the compiler combining several stages of work , Only scan and analyze once .（ Advantages and disadvantages of one-time scanning ）—— optimal ： Efficient , Reduce repetitive work ; shortcoming ：（ Algorithm 、 Code optimization 、 Error handling ） Algorithm logic is not clear 、 Not conducive to code optimization 、 Errors in the grammatical and semantic analysis process lead to the invalidation of the results of the previous analysis process .

• The operation of language ：

  memory ： hand over 、 and 、 Bad 、 Connect 、 Closure 、 Positive closure

  1. $X=L\cap M,X=\{s|s\in Lands\in M\}$
  2. $X=L\cup M,X=\{s|s\in Lors\in M\}$
  3. $X=L-M,X=\{s|s\in Lands\notin M\}$
  4. $X=LM,X=\{st|s\in Landt\in M\}$
  5. $X=L^{\ast },X=\{s|s\in L^0\cup L^1\cup \dots \}$
  6. $X=L^{+},X=\{s|s\in L^1\cup L^2\cup \dots \}$

• Construct normal form ：

  • Construction of identifier ：
    $digit\to [0-9]$
    $letter\to [a-zA-Z\_]$
    $id\to letter(letter|digit{)}^{\ast }$
  • Construction of floating point numbers ：
    $zero\to 0$
    $nonzero\to [1-9]$
    $digit\to zero|nonzero$
    $digits\to digitdigi{t}^{\ast }$
    $integerPart\to zero|nonzerodigi{t}^{\ast }$
    $optionalFraction\to .digits|ϵ$
    $FloatNum=integerPartoptinalFraction$

• Proof of normal equivalence ：
  If normal P、Q Represents the same normal set , said P、Q Equivalent , Write it down as P=Q. The algebraic properties of identity operations of normal formulas can be used , Simplify complex normal form , So as to judge whether the normal formula is equivalent .

  memory ：“ or ” Operation has commutative law 、 Associative law , Connection operation has the law of Association , Positive closure operation $r^{+}=r{r}^{\ast }=r^{\ast }r$, Closure operations $r^{\ast }=r^{+}|ϵ$, Default operation $r?=r|ϵ$.

• DFA Three forms of transformation ：

  1. State transition functions $s_j=\delta (s_i,a)$
  2. State transition diagram （ notes ： The start state is pointed to by a double arrow , The end state is marked with double circles ）
  3. State transition table （ notes ： Each table element represents the transition state of a state when an input symbol ）

• Thompson Algorithm ：
  effect —— Construct recognition normal NFA.
  form ——$r_1{r}_2,r_1|r_2,r_1^{\ast }$

  memory ：Thompson Constructed by algorithm NFA in , non-existent “ Self return ” And a certain state can only lead to one non $ϵ$ Transfer .

  improvement ： In accordance with the normal structure NFA In practice , Always use “ The improved Thompson Algorithm ”, Simplify NFA The state of .

• Eliminate ambiguity ：

  1. Introduce a new non Terminator , Add a substructure and raise the priority level
  2. The position of recursive non terminator in production formula can reflect the associativity of grammatical symbols

  else Suspension problem ：

  $S\to ifbthenS$
  $|ifbthenSelseS$
  $|A$

  if b then if b then A else A It has two meanings . The reason for this ambiguity is else and then The numbers are different , Undetermined else And the first then Corresponding to the second then Corresponding . therefore , take S It is divided into exact match （MS） And do not exactly match （UMS）, Matching perfectly else-then The same number , Every else Can be found then With the corresponding , and UMS in else-then The numbers are different .MS and UMS It should be reflected in else The right combination of , That is, closest to else Sinister then matching .

  The result of eliminating ambiguity ：

  $S\to MS|UMS$
  $MS\to ifbthenMSelseMS$
  $UMS\to ifbthenS|ifbthenMSelseUMS$

• predictive analyzer ：
  By the drive 、 Symbol stack and prediction analysis table . The input buffer stores the string to be analyzed , With # Mark the end of the input string , Finally output the result of parsing . Drive control read mark , According to the stack top symbol and the current read symbol , The operation of symbol stack is determined by the prediction analysis table .

• Move into the protocol analyzer ：
  By the drive 、 Symbol state stack and move in reduction analysis table , Its working mode is exactly the same as that of the prediction analyzer . The input buffer stores the string to be analyzed , With # Mark the end of the input string , Finally output the result of parsing . Drive control read mark , According to the top state of the stack and the current read symbol , Move into the reduction analysis table to decide what operation to do with the symbol state stack .

• Conversion between infix and suffix ：

  • Infix to suffix ： The order of operands in the suffix formula is consistent with that in the infix formula , Operators are placed after the corresponding operands in the order of operation ;
  • Suffix to infix ： Sequence traversal suffix , If the current input is an operand , Then enter the stack ; If the current input is an operator , Then pop the operand from the stack for operation , Push the result back on the stack .

  memory ： The introduction of suffix eliminates brackets , Easy to calculate .

reference

1. Liu Jian . Fundamentals of compiler principles . Xi'an ： Xi'an University of Electronic Science and Technology Press ,2008.
2. Liu Ming . Compiler principle [M]. Beijing ： Electronic industry press ,2018.
3. Huang Xianying . Compilation principle and practice tutorial [M]. Beijing ： tsinghua university press ,2019.
4. Keith Cooper. Compiler design [M]. Beijing ： People's post and Telecommunications Press ,2012.
5. Huang Xianying . Compiler principle ： Analysis of key and difficult points · Problem solving · Experimental instruction [M]. Beijing ： Mechanical industry press ,2008.