<> 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 .

©2019-2020 Toolsou All rights reserved,
TP6 Application examples of verifier and correct verification data ESP8266/ESP32 System : Optimize system startup time 2021 year 2 Chinese programming language ranking 2021 year 1 Monthly programmer salary statistics , average 14915 element CSS architecture design It's not depravity that's terrible , It's about knowing you're falling Gude Haowen serial - You deserve to be an engineer ( Preface ) Software testing BUG describe C Course design of language programming of 《 Student achievement management system 》vue In the project axios Global encapsulation of