Bytecode compression via profiled grammar rewriting

This paper describes the design and implementation of a method for producin g compact, bytecoded instruction sets and interpreters for them. It accepts a grammar for programs written using a simple bytecoded stack-based instru ction set, as well as a training set of sample programs. The system transfo rms the grammar, creating an expanded grammar that represents the same lang uage as the original grammar, but permits a shorter derivation of the sampl e programs and others like them. A program's derivation under the expanded grammar forms the compressed bytecode representation of the program. The in terpreter for this bytecode is automatically generated from the original by tecode interpreter and the expanded grammar. Programs expressed using compr essed bytecode can be substantially smaller than their original bytecode re presentation and even their machine code representation. For example, compr ession cuts the bytecode for Ice from 199KB to 58KB but increases the size of the interpreter by just over 11KB.