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.