<> An overview of grammar guided translation
Syntax-directed translation （Syntax-Directed Translation）=『 lexical analysis + semantic translation =『 semantic analysis + Intermediate code generation 』』
Grammar guided translation use CFG To guide the translation of language , It is a grammar oriented translation technique .
Grammar guided translation ： A formal semantic description method , Including two specific forms ：
* syntax-directed definition (Syntax-Directed Definitions, SDD)： Defining semantic attributes and rules necessary for translation , Generally, the calculation sequence is not involved .
* Grammar guided translation scheme (Syntax-Directed Translation Scheme,SDT)： Give the calculation order of semantic rules .
SDD Yes, it is CFG Promotion of ：
* Associate each grammar symbol with a set of semantic attributes .
* Associate each production with a set of semantic rules , These rules are used to calculate the attribute values of the grammar symbols in the production .
SDT It's embedded in the right part of the production CFG, These program fragments are called semantic actions .
<> syntax-directed definition SSD
Comprehensive attribute (synthesized attribute)：
* At the analysis tree node N Nonterminal on A The comprehensive attribute of can only be passed through N Or N Defined by its own property value .
* Terminators can have comprehensive properties . The comprehensive attribute value of the terminator is the lexical value provided by the lexical analyzer , So in SDD There is no semantic rule to calculate the value of the terminator property in .
Inheritance properties (inherited attribute)
* At the analysis tree node N Nonterminal on A Inherited properties of can only be passed through N Parent node of ,N Or N Defined by its own property value .
* Terminator has no inherited property . Terminator obtained from lexical analyzer Attribute value of is classified as comprehensive attribute value .
Virtual properties
rely on
side effect （side effects）： General attribute value calculation （ Based on property value or constant ） Other functions . One with no side effects SDD Sometimes called attribute grammar .
<>SDD Evaluation order of
The dependency graph is a graph that describes the dependency relationship between node attributes in the analysis tree
Directed graph of a system , Each label in the analysis tree is X Each attribute of the node of a All corresponding
A node in dependency graph , If attribute X.a The value of depends on the property Y.b Value of , Then there is a dependency graph from Y.b Point to X.a The directed edge of the node of .
* For those with only comprehensive attributes SDD, According to any self Calculate their values in bottom-up order .
* For those with both inherited and comprehensive attributes SDD, There is no guarantee that there is a sequence to enter the attributes on each node Row evaluation .
<>S- Attribute definition and L- Attribute definition
Using only comprehensive attributes SDD be called S Attribute SDD.
If one SDD yes S Attribute , Each attribute value can be calculated in any bottom-up order of the parse tree nodes .
L- Intuitive meaning of attribute definition ： Between the attributes associated with a production , The edge of a dependency graph can be left to right , But not right to left . Namely A->X1X2……Xn in Xi Each inherited property of depends only on ：
* A Inherited properties of
* Xi Symbol on the left X1,……Xi-1 Properties of
* Xi Its own properties , But we can't form a loop in the dependency graph .
each S- Property definitions are all L- Attribute definition .
Technology
Daily Recommendation