Short Notes: Syntax Directed Translation | Short Notes for Computer Science Engineering - Computer Science Engineering (CSE) PDF Download

 Page 1


  
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.
Attribute Grammar Framework
• Generalization of CFG where each grammar symbol has an associated set of 
attributes
• Values of attributes are computed by semantic rules
• Two notations for associating semantic rules with productions
Syntax directed definition
• high level specifications
• hides implementation details
• explicit order of evaluation is not specified
Translation schemes •
• indicate order in which semantic rules are to be evaluated
• allow some implementation details to be shown
Evaluation of the semantic rules are as follows
1. May generate intermediate codes
2. May put information into the symbol table
3. May perform type checking
4. May issue error messages
5. May perform some other activities
Page 2


  
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.
Attribute Grammar Framework
• Generalization of CFG where each grammar symbol has an associated set of 
attributes
• Values of attributes are computed by semantic rules
• Two notations for associating semantic rules with productions
Syntax directed definition
• high level specifications
• hides implementation details
• explicit order of evaluation is not specified
Translation schemes •
• indicate order in which semantic rules are to be evaluated
• allow some implementation details to be shown
Evaluation of the semantic rules are as follows
1. May generate intermediate codes
2. May put information into the symbol table
3. May perform type checking
4. May issue error messages
5. May perform some other activities
• An attribute may hold a string, a number, a memory location, a complex record 
etc.
• 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.
Attributes
• Attributes fall into two classes: synthesized and inherited
• The value of a synthesized attribute is computed from the values of its 
children nodes
• The value of an inherited attribute is computed from the sibling and parent 
nodes.
S-Attributed grammar: A syntax directed definition that uses only synthesized 
attributes is said to be an S- attributed definition. A parse tree for an S-attributed 
definition can be annotated by evaluating semantic rules for attributes.
Translations are appended only at the end.
It uses bottom up parsing for evaluation.
L-attributed grammar: When translation takes place during parsing, order of 
evaluation is linked to the order in which nodes are created. L-attributed definition: 
where attributes can be evaluated in depth-first order.
This definition can use synthesized attributes and also restricted inherited 
attributes(the value can be taken from parent and left siblings only).
Translations can append anywhere in the rhs of the production.
It uses a natural order in both top-down and bottom-up parsing is depth first-order. 
Evaluation order of SDT’s
• Using definitions: L-attributed definition and S-attributed definition
• Using parsing: Top-down evaluation and Bottom up evaluation
Dependency Graph : Directed graph indicating interdependencies among the 
synthesized and inherited attributes of various nodes in a parse tree.
Syntax directed translation table: Symbols E, T and F are associated with an 
attribute value.
P r o d u c tio n S e m a n tic R u le P r o g r a m F r a g m e n t
L —» E return Print (E.val) Print (val [top - 1])
E ^ E ' + T E.val = E '.val + T.val V a l [n top] = val [top - 2] + val [top]
E - * T 
T T' * F
E.val = T.val 
T.val = T '.val * F.val V a l [n top] = val [top - 2] * val [top]
T ^ F
F - ( E )
T.val = F.val 
F.val = E.val V a l [n top] = val [top - 1]
F —* ¦ digit F.val = digit .lexval V a l [top] = digit.lexval