Article

Free access

Attribute grammars and data-flow languages

Author:

Rodney FarrowAuthors Info & Claims

SIGPLAN '83: Proceedings of the 1983 ACM SIGPLAN symposium on Programming language issues in software systems

Pages 28 - 40

https://doi.org/10.1145/800226.806849

Published: 01 June 1983 Publication History

Abstract

This paper examines the similarity between attribute grammars and data-flow languages. For any attribute grammar there is a data-flow program that is an evaluator for it, and we describe how to build this data-flow program. The design of semantic functions for an attribute grammar is seen to be a problem of programming in a data-flow language. Reinterpreting our experience writing attribute grammars, we suggest some techniques to use in data-flow programming and propose language features that will support them. We also propose using data-flow notation to specify the semantic functions of attribute grammars and implementing attribute evaluators in a data-flow language.

References

[1]

W.B. Ackerman. Data flow languages. IEEE Computer 15(2), February, 1982.

[2]

W.B. Ackerman and J.B. Dennis. VAL - a value oriented algorithmic language: Preliminary reference manual. Technical Report 278, Laboratory for Computer Science, MIT, June, 1979.

Digital Library

[3]

Arvind, K.P. Gostelow, and W. Plouffe. An asynchronous programming language and computing machine. Technical Report 114-a, Dept. of Information and Computer Science, University of Calif., Irvine, December, 1978.

[4]

J. Backus. Can Programming Be Liberated from the von Neumann Style? A Functional Style and its Algebra of Programs. CACM 21(8), August, 1978.

Digital Library

[5]

G.V. Bochmann. Semantic evaluation from left to right. Communications of the ACM 19, 1976. pp. 55-62.

Digital Library

[6]

D. Comte, G. Durrieu, O. Gelly, A. Plas, and J.C. Tyre. Parallelism, control and synchronization expression in a single assignment language. SIGPLAN Notices (1), January, 1978.

Digital Library

[7]

J.B. Dennis. Data Flow Supercomputers. IEEE Computer 13(11), November, 1980.

[8]

S. Drossopoulou, J. Uhl, G. Persch, G. Goos, M. Dausmann, and G. Winterstein. An Attribute Grammar for Ada. In Proceedings of the SIGPLAN '82 Symposium on Compiler Construction. ACM, June, 1982.

Digital Library

[9]

I. Fang. FOLDS, a declarative formal language definition system. Technical Report STAN-CS-72-329, Stanford University, 1972.

Digital Library

[10]

Rodney Farrow. LINGUIST-86 Yet another translator writing system based on attribute grammars. In Proceedings of the SIGPLAN symposium on compiler construction. ACM, June, 1982.

Digital Library

[11]

R. Farrow. Experience with an attribute grammar based compiler. In Conference Record of the Ninth ACM Symposium on Principles of Programming Languages. ACM, January, 1982.

Digital Library

[12]

H. Ganzinger, K. Ripken, and R. Wilhelm. Automatic generation of optimizing, multipass compilers. In Proceddings of IFIP 1977. 1977.

[13]

H. Ganzinger, R. Giegerich, U. Moncke and R. Wilhelm. A Truly Generative Semantics-Directed Compiler Generator. In Proceedings of the SIGPLAN Symposium on compiler construction. ACM, June, 1982.

Digital Library

[14]

H. Ganzinger. On storage optimization for automatically generated compilers. In K. Weirauch (editor), Theoretical Computer Science - Fourth GI Conference, Springer-Verlag, Berlin-Heidelberg-New York, 1979.

Digital Library

[15]

Peter Henderson and James H. Morris, Jr. A Lazy Evaluator. In Conference Record of the Third ACM Symposium on Principles of Programming Languages. ACM, January, 1976.

Digital Library

[16]

M. Jazayeri, W.F. Ogden, and W.C. Rounds. The intrinsically exponential complexity of the circularity problem for attribute grammars. Communications of the ACM 18, 1975.

Digital Library

[17]

M. Jazayeri and K.G. Walter. Alternating semantic evaluator. In Proceedings of ACM l975 Annual Conference. ACM, 1975.

Digital Library

[18]

U. Kastens, R. Kollner, E. Zimmerman, P. Hruschka, and A. Kappatsch. Eine attributierte Grammatik fur PEARL. Technical Report, Fak. f. Informatik, Universitat Karlsruhe, 1980.

[19]

Uwe Kastens, Brigitte Hutt, and Erich Zimmermann. GAG:A Practical Compiler Generator. Spring-Verlag, Berlin-Heidelberg-New York, 1982.

[20]

U. Kastens. Ordered attribute grammars. Acta Informatica 13, 1980.

[21]

T. Katayama. Translation of attribute grammar into procedures. Technical Report CS—K8001, Dept. of Computer Science, Tokyo Institute of Technology, July, 1980.

[22]

K. Kennedy and S. K. Warren. Automatic generation of efficient evaluators for attribute grammars. In Conference record of the third ACM symposium on principles of programming languages. ACM, 1976.

Digital Library

[23]

D. E. Knuth. Semantics of context-free languages. Mathematical Systems Theory 2, 1968. correction in volume 5, number 1.

[24]

K. Koskimies, L. Juutinen, and J. Paalli. An Attribute Grammar for C-Euclid, Computer Listing. Technical Report, Dept. of Computer Science, University of Helsinki, March, 1982.

[25]

K. Koskimies, K-J. Raiha, and M. Sarjakoski. Compiler Construction Using Attribute Grammars. In Proceedings of the SIGPLAN Symposium on compiler construction. ACM, June, 1982.

Digital Library

[26]

M. Marcotty, H.F. Ledgard, and G. Bochmann. A Sampler of Formal Definitions. Computing Surveys 8(2), June, 1976.

Digital Library

[27]

James R. McGraw. The VAL Language: Description and Analysis. ACM TOPLAS 4(1), January, 1982.

Digital Library

[28]

D. Pozefsky and M. Jazayeri. Space efficient storage management in an attribute evaluator. ACM TOPLAS 3(4), 1981.

Digital Library

[29]

Kari-Jouko Raiha, M. Saarinen, E. Soisalon-Soininen and M. Tienari. The Compiler Writing System HLP (Helsinki Language Processor). Technical Report A-1978-2, Dept. of Computer Science, Univ. of Helsinki, 1978.

[30]

Raiha, Kari-Jouko. Dynamic allocation of space for attribute-instances in multi-pass evaluators of attribute grammars. In Proceedings of the SIGPLAN symposium on compiler construction. ACM, 1979.

Digital Library

[31]

M. Saarinen. On constructing efficient evaluators for attribute grammars. In C. Ausiello and C. Bohm (editor), Automata, Languages, and Programming: 5th Colloquium. Springer-Verlag, Springer-Verlag, New York, 1978.

Digital Library

[32]

Richard M. Schell, Jr. Methods for constructing parallel compilers for use in a multiprocessor environment. PhD thesis, Computer Science Dept., University of Illinois at Urbana-Champaign, February, 1979.

Digital Library

[33]

W.A. Schulz. Semantic analysis and target language synthesis in a translator. PhD thesis, University of Colorado, Boulder, Colorado, July, 1976.

Digital Library

[34]

S. K. Warren. The coroutine model of attribute grammar evaluation. PhD thesis, Rice University, May, 1976.

Digital Library

[35]

D.A. Watt. An Extended Attribute Grammar for Pascal. SIGPLAN Notices 14(2), 1979.

Digital Library

[36]

C.S. Wetherell. Error Data Values in the Data-Flow Language VAL. ACM TOPLAS 4(2), April, 1982.

Digital Library

[37]

W. T. Wilner. A declarative semantic definition. PhD thesis, Dept. of Computer Science, Stanford University, 1971.

Digital Library

Cited By

Marttila-Kontio MRonkko MToivanen P(2009)Visual data flow languages with action systems2009 International Multiconference on Computer Science and Information Technology10.1109/IMCSIT.2009.5352781(589-594)Online publication date: Oct-2009
https://doi.org/10.1109/IMCSIT.2009.5352781
Marttila-Kontio MHassinen M(2008)Implementation of an automated documentation system with a visual data flow programming language2008 First International Conference on the Applications of Digital Information and Web Technologies (ICADIWT)10.1109/ICADIWT.2008.4664320(68-73)Online publication date: Aug-2008
https://doi.org/10.1109/ICADIWT.2008.4664320
Liu YZhang N(2002)On Concept-Based Definition of Domain-Specific LanguagesFormal Methods and Software Engineering10.1007/3-540-36103-0_27(237-248)Online publication date: 10-Oct-2002
https://doi.org/10.1007/3-540-36103-0_27
Show More Cited By

Index Terms

Attribute grammars and data-flow languages
1. Software and its engineering
  1. Software notations and tools
    1. General programming languages
      1. Language types
        Data flow languages
2. Theory of computation
  1. Formal languages and automata theory
    1. Formalisms
      1. Rewrite systems
    2. Grammars and context-free languages

Recommendations

Attribute grammars and data-flow languages

This paper examines the similarity between attribute grammars and data-flow languages. For any attribute grammar there is a data-flow program that is an evaluator for it, and we describe how to build this data-flow program. The design of semantic ...
The formal power of one-visit attribute grammars

An attribute grammar is one-visit if the attributes can be evaluated by walking through the derivation tree in such a way that each subtree is visited at most once. One-visit (1V) attribute grammars are compared with one-pass left-to-right (L) attribute ...
Conditional attribute grammars

Attribute grammars are a useful formalism for the specification of computations on structured terms. The classical definition of attribute grammars, however, has no way of treating conditionals nonstrictly. Consequently, the natural way of expressing ...

Comments

Please enable JavaScript to view thecomments powered by Disqus.

Information & Contributors

Information

Published In

cover image ACM Conferences

SIGPLAN '83: Proceedings of the 1983 ACM SIGPLAN symposium on Programming language issues in software systems

June 1983

230 pages

ISBN:0897911083

DOI:10.1145/800226

ACM SIGPLAN Notices Volume 18, Issue 6
June 1983
219 pages
ISSN:0362-1340
EISSN:1558-1160
DOI:10.1145/872728
Issue’s Table of Contents

Copyright © 1983 Author.

Sponsors

SIGPLAN: ACM Special Interest Group on Programming Languages

Publisher

Association for Computing Machinery

New York, NY, United States

Publication History

Published: 01 June 1983

Permissions

Request permissions for this article.

Request Permissions

Check for updates

Qualifiers

Article

Conference

VEE05

Sponsor:

SIGPLAN

VEE05: First International Conference on Virtual Execution Environments

June 27 - 29, 1983

California, San Francisco, USA

Contributors

Other Metrics

View Article Metrics

Bibliometrics & Citations

Bibliometrics

Article Metrics

11
Total Citations
View Citations
545
Total Downloads

Downloads (Last 12 months)125
Downloads (Last 6 weeks)13

Reflects downloads up to 21 Nov 2024

Other Metrics

View Author Metrics

Citations

Cited By

Marttila-Kontio MRonkko MToivanen P(2009)Visual data flow languages with action systems2009 International Multiconference on Computer Science and Information Technology10.1109/IMCSIT.2009.5352781(589-594)Online publication date: Oct-2009
https://doi.org/10.1109/IMCSIT.2009.5352781
Marttila-Kontio MHassinen M(2008)Implementation of an automated documentation system with a visual data flow programming language2008 First International Conference on the Applications of Digital Information and Web Technologies (ICADIWT)10.1109/ICADIWT.2008.4664320(68-73)Online publication date: Aug-2008
https://doi.org/10.1109/ICADIWT.2008.4664320
Liu YZhang N(2002)On Concept-Based Definition of Domain-Specific LanguagesFormal Methods and Software Engineering10.1007/3-540-36103-0_27(237-248)Online publication date: 10-Oct-2002
https://doi.org/10.1007/3-540-36103-0_27
Economakos GPapakonstantinou G(1999)Language based design verification with semantic analysisProceedings 25th EUROMICRO Conference. Informatics: Theory and Practice for the New Millennium10.1109/EURMIC.1999.794479(268-275 vol.1)Online publication date: 1999
https://doi.org/10.1109/EURMIC.1999.794479
Economakos GPapakostantinou GTsankas PGeorge KLamong G(1998)Incorporating multi-pass attribute grammars for the high-level synthesis of ASICsProceedings of the 1998 ACM symposium on Applied Computing10.1145/330560.330568(45-49)Online publication date: 27-Feb-1998
https://dl.acm.org/doi/10.1145/330560.330568
Paakki J(1995)Attribute grammar paradigms—a high-level methodology in language implementationACM Computing Surveys10.1145/210376.19740927:2(196-255)Online publication date: 1-Jun-1995
https://dl.acm.org/doi/10.1145/210376.197409
Klaiber AGokhale M(1992)Parallel Evaluation of Attribute GrammarsIEEE Transactions on Parallel and Distributed Systems10.1109/71.1272613:2(206-220)Online publication date: 1-Mar-1992
https://dl.acm.org/doi/10.1109/71.127261
Wang SYe D(1991)On parallel evaluation of ordered attribute grammarsJournal of Computer Science and Technology10.1007/BF029483946:4(347-354)Online publication date: Oct-1991
https://doi.org/10.1007/BF02948394
Farrow RStanculescu A(1989)A VHDL compiler based on attribute grammar methodologyACM SIGPLAN Notices10.1145/74818.7482924:7(120-130)Online publication date: 21-Jun-1989
https://dl.acm.org/doi/10.1145/74818.74829
Farrow RStanculescu A(1989)A VHDL compiler based on attribute grammar methodologyProceedings of the ACM SIGPLAN 1989 conference on Programming language design and implementation10.1145/73141.74829(120-130)Online publication date: 21-Jun-1989
https://dl.acm.org/doi/10.1145/73141.74829
Show More Cited By

View Options

View options

PDF

View or Download as a PDF file.

eReader

View online with eReader.

Login options

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

Full Access

Get this Publication

Media

Figures

Other

Tables

View Table of Contents