Mobiler Code

Syntaxorientierte Kodierung

Thema: Komprimierung von Java-Programmen auf Basis des abstrakten Syntaxbaums

Während der Syntaxüberprüfung eines Java-Programms wird durch den Parser ein abstrakter Syntaxbaum (AST) erstellt. Statt dem AST wird allerdings bei herkömmlichen Verfahren eine (Byte-Code) Repräsentation des Codes erzeugt und komprimiert. Allerdings benötigt auf der Konsumentenseite der Compiler (Backend) zur Codeerzeugung erneut den AST. Was zur Folge hat, dass dieser unter Verlust von wertvoller Rechenzeit mühsam neu aufgebaut werden muss.
Hier setzt dieses Verfahren an. Indem statt einer Repräsentation des Codes, die Repräsentation des AST erzeugt und komprimiert wird, kann der Baum nach der Dekompression auf der Konsumentenseite sofort zur Verarbeitung an das Backend weitergegeben werden.

Ein erneutes Parsen entfällt, die Start-Up Zeit wird somit verkürzt. Zusätzlich erreicht dieses Verfahren durch die Ausnutzung der syntaktischen Eigenheiten des vorliegenden Programms höhere Kompressionsraten als die bislang bekannten Verfahren.
Aus diesen Gründen muss (und kann) allerdings hingenommen werden, dass die Kompression auf der Produzentenseite was die benötigte Rechenzeit betrifft, verglichen mit anderen Verfahren sehr aufwendig ist.

Abb. 1: Übersicht der verschiedenen Kompressionsverfahren (Folie des korrespondierenden Vortrags)

Überblick

Kompressionsverfahren lassen sich grob in 3 Kategorien unterteilen.

• Analyse und Optimierung des Quellcodes
• Statistische Auswertung und Kompression des Objekt-Codes mit Hilfe statistischer Verfahren
• Kompression des abstrakten Syntaxbaums (AST) mit Hilfe von "Wörterbüchern" oder statistischen Verfahren

Die Besonderheit bei Verfahren der Quellcodeoptimierung besteht darin, dass der eigentliche Quellcode mit Hilfe bestimmter, für die Programmiersprache spezifischer, Regeln lediglich verkürzt wird - und somit ausführbar bleibt.
Die zweite Kategorie umfasst verschiedene allg. und spezielle Komprimierungstechniken - wie "Arithmetic Coding", "Wheeler Transformation" und ähnliche Verfahren. Diese haben gemein, dass die Kompression am Objekt-Code stattfindet. Das Ergebnis muss auf der Konsumentenseite zunächst dekomprimiert werden, um weiter verarbeitet werden zu können.
Ebenso verfährt die dritte Kategorie der Kompressionsverfahren, wobei diese jedoch nicht mit dem Objekt-Code, sondern auf der Basis des abstrakten Syntaxbaums (AST) arbeiten.

Der AST selbst wird mit Hilfe einer für die Programmiersprache spezifischen abstrakten Grammatik (AG) vom Parser erstellt. Der so erhaltene AST wird analysiert und komprimiert. Dabei kann der Komprimierungsvorgang mit Hilfe von Wörterbüchern oder mit statistischen Verfahren realisiert werden.
Im ersten Fall wird mit Hilfe eines Algorithmus eine Wortliste der angetroffenen "Texte" erstellt. Dabei werden Redundanzen beseitigt - der AST somit verkleinert.
Noch ein Stück weiter geht unser Ansatz. Hier werden zunächst ebenfalls - allerdings nur bestimmte - Strings (Klassennamen, Textstellen...) gesammelt und Redundanzen beseitigt. Der verbleibende Baum wird nun nach statistischen Kriterien optimiert (Aufgabe des PPM) und ausgelesen. Das Ergebnis ist eine Repräsentation des Baumes, du nunmehr nur aus Ganzzahlwerten besteht und durch geeignete Komprimierungsverfahren (hier: "Arithmetic Coder") mit besseren Ergebnissen komprimiert werden kann, als die Wörterbuchvariante.

Abb. 2: Arbeitsschritte auf dem Weg vom Quellcode zum komprimierten AST (und zurück)
links: Produzentenseite (Kompression)
rechts: Konsumentenseite (Dekompression)
(Folie des korrespondierenden Vortrags)

Implementierung

Dieses Modell nutzt ein in Java geschriebenes Frontend zum Parsen der Eingangsdaten. Der daraus erstellte AST wird von einem in Python verfassten Prototyp analysiert, komprimiert und auf der Konsumentenseite auch dekomprimiert. Der daraus resultierende AST kann ohne Verifikation an jedes beliebige Backend übergeben werden.

Jeder AST korrespondiert zu einer entsprechenden abstrakten Grammatik (AG). Dabei handelt es sich um eine für die Programmiersprache geschriebene Datei, welche eine Menge von Regeln enthält, die ihrerseits die syntaktische Struktur der Programmiersprache beschreiben.

Gegen diese Datei kann ein vorliegender Quellcode geparst und so auf syntaktische Korrektheit geprüft werden.

Die Syntaxprüfung selbst kann als Bottom-Up Verfahren implementiert werden. Vereinfacht gesprochen enthält die Grammatik eine Reihe von Verkürzungsregeln. Diese lassen sich als Baum darstellen, der alle syntaktisch korrekten ASTs (und damit auch Programme) beschreibt. Der Parser wendet auf den Eingabestring wiederholt die Verkürzungsregeln an, bis entweder der leere String entsteht - was bedeutet, dass die Eingabe syntaktisch korrekt ist - oder sich keine Regel mehr anwenden lässt - was nichts anderes heißt, als dass ein syntaktischer Fehler vorliegt.

Abb. 3: Baumdarstellung einer abstrakten Grammatik (Folie des korrespondierenden Vortrags)

Dabei entsteht (ausgehend von den Blättern) eine konkrete Baumrepräsentation des Programms.

Die meisten Programmiersprachen sind kontextfrei, natürliche Sprachen zumindest noch kontextsensitiv. Es handelt sich also nicht um finite Sprachen. Aus den Regeln, welche AG zur Verfügung stellen, lässt sich eine unendlich große Menge syntaktisch korrekter Programme ableiten.

Die AG selbst ist nicht zwangsweise eindeutig - es gibt für eine Programmiersprache mehrere äquivalente Grammatiken, die unterschiedlich kompliziert sein können. Zur besseren Lesbarkeit ist es sinnvoll, sich auf eine Reihe von Normalformen für diese Grammatiken zu beschränken. Was nichts anderes heißt, als die Anzahl der erlaubten Regeln zwecks Lesbarkeit und besserer Verarbeitung zu begrenzen, ohne dabei die Funktionalität einzuschränken.

AG enthalten sowohl terminale Zeichenketten, wie auch non-terminale Symbole. In der Praxis kommen außerdem eine Reihe Schlüsselwörter für den Parser hinzu.
Grob betrachtet gibt es 3 verschiedene Gruppen von Regeln.

• Die erste Gruppe sind String-Regeln (oder "Entities"). Dabei handelt es sich um solche Regeln, die ein non-terminales Symbol (oder "Element") auf eine Menge terminaler Zeichenketten ableiten.
• Kompositionsregeln leiten ihrerseits ein non-term. Symbol auf eine Folge anderer non-term. Symbole ab.
• Wahlregeln leiten ein non-term. Symbol auf eine Menge non-term. Symbole ab.

Für die weitere Verarbeitung wird eine Repräsentation des Baums erstellt.

Abb. 4: Die Umsetzung einer abstrakten Grammatik als genormte, informelle Beschreibung(Folie des korrespondierenden Vortrags)

An dieser Stelle kommt der Prototyp zum Einsatz. Hier wird der Baum nun erneut durchlaufen und als Vorbereitung für den "Arithmetic Coder" Wahrscheinlichkeiten mit Hilfe von "Prediction by Partial Match" für die verschiedenen Pfade bestimmt. Stringkonstanten werden dabei extrahiert und getrennt nach ihrem Typ (z.Bsp. Klassenbezeichnungen, Feldnamen oder Methodennamen...) in separaten Listen gespeichert.

Der "Arithmetic Coder" komprimiert abschließend den so bereits verkürzten Baum.

Abb. 5: Inhalt des komprimierten abstrakten
Syntaxbaums (CAST)

Da sich die AG - wie schon erwähnt - als Baum darstellen lässt, gibt es quasi einen Referenzbaum. Dieser repräsentiert alle syntaktisch korrekten Programme. Durch Entfernung der redundanten Informationen erhält man eine brauchbare Referenz. So kommt es, dass dank dieser Referenz es auch nicht mehr notwendig ist, den eigentlichen Baum zu erhalten. Die einzige wirklich benötigte Information beschreibt für den Fall, dass ein Knoten mehrere Kinder hat, welches davon gewählt wurde.

Das Ergebnis ist eine Kette von Ganzzahlwerten, die sich mit "Arithmetic Coding" besser komprimieren lässt.

Zu diesem komprimierten AST (CAST) gehört neben der komprimierten Baumrepräsentation auch eine Konfigurationsdatei, welche die zugehörige AG und weitere Informationen - zum Beispiel bzgl. enthaltener Stringkonstanten etc. enthält (denn diese werden wie bereits erwähnt getrennt vom eigentlichen AST gespeichert und komprimiert).

Diese Daten können nun lokal gespeichert und über ein Interface - zum Beispiel das Internet - übertragen werden.

Mit Hilfe einer AG lässt sich aus nativem Code ein AST und umgekehrt mit einem AST und einer AG nativer Code erzeugen.
Auf der Konsumentenseite muss dazu zunächst ein entsprechender Dekoder vorhanden sein. Der existierende Prototyp ist ebenfalls in Python geschrieben und zeichnet sich vor allem dadurch aus, dass die für die Dekompression notwendige Zeit verglichen mit anderen Kompressionsverfahren kurz ist. Das liegt nicht zuletzt daran, dass die normalerweise notwendige Prüfung auf syntaktische Korrektheit hier entfallen kann. Das ist darauf begründet, dass der übertragene AST keine "echten" Anweisungen enthält. Er kann auch auf der Produzentenseite überhaupt nur erzeugt werden, wenn das zugrunde liegende Programm syntaktisch korrekt war. Da die Dekompression auf Basis der AG geschehen muss, entsteht somit auch gar nicht erst die Gefahr, dass die vorliegende Datei unvorhergesehene Anweisungen enthält. Wäre dem dennoch so, müsste diese Datei bereits an der Dekodierung scheitern.

Das Ergebnis ist erneut der AST, der somit direkt an ein vorhandenes Backend (Compiler) zur Codeerzeugung weitergegeben werden kann.

(ac/tom) Diskussion