Optimization of Parser Tables for Portable Compilers

Abstract

Six methods for parser table compression are compared.The investigations are focused on four methods that allow the access of table entries with a constant number of index operations.The advantage of these methods is that the access to the compressed tables can be programmed efficiently in portable high-level languages like Pascal or FORTRAN.The results are related to two simple methods based on list searching.Experimental results on eleven different grammars show that, on the average, a method based on graph coloring turns out best.