[compilation principle] 05- syntax guided semantic computing -- Semantic Computing Based on translation mode

Translation mode

• Attributive grammar Semantic rules of ： It's always on The tail of production
• Translation mode ： Put semantic rules （ Also called semantic actions ）, use Curly braces {} Cover up , Insert To production Right position On . Further refine the timing of semantic computing .

S- Translation mode

• Only comprehensive attributes are involved , The semantic action set is placed at the right end of the production At the end of ;
• Always use LR Bottom-up analysis of , and S- Attribute grammars are similar

L- Translation mode

• contain Comprehensive attributes , It can also include Inheritance attribute

• The following conditions must be met ：

  • Of the production right sign Inheritance attribute , Its semantic calculation must be located in Before this symbol , And the semantic action does not access the attribute of the symbol on the right
  • Of the left sign of production Comprehensive attributes It can only be calculated after all the attributes it refers to have been calculated . The action of calculating this property is usually At the end of the production ;
    • The former $\{C.i=B.v+1\}$ in i by Inheritance attribute , Need to be located at Before this symbol
    • the latter $\{A.v=B.v+C.v\}$ in v by Comprehensive attributes , Need to be located at End of production

  $$A\to B\{C.i=B.v+1\}C\{A.v=B.v+C.v\},B\to ..,C\to ..$$

  • Inheritance attribute Can only depend on Brother's attributes 、 Father's inheritance property 、 Properties of itself
  • Dependency graph between attributes Unable to form a loop

S- Translation mode and L- Examples of translation patterns

be based on S- Semantic computation of translation patterns

and S- Attribute grammars are similar ：

• Basic grammar ：LL(1)： The top-down Calculation
• Basic grammar ：LR system ： Bottom up Calculation

be based on L- Top down calculation of translation mode

Recursive descent L- Translation mode

• The analyzer consists of a set of Recursive subroutine （ function ） form , Every non-terminal Corresponding to one Subroutines
• If non-terminal Yes Multiple production , according to Current symbols and SELECT Set Decide which production to use
• Parse symbol strings from left to right , encounter Terminator Just matching , encounter non-terminal Call the corresponding analysis Subroutines
• requirement The basic grammar is LL(1)

I understand it ：

• There are clear semantic computing opportunities
• Semantic actions are also seen as similar to a symbol as a node , according to select After the collection constructs the syntax tree , The sequence of previous traversal is executed

Translation steps ：

1. Check whether the basic grammar is LL(1) Grammar
2. structure LL(1) Analysis subroutine

Non recursively descending L- Translation mode

• stay LL(1) On the basis of analytical method , Add attribute list stack
• From the leftmost derivation of the grammar starting symbol , According to the next symbol and select Set selection production
• Production right and Semantic action The reverse Into the stack
• Comprehensive attributes Calculate the result and then stack it

My notes ：

• Inheritance attribute The calculation of is top-down , So top down L- Translation mode The first calculation is the inheritance property
• Comprehensive attributes yes Last “ store at the bottom of a suitcase ” Finally, the stack is slowly popped up and calculated

https://www.bilibili.com/video/BV13B4y197wo?t=1403.2
Precise positioning ！From The teacher in this video explained it very thoroughly ！

be based on L- Bottom up calculation of translation mode

There are the following Three methods ：（ There is no guarantee that grammar can be translated ）

1. From the translation mode Delete Embedded in the Semantic actions in the middle of production
2. The evaluation results of inherited attributes are stored in the semantic stack as comprehensive attributes , When the inheritance attribute is calculated from the comprehensive attribute , Access to inherited properties become Access to a comprehensive attribute of the semantic stack
3. Simulate inherited properties The calculation of

The first one is ： Delete semantic actions embedded in production , That is, to transform the translation mode ：

• Put every... Embedded in the production Semantic action use Different non terminators （ such as M,N,…) Instead of
• Join in New production M → $\epsilon$
• And then The original semantic action Put it in production M → $\epsilon$ Of At the end of

example ： take L- The attribute grammar becomes S- Attribute grammar translation mode （ Bottom up and top down ）

The second kind ： The evaluation results of inherited attributes are stored in the semantic stack as comprehensive attributes , Access to inherited attributes becomes access to a comprehensive attribute in the semantic stack

• Yes LR Stack expansion , add to entry Storage identifier ,type by type Property value
• The first line production does not need to be extended , because L.in It must be T.type The latter
• Of the last two productions in Value from type, A fixed position in the stack
• When making the rules , The operation of storing identifiers and types in the symbol table is According to the rule that synthetic attributes and inherited attributes differ by a fixed number of digits in the stack

Having no regular pattern L- Translation mode

resolvent ：

• add to M after , send C.i The location from which the inherited property of is derived is fixed , It's a forward position

The third kind of ： Simulate the calculation of inherited properties （ Inherited attribute is not a duplicate value , By operation ）

• The introduction of a New non Terminator
• Add a new non terminal to this , add to The calculated value of the value of the original inherited attribute of the comprehensive attribute
• Give Way Inheritance attribute Copy this Comprehensive attributes , And use this inherited attribute as a function parameter , Change it into comprehensive attribute
  

for instance , Rational thinking ：

• First step ： Rewrite the translation mode , Make inherited properties contain replication rules only
• The second step ： Transform semantic rules into stack operations
• The third step ： According to the basic grammar , structure LR automata
• Step four ： according to LR automata , structure LR Analysis of the table
• Step five ： according to LR Analysis of the table , And stack operation instructions , Analyze the target symbol string