Parser uses a CFG (Context-free-Crammer) to validate the input string and produce output for next phase of the compiler. Output could be either a parse tree or abstract syntax tree. Now to interleave semantic analysis with syntax analysis phase of the compiler, we use Syntax Directed Translation.
Syntax-directed translation fundamentally works by adding actions to the productions in a context-free grammar, resulting in a Syntax-Directed Definition (SDD).
Actions are steps or procedures that will be carried out when that
production is used in a derivation. A grammar specification embedded
with actions to be performed is called a Syntax-Directed Translation scheme (sometimes simply called a 'translation scheme'.)
Syntax Directed Translation SDT
Syntax-directed translation is done by attaching rules or program fragments to
productions in a grammar.
In syntax directed translation, along with the grammar we associate some informal notations and these notations are called as semantic rules.
Grammar + Semantic Rule = SDT (Syntax Directed Translation)
Common attributes could include a variable type, the value of an expression, etc. Given a symbol X, with an attribute t, that attribute is referred to as X.t. Attribute may hold anything like a string, a number, a memory location and a complex record
The most general approach to syntax-directed translation is to construct a parse tree or a syntax tree, and then to compute the values of attributes at the nodes of the tree by visiting the nodes of the tree.
SDT involves passing information bottom-up and/or top-down the parse tree in form of attributes attached to the nodes.
In many cases, translation can be done during parsing, without building an explicit tree. (We don’t need to build a parse tree all the time. Translation can be done during parsing.)
This section introduces two concepts related to syntax-directed translation:
#Attributes
- An attribute is any quantity associated with a programming construct.
- Examples of attributes are data types of expressions, the number of instructions in the generated code, or the location of the first instruction in the generated code for a construct, among many other possibilities.
- Since we use grammar symbols (non terminals and terminals) to represent programming constructs, we extend the notion of attributes from constructs to the symbols that represent them.
#( Syntax-directed ) translation schemes
- A translation scheme is a notation for attaching program fragments to the productions of a grammar.
- The program fragments are executed when the production is used during syntax analysis.
- The combined result of all these fragment executions, in the order induced by the syntax analysis, produces the translation of the program to which this analysis/synthesis process is applied.
Syntax Directed Definitions - A syntax-directed definition (SDD) is a context-free grammar together with attributes and rules.
- Syntax directed definition specifies the values of attributes by associating semantic rules with the grammar productions.
- Attributes are associated with grammar symbols and rules are associated with productions.
- If X is a symbol and a is one of its attributes, then we write X:a to denote the value of a at a particular parse-tree node
labeled X . - Attributes may be of any kind: numbers, types, table references, or strings, for instance.
- A syntax-directed definition hides many implementation details (attribute grammar).
- High-level specifications for translation.
- User does not have to explicitly specify the order in which the translation occurs.
- Generates Annotated Parse Tree
The process of syntax directed translation is two-fold:
• Construction of syntax tree and
• Computing values of attributes at each node by visiting the nodes of syntax tree.
SDT Scheme- Syntax-directed translation schemes are a complementary notation to syntax-directed definitions.
- All of the applications of syntax-directed definitions in can be implemented using syntax-directed translation schemes.
- A syntax-directed translation scheme (SDT) is a context-free grammar with program fragments embedded within production bodies.
- The program fragments are called semantic actions and can appear at any position within a production body.
- By convention, we place curly braces around actions; if braces are needed as grammar symbols, then we quote them.
- Any SDT can be implemented by first building a parse tree and then performing the actions in a left-to-right depth- first order; that is, during a preorder traversal.
- Typically, SDT's are implemented during parsing, without building a parse tree.
- More implementation oriented.
- Indicate the order in which semantic rules are to be evaluated.
Example: E -> E + T { print '+ ' }
Between the two notations, syntax-directed definitions can be more readable, and hence more useful for specifications. However, translation schemes can be more efficient, and hence more useful for implementations.
A class of syntax-directed translations called \L-attributed translations" (L for left-to-right), which encompass virtually all translations that can be performed during parsing. We also study a smaller class, called \S-attributed translations" (S for synthesized), which can be performed easily in connection with a bottom-up parse.
#Synthesized Attributes
Attributes that depend only on the attribute values of children nodes.
Thus
[ E -> E+T { E.val = E.val + T.val } ] has a synthesized attribute
val corresponding to node E. If all the semantic attributes in an
augmented grammar are synthesized, one depth first search traversal in
any order is sufficient for semantic analysis phase.
#Inherited Attributes
Attributes that depend on parent and/or siblings attributes.
Thus
[ Ep -> E+T { Ep.val = E.val + T.val, T.val = Ep.val } ], where E
& Ep are same production symbols annotated to differentiate between
parent and child, has an inherited attribute val corresponding to node
T.
- An SDD without side effects is sometimes called an attribute grammar . The rules in an attribute grammar define the value of an attribute purely in terms of the values of other attributes and constants.
- A parse tree, showing the value(s) of its attribute(s) is called an annotated parse tree .
No comments:
Post a Comment