| Article ID: | iaor19961895 |
| Country: | United States |
| Volume: | 17 |
| Issue: | 3 |
| Start Page Number: | 461 |
| End Page Number: | 486 |
| Publication Date: | Jul 1995 |
| Journal: | ACM Trans Progr Lang Sys |
| Authors: | Proebsting T.A. |
A simple and efficient algorithm for generating bottom-up rewrite system (BURS) tables is described. A small code-Generator generator implementation produces BURS tables efficiency, even for complex instruction set descriptions. The algorithm does not require novel data structures or complicated algorithmic techniques. Previously published methods for on-the-fly elimination of states are generalized and simplified to create a new method, triangle trimming, that is employed in the algorithm. A prototype implementation, BURG, generates BURS tables very efficiently.