GRAMMAR-BASED COMPRESSION
William S. Evans, Christopher W. F Raser · 2003
rnear top speed must useograms that must run at ornative machine code, butsome programs have moremodest performance require-ments. For example, a cellu-lar telephone handsetmight include software that reacts to key-strokes and spends most of its time waiting forthe next input. An interpreted code can runquickly enough for such applicationsand can be smaller than machinecode. Witness the success of the lan-guage Forth in embedded systems.Good encodings are, however,difficult to design. They mustanticipate the sequences of opera-tions that programmers will usemost often and assign the shortest codesto the most common sequences. Typical programs can be analyzed for sta-tistics to guide the design. Indeed, thedesigner of a compact representation maytarget a single program and design a com-pact language exclusively for that program.Of course, designing a language for everyprogram is too labor-intensive to be done byhand. It requires both automation and a dif-ferent interpreter for each compacted program,which can also be expensive. A better solutionmay be to design an interpreter for a set of pro-grams and use one interpreted language for all.Our focus here is on the automatic designand implementation of compact interpretablebytecodes. The objective is a form that is com-pact for a set of sample programs and for otherprograms with similar characteristics. Thekey to designing such compact byte-codes is to identify frequently occur-ring patterns of programconstructs, and to replace them witha single interpreted construct. Thisprocess is unlike the Huffmanfixed-to-variable length coding,which encodes single symbols using avariable number of bits, and more likeTunstall variable-to-fixed length coding,which encodes multiple symbols as a single,fixed-size codeword [12].