31-10-2012, 05:09 PM
Syntax-Directed Translation
Syntax-Directed.ppt (Size: 146 KB / Downloads: 341)
Syntax Directed 1.ppt (Size: 208.5 KB / Downloads: 148)
Directed Translation.ppt (Size: 139.5 KB / Downloads: 37)
Syntax Directed Translation.ppt (Size: 62 KB / Downloads: 84)
SDT.ppt (Size: 56.5 KB / Downloads: 24)
Grammar symbols are associated with attributes to associate information with the programming language constructs that they represent.
Values of these attributes are evaluated by the semantic rules associated with the production rules.
Evaluation of these semantic rules:
may generate intermediate codes
may put information into the symbol table
may perform type checking
may issue error messages
may perform some other activities
in fact, they may perform almost any activities.
An attribute may hold almost any thing.
a string, a number, a memory location, a complex record.
Syntax-Directed Definitions and Translation Schemes
When we associate semantic rules with productions, we use two notations:
Syntax-Directed Definitions
Translation Schemes
Syntax-Directed Definitions:
give high-level specifications for translations
hide many implementation details such as order of evaluation of semantic actions.
We associate a production rule with a set of semantic actions, and we do not say when they will be evaluated.
Translation Schemes:
indicate the order of evaluation of semantic actions associated with a production rule.
In other words, translation schemes give a little bit information about implementation details.
Syntax-Directed Definitions
A syntax-directed definition is a generalization of a context-free grammar in which:
Each grammar symbol is associated with a set of attributes.
This set of attributes for a grammar symbol is partitioned into two subsets called synthesized and inherited attributes of that grammar symbol.
Each production rule is associated with a set of semantic rules.
Semantic rules set up dependencies between attributes which can be represented by a dependency graph.
This dependency graph determines the evaluation order of these semantic rules.
Evaluation of a semantic rule defines the value of an attribute. But a semantic rule may also have some side effects such as printing a value.
Annotated Parse Tree
A parse tree showing the values of attributes at each node is called an annotated parse tree.
The process of computing the attributes values at the nodes is called annotating (or decorating) of the parse tree.
Of course, the order of these computations depends on the dependency graph induced by the semantic rules.
S-Attributed Definitions
Syntax-directed definitions are used to specify syntax-directed translations.
To create a translator for an arbitrary syntax-directed definition can be difficult.
We would like to evaluate the semantic rules during parsing (i.e. in a single pass, we will parse and we will also evaluate semantic rules during the parsing).
We will look at two sub-classes of the syntax-directed definitions:
S-Attributed Definitions: only synthesized attributes used in the syntax-directed definitions.
L-Attributed Definitions: in addition to synthesized attributes, we may also use inherited attributes in a restricted fashion.
To implement S-Attributed Definitions and L-Attributed Definitions are easy (we can evaluate semantic rules in a single pass during the parsing).
Implementations of S-attributed Definitions are a little bit easier than implementations of L-Attributed Definitions
Translation Schemes
When designing a translation scheme, some restrictions should be observed to ensure that an attribute value is available when a semantic action refers to that attribute.
These restrictions (motivated by L-attributed definitions) ensure that a semantic action does not refer to an attribute that has not yet computed.
In translation schemes, we use semantic action terminology instead of semantic rule terminology used in syntax-directed definitions.
The position of the semantic action on the right side indicates when that semantic action will be evaluated.