CS606 - Compiler Construction - Lecture Handout 31

User Rating:  / 0
PoorBest

Beyond Syntax

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.

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 → 01

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