Sharing Trees and Contextual Information: Re-imagining Forwarding in Attribute Grammars

Lucas Kramer, Eric Van Wyk

Research output: Chapter in Book/Report/Conference proceedingConference contribution

Abstract

It is not uncommon to design a programming language as a core language with additional features that define some semantic analyses, but delegate others to their translation to the core. Many analyses require contextual information, such as a typing environment. When this is the same for a term under a new feature and under that feature's core translation, then the term (and computations over it) can be shared, with context provided by the translation. This avoids redundant, and sometimes exponential computations. This paper brings sharing of terms and specification of context to forwarding, a language extensibility mechanism in attribute grammars. Here context is defined by equations for inherited attributes that provide (the same) values to shared trees. Applying these techniques to the ableC extensible C compiler replaced around 80% of the cases in which tree sharing was achieved by a crude mechanism that prevented sharing context specifications and limited language extensibility. It also replaced all cases in which this mechanism was used to avoid exponential computations and allowed the removal of many, now unneeded, inherited attribute equations.

Original languageEnglish (US)
Title of host publicationSLE 2023 - Proceedings of the 16th ACM SIGPLAN International Conference on Software Language Engineering, Co-located with
Subtitle of host publicationSPLASH 2023
EditorsJoao Saraiva, Thomas Degueule, Elizabeth Scott
PublisherAssociation for Computing Machinery, Inc
Pages56-69
Number of pages14
ISBN (Electronic)9798400703966
DOIs
StatePublished - Oct 23 2023
Event16th ACM SIGPLAN International Conference on Software Language Engineering, SLE 2023 - Cascais, Portugal
Duration: Oct 23 2023Oct 24 2023

Publication series

NameProceedings of the 16th ACM SIGPLAN International Conference on Software Language Engineering

Conference

Conference16th ACM SIGPLAN International Conference on Software Language Engineering, SLE 2023
Country/TerritoryPortugal
CityCascais
Period10/23/2310/24/23

Bibliographical note

Publisher Copyright:
© 2023 ACM.

Keywords

  • attribute grammars
  • compilers
  • modular and extensible languages
  • static analysis
  • well-definedness

Fingerprint

Dive into the research topics of 'Sharing Trees and Contextual Information: Re-imagining Forwarding in Attribute Grammars'. Together they form a unique fingerprint.

Cite this