**Related Content:** CS606 - VU Lectures, Handouts, PPT Slides, Assignments, Quizzes, Papers & Books of Compiler Construction

These questions are part of context-sensitive analysis. Answers depend on values, not parts of speech. Answers may involve computation.

These questions can be answered by using formal methods such as context-sensitive grammars and attribute grammars or by using ad-hoc techniques.

One of the most popular is the use of attribute grammars.

A CFG is augmented with a set of rules. Each symbol in the derivation has a set of values or attributes. Rules specify how to compute a value for each attribute

Consider the grammar for signed binary numbers (SBN)

**Number → Sign List
Sign → + –
List → List Bit | Bit
Bit → 01**

The string “–1” can be derived as follows:

**Number → Sign List
→ – List
→ – Bit
→ – 1**

Similarly, the derivation for “-101” is

**Number → Sign List
→ Sign List Bit
→ Sign List 1
→ Sign List Bit 1
→ Sign List 0 1
→ Sign Bit 0 1
→ Sign 1 0 1
→ – 1 0 1**

For an attributed version of SBN, the following attributes are needed

Symbol |
Attributes |

Number | val |

Sign | neg |

List | pos, val |

Bit | pos, val |

We will add rules to compute decimal value of a signed binary number

Productions |
Attribution Rules |

Number → Sign List | List.pos ← 0 if Sign.neg then Number.val ← – List.val else Number.val ← List.val |

Sign → + | Sign.neg ← false |

Sign → – | Sign.neg ← true |

List0 → List1 Bit | List1.pos ← List0.pos + 1 Bit.pos ← List0.pos List0.val ← List1.val + Bit.val |

List → Bit | Bit.pos ← List.pos List.val ← Bit.val |

Bit → 0 | Bit.val ← 0 |

Bit → 1 | Bit.val ← 2Bit.pos |

Attributes are associated with nodes in parse tree. Rules are value assignments associated with productions. Rules and parse tree define an attribute dependence graph which must be acyclic.

Attributes are distinguished based on the direction of value flow. Attributes of a node whose values are defined wholly in terms of attributes of node’s children and from constants are called synthesized attributes. Values used to compute synthesized attributes flow bottom-up in the parse tree.

Attributes whose values are defined in terms of a node’s own attributes, node’s siblings and node’s parent are called inherited attributes. Values flow top-down and laterally in the parse tree. The following attributed tree shows the inherited and synthesized attributes for the input signed binary number -101.

When the parse tree is peeled away, we get the attribute dependence graph