A finest partitioning algorithm for attribute grammars

Wuu Yang*

*Corresponding author for this work

Research output: Contribution to journalArticlepeer-review


The attribute dependence graph of a syntax tree may be partitioned into disjoint regions. Attribute instances in different regions are independent of one other. The advantages of partitioning the attribute dependence graph include simplifying the attribute grammar conceptually and allowing the possibility of parallel evaluation. We present a static partitioning algorithm for attribute grammars. The algorithm builds the set of all feasible partitions for every production by analyzing the grammar. After the attributed syntax tree is constructed, one of the feasible partitions is chosen for each production instance in the syntax tree. Gluing together the selected partitions for individual production instances results in a partition of the attribute dependence graph of the syntax tree. No further merging or partitioning is needed at evaluation time. In addition to static partitioning, the algorithm always produces the finest partition of every attribute dependence graph. An application of the partitioning technique is the strictness analysis for a simple programming language that contains no higher-order functions.

Original languageEnglish
Pages (from-to)145-164
Number of pages20
JournalComputer Languages
Issue number3
StatePublished - Oct 1999


  • Attribute grammars
  • Parallel evaluation
  • Partitioning
  • Strictness analysis

Fingerprint Dive into the research topics of 'A finest partitioning algorithm for attribute grammars'. Together they form a unique fingerprint.

Cite this