article

Free access

Simple and efficient BURS table generation

Author:

Todd A. ProebstingAuthors Info & Claims

ACM SIGPLAN Notices, Volume 27, Issue 7

Pages 331 - 340

https://doi.org/10.1145/143103.143145

Published: 01 July 1992 Publication History

PDF eReader

Abstract

A simple and efficient algorithm for generating bottom-up rewrite system (BURS) tables is described. A small prototype implementation produces tables 10 to 30 times more quickly than the best current techniques. The algorithm does not require novel data structures or complicated algorithmic techniques. Previously published methods for the on-the-fly elimination of states are generalized and simplified to create a new method, triangle trimming, that is employed in the algorithm.

References

[1]

Alfred V. Aho, Mahedevan Ganapathi, and Steven W. K. Tjiang. Code generation using tree matching and dynamic programming. ACM Transactions on Programming Languages and Systems, 11(4):491-516, October 1989.

Digital Library

Google Scholar

[2]

A. Balachandran, D. M. Dhamdhere, and S. Biswas. Efficient retargetable code generation using bottom-up tree pattern matching. Computer Languages, 15(3):127-140, 1990.

Digital Library

Google Scholar

[3]

David R. Chase. An improvement to bottomup tree pattern matching. In Proceedings of the ljth Annual Symposium on Principles of Programming Languages, pages 168-177, 1987.

Digital Library

Google Scholar

[4]

Christopher W. Fraser and David R. Hanson. A code generation interface for ANSI C. Software--Practice and Experience, 21(9):963-988, September 1991.

Digital Library

Google Scholar

[5]

Christopher W. Fraser and Robert R. Henry. Hard-coding bottom-up code generation tables to save time and space. Software-- Practice and Experience, 21(1):1-12, January 1991.

Digital Library

Google Scholar

[6]

Christopher W. Fraser, Robert R. Henry, and Todd A. Proebsting. BURG -- fast optimal instruction selection and tree parsing. Technical Report 1066, University of Wisconsin, 1991.

Google Scholar

[7]

David R. Hanson. Fast allocation and deallocation of memory based on object lifetimes. Software--Practice and Experience, 20(1):5- 12, January 1990.

Digital Library

Google Scholar

[8]

Robert R. Henry. Encoding optimal pattern selection in a table-driven bottom-up treepattern marcher. Technical Report 89-02-04, University of Washington, 1989.

Google Scholar

[9]

Eduardo Peiegri-Llopart. Rewrite Systems, Pattern Matching, and Code Generation. Phd Thesis, Technical Report UCB/CSD 88/423, Computer Science Division, University of California, Berkeley, 1988.

Digital Library

Google Scholar

[10]

Eduardo Pelegri-Llopart and Susan L. Graham. Optimal code generation for expression trees: An application of BURS theory. In Proceedings of ~he 15th Annual Symposium on Principles of Programming Languages, pages 294-308, 1988.

Digital Library

Google Scholar

Cited By

View all

(2023)BibliographyEngineering a Compiler10.1016/B978-0-12-815412-0.00023-1(793-813)Online publication date: 2023
https://doi.org/10.1016/B978-0-12-815412-0.00023-1
Cooper KTorczon L(2023)Runtime OptimizationEngineering a Compiler10.1016/B978-0-12-815412-0.00020-6(713-755)Online publication date: 2023
https://doi.org/10.1016/B978-0-12-815412-0.00020-6
Cooper KTorczon L(2023)Instruction SelectionEngineering a Compiler10.1016/B978-0-12-815412-0.00017-6(575-616)Online publication date: 2023
https://doi.org/10.1016/B978-0-12-815412-0.00017-6
Show More Cited By

Index Terms

Simple and efficient BURS table generation

Recommendations

BURS automata generation

A simple and efficient algorithm for generating bottom-up rewrite system (BURS) tables is described. A small code-generator generator implementation produces BURS tables efficiently, even for complex instruction set descriptions. The algorithm does not ...
Simple and efficient BURS table generation
PLDI '92: Proceedings of the ACM SIGPLAN 1992 conference on Programming language design and implementation

A simple and efficient algorithm for generating bottom-up rewrite system (BURS) tables is described. A small prototype implementation produces tables 10 to 30 times more quickly than the best current techniques. The algorithm does not require novel data ...
Quality isosurface mesh generation using an extended marching cubes lookup table
EuroVis'08: Proceedings of the 10th Joint Eurographics / IEEE - VGTC conference on Visualization

The Marching Cubes Algorithm may return degenerate, zero area isosurface triangles, and often returns isosurface triangles with small areas, edges or angles. We show how to avoid both problems using an extended Marching Cubes lookup table. As opposed to ...

Comments

Please enable JavaScript to view thecomments powered by Disqus.

Information & Contributors

Information

Published In

ACM SIGPLAN Notices Volume 27, Issue 7

July 1992

352 pages

ISSN:0362-1340

EISSN:1558-1160

DOI:10.1145/143103

Editor:
Richard Wexelblat
IDA/CDED, Alexandria, VA

Issue’s Table of Contents

PLDI '92: Proceedings of the ACM SIGPLAN 1992 conference on Programming language design and implementation
July 1992
352 pages
ISBN:0897914759
DOI:10.1145/143095
Chairman:
Stuart I. Feldman
Bell Communications Research, Morristown, NJ
,
Editor:
Richard L. Wexelblat

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: 01 July 1992

Published in SIGPLAN Volume 27, Issue 7

Check for updates

Qualifiers

Article

Contributors

Other Metrics

View Article Metrics

Bibliometrics & Citations

Bibliometrics

Article Metrics

33
Total Citations
View Citations
658
Total Downloads

Downloads (Last 12 months)123
Downloads (Last 6 weeks)19

Reflects downloads up to 21 Nov 2024

Other Metrics

View Author Metrics

Citations

Cited By

View all

(2023)BibliographyEngineering a Compiler10.1016/B978-0-12-815412-0.00023-1(793-813)Online publication date: 2023
https://doi.org/10.1016/B978-0-12-815412-0.00023-1
Cooper KTorczon L(2023)Runtime OptimizationEngineering a Compiler10.1016/B978-0-12-815412-0.00020-6(713-755)Online publication date: 2023
https://doi.org/10.1016/B978-0-12-815412-0.00020-6
Cooper KTorczon L(2023)Instruction SelectionEngineering a Compiler10.1016/B978-0-12-815412-0.00017-6(575-616)Online publication date: 2023
https://doi.org/10.1016/B978-0-12-815412-0.00017-6
(2012)BibliographyEngineering a Compiler10.1016/B978-0-12-088478-0.00024-4(765-785)Online publication date: 2012
https://doi.org/10.1016/B978-0-12-088478-0.00024-4
Ramsey NDias JBall TSagiv M(2011)Resourceable, retargetable, modular instruction selection using a machine-independent, type-based tiling of low-level intermediate codeProceedings of the 38th annual ACM SIGPLAN-SIGACT symposium on Principles of programming languages10.1145/1926385.1926451(575-586)Online publication date: 26-Jan-2011
https://dl.acm.org/doi/10.1145/1926385.1926451
Ramsey NDias J(2011)Resourceable, retargetable, modular instruction selection using a machine-independent, type-based tiling of low-level intermediate codeACM SIGPLAN Notices10.1145/1925844.192645146:1(575-586)Online publication date: 26-Jan-2011
https://dl.acm.org/doi/10.1145/1925844.1926451
Dias JRamsey N(2006)Converting intermediate code to assembly code using declarative machine descriptionsProceedings of the 15th international conference on Compiler Construction10.1007/11688839_18(217-231)Online publication date: 30-Mar-2006
https://dl.acm.org/doi/10.1007/11688839_18
Kang K(2005)A study on the generation of JIT compiler using JBURGThe KIPS Transactions:PartA10.3745/KIPSTA.2005.12A.1.05912A:1(59-64)Online publication date: 1-Feb-2005
https://doi.org/10.3745/KIPSTA.2005.12A.1.059
Proebsting TWhaley B(2005)One-pass, optimal tree parsing — With or without treesCompiler Construction10.1007/3-540-61053-7_69(294-306)Online publication date: 7-Jun-2005
https://doi.org/10.1007/3-540-61053-7_69
Waite W(2005)Compiler construction: Craftsmanship or engineering?Compiler Construction10.1007/3-540-61053-7_59(151-159)Online publication date: 7-Jun-2005
https://doi.org/10.1007/3-540-61053-7_59
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.

Abstract

References

Cited By

Index Terms

Recommendations

BURS automata generation