7.b) What is dependency graph? Write dependency graph for the expression 3 * 5 with suitable top down grammar.

Answer:

Dependency graph

A dependency graph is a directed graph that shows the flow of information among attribute instances in a parse tree. It is used to determine a valid order of attribute evaluation during syntax-directed translation. In this graph:

Nodes represent attribute instances.
Edges represent dependencies—an edge from attribute X.a to Y.b means that Y.b depends on X.a (i.e., the value of Y.b requires the value of X.a).

Dependency graphs help identify in what order attributes should be computed to avoid circular dependencies and ensure correctness.

Top-Down Grammar for Expression **3 * 5**

We define a simple grammar for multiplication:

E → T
T → F T1
T1 → * F T1 | ε
F → digit

Let the semantic rules be:

F.val = digit.lexval
T1.inh = F.val
T1.syn = T1.inh * F.val
T.val = T1.syn
E.val = T.val

Expression Tree for **3 * 5**

The parse tree for the expression 3 * 5 using the above grammar looks like this:

      E
      |
      T
     / \
    F  T1
   |   / | \
digit * F T1
 (3)     |  \
       digit ε
        (5)

Dependency Graph for **3 * 5**

We now construct the dependency graph using the semantic rules:

F1.val ← digit1.lexval (3)

F2.val ← digit2.lexval (5)

T1_1.inh ← F1.val

T1_2.inh ← T1_1.syn

T1_1.syn ← T1_1.inh * F2.val

T.val ← T1_2.syn

E.val ← T.val

Dependency graph? Dependency graph for the expression 3 * 5.