A classification of noncircular attribute grammars based on the look-ahead behavior

Wuu Yang*

*Corresponding author for this work

Research output: Contribution to journalArticlepeer-review

Abstract

We propose a family of static evaluators for subclasses of the well-defined (i.e., noncircular) attribute grammars. These evaluators augment the evaluator for the absolutely noncircular attribute grammars with look-ahead behaviors. Because this family covers exactly the set of all well-defined attribute grammars, well-defined attribute grammars may be classified into a hierarchy called the NC hierarchy, according to their evaluators in the family. The location of a noncircular attribute grammar in the NC hierarchy is an intrinsic property of the grammar. The NC hierarchy confirms a result of Riis and Skyum, which says that all well-defined attribute grammars allow a (static) pure multivisit evaluator by actually constructing such an evaluator. We also show that, for any finite m, an NC(m) attribute grammar can be transformed to an equivalent NC(0) grammar.

Original languageEnglish
Pages (from-to)210-227
Number of pages18
JournalIEEE Transactions on Software Engineering
Volume28
Issue number3
DOIs
StatePublished - 1 Mar 2002

Keywords

  • Attribute grammars
  • Grammar classification
  • Noncircular attribute grammars
  • Ordered attribute grammars
  • Pure multivisit attribute grammars
  • Simple multivisit attribute grammars
  • Well-defined attribute grammars

Cite this