Article

Free access

Higher order attribute grammars

Authors:

H. H. Vogt,

S. D. Swierstra,

M. F. KuiperAuthors Info & Claims

PLDI '89: Proceedings of the ACM SIGPLAN 1989 conference on Programming language design and implementation

Pages 131 - 145

https://doi.org/10.1145/73141.74830

Published: 21 June 1989 Publication History

PDF eReader

Abstract

A new kind of attribute grammars, called higher order attribute grammars, is defined. In higher order attribute grammars the structure tree can be expanded as a result of attribute computation. A structure tree may be stored in an attribute. The term higher order is used because of the analogy with higher order functions, where a function can be the result or parameter of another function. A relatively simple method, using OAGs, is described to derive an evaluation order on the defining attribute occurrences which comprises all possible direct and indirect attribute dependencies. As in OAGs, visit-sequences are computed from which an efficient algorithm for attribute evaluation can be derived.

References

[1]

M. Jazayeri, W.F. Ogden, W.C. Rounds. The intrinsically exponential complexity of the circularity problem for attributed grammars. In CACM 18, pages 679-706, 1975.

Digital Library

Google Scholar

[2]

U. Kastens, B. Hutt, and E. Zimmerman. GAG: A Practical Compiler Generator. Springer, 1982.

Google Scholar

[3]

H. Ganzinger and R. Giegerich. Attribute Coupled Grammars Sigplan Notices Vol. 19, No. 6, pages 157-170, 1984.

Digital Library

Google Scholar

[4]

U. Kastens. Ordered Attributed Grammars. Acta Informatica, 13, pages 229-256, 1980.

Google Scholar

[5]

D.E. Knuth. Semantics of context-free languages. Math. Syst. Theory, 2(2):127-145, 1968.

Crossref

Google Scholar

[6]

D.E. Knuth. Semantics of context-free languages (correction). Math. Syst. Theory, 5(1):95-96, 1971.

Crossref

Google Scholar

[7]

T. Reps. Generating language based environments, Tech. Rep, 82-514 and Ph.D dissertation, Dept. of Computer Science, Cot'nell Univ., Ithaca, N.Y., Aug. 1982.

Digital Library

Google Scholar

[8]

T. Reps, T. Teitelbaum and A. Demers. Incremental Context-Dependent Analysis for Language Based Editors. In ACM Transactions on Progr. Lang. and Systems, Vol. 5, No. 3, pages 449-477, July 1983.

Digital Library

Google Scholar

[9]

Reps, T. and Teitelbaum, T. The Synthesizer Generator Reference Manual. Cornell University, July, 1987.

Digital Library

Google Scholar

[10]

W.M. Waite and G.Goos. Compiler Construction. Springer, 1984.

Digital Library

Google Scholar

Cited By

View all

Podlubne AMey JAndreou APertuz SAßmann UGöhringer D(2024)Model-Based Generation of Hardware/Software Architectures With Hybrid Schedulers for Robotics SystemsIEEE Transactions on Computers10.1109/TC.2023.332380473:7(1640-1654)Online publication date: Jul-2024
https://doi.org/10.1109/TC.2023.3323804
Kramer LVan Wyk ESaraiva JDegueule TScott E(2023)Sharing Trees and Contextual Information: Re-imagining Forwarding in Attribute GrammarsProceedings of the 16th ACM SIGPLAN International Conference on Software Language Engineering10.1145/3623476.3623520(56-69)Online publication date: 23-Oct-2023
https://dl.acm.org/doi/10.1145/3623476.3623520
Ringo NKramer LVan Wyk ESaraiva JDegueule TScott E(2023)Nanopass Attribute GrammarsProceedings of the 16th ACM SIGPLAN International Conference on Software Language Engineering10.1145/3623476.3623514(70-83)Online publication date: 23-Oct-2023
https://dl.acm.org/doi/10.1145/3623476.3623514
Show More Cited By

Index Terms

Higher order attribute grammars
1. Software and its engineering
  1. Software notations and tools
    1. Compilers
    2. Formal language definitions
2. Theory of computation
  1. Formal languages and automata theory
    1. Formalisms
      1. Rewrite systems
    2. Grammars and context-free languages

Recommendations

Linearly Ordered Attribute Grammars: with Automatic Augmenting Dependency Selection
PEPM '15: Proceedings of the 2015 Workshop on Partial Evaluation and Program Manipulation

Attribute Grammars (AGs) extend Context-Free Grammars with attributes: information gathered on the syntax tree that adds semantics to the syntax. AGs are very well suited for describing static analyses, code-generation and other phases incorporated in a ...
Higher order attribute grammars
Proceedings of the SIGPLAN '89 symposium on Interpreters and interpretive techniques

A new kind of attribute grammars, called higher order attribute grammars, is defined. In higher order attribute grammars the structure tree can be expanded as a result of attribute computation. A structure tree may be stored in an attribute. The term ...
Monolithic and modular termination analyses for higher-order attribute grammars

In this paper we describe a sound, but not complete, analysis to prove the termination of higher-order attribute grammar evaluation caused by the creation of an unbounded number of (finite) trees as local tree-valued attributes, which are then ...

Comments

Please enable JavaScript to view thecomments powered by Disqus.

Information & Contributors

Information

Published In

PLDI '89: Proceedings of the ACM SIGPLAN 1989 conference on Programming language design and implementation

June 1989

355 pages

ISBN:089791306X

DOI:10.1145/73141

Editor:
R. L. Wexelblat
ACM Headquarters, New York, NY

ACM SIGPLAN Notices Volume 24, Issue 7
Proceedings of the SIGPLAN '89 symposium on Interpreters and interpretive techniques
July 1989
355 pages
ISSN:0362-1340
EISSN:1558-1160
DOI:10.1145/74818
Editor:
Richard Wexelblat
Issue’s Table of Contents

Permission to make digital or hard copies of all or part of this work for personal or classroom use is granted without fee provided that copies are not made or distributed for profit or commercial advantage and that copies bear this notice and the full citation on the first page. Copyrights for components of this work owned by others than ACM must be honored. Abstracting with credit is permitted. To copy otherwise, or republish, to post on servers or to redistribute to lists, requires prior specific permission and/or a fee. Request permissions from [email protected]

Publisher

Association for Computing Machinery

New York, NY, United States

Publication History

Published: 21 June 1989

Permissions

Request permissions for this article.

Request Permissions

Check for updates

Qualifiers

Article

Conference

PLDI89

Sponsor:

SIGPLAN

PLDI89: Programming Language Design & Implementation

June 19 - 23, 1989

Oregon, Portland, USA

Acceptance Rates

Overall Acceptance Rate 406 of 2,067 submissions, 20%

Contributors

Other Metrics

View Article Metrics

Bibliometrics & Citations

Bibliometrics

Article Metrics

167
Total Citations
View Citations
1,015
Total Downloads

Downloads (Last 12 months)161
Downloads (Last 6 weeks)18

Reflects downloads up to 30 Dec 2024

Other Metrics

View Author Metrics

Citations

Cited By

View all

Podlubne AMey JAndreou APertuz SAßmann UGöhringer D(2024)Model-Based Generation of Hardware/Software Architectures With Hybrid Schedulers for Robotics SystemsIEEE Transactions on Computers10.1109/TC.2023.332380473:7(1640-1654)Online publication date: Jul-2024
https://doi.org/10.1109/TC.2023.3323804
Kramer LVan Wyk ESaraiva JDegueule TScott E(2023)Sharing Trees and Contextual Information: Re-imagining Forwarding in Attribute GrammarsProceedings of the 16th ACM SIGPLAN International Conference on Software Language Engineering10.1145/3623476.3623520(56-69)Online publication date: 23-Oct-2023
https://dl.acm.org/doi/10.1145/3623476.3623520
Ringo NKramer LVan Wyk ESaraiva JDegueule TScott E(2023)Nanopass Attribute GrammarsProceedings of the 16th ACM SIGPLAN International Conference on Software Language Engineering10.1145/3623476.3623514(70-83)Online publication date: 23-Oct-2023
https://dl.acm.org/doi/10.1145/3623476.3623514
Zhao WMey JSchöne RGötz SAßmann U(2023)RobotRAGs: A Reference Attribute Grammar-based Integration Approach for Robotic Assembly Lines2023 49th Euromicro Conference on Software Engineering and Advanced Applications (SEAA)10.1109/SEAA60479.2023.00013(22-29)Online publication date: 6-Sep-2023
https://doi.org/10.1109/SEAA60479.2023.00013
Sasano IChoi K(2023)A text-based syntax completion method using LR parsing and its evaluationScience of Computer Programming10.1016/j.scico.2023.102957228:COnline publication date: 5-Jun-2023
https://dl.acm.org/doi/10.1016/j.scico.2023.102957
Steinhöfel DZeller ARoychoudhury ACadar CKim M(2022)Input invariantsProceedings of the 30th ACM Joint European Software Engineering Conference and Symposium on the Foundations of Software Engineering10.1145/3540250.3549139(583-594)Online publication date: 7-Nov-2022
https://dl.acm.org/doi/10.1145/3540250.3549139
Dura AReichenbach CSöderberg E(2021)JavaDL: automatically incrementalizing Java bug pattern detectionProceedings of the ACM on Programming Languages10.1145/34855425:OOPSLA(1-31)Online publication date: 15-Oct-2021
https://dl.acm.org/doi/10.1145/3485542
Sasano IChoi KLindley SMogensen T(2021)A text-based syntax completion method using LR parsingProceedings of the 2021 ACM SIGPLAN Workshop on Partial Evaluation and Program Manipulation10.1145/3441296.3441395(32-43)Online publication date: 18-Jan-2021
https://dl.acm.org/doi/10.1145/3441296.3441395
Hinkel GGarcia-Dominguez ASchöne RBoronat ATisi MLe Calvar TJouault FMarton JNyíri TAntal JElekes MSzárnyas G(2021)A cross-technology benchmark for incremental graph queriesSoftware and Systems Modeling10.1007/s10270-021-00927-521:2(755-804)Online publication date: 8-Dec-2021
https://doi.org/10.1007/s10270-021-00927-5
Kramer LVan Wyk ELämmel RTratt Lde Lara J(2020)Strategic tree rewriting in attribute grammarsProceedings of the 13th ACM SIGPLAN International Conference on Software Language Engineering10.1145/3426425.3426943(210-229)Online publication date: 16-Nov-2020
https://dl.acm.org/doi/10.1145/3426425.3426943
Show More Cited By

View Options

View options

PDF

View or Download as a PDF file.

PDF

eReader

View online with eReader.

eReader

Login options

Check if you have access through your login credentials or your institution to get full access on this article.

Cited By

Index Terms

Recommendations

Linearly Ordered Attribute Grammars: with Automatic Augmenting Dependency Selection

Higher order attribute grammars

Monolithic and modular termination analyses for higher-order attribute grammars