2026-07-20T05:35:40Z https://drops.dagstuhl.de/oai

oai:drops-oai.dagstuhl.de:963 2024-03-06T11:07:00Z ddc:004 open_access

Program Compression Evans, William S. Program compression clone detection bytecode interpretation variable-to-fixed length codes context-free grammars 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. Schloss Dagstuhl – Leibniz-Zentrum für Informatik William S. Evans 2007 Is Part Of Dagstuhl Seminar Proceedings, Volume 6301, Duplication, Redundancy, and Similarity in Software (2007) InProceedings Text doc-type:ResearchArticle publishedVersion application/pdf doi:10.4230/DagSemProc.06301.10 urn:nbn:de:0030-drops-9635 https://drops.dagstuhl.de/entities/document/10.4230/DagSemProc.06301.10 eng https://creativecommons.org/licenses/by/4.0/legalcode