Soft test --- fundamentals of programming language (Part 2)

One 、 Basic principle of compiling system （ Next ）

（1） Finite state machine

1.1 Concept

        If the state of a finite state machine after each transition is unique, it is called Determine finite state automata （DFA）;

        If the subsequent state after conversion is not unique, it is called Uncertain finite state automata （NFA）;

        

        The state machine has three states ：

        The initial state : The initial state ;

        Successor status ： When a finite state machine reads a character , Its state changes to another state , Then the changed state is called subsequent state ;

        Termination status （ Reception status ）： The end state of the current activity or event ;

1.2 Deterministic finite state machine （DFA）

        A deterministic finite automata （DFA）M It's a pentagram ：

        M = { S ,Σ ,δ ,K ,F }, among

        1. S It's a finite set , It includes all States in the state machine ;

        2. Σ It's a poor alphabet , Store converted characters ;

        3. δ Is a conversion function  δ（ The previous state , The conversion character ）= The converted state ;

        4. K yes S Middle initial state , Have uniqueness ;

        5. F Is the final state set ,F ⊆ S ;（ Can be empty ）

  example ：

        M = { S ,Σ ,δ ,K ,F }

  among ：

        S = { S0 ,S1 ,S2 ,S3 };

        Σ = { a , b ,c };

        δ Conversion function ：

        ( S0 ,a ) = S1 ;        ( S1 ,b ) = S2 ;        ( S1 ,c ) = S3 ;

        K = S0 ;

        F = { S2 ,S3 };

（2） The stage of grammatical analysis

        The parser takes the unit symbol as input , Analyze whether word symbol strings form grammatical units of grammatical rules , Like the expression 、 assignment 、 Cycle, etc , Analyze and check whether each statement has the correct logical structure according to the grammar rules ;

        for example ：

        int arr[2] ,b;

        b = arr * 10;

        The parser can only judge its operator collocation , We won't find the problem that arrays can't be multiplied by variables directly ;

        

        The method of grammar analysis ：

        1. Top down analysis ;

        2. Bottom up analysis ;

（3） Semantic analysis stage  

          The semantic analysis stage is mainly to check whether there are semantic errors in the source program , And collect type information for later code generation phase , Only the source program with correct syntax and semantics can be translated into the correct object code ;

        The main work of semantic analysis is to carry out various types of analysis and inspection , For example, whether the left and right ends of the assignment statement match 、 Whether the divisor of the expression is 0 etc. ;

（4） Intermediate code generation phase

        The work of intermediate code generation stage is based on Output of semantic analysis Generate intermediate code ;

        Intermediate code is a simple and clear notation system , There can be several forms , Common are Reverse Polish sign 、 Quaternion 、 Ternary form and Trees ;

        Their common feature is the way they code It has nothing to do with the specific machine ;

 （5） Code optimization phase

        The code optimization stage is to transform or transform the intermediate code generated in the previous stage , The purpose is to make the generated object code more advanced , Saving time and space ;

 （6） Object code generation stage

        It is to transform intermediate code into absolute instruction code or relocatable instruction code or assembly instruction code on a specific machine ;

        This is the final stage of compilation , Its work is related to the structure of hardware system and the meaning of instructions ;

Two 、 Control structure of program language

        Three basic structures ： Sequential structure 、 Selection structure 、 Loop structure ;

（1） expression  

        Prefix expression ：

        Also known as polish notation , It is characterized by placing operators before operands , Such as + - 3 2 1 ;

        

        Infix expression ：

        That is, our common expression , Such as 3 - 2 + 1 ;

        

        Postfix expression ：

        Also known as anti Polish law , It is characterized by placing the operator after the operand , Such as 3 2 - 1 + ; 

 （2） The priority of the operator

         An expression may contain multiple expressions connected by different operators 、 Data objects with different data types ;

         Because expressions have many operations , Different combination order may lead to different results and even wrong operation , Because when the expression contains multiple operations , Must be combined in a certain order , To ensure the rationality of the operation and the correctness of the result 、 Uniqueness .

         The priority decreases from top to bottom , The top has the highest priority , The comma operator has the lowest priority . The combination order of expressions depends on the priority of various operators in the expression . Operators with higher priority are combined first , Low priority operators are combined with , Operators in the same line have the same priority ;

 （3） process control

        How parameters are passed ：

        Value transfer call --- Data transmission is one-way

        Reference call （ Address call ）--- Data transmission is bidirectional