Passes and paths of attribute grammars

Joost Engelfriet, Gilberto Filè

Research output: Contribution to journalArticleAcademic

13 Citations (Scopus)
8 Downloads (Pure)


An attribute grammar is pure (left-to-right) multi-pass if a bounded number of left-to-right passes over the derivation tree suffice to compute all its attributes. There is no requirement, as for the usual multi-pass attribute grammars, that all occurrences of the same attribute are computed in the same pass. It is shown that the problem of determining whether an arbitrary attribute grammar is pure multipass, is of inherently exponential time complexity. For fixed k > 0, it can be decided in polynomial time whether an attribute grammar is pure k-pass. The proofs are based on a characterization of pure multi-pass attribute grammars in terms of paths through their dependency graphs. A general result on dependency paths of attribute grammars relates them to (finite-copying) top-down tree transducers. The formal power of k-pass attribute grammars increases with increasing k. Formally, multi-pass attribute grammars are less powerful than arbitrary attribute grammars.
Original languageEnglish
Pages (from-to)125-169
JournalInformation and Control
Issue number2
Publication statusPublished - 1981
Externally publishedYes


Dive into the research topics of 'Passes and paths of attribute grammars'. Together they form a unique fingerprint.

Cite this