CSCE 434 Lecture 23

« previous | Wednesday, October 16, 2013 | next »

Lecture Slides

Context-Sensitive Analysis

Production	Evaluation Rules
decl := type list	list.in = type.type
type := int	type.type = integer
type := char	type.type = char
list0 := list1, id	add type(id.entry, list0.in) list1.in = list0.in
list := id	add type(id.entry, list.in)

Attribute Grammar

• Generalization of a context-free grammar
• Each symbol has associated set of attributes
• Grammar augmented with rules that define values
• High-level specification, independent of evaluation scheme

Dependencies Between Attributes

Values are computed from constants and other attributes:

• synthesized attributes are computed from children
• inherited attributes are computed from siblings and parent

Example: Evaluating Signed Binary Numbers

num
    : sign list
        {
            list.pos = 0
            num.val = sign.neg ? -list.val : list.val
        }
    ;

sign
    : '+' { sign.neg = false }
    | '-' { sign.neg = true }
    ;

list
    : bit
        {
            bit.pos = list.pos
            list.val = bit.val
        }
    ;

list0
    : list1 bit
        {
            list1.pos = list0.pos + 1
            bit.pos = list0.pos
        }
    ;

bit
    : 0 { bit.val = 0 }
    | 1 { bit.val = pow(2, b.pos)
    ;

In this snippet,

• val and neg are synthesized because they are computed based on children
• pos is inherited because it is given by the parent

Attribute Dependency Graph

• Nodes represent attributes
• Edges represent flow of values
• graph is specific to parse tree (related sizes; and can be built alongside the parse tree)

Must be a acyclic

Summary

Advantages

• Clean formalism
• Automatic generation of evaluator
• High-level specification

Disadvantages:

• Evaluation strategy determines efficiency
• Increased space requirements
• Results distributed over tree
• Circularity testing

(today these disadvantages are no longer very disadvantageous)