Slide 4.4: Annotated parse trees
Slide 4.6: Dependency graphs
Home

Evaluation Orders for SDDs

Dependency graphs are a useful tool for determining an evaluation order for the attribute instances in a given parse tree. While an annotated parse tree shows the values of attributes, a dependency graph helps us determine how those values can be computed.
A dependency graph depicts the flow of information among the attribute instances in a particular parse tree; an edge from one attribute instance to another means that the value of the first is needed to compute the second.
The attribute grammar of a base- 8 and 10 number is as follows:

  Production Semantic Rules
1. <based-num> ::= <num> <basechar> Val(<based-num>) = Val(<num>)
Base(<num>) = Base(<basechar>)
2. <basechar> ::= o Base(<basechar>) = 8
3. <basechar> ::= d Base(<basechar>) = 10
4. <num1> ::= <num2> <digit> Val(<num1>) =
  if Val(<digit>) == error or Val(<num2>) == error
  then error
  else Val(<num2>) * Base(<num1>) + Val(<digit>)
Base(<num2>) = Base(<num1>)
Base(<digit>) = Base(<num1>)
5. <num> ::= <digit> Val(<num>) = Val(<digit>)
Base(<digit>) = Base(<num>)
6. <digit> ::= 0 Val(<digit>) = 0
…   …   …
14. <digit> ::= 8 Val(<digit>) =
  if Base(<digit>) == 8
  then error else 8
15. <digit> ::= 9 Val(<digit>) =
  if Base(<digit>) == 8
  then error else 9