[go: up one dir, main page]
Scribd
Upload
165 views7 pages

3-Chapter 5 - Syntax Directed Translation

The document discusses syntax directed translation using dependency graphs and topological sorting. A dependency graph depicts the flow of information between attribute instances in a parse tree, with edges showing which attributes must be evaluated before others. Topological sorting can find a valid evaluation order by arranging nodes such that dependencies are satisfied. The document provides an example of a dependency graph and topological sorting for a grammar, and discusses how to control side effects in semantic rules through evaluation ordering constraints.

Uploaded by

B. POORNIMA
Copyright
© © All Rights Reserved
We take content rights seriously. If you suspect this is your content, claim it here.
Available Formats
Download as PPTX, PDF, TXT or read online on Scribd
165 views7 pages

3-Chapter 5 - Syntax Directed Translation

The document discusses syntax directed translation using dependency graphs and topological sorting. A dependency graph depicts the flow of information between attribute instances in a parse tree, with edges showing which attributes must be evaluated before others. Topological sorting can find a valid evaluation order by arranging nodes such that dependencies are satisfied. The document provides an example of a dependency graph and topological sorting for a grammar, and discusses how to control side effects in semantic rules through evaluation ordering constraints.

Uploaded by

B. POORNIMA
Copyright
© © All Rights Reserved
We take content rights seriously. If you suspect this is your content, claim it here.
Available Formats
Download as PPTX, PDF, TXT or read online on Scribd
You are on page 1/ 7

Compiler Design

CHAPTER 5
SYNTAX DIRECTED TRANSLATION
Dependency Graph

 Dependency Graph depicts the flow of information among the attribute instances in a
particular parse tree.
 If an attribute b depends on attribute c, then attribute b has to be evaluated AFTER c
 An edge form one attribute instance to another means that the value of the first is needed
to compute the second.
 If Dependency Graph has cycles, there is no way to evaluate the SDD on the parse tree.

Attribute Dependencies
 Given a SDD, we can describe the dependencies between the attributes with a
DEPENDENCY GRAPH.
Order of Evaluation of Attributes

Finding a valid evaluation order


 A TOPOLOGICAL SORT of a directed acyclic graph orders the nodes such that for any
nodes a and b, if there is an edge from a to b, i.e. ab, a appears BEFORE b in the
ordering.
 There are many possible topological orderings for a DAG.
 Each of the possible orderings give a valid order for the evaluation of the semantic
rules.
Topological sort
 If Dependency graph has cycles, then there are no topological sort. If no cycles then
at least one topological sort order can be obtained
Draw Dependency Graph and Topological
sort order for the grammar given

DBD’
D’BD’
D’ε
B0
B1
Semantic Rules with Controlled Side
Effects
Translations involve side effects:
 A desk calculator may print result.
 Code Generator might enter the type of an identifier into symbol table.
Attribute Grammar: Grammar with no side effects and allow any
evaluation order.
Can Control side effects in SDD’s in the following ways
 Permit incidental side effects that do not constrain attribute evaluation.
 Constrain the allowable evaluation orders.
SDD for Basic Type Declarations

addType()
is just a
Production Semantic Rules procedure
DT L L.inh=T.type that sets
Tint T.type=int the type
field in the
Tfloat T.type=float symbol
LL1, id L1.inh=L.inh table.
addType(id.entry, L.inh)
Lid addType(id.entry, L.inh)

id.entry- a lexical value that points to a symbol table


Annotated Parse Tree for
float id1, id2, id3

What are the dependencies?


Can be achieved through Dependency Graph

You might also like