License
When quoting this document, please refer to the following
URN: urn:nbn:de:0030-drops-9635
URL: http://drops.dagstuhl.de/opus/volltexte/2007/963/
Go to the corresponding Portal


Evans, William S.

Program Compression

pdf-format:
Document 1.pdf (146 KB)


Abstract

The talk focused on a grammar-based technique for identifying redundancy in program code and taking advantage of that redundancy to reduce the memory required to store and execute the program. The idea is to start with a simple context-free grammar that represents all valid basic blocks of any program. We represent a program by the parse trees (i.e. derivations) of its basic blocks using the grammar. We then modify the grammar, by considering sample programs, so that idioms of the language have shorter derivations in the modified grammar. Since each derivation represents a basic block, we can interpret the resulting set of derivations much as we would interpret the original program. We need only expand the grammar rules indicated by the derivation to produce a sequence of original program instructions to execute. The result is a program representation that is approximately 40% of the original program size and is interpretable by a very modest-sized interpreter.

BibTeX - Entry

@InProceedings{evans:DSP:2007:963,
  author =	{William S. Evans},
  title =	{Program Compression},
  booktitle =	{Duplication, Redundancy, and Similarity in Software},
  year =	{2007},
  editor =	{Rainer Koschke and Ettore Merlo and Andrew Walenstein},
  number =	{06301},
  series =	{Dagstuhl Seminar Proceedings},
  ISSN =	{1862-4405},
  publisher =	{Internationales Begegnungs- und Forschungszentrum f{\"u}r Informatik (IBFI), Schloss Dagstuhl, Germany},
  address =	{Dagstuhl, Germany},
  URL =		{http://drops.dagstuhl.de/opus/volltexte/2007/963},
  annote =	{Keywords: Program compression, clone detection, bytecode interpretation, variable-to-fixed length codes, context-free grammars}
}

Keywords: Program compression, clone detection, bytecode interpretation, variable-to-fixed length codes, context-free grammars
Seminar: 06301 - Duplication, Redundancy, and Similarity in Software
Issue Date: 2007
Date of publication: 19.04.2007


DROPS-Home | Fulltext Search | Imprint Published by LZI