License: Creative Commons Attribution 4.0 International license (CC BY 4.0)
When quoting this document, please refer to the following
DOI: 10.4230/DagSemProc.06301.10
URN: urn:nbn:de:0030-drops-9635
URL: http://dagstuhl.sunsite.rwth-aachen.de/volltexte/2007/963/
Go to the corresponding Portal

Evans, William S.

Program Compression

pdf-format:
06301.EvansWilliam.Paper.963.pdf (0.1 MB)

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:DagSemProc.06301.10,
  author =	{Evans, William S.},
  title =	{{Program Compression}},
  booktitle =	{Duplication, Redundancy, and Similarity in Software},
  pages =	{1--10},
  series =	{Dagstuhl Seminar Proceedings (DagSemProc)},
  ISSN =	{1862-4405},
  year =	{2007},
  volume =	{6301},
  editor =	{Rainer Koschke and Ettore Merlo and Andrew Walenstein},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/opus/volltexte/2007/963},
  URN =		{urn:nbn:de:0030-drops-9635},
  doi =		{10.4230/DagSemProc.06301.10},
  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
Collection: 06301 - Duplication, Redundancy, and Similarity in Software
Issue Date: 2007
Date of publication: 19.04.2007

DROPS-Home | Fulltext Search | Imprint | Privacy Published by LZI