Spread Knowledge

CS606 - Compiler Construction - Lecture Handout 31

User Rating:  / 0
PoorBest 

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

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.

Sign.neg

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.

parse tree

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

dependence graph