article

Free access

Using dynamic programming to generate optimized code in a Graham-Glanville style code generator

Authors:

Thomas W. Christopher,

Philip J. Hatcher,

Ronald C. KukukAuthors Info & Claims

ACM SIGPLAN Notices, Volume 19, Issue 6

Pages 25 - 36

https://doi.org/10.1145/502949.502877

Published: 01 June 1984 Publication History

PDF eReader

Abstract

We have performed an investigation of using a dynamic programming to generate optimized code in a Graham-Glanville style code generator We use Earley's algorithm rather than an IR algorithm for parsing in the code generator Not only does the use of Earley's algorithm make the construction of the code generator very easy it allows the selection of optimal code by dynamic programming (using a modification of the technique developed by Lvon) We compare two implementations of this technique to conventional hand-coded code generators using a subset of BASIC as the source language Further we discuss the use of this technique in an experimental C compiler.

References

[1]

Aho, A. V. and Johnson, S. C. "Optimal Code Generation For Expression Trees" JACM 23,3(July 76) 488-501.

Digital Library

Google Scholar

[2]

Bird, P. L. "An Implementation of a Code Generator Specification Language for Table Driven Code Generators" Proceedings of the SIGPLAN '82 Symposium on Compiler Construction, Boston, Mass. June 23-25, 1982, SIGPLAN Notices 17,6 (June 1982) 44-55.

Digital Library

Google Scholar

[3]

Cattell, R. G. G. "Automatic Derivation of Code Generators from Machine Descriptions" TOPLAS 2,2 (Apr. 1980) 173-190

Digital Library

Google Scholar

[4]

Crawford, J. "Engineering a Production Code Generator" Proceedings of the SIGPLAN '82 Symposium on Compiler Construction, Boston, Mass. June 23-25, 1982, SIGPLAN Notices 17,6 (June 1982) 205-215.

Digital Library

Google Scholar

[5]

Earley, J. "An Efficient Context-Free Parsing Algorithm" CACM 13,2 (Feb 70) 94-102.

Digital Library

Google Scholar

[6]

Glanville, R. S. "A Machine Independent Algorithm for Code Generation and Its Use in Retargetable Compilers" Phd Dissertation, Univ. of California, Berkeley, 1977.

Digital Library

Google Scholar

[7]

Graham, S. L. "Table-Driven Code Generation" Computer, 13,8 (Aug. 1980) 25-34.

Digital Library

Google Scholar

[8]

Graham, S. L., Henry, R. R., Schulman, R. A. "An Experiment in Table Driven Code Generation" Proceedings of the SIGPLAN '82 Symposium on Compiler Construction, Boston, Mass. June 23-25, 1982, SIGPLAN Notices 17,6 (June 1982) 32-43.

Digital Library

Google Scholar

[9]

Johnson, S. C. "A Portable Compiler: Theory and Practice" Proceedings of the Fifth ACM Symposium on Principles of Programming Languages, Jan 1978.

Digital Library

Google Scholar

[10]

Krumme, D. W., Ackley, D. H. "A Practical Method for Code Generation Based on Exhaustive Search" Proceedings of the SIGPLAN '82 Symposium on Compiler Construction, Boston, Mass. June 23-25, 1982, SIGPLAN Notices 17,6 (June 1982) 185-196.

Digital Library

Google Scholar

[11]

Landwehr, R., Jansohn, H-S, Goos, G. "Experience with an Automatic Code Generator Generator" Proceedings of the SIGPLAN '82 Symposium on Compiler Construction, Boston, Mass. June 23-25, 1982, SIGPLAN Notices 17,6 (June 1982) 56-66.

Digital Library

Google Scholar

[12]

Lyon, G. "Syntax-Directed Least-Errors Analysis for Context Free Languages: A Practical Approach" CACM 17,1 (Jan 74) 3-14.

Digital Library

Google Scholar

Cited By

View all

Yang W(2010)A fast general parser for automatic code generationProceedings of the Second Russia-Taiwan conference on Methods and tools of parallel programming multicomputers10.5555/1927517.1927523(30-39)Online publication date: 16-May-2010
https://dl.acm.org/doi/10.5555/1927517.1927523
Shankar P(2010)Instruction Selection Using Tree ParsingThe Compiler Design Handbook10.1201/9781420040579.ch15Online publication date: 7-Mar-2010
https://doi.org/10.1201/9781420040579.ch15
Shankar P(2009)Instruction Selection Using Tree ParsingThe Compiler Design Handbook10.1201/9781420043839.ch17(17-1-17-36)Online publication date: 7-Dec-2009
https://doi.org/10.1201/9781420043839.ch17
Show More Cited By

Index Terms

Using dynamic programming to generate optimized code in a Graham-Glanville style code generator
1. Software and its engineering
  1. Software notations and tools
    1. Compilers

Index terms have been assigned to the content through auto-classification.

Recommendations

Using dynamic programming to generate optimized code in a Graham-Glanville style code generator
SIGPLAN '84: Proceedings of the 1984 SIGPLAN symposium on Compiler construction

We have performed an investigation of using a dynamic programming to generate optimized code in a Graham-Glanville style code generator We use Earley's algorithm rather than an IR algorithm for parsing in the code generator Not only does the use of ...
Graham/glanville code generators (compiler, parser, programming language)
Two Birds with One Stone: Boosting Code Generation and Code Search via a Generative Adversarial Network

Automatically transforming developers' natural language descriptions into source code has been a longstanding goal in software engineering research. Two types of approaches have been proposed in the literature to achieve this: code generation, which ...

Comments

Please enable JavaScript to view thecomments powered by Disqus.

Information & Contributors

Information

Published In

ACM SIGPLAN Notices Volume 19, Issue 6

Proceedings of the SIGPLAN '84 symposium on compiler construction

June 1984

318 pages

ISSN:0362-1340

EISSN:1558-1160

DOI:10.1145/502949

Issue’s Table of Contents

SIGPLAN '84: Proceedings of the 1984 SIGPLAN symposium on Compiler construction
June 1984
328 pages
ISBN:0897911393
DOI:10.1145/502874
General Chair:
Mary Van Deusen
IBM
,
Program Chair:
Susan L. Graham
University of California, Berkeley

Publisher

Association for Computing Machinery

New York, NY, United States

Publication History

Published: 01 June 1984

Published in SIGPLAN Volume 19, Issue 6

Check for updates

Author Tags

Qualifiers

Article

Contributors

Other Metrics

View Article Metrics

Bibliometrics & Citations

Bibliometrics

Article Metrics

16
Total Citations
View Citations
476
Total Downloads

Downloads (Last 12 months)64
Downloads (Last 6 weeks)25

Reflects downloads up to 14 Aug 2024

Other Metrics

View Author Metrics

Citations

Cited By

View all

Yang W(2010)A fast general parser for automatic code generationProceedings of the Second Russia-Taiwan conference on Methods and tools of parallel programming multicomputers10.5555/1927517.1927523(30-39)Online publication date: 16-May-2010
https://dl.acm.org/doi/10.5555/1927517.1927523
Shankar P(2010)Instruction Selection Using Tree ParsingThe Compiler Design Handbook10.1201/9781420040579.ch15Online publication date: 7-Mar-2010
https://doi.org/10.1201/9781420040579.ch15
Shankar P(2009)Instruction Selection Using Tree ParsingThe Compiler Design Handbook10.1201/9781420043839.ch17(17-1-17-36)Online publication date: 7-Dec-2009
https://doi.org/10.1201/9781420043839.ch17
Horspool RScheunemann A(2006)Automating the selection of code templatesSoftware: Practice and Experience10.1002/spe.438015050915:5(503-514)Online publication date: 30-Oct-2006
https://doi.org/10.1002/spe.4380150509
Nymeyer AKatoen JWestra YAlblas H(2005)Code generation = A* + BURSCompiler Construction10.1007/3-540-61053-7_60(160-176)Online publication date: 7-Jun-2005
https://doi.org/10.1007/3-540-61053-7_60
Giegerich RSchmal K(2005)Code selection techniques: Pattern matching, tree parsing, and inversion of derivorsESOP '8810.1007/3-540-19027-9_17(247-268)Online publication date: 1-Jun-2005
https://doi.org/10.1007/3-540-19027-9_17
(2000)Extending Graham-Glanville techniques for optimal code generationACM Transactions on Programming Languages and Systems10.1145/371880.37188122:6(973-1001)Online publication date: 1-Nov-2000
https://dl.acm.org/doi/10.1145/371880.371881
Aho AGanapathi MTjiang S(1989)Code generation using tree matching and dynamic programmingACM Transactions on Programming Languages and Systems10.1145/69558.7570011:4(491-516)Online publication date: 1-Oct-1989
https://dl.acm.org/doi/10.1145/69558.75700
Hemerik CKateon J(1989)Bottom-up tree acceptorsScience of Computer Programming10.1016/0167-6423(89)90015-413:1(51-72)Online publication date: 1-Dec-1989
https://dl.acm.org/doi/10.1016/0167-6423%2889%2990015-4
Ryan RSpiller H(1985)The C programming language and a C compilerIBM Systems Journal10.1147/sj.241.003724:1(37-48)Online publication date: 1-Mar-1985
https://dl.acm.org/doi/10.1147/sj.241.0037
Show More Cited By

View Options

View options

PDF

View or Download as a PDF file.

PDF

eReader

View online with eReader.

eReader

Get Access

Login options

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

Abstract

References

Cited By

Index Terms

Recommendations