Coupon Accepted Successfully!


Syntax Directed Translation

The conceptual view of syntax-directed translation,

Input string → parse tree  dependency graph  evaluation order for semantic rules


Syntax directed definitions (SDD)

This is a generalization of context free grammar in which each grammar symbol has an associated set of attributes and rules. Attributes are associated with grammar symbols and rules are associated with productions.


Syntax directed translation schemes (SDT)

Example : An annotated parse tree for 2*6+ 4n


S-attributed Definitions

An SDD is S-attributed if every attribute is synthesized. S-attributed definitions is evaluated in bottom up fashion in a parse tree and it can be implemented during bottom-up parsing as bottom up traversal corresponds to post order traversal and post order corresponds to the order in which an LR parser reduces a production body to its head.

L-attributed definitions

Between the attributes associated with production body, the edges in the dependency graph can go from left to right but not right to left. Hence the name L-attributed.

Each attribute must be either

– Synthesized attributes

– Inherited attribute. It follows certain rules,

For a given production A →
 X1 X2…..Xn and there is an inherited attribute Xi.a associated with this production. Then the rule may use only,

  1. Inherited attributes associated with head A.
  2. Either synthesized attribute or inherited attribute with the occurences X1 X2 …Xi-1
    Located to the left of Xi
  3. There should not be any cycles in the dependency graph for the occurrences of Xi formed by the attributes of Xi.

Application of syntax directed translation


Syntax tree for L-attributed definition

Production Semantic Rules


Parse-Stack implementation of postfix SDT’s

  • In a shift-reduce parser we can easily implement semantic action using the parser stack
  • For each nonterminal (or state) on the stack we can associate a record holding its attributes
  • Then in a reduction step we can execute the semantic action at the end of a production to evaluate the attribute(s) of the non-terminal at the leftside of the production
  • And put the value on the stack in replace of the rightside of production

SDT’s for L-Attributed definitions

  • We can convert an L-attributed SDD into an SDT using following two rules:
  1. Embed the action that computes the inherited attributes for a nonterminal A immediately before that occurrence of A. if several inherited attributes of A are dependent on one another in an acyclic fashion, order them so that those needed first are computed first.
  2. Place the action of a synthesized attribute for the head of a production at the end of the body of the production

Steps to construct parse tree for a+2*c
Steps in the construction of syntax tree
(1) S1 = new leaf (id, entry a);
(2). S2 = new leaf (num 2);
(3) S3 = new node (+, S1, S2);
(4) S4 = new leaf (id, entry c);
(5) S5 = new node (*, S3, S4);
Dependency graph for a + 2 * c with L-attributed SDD


Test Your Skills Now!
Take a Quiz now
Reviewer Name