Program Slicing - Ein komponentenbasiertes und adaptierbares Referenztool, exemplarisch angepasst für C

Inhaltsverzeichnis

1. Einleitung
1.1. Motivation
1.2. Ziel der Diplomarbeit

2. Grundlagen
2.1. Program Slicing
2.1.1. Statisches Slicen
2.1.2. Datenfluss der Slicing-Dienste
2.2. TGraph
2.2.1. TGraph Eigenschaften
2.2.2. Schema
2.3. Referenzschema

3. Entwicklung eines Referenzschemas für Programmiersprachen
3.1. Entwicklung des Referenzschemas
3.2. Erweiterung des EL-Schemas zum Referenzschema
3.3. Abbildung des C-Schemas auf das Referenzschema
3.3.1. Direkte Abbildungen vom RePSS auf das C-Schema
3.3.2. Klassen des C-Schemas und von RePSS ohne Abbildung
3.3.3. Unterschiede zwischen dem C-Schema und RePSS
3.3.4. Kantenklassen im C-Schema und in RePSS
3.4. Datenmodelle des C-Schemas
3.4.1. Abstrakter Syntaxgraph (ASG) für C
3.4.2. Erweiterter Kontrollflussgraph (ACFG) für C
3.4.3. Points-to-Graph (PG) für C
3.4.4. Aufrufgraph (CG) und erweiterter Aufrufgraph (ECG) für C
3.4.5. Erweiterter Systemabhängigkeitsgraph (ESDG) für C
3.5. Fazit zu RePSS

4. Definition von RePST
4.1. Anwendungsfälle
4.2. Anforderungen
4.2.1. Funktionale Anforderungen
4.2.2. Technische Anforderungen
4.2.3. Anforderungen an die Architektur
4.2.4. Qualitätsanforderungen
4.2.5. Anforderungen an die Benutzerschnittstelle
4.2.6. Anforderungen an die Dokumentation

5. Architektur
5.1. Architektur-Muster
5.2. Architektur Eigenschaften von RePST
5.3. Architektur der Komponente ProgramSlicingTool .
5.4. Architektur der Komponente ProgramPreprocessor
5.5. Architektur der Komponente ProgramSlicer
5.6. Konfiguration von RePST
5.7. Verwendung gemeinsamer Komponenten

6. Realisierung der Komponenten
6.1. ProgramSlicingTool
6.2. ProgramPreprocessor
6.3. ASGComputer
6.4. ACFGComputer
6.5. PGComputer
6.6. ECGComputer
6.7. CGComputer
6.8. DefUseInfComputer
6.9. ESDGComputer
6.10. BasicESDGComputer
6.11. IntMetEdgesComputer
6.12. ConDepEdgesComputer
6.13. DataFlowEdgesComputer
6.14. SumEdgesComputer
6.15. ProgramSlicer
6.16. ESDGMarker
6.17. StaticBackwardSliceComputer
6.18. StaticForwardSliceComputer .
6.19. Weitere Slice- und ChopComputer
6.20. ESDGToCodeConverter
6.21. ProgramSlicingComponent
6.22. SharedComponent
6.23. GReQLAdapter

7. Implementation
7.1. TGraph-Anfragen
7.1.1. Anfragen mit GReQL2
7.1.2. Algorithmen mit dem RePSS-API
7.1.3. Bewertung der TGraph-Anfragen
7.1.4. GReQL2-Nutzung in RePST
7.2. Unittests gegen ein C-Testprogramm
7.2.1. Testprogramm
7.2.2. ASGComputerForCTest
7.2.3. ACFGComputerForCTest
7.2.4. PGComputerForCTest
7.2.5. CGComputerForCTest
7.2.6. DefUseInfComputerForCTest . .
7.2.7. BasicESDGComputerForCTest .
7.2.8. IntMetEdgesComputerForCTest .
7.2.9. ConDepEdgesComputerForCTest
7.2.10. DataFlowEdgesComputerForCTest
7.2.11. SumEdgesComputerForCTest . .
7.2.12. ESDGMarkerForCTest
7.2.13. StaticBackwardSliceComputerForCTest
7.2.14. StaticForwardSliceComputerForCTest .
7.2.15. ESDGToCodeConverterForCTest
7.3. Ausnahmebehandlung
7.3.1. Exception-Hierarchie in RePST
7.3.2. Mögliche Auslöser der ProgramSlicingToolExceptions
7.4. Installation von RePST
7.5. Die Benutzungsoberfläche von RePST
7.6. Steuerung von RePST per Konsole
7.7. API von RePST

8. Fazit
8.1. Bewertung
8.1.1. Bewertung: Funktionale Anforderungen
8.1.2. Bewertung: Technische Anforderungen
8.1.3. Bewertung: Anforderungen an die Architektur
8.1.4. Bewertung: Qualitätsanforderungen
8.1.5. Bewertung: Anforderungen an die Benutzerschnittstelle
8.1.6. Bewertung: Anforderungen an die Dokumentation
8.2. Weiterentwicklung
8.2.1. Program Slicing von Quellcode in anderen Programmiersprachen
8.2.2. Alternative Slicing- und Chopping-Verfahren
8.2.3. PGComputer
8.2.4. Implementierung der abstrakten RePST-Komponenten
8.2.5. Program Slicing für C-Programme
8.2.6. Integration in fremde Umgebungen
8.3. Zusammenfassung

A. Glossar

Abbildungsverzeichnis

2.1. Datenflussdiagramm: ProgramSlicing [Sch07]

2.2. Datenflussdiagramm: preprocessProgram [Sch07]

2.3. Datenflussdiagramm: computeExtendedSystemDependenceGraph [Sch07]

2.4. Datenflussdiagramm: sliceProgram, angepasst aus [Sch07]

2.5. Parse-Baumausschnitt eines C-Programms

2.6. Darstellung des Parse-Baums aus Abb. 2.5 als TGraph

3.1. EL-Schema zur Beschreibung von ASG [Sch07]

3.2. Das Referenzschema für Program Slicing (RePSS)

3.3. C-Schema (Teil 1) [Rie01a]

3.4. C-Schema (Teil 2) [Rie01a]

3.5. Schema der ACFG-Menge für C

3.6. Schema der PG-Menge für C

3.7. Schema des ECG für C

3.8. Schema des ESDG für C

4.1. Anwendungsfalldiagramm: RePST

5.1. Komponentendiagramm: grober Architekturüberblick

5.2. Viewpoint zum Architektur-Muster: Call-Return

5.3. Hauptkomponenten und grafischer Client des Program Slicing Tools

5.4. Klassendiagramm: RePST

5.5. Klassendiagramm: ProgramPreprocessor

5.6. Klassendiagramm: ProgramSlicer

5.7. Klassendiagramm: Factory zur Konfiguration von RePST

5.8. Klassendiagramm: Verwendung der gemeinsamen Komponente

6.1. Klassendiagramm: ASGComputer

6.2. Aktivitätsdiagramm: Berechnung des ASGs für C

6.3. Klassendiagramm: ACFGComputer

6.4. Klassendiagramm: PGComputer

6.5. Klassendiagramm: ECGComputer, CGComputer und DefUseInfComputer

6.6. Klassendiagramm: ESDGComputer, BasicESDGComputer, IntMetEdges- Computer, ConDepEdgesComputer, DataFlowEdgesComputer und SumEd- gesComputer

6.7. Klassendiagramm: ProgramSlicer, StaticBackwardSliceComputer, StaticFor- wardSliceComputer, StaticChopComputer, DynamicBackwardSliceCompu- ter, DynamicForwardSliceComputer und DynamicChopComputer

6.8. Klassendiagramm: ProgramSlicer, ESDGMarker und ExecutableBackwardS- liceComputer

6.9. Klassendiagramm: ESDGToCodeConverter

6.10. Klassendiagramm: GReQLAdapter und ProgramSlicingComponent

6.11. Klassendiagramm: SharedComponent

7.1. ACFG der Methode init

7.2. ACFG der Methode m

7.3. ACFG der Methode m

7.4. ACFG der Methode main

7.5. ECG des C-Programms aus Listing

7.6. Grundgerüst des ESDG für die Methode m2 aus Listing

7.7. Kontrollkanten der Methode m1 aus Listing

7.8. Kontrollkanten der Methode m2 aus Listing

7.9. Datenflusskanten der Methode m2 aus Listing

7.10. Klassendiagramm: Exception-Hierarchie in RePST

7.11. Grafische Benutzungsoberfläche für RePST zum Slicen von C-Quellcode

Tabellenverzeichnis

3.1. Abbildungen zwischen RePSS und dem C-Schema durch Spezialisierung

3.2. Elemente eines Schemas ohne direkte Abbildung ins andere Schema

3.3. Unterschiede zwischen RePSS und dem C-Schema

4.1. Tabellarischer Überblick über die Dienste und deren Funktion. (Teil 1) . .

4.2. Tabellarischer Überblick über die Dienste und deren Funktion. (Teil 2) . .

5.1. Tabellarischer Überblick über die Dienste und deren Umsetzung durch RePST-Komponenten und programmiersprachenabhängige Komponenten.

5.2. Tabellarischer Überblick über die Ein- und Ausgaben der Komponenten. .

6.1. Reguläre Ausdrücke für Benutzer-Eingaben (Terminale befinden sich in Hochkommata)

7.1. PG-Mengen des Testprogramms aus Listing 7

7.2. ParameterVertex-Instanzen des Testprogramms aus Listing 7

7.3. Verschiedene Slicing-Kriterien und ihre Markierung durch den ESDGMarker im ESDG zu Listing 7.5 (ESDG-Knoten werden hier als Tupel bestehend aus Knoten-ID und entsprechender Zeilennummer im Testprogramm angegeben)

7.4. Verschiedene Slicing-Kriterien und ihre Markierung durch den StaticBack- wardSliceComputer im ESDG zu Listing 7.5 (ESDG-Knoten werden hier als Tupel bestehend aus Knoten-ID und entsprechender Zeilennummer im Test- programm angegeben)

7.5. Verschiedene Slicing-Kriterien und ihre Markierung durch den StaticFor- wardSliceComputer im ESDG zu Listing 7.5 (ESDG-Knoten werden hier als Tupel bestehend aus Knoten-ID und entsprechender Zeilennummer im Testprogramm angegeben)

8.1. Tabellarischer Überblick über den prozentualen Anteil von Quellcode in RePST-Komponenten

Abstract

Im Rahmen dieser Diplomarbeit wird das Dienstmodell für Program Slicing, welches von Hannes Schwarz in [Sch07] vorgestellt wurde, zu einem komponentenbasierten Referenztool weiterentwickelt und implementiert.

Dieses Referenztool verwendet zum Slicen ein Referenzschema für Programmiersprachen, welches ebenfalls in dieser Arbeit eingeführt wird. Die hier eingesetzten Slicing-Verfahren basieren auf diesem Referenzschema. Somit kann das Referenztool als Grundlage zum Slicen von Quellcode in beliebigen Programmiersprachen genutzt werden, wenn das Referenzschema vorab an die Gegebenheiten dieser Sprachen angepasst wird.

Exemplarisch wird in dieser Diplomarbeit ein Program Slicing Tool für C-Quellcode entwi- ckelt. Dieses Slicing Tool basiert auf dem Referenztool, in dem es die einzelnen Komponen- ten des Referenztools bei Bedarf spezialisiert oder in der ursprünglichen Form übernimmt.

Damit das Program Slicing Tool als Referenz gelten kann, wird in dieser Arbeit eine einfache, erweiterbare und komponentenbasierte Architektur entwickelt. Diese entsteht durch den Einsatz aktueller Prinzipien der Softwaretechnik.

Danksagung

Zu Beginn meiner Diplomarbeit möchte ich allen Personen danken, die direkt oder indirekt zum Gelingen dieser Arbeit beigetragen haben.

An erster Stelle danke ich meinen beiden Betreuern Prof. Dr. Jürgen Ebert und Hannes Schwarz für ihre intensive Betreuung. In unseren regelmäßigen Treffen haben sie durch konstruktive Kritik und gute Ideen zum Erfolg dieser Arbeit maßgeblich beigetragen. Ein spezieller Dank gilt Hannes, der mir jederzeit alle Fragen beantwortet hat.

Des Weiteren möchte ich mich bei Daniel Bildhauer bedanken, weil er mir des Öfteren in Sachen Linux und GReQL geholfen hat.

Schließlich danke ich meinen Eltern und meiner Freundin für ihre Unterstützung in jeder Hinsicht.

1. Einleitung

1.1. Motivation

Program Slicing [Wei79] ist ein Konzept zur Analyse von Programmen. Anhand eines vorher zu spezifizierenden Slicing-Kriteriums wird ein möglichst kleiner Programmausschnitt bestimmt, welcher nur Programmanweisungen enthält, die sich entweder auf das SlicingKriterium auswirken oder auf die sich das Slicing-Kriterium auswirkt.

Das Konzept des Program Slicing wurde schon in mehreren Werkzeugen umgesetzt. Beispiele hierfür sind das Indus¹ Projekt der Kansas State University und der CodeSurfer² [AT01] der Firma GrammaTech.

Diese Werkzeuge basierten in ihren ursprünglichen Versionen auf einer monolithischen Architektur. Monolithische Architekturen haben im Vergleich zu komponentenbasierten Architekturen einige Nachteile bezüglich der Flexibilität und Wiederverwendbarkeit.

Es gibt viele verschiedene Program Slicing-Verfahren, wie zum Beispiel statisches Slicing [OO84], dynamisches Slicing [KL88] oder Chopping [RR95]. Wenn diese verschiedenen Verfahren in einzelnen Komponenten realisiert wären, so könnte man neue Werkzeuge durch Wiederverwendung dieser Komponenten leichter und schneller produzieren.

1.2. Ziel der Diplomarbeit

Ziel dieser Diplomarbeit ist die Implementation eines Dienstmodells für Program Slicing. Dabei versteht man unter einem Dienstmodell eine Sammlung zusammenarbeitender Soft- warekomponenten oder Software-Dienste³, deren Funktionalitäten jeweils abgegrenzte Teil- aspekte des gesamten Program Slicing-Konzeptes realisieren. Dieses Dienstmodell basiert auf dem Buch von Hannes Schwarz [Sch07].

Die Implementation des Slicing-Konzeptes soll so allgemein gehalten werden, dass Program Slicing für möglichst viele Programmiersprachen möglich ist. Slicing⁴ für eine konkrete Programmiersprache kann dann durch Spezialisierung eines zu definierenden Referenzschemas für Programmiersprachen geschehen. In dieser Diplomarbeit wird exemplarisch das Slicen von C-Programmen umgesetzt.

Die Berechnung einer Slice geschieht auf der Basis von Graphen. Das zu slicende Programm wird in einen TGraphen [EF95] überführt, um anschließend die Slice-Berechnung anhand des Slicing-Kriteriums auf einem TGraphen durchzuführen.

Das zu entwickelnde Slicing-Werkzeug wird aus einigen wesentlichen Teilkomponenten bzw. Teildiensten bestehen, die sich selbst auch aus mehreren Teilkomponenten zusammen- setzen können.

Es gibt drei Hauptaufgaben, die von unterschiedlich vielen Komponenten realisiert wer- den. Die erste Hauptaufgabe ist das Erstellen eines erweiterten Systemabhängigkeitsgraphen [Sch07] aus dem zu slicenden Programmcode. Die Teildienste zur Realisierung der zweiten Hauptaufgabe berechnen auf dem Systemabhängigkeitsgraphen in Abhängigkeit von Einga- ben, wie zum Beispiel dem Slicing-Kriterium, die Slice. Die Slice wird als Markierung im Systemabhängigkeitsgraphen an die letzte Komponente übergeben. Diese markiert im Pro- grammcode die Slice.

Diese Diplomarbeit stellt einen kompletten Software-Entwicklungsprozess dar. Zuerst werden Anforderungen an das zu entwickelnde Slicing-Werkzeug erhoben. Anschließend wird eine komponentenbasierte Software-Architektur entwickelt, die sich an den Datenflussbeschreibungen aus [Sch07] orientiert. Die Implementation des Slicing-Werkzeuges geschieht in Java. Zur Darstellung des Programmcodes wird das Java Graphenlabor (JGraLab) [Kah06] benutzt und zur Berechnung der Slices wird möglichst die Graph Query Language 2 (GReQL2) [Mar06] verwendet. Abschließend werden die einzelnen Dienste sowie das gesamte Werkzeug getestet und anhand von Beispiel-Slices evaluiert.

2. Grundlagen

In diesem Kapitel werden Grundlagen zum besseren Verständnis dieser Arbeit dargestellt. Daher werden im Folgenden einige wichtige Begriffe ausführlich erläutert.

2.1. Program Slicing

Das Program Slicing Tool, welches in dieser Diplomarbeit entwickelt wird, bietet eine Platt- form für verschiedene Slicing-Verfahren. Konkret wird das statische Rückwärts- und Vor- wärtsslicen implementiert. Alternative Verfahren, wie dynamisches Slicen, Choppen oder die Berechnung ausführbarer Slices, werden in [KL88], [AH90], [RR95] und [Bin93] vorge- stellt.

2.1.1. Statisches Slicen

Program Slicing wurde 1979 in Weisers Dissertation [Wei79] eingeführt. Die deutsche Über- setzung „ein Programm in Scheiben schneiden“ [Sch07] beschreibt, was Programmierer laut Weisers Studie [Wei82] im Kopf tun, wenn sie ein Programm debuggen. So zerlegt oder schneidet der Programmierer den Quellcode in kleinere Teile, die nur die relevanten Stellen des Codes enthalten. Diese Teile können dann auch als Scheiben des Quellcodes betrachtet werden.

Die Reduzierung des Quellcodes auf die relevanten Stellen geschieht beim Program Slicing in Abhängigkeit von einem Slicing-Kriterium. Dieses Kriterium variiert je nach angewendetem Slicing-Verfahren. Im ursprünglichen Verfahren besteht es jedoch aus einer bestimmten Stelle im Quellcode und einer Teilmenge aller Variablen des Quellcodes.

Die hier implementierten statischen Slicing-Verfahren verwenden ein Slicing-Kriterium Sli- ceCrit = <i,X>, wobei i für eine Anweisung im Quellcode steht und X eine Variablenmenge festlegt. Eine Slice ist nun ein Ausschnitt des Quellcodes, welche aus Streichungen von Anweisungen im ursprünglichen Quellcode hervorgeht. Diese Streichungen basieren auf der Traversierung des erweiterten Systemabhängigkeitsgraphen (ESDG). Beim Rückwärtsslicen wird ausgehend von der Anweisung i rückwärts traversiert; analog dazu wird beim Vorwärtsslicen vorwärts traversiert. Während der Traversierung werden alle Anweisungen gestrichen, die keine Abhängigkeiten zu den Variablen in der Menge X besitzen.

Die Berechnung des erweiterten Systemabhängigkeitsgraphen ist in [Sch07] erklärt. Sie basiert auf einigen anderen Graphen, die in Abschnitt 3.4 vorgestellt werden.

Listing 2.1 enthält ein kleines C-Programm, das anhand des Slicing-Kriteriums „<10,{aLo- cal}>“ mittels statischem Rückwärtsslicen geslicet werden soll. Die entsprechende Slice ist in Listing 2.2 zu sehen. Da sich die Variable „aLocal“ und Anweisung „10“ im Slicing- Kriterium befinden, müssen alle Anweisungen ausgehend von der letzten Zeile „10“ auf Abhängigkeiten zu „aLocal“ analysiert werden. Man stellt fest, dass die Anweisungen in den Zeilen „4“, „7“ und „9“ keine Abhängigkeit zu „aLocal“ besitzen, so dass sie auch nicht in der Slice enthalten sind. Die Anweisung in Zeile „6“ besitzt im Gegensatz zu den Anwei- sungen in den Zeilen „3“, „5“ und „8“ zwar keine direkte Abhängigkeit zu „aLocal“, ist aber dennoch in der Slice enthalten, da sie die Variable „bLocal“ definiert, welche in Zeile „8“ zur Definition von „aLocal“ benutzt wird.

Abbildung in dieser Leseprobe nicht enthalten

Listing 2.2: Beispiel: Slice des C-Programms aus Listing <10,{aLocal}>

2.1.2. Datenfluss der Slicing-Dienste

Dieser Abschnitt fasst das Dienstmodell für das Konzept des Program Slicing aus [Sch07] zusammen. Die Idee des Dienstmodells ist die hierarchische Zerlegung von Diensten in kleinere Teildienste. So wird in [Sch07] der Dienst ProgramSlicing in drei Teildienste zerlegt, welche selbst so lange zerlegt werden, bis weitere Zerlegungen keine sinnvollen Teildienste mehr liefern. Die Dienste auf niedrigster Ebene werden als atomar bezeichnet.

Mit Hilfe von Datenflussdiagrammen wird die Zerlegung der Dienste visualisiert, da hier insbesondere die Abhängigkeiten der einzelnen Dienste bezüglich ihrer Ein- und Ausgaben deutlich werden. Die Funktionalität der Dienste bzw. der Komponenten, welche die Dienste umsetzen, wird in den Kapiteln 4.2.1 und 6 genauer erläutert.

Abb. 2.1 zeigt ein Datenflussdiagramm, das die Teildienste des Dienstes ProgramSlicing ent- hält. Im ersten Schritt werden durch den Teildienst preprocessProgram aus dem Quellcode ein erweiterter Systemabhängigkeitsgraph und erweiterte Kontrollflussgraphen (ACFGs) er- zeugt. Diese Graphen und von außen kommend ein Slicing- oder Chopping-Kriterium sowie eine optionale Trace bilden die Eingabe für den zweiten Teildienst sliceProgram. Für dyna- mische Slicing- oder Chopping-Verfahren ist die Eingabe der Trace zwingend erforderlich, während die Trace in statischen Verfahren nicht berücksichtigt wird. Der zweite Teildienst markiert im ESDG die Slice oder den Chop und übermittelt diese an den letzten Teildienst convertESDGToCode, welcher für die Umwandlung des ESDG in ein geslicetes Programm zuständig ist, das als Ausgabe geliefert wird. Die Eingabedaten Quellcode, Trace, Slicing- und Chopping-Kriterium kommen vom Benutzer oder von der Systemumgebung.

Abbildung in dieser Leseprobe nicht enthalten

Abbildung 2.1.: Datenflussdiagramm: ProgramSlicing [Sch07]

Der Dienst preprocessProgram zerlegt sich ebenfalls in mehrere Teildienste, da die Berech- nung des ESDG einige Zwischenschritte erfordert. Abb. 2.2 veranschaulicht das Zusam- menspiel der einzelnen Teildienste. Zuerst wird aus dem Quellcode durch den atomaren Teildienst computeAbstractSyntaxGraph ein abstrakter Syntaxgraph (ASG) berechnet, der als Eingabe für alle anderen Teildienste von preprocessProgram dient. Den atomaren Teil- diensten computeAugmentedControlFlowGraphs und computePointsToGraphs genügt der ASG als Eingabe, so dass sie anschließend erweiterte Kontrollflussgraphen bzw. Points-to- Graphen (PGs) produzieren. Der Teildienst computeExtendedCallGraph erzeugt einen er- weiterten Aufrufgraph (ECG) und zerlegt sich in die Dienste computeCallGraph und com- puteDefUseInformation. Da diese beiden Dienste aber eine einfache Sequenz bilden, wird dies in keinem weiteren Datenflussdiagramm dargestellt. Ein wesentlich komplexerer Teil- dienst ist computeExtendedSystemDependenceGraph. Dieser Teildienst benötigt zur Erzeu- gung des ESDG die Ausgabe aller anderen Teildienste als Eingabe, nämlich den ASG, die ACFGs, die PGs und den ECG.

Abb. 2.3 zeigt detailliert die Zerlegung von computeExtendedSystemDependenceGraph in seine atomaren Teildienste. Die Berechnung des ESDG entspricht hierbei einer Sequenz der Dienste computeBasicESDG, computeInterMethodEdges, computeControlDependenceEdges, computeDataFlowEdges und computeSummaryEdges.

Abbildung in dieser Leseprobe nicht enthalten

Abbildung 2.2.: Datenflussdiagramm: preprocessProgram [Sch07]

Abbildung in dieser Leseprobe nicht enthalten

Abbildung 2.3.: Datenflussdiagramm: computeExtendedSystemDependenceGraph [Sch07]

Eine Datenflussbeschreibung für den Dienst sliceProgram befindet sich in Abb. 2.4. Die Markierung des Slicing- oder Chopping-Kriteriums im ESDG durch den atomaren Teil- dienst markESDG geschieht anhand der Eingabedaten ESDG, ACFG-Menge und optional Trace, sowie dem Slicing- oder Chopping-Kriterium. Im zweiten Schritt wird die Slice oder der Chop unter Zuhilfenahme des markierten ESDG in einem der atomaren Dienste compu- teStaticBackwardSlice, computeStaticForwardSlice, computeDynamicBackwardSlice, com- puteDynamicForwardSlice, computeStaticChop oder computeDynamicChop berechnet. Die- se Dienste sind Alternativen zueinander und liefern alle als Ausgabe einen ESDG mit mar- kierter Slice oder markiertem Chop. Der Teildienst computeExecutableBackwardSlice kann optional auf die Ausgabe der Dienste computeStaticBackwardSlice und computeDynamic- BackwardSlice zur Ermittlung einer ausführbaren Slice angewendet werden.

Abbildung in dieser Leseprobe nicht enthalten

Abbildung 2.4.: Datenflussdiagramm: sliceProgram, angepasst aus [Sch07]

2.2.1. TGraph Eigenschaften

Ein Graph besteht aus Knoten und Kanten, wobei eine Kante zwei Knoten verbindet. Weiterführendes zu Graphen im Allgemeinen findet der Leser in [Cha85].

TGraphen sind eine spezielle Art von Graphen. Sie werden durch die folgenden Eigenschaften definiert:

- typisiert: Der TGraph selbst und all seine Knoten und Kanten besitzen jeweils einen festgelegten Typ. Knoten, Kanten oder TGraphen, welche den gleichen Typ besitzen, werden in Knoten-, Kanten- bzw. Graphklassen zusammengefasst.
- attributiert: Alle Elemente des Graphen dürfen Attribut-Werte-Paare besitzen.
- gerichtet: Die Kanten in TGraphen sind immer gerichtet. Allerdings können sie ohne Änderung der Darstellung auch als ungerichtete Graphen betrachtet werden, so dass zum Beispiel gleichzeitig eine gerichtete und eine ungerichtete Graphen-Traversierung durchgeführt werden kann.
- angeordnet: Die Graphelemente innerhalb eines Graphen befinden sich prinzipiell in Anordnungen untereinander. So gibt es eine Anordnung der Knoten, eine Anordnung der Kanten und für jeden Knoten eine Anordnung der ein- und ausgehenden Kanten.

Durch ihre charakteristischen Eigenschaften eignen sich TGraphen zum Beispiel zur Be- schreibung von abstrakten Syntaxgraphen (siehe dazu Abschnitt 3.4.1). Abstrakte Syntax- graphen können Parse-Bäume abstrakt beschreiben. Der Parse-Baum ist der erste Schritt auf dem Weg vom ursprünglichen Programmcode zum gesliceten Programmausschnitt. Er ent- steht durch Anwendung der Compilerbautechniken [ASU86] lexikalische und syntaktische Analyse.

Abbildung in dieser Leseprobe nicht enthalten

Listing 2.3: Ausschnitt eines C-Programms

Abbildung in dieser Leseprobe nicht enthalten

Abb. 2.5 zeigt einen Ausschnitt eines Parse-Baums, wie er beim Parsen des C- Programmausschnitts in Listing 2.3 entsteht. Dieser Parse-Baum kann in abstrakter Form auch als TGraph dargestellt werden, siehe dazu Abb. 2.6. Sowohl der Parse-Baum als auch der TGraph entsprechen dem in Kapitel 3.3 vorgestellten C-Schema.

Anhand von Abb. 2.6 erkennt man sehr gut den Nutzen der einzelnen Eigenschaften von TGraph:

- Aufgrund der Typisierung kann man im Beispiel-TGraph aus Abb. 2.6 er- kennen, dass es hier jeweils einen Knoten vom Typ CompoundStatement, SelectionStatement und OperatorExpression und zwei Knoten vom Typ ExpressionStatement gibt. Zusätzlich erkennt man die Typen der Kanten: IsExprIn und IsStmtIn.
- Durch die Attributierung wird im Beispiel-TGraph festgelegt, dass Knoten v2 eine if-Anweisung repräsentiert. Hierfür sind im Parse-Baum zusätzliche Blätter nötig.
- Da die Kanten innerhalb des TGraphen gerichtet sein können, ist es möglich, die Baumstruktur des Parse-Baums im TGraphen wiederzugeben. Da zum Beispiel Knoten v1 nur eingehende Kanten besitzt, kann man ihn als Wurzel identifizieren.
- Die Anordnung der einzelnen Elemente ist beim Parsen von zentraler Bedeutung, da- mit man die Abarbeitungsreihenfolge der einzelnen Anweisungen erkennen kann. Im Parse-Baum ist die Anordnung nur grafisch dargestellt, Elemente auf gleicher Ebe- ne werden von links nach rechts abgearbeitet. Innerhalb des TGraphen sind sowohl die Knoten als auch die Kanten angeordnet. In Abb. 2.6 ist dies für die Knoten durch Bezeichnungen wie v3 (dritter Knoten) dargestellt. Mit den Kanten wird analog ver- fahren. Zusätzlich besitzt jeder Knoten eine Anordnung seiner ein- und ausgehenden Kanten. Im Beispiel-TGraph ist dies durch Nummern in geschweiften Klammern dar- gestellt. Auf diese Weise erkennt man, dass zum Beispiel innerhalb der if-Anweisung v3 vor v4 abgearbeitet werden muss, weil die Nummer der in v2 eingehenden Kante e2 kleiner¹ als die von e3 ist.

Eine formale Definition von TGraphen kann in [EF95] gefunden werden. Weiterführende Erklärungen zu TGraphen besonders im Bezug zu JGraLab befinden sich in [Kah06].

Abbildung in dieser Leseprobe nicht enthalten

Abbildung 2.5.: Parse-Baumausschnitt eines C-Programms

Abbildung in dieser Leseprobe nicht enthalten

Abbildung 2.6.: Darstellung des Parse-Baums aus Abb. 2.5 als TGraph

2.2.2. Schema

Der Begriff Schema wird in der Informatik häufig im Zusammenhang mit Datenbanken und deren Datenmodellen [KE04] verwendet. In diesem Zusammenhang definiert ein Datenmo- dell generische Strukturen und Operationen, welche zur Modellierung einer konkreten An- wendung genutzt werden. Es bietet dem Benutzer somit die Möglichkeit zur Beschreibung von Datenobjekten und zur Bestimmung von anwendbaren Operatoren und deren Wirkung.

Ein Schema entspricht einem Datenmodell, das auf einen „speziellen Einsatzfall“ [Bal00] angewendet wird. Im Kontext dieser Diplomarbeit wird ein Schema genutzt, um die möglichen Strukturen von TGraphen festzulegen. So wird zum Beispiel durch ein Schema festgelegt, dass ein konkreter TGraph zur abstrakten Beschreibung eines Parse-Baums nur ein Wurzelelement haben kann.

Konkrete Schemata zur Beschreibung von Programmiersprachen werden in Kapitel 3 vorge- stellt.

Graphklasse Im Kontext von JGraLab wird der Schema-Begriff überladen. So versteht man im Kontext von JGraLab unter einem Schema eine Menge von Graphklassen, welche wiederum Mengen von Knoten- und Kantenklassen enthalten. Dabei können zwischen den einzelnen Klassen Beziehungen und Vererbungshierarchien bestehen.

In dieser Diplomarbeit werden Graphklassen verwendet, um die Struktur von Quellcode in einem TGraph darzustellen. Dabei gibt es für jede Programmiersprache eine eigene Graph- klasse, so dass beispielsweise die Struktur eines C-Programms mit Hilfe der C-Graphklasse dargestellt wird.

2.3. Referenzschema

Ein Referenzschema ist ein Schema, das als Vorbild, Empfehlung oder Bezug für speziel- lere Schemata dient. Die folgende Definition aus [Win00] legt den Begriff Referenzschema genauer fest.

Definition: Referenzschema [Win00] Ein Referenzschema² ist ein ausgewiesenes Schema, das charakteristische Eigenschaften einer Klasse gleichartiger Systeme beschreibt und als Bezugspunkt für spezielle Schemata dient.

Aus einer Menge von Schemata auf gleicher Abstraktionsebene kann ein Schema ausge- wählt werden und als Referenzschema bezeichnet werden. Dieses ausgewählte Schema sollte im Vergleich zu den anderen Schemata auf gleicher Abstraktionsebene möglichst allgemein sein, um die gemeinsamen, problembezogenen Aspekte der Schemata durch Abstraktion möglichst einfach darzustellen. In diesem Zusammenhang kann das Referenzschema durch- aus einen konkreten Fall beschreiben, da es sich auf der gleichen Ebene wie die anderen Schemata befindet. Jedoch sollte es möglichst in der Menge der anderen Schemata keines geben, das eine größere Menge als das ausgewählte Referenzschema an Gemeinsamkeiten zu den übrigen Schemata besitzt.

Ein Referenzschema kann als Basis zur Entwicklung speziellerer Schemata dienen, indem es Entwicklern einen „vorgefertigte[n] Lösungsrahmen“ [Seu97] bereitstellt. Somit ist das Entwickeln eines speziellen Schemas auf der Basis eines Referenzschemas meist schneller und führt zu höherer Qualität als die vergleichbare Neuentwicklung des Schemas ohne Vorbild. Daher benötigt das Referenzschema eine hohe Qualität, damit es seiner Rolle als Vorbild oder Empfehlung gerecht werden kann. Qualitätskriterien zur Bewertung eines Referenzschemas sind zum Beispiel Korrektheit, Vollständigkeit, Allgemeingültigkeit, Erweiterbarkeit und Anwendbarkeit. Weiterführendes ist in [Win00] zu finden.

In der Informatik gibt es bereits eine Vielzahl von Referenzschemata. So kann zum Beispiel UML (Unified Modeling Language) [OMG05] als ein Referenzschema betrachtet werden, da sich UML [BRJ06] gegenüber einer Vielzahl anderer Entwurfsbeschreibungssprachen, wie zum Beispiel OMT [Rum96], OML [FHSG98] oder Syntropy [CD94], als Standard durchgesetzt hat. Ein Beispiel für ein spezielleres Schema, welches das UML-Schema als Basis bzw. Referenzmodell verwendet, ist das Schema der Modellierungssprache grUML [BRSS07].

3. Entwicklung eines Referenzschemas für Programmiersprachen

Dieses Kapitel beschreibt die Entwicklung des Referenzschemas und die Abbildung zwischen diesem und dem C-Schema, welche die Voraussetzung zum Slicen von C-Programmen mit dem Program Slicing Referenztool schafft.

3.1. Entwicklung des Referenzschemas

Jede Programmiersprache besitzt eine abstrakte Syntax, welche als Schema dargestellt werden kann. Durch dieses Schema wird der Aufbau von syntaktisch korrekten, abstrakten Syntaxgraphen in der entsprechenden Sprache festgelegt. Die Schemata von verschiedenen Programmiersprachen haben sowohl Unterschiede als auch Gemeinsamkeiten. Im Zuge dieser Diplomarbeit wird an einem Referenzschema gearbeitet, welches die Gemeinsamkeiten von möglichst vielen Sprachen beschreibt.

Als Grundlage für dieses Referenzschema dient das Schema der Beispiel-Sprache EL [Sch07]. EL (engl. Exemplary Language) ist eine relativ kompakte Sprache zur imperati- ven Programmierung, welche die Konzepte Objektorientierung, Prozeduren, Sprunganwei- sungen und Zeiger umsetzt. Abb. 3.1 zeigt das EL-Schema zur Beschreibung von abstrakten Syntaxgraphen (ASG).

[KG98] führt einen generalisierten abstrakten Syntaxbaum (GAST) ein, um Programmcode von verschiedenen Programmiersprachen, wie zum Beispiel C und Ada, zu repräsentieren. Die Überführung von Programmcode in einen GAST ermöglicht eine Datenflussanalyse, sowie die Berechnung von verschiedenen Sichten auf den Programmcode. Dieser Ansatz wird hier jedoch nicht weiter verfolgt, da es in [KG98] weder eine Grammatik noch ein Schema zur genauen Definition des GASTs gibt.

Abbildung in dieser Leseprobe nicht enthalten

Abbildung 3.1.: EL-Schema zur Beschreibung von ASG [Sch07]

Um ein Program Slicing Tool, das im Folgenden auch als Reference Program Slicing Tool (RePST) bezeichnet wird, nach dem beschriebenen Dienstmodell in [Sch07] zu entwickeln, benötigt man je nach gewünschter Programmiersprache eine Abbildung zwischen dem Re- ferenzschema und dem Schema der konkreten Programmiersprache. Mit Hilfe dieser Ab- bildung kann dann ein konkretes Program Slicing Tool mit möglichst geringem Aufwand entwickelt werden, da es eine Abwandlung des abstrakten, auf dem Referenzschema arbei- tenden Program Slicing Tools ist.

3.2. Erweiterung des EL-Schemas zum Referenzschema

Das Schema von EL dient als Grundlage für das Referenzschema. Im Hinblick auf das Program Slicing von konkreten Programmiersprachen, wie zum Beispiel C, sind einige Erweiterungen oder Änderungen am EL-Schema nötig. Das Ergebnis dieser Änderungen wird dann als Referenzschema für Program Slicing oder Reference Program Slicing Schema (RePSS) bezeichnet. In diesem Abschnitt werden diese Veränderungen aufgezählt.

1. Nach den Code-Konventionen in [Sun99] beginnen Klassennamen stets mit einem Großbuchstaben. Dies wurde im Referenzschema entsprechend angepasst. Im Quellcode von RePST besitzen alle Knoten des Referenzschemas den Präfix „EL“. Dies wird in der schriftlichen Ausarbeitung jedoch nicht weiter berücksichtigt.

2. Aufgrund des Analogieprinzips enden im Referenzschema alle Klassen, die von Statement erben, mit dem Postfix „Statement“.

3. Die Bezeichner der Klassen if und loop innerhalb des EL-Schemas klingen zu sehr nach einer konkreten Programmiersprache. So ist zum Beispiel „if“ in Java oder C ein Schlüsselwort. Daher wird die EL-Schema-Klasse if in SelectionStatement und loop in IterationStatement umbenannt.

4. Da EL eine objektorientierte Sprache ist, können durch das EL-Schema keine proze- duralen Programmiersprachen beschrieben werden. Deshalb besitzt das Referenzschema die abstrakte Oberklasse Unit, von dieser erben die Klassen Class und SourceUnit. So- mit gibt es im Referenzschema für objektorientierte Sprachen die Klasse Class und für prozedurale SourceUnit.

5. Durch das Einfügen der Oberklasse Unit wurden folgende Klassen umbenannt:

- Die Klasse classMember heißt nun UnitMember.
- Die Klasse memberVariableDeclaration heißt nun UnitVariableDeclaration.
- Die Klasse memberFunctionDefinition heißt nun UnitFunctionDefinition.
- Die Klasse memberFunction heißt nun UnitFunction.

6. Die Multiplizität zwischen SelectionStatement und Statement wurde so angepasst, dass im Referenzschema eine SelectionStatement-Instanz mit „else“ zwei Statement-Instanzen besitzt, während eine SelectionStatement-Instanz oh- ne „else“ nur eine Statement-Instanz besitzt. Im ursprünglichen EL-Schema muss ei- ne if-Instanz stets zwei statement-Instanzen besitzen, wobei die zweite eine empty- Statement-Instanz sein muss, falls das if-Statement keinen „else“-Zweig besitzt.

7. Zur besseren Unterscheidung zwischen Programmiersprachen mit und ohne ZeigerKonzept, gibt es im Referenzschema die Variable-Spezialisierung Pointer. Die Klasse Pointer ersetzt das EL-Schema-Attribut -isPointer.

Abb. 3.2 zeigt das fertige Referenzschema bzw die Änderungen an EL.

Abbildung in dieser Leseprobe nicht enthalten

3.3. Abbildung des C-Schemas auf das Referenzschema

Da in dieser Diplomarbeit ein Program Slicing Tool für die Programmiersprache C entwickelt wird, benötigt man eine Abbildung vom Schema der Programmiersprache C auf RePSS. Die Abb. 3.3 und 3.4 zeigen das C-Schema [Rie01a]. Dieses C-Schema orientiert sich an der ANSI C-Spezifikation [BCM+98]. Im Folgenden werden die Gemeinsamkeiten und Unterschiede zwischen dem C-Schema und dem Referenzschema gezeigt.

Abbildung in dieser Leseprobe nicht enthalten

Abbildung 3.2.: Das Referenzschema für Program Slicing (RePSS)

Abbildung in dieser Leseprobe nicht enthalten

3.3. Abbildung des C-Schemas auf das Referenzschema

Da die grafischen Darstellungen des C-Schemas und des Referenzschemas beide bereits re- lativ groß sind, wird aus Gründen der Übersichtlichkeit auf eine grafische Darstellung der Abbildung zwischen dem C-Schema und dem Referenzschema verzichtet. Die grafische Darstellung der Abbildung müsste mindestens beide Schemata enthalten und zusätzliche Spezialisierungspfeile zwischen den Klassen, die aufeinander abgebildet werden. Dabei sind die Klassen des Referenzschemas die Oberklassen und die Klassen des C-Schemas die Spe- zialisierungen.

Die Abbildung zwischen den beiden Schemata wird durch die Tabellen 3.1, 3.2 und 3.3 beschrieben.

3.3.1. Direkte Abbildungen vom RePSS auf das C-Schema

Tabelle 3.1 enthält die direkten Abbildungen vom RePSS auf das C-Schema. Diese Abbil- dungen lassen sich relativ einfach durch Spezialisierungen umsetzen. Das heißt, es existie- ren Klassen im Referenzschema, die Superklasse von C-Schema-Klassen sind. So kann zum Beispiel der Tabelle 3.1 entnommen werden, dass die RePSS-Klasse LocalVariable- Declaration Oberklasse der C-Schema-Klasse Declaration ist oder dass die C- Schema-Klasse CompoundStatement eine Spezialisierung der RePSS-Klasse Block- Statement ist.

Als Beleg für die Korrektheit der Tabelle 3.1 dient ein Vergleich zwischen dem Referenzschema und dem C-Schema.

1 Die Abbildung zwischen Program und Program wird gemacht, weil beides als Startsymbol der jeweiligen Grammatik betrachtet werden kann.
2 RePSS wurde um SourceUnit erweitert, damit eine Abbildung zur SourceUsage im C-Schema gemacht werden kann. Siehe dazu Abschnitt 3.2.
3 DeclarationSpecifier wurde als Spezialisierung von Type ausgewählt, weil die Klasse DeclarationSpecifier an höchster Vererbungshierarchiestufe zur Spezifika- tion von Deklarationen steht. Die Unterklassen des DeclarationSpecifier beschrei- ben Details, die im Referenzschema nicht gezeigt werden. Außerdem wird dem Analogie- prinzip entsprechend die Klasse Type bzw. DeclarationSpecifier von den Klassen

Abbildung in dieser Leseprobe nicht enthalten

Tabelle 3.1.: Abbildungen zwischen RePSS und dem C-Schema durch Spezialisierung

FunctionDefinition und Declaration bzw. UnitFunctionDefinition und VariableDeclaration aggregiert. Da VariableDeclaration nicht im C-Schema abgebildet werden kann, müssen hier die entsprechenden Unterklassen verglichen werden. Siehe dazu Tabelle 3.1 und Abschnitt 3.3.2.

4 Die Klasse LocalVariableDeclaration beschreibt Variablendeklarationen, die sich in einem Block befinden. Somit entspricht sie der Klasse Declaration, de- ren Instanzen sich ebenfalls in einem CompoundStatement oder einer Function- Definition befinden. Die von VariableDeclaration geerbten Aggregationen der Klassen Variable und Type entsprechen den Aggregationen der Klasse Declaration.

5 Durch die Klasse UnitVariableDeclaration werden globale Variablen beschrie- ben, die von der Klasse Unit beinhaltet werden. Im C-Schema beinhaltet die Klasse SourceUsage, als Spezialisierung von SourceUnit, die abstrakte Klasse External- Declaration. Somit muss eine globale Variable laut C-Schema Instanz der Klasse ExternalDeclaration sein. Im konkreten Fall ist die globale Variable somit auch In- stanz der Klasse Declaration. Da aber nicht jede Declaration-Instanz eine globa- le Variable ist, besteht die Abbildung zwischen ExternalDeclaration und Unit- VariableDeclaration.

6 FunctionDefinition wird als Spezialisierung von UnitFunction- Definition betrachtet, da FunctionDefinition genau eine Compound- Statement-Instanz besitzt, die der BlockStatement-Instanz von UnitFunction- Definition entspricht. Außerdem aggregiert FunctionDefinition eine DeclarationSpecifier-Instanz, welche das UnitFunctionDefinition- Aggregat Type spezialisiert. Eine direkte Abbildung der Klasse FormalParameter gibt es im C-Schema nicht. Um entsprechendes zur Komposition zwischen Formal- Parameter und UnitFunctionDefinition im C-Schema zu finden, sei auf Abschnitt 3.3.3 verwiesen.

7 Aufgrund der gleichen Bezeichner ist die Abbildung von Statement auf Statement naheliegend. Außerdem befinden sich diese beiden abstrakten Klassen in CompoundStatement bzw. BlockStatement, in SelectionStatement und in IterationStatement. Zudem sind beide Klassen mit Label-Klassen assoziiert.

8 Die Klasse CompoundStatement ist innerhalb des C-Schemas die Klasse, die beliebig viele andere Statement-Instanzen beinhalten kann. Innerhalb des Referenzschemas übernimmt die Klasse BlockStatement diese Rolle, da eine BlockStatementInstanz beliebig viele Statement-Instanzen aggregieren kann. Zusätzlich sind beide Klassen Spezialisierungen von Statement und werden von FunctionDefinition bzw. UnitFunctionDefinition aggregiert.

9 Die RePSS-Klasse IterationStatement als Unterklasse von Statement ent- spricht der Klasse IterationStatement im C-Schema, da das C-Iteration- Statement analog dazu von Statement erbt und beide Klassen genau ein Statement enthalten.

10 Die C-SelectionStatement-Klasse kann als Spezialisierung von Selection- Statement im Referenzschema betrachtet werden, da beide Klassen die gemeinsame Oberklasse Statement haben und mindestens eine Instanz dieser Oberklasse aggregie- ren. Bei dieser Abbildung wird vernachlässigt, dass SelectionStatement in Abb. 3.4 genau ein Statement beinhaltet, da dies ein Fehler in der Grafik des C-Schema ist.

11 Da C-JumpStatement und JumpStatement im Referenzschema den gleichen Klassennamen haben, die gleichen Unterklassen (siehe 12 bis 15) und beide von Statement erben, wird zwischen beiden Klassen eine Abbildung hergestellt.

12 Die C-ContinueStatement-Klasse wird aufgrund der gemeinsamen Oberklasse JumpStatement und des gleichen Bezeichners auf ContinueStatement im Referenzschema abgebildet.

13 BreakStatement im C-Schema ist eine Spezialisierung von BreakStatement in RePSS, weil beide Klassen die Oberklasse JumpStatement und gleiche Bezeichner haben.

14 Die Klassen ReturnStatement und ReturnStatement haben gleiche Bezeichner, die gleiche Position in der Vererbungshierarchie und enthalten höchstens eine Instanz von Expression. Daher kann ReturnStatement im C-Schema als Spezialfall von ReturnStatement im Referenzschema betrachtet werden.

15 Die Klassen GotoStatement und GotoStatement haben gleiche Bezeichner und die gleiche Position in der Vererbungshierarchie. Ihre Abbildung aufeinander wird zusätzlich bestätigt durch die Aggregation der Klasse Label bzw. der Klasse Identifier, die sich in einem LabelStatement befindet.

16 Die Klassen AssignmentStatement und ExpressionStatement besitzen unterschiedliche Assoziationen, so dass die Verwendung der Klasse AssignmentStatement genauer definiert ist als die Verwendung der Klasse ExpressionStatement. Da beide Klassen Unterklasse von Statement sind und ExpressionStatement die einzige Statement-Spezialisierung ist, die eine Expression enthält, werden die beiden Klassen aufeinander abgebildet. Jedoch ist zu beachten, dass das Definieren einer Variable im C-Schema durch die Klasse OperatorExpression geschieht, die in einem ExpressionStatement enthalten ist.

17 C-Expression kann aufgrund des gleichen Bezeichners und ähnlicher Unterklassen auf Expression in RePSS abgebildet werden.

18 C-Constant wird auf Constant im Referenzschema abgebildet, weil beide Klassen den gleichen Bezeichner haben, Unterklassen von Expression sind und das Attribut value besitzen.

19 Die RePSS-Klasse CompoundExpression ist Oberklasse der C-Schema-Klasse OperatorExpression, da beide Klassen genau eine Operator-Instanz und mindes- tens eine Expression-Instanz aggregieren. Außerdem sind beide Klassen Unterklasse von Expression.

20 Die C-Klasse Operator wird auf die RePSS-Klasse Operator abgebildet, weil beide Klassen gleiche Bezeichner haben und von der Klasse OperatorExpression bzw. CompoundExpression aggregiert werden.

21 Labels werden in beiden Schemata unterschiedlich mit der Klasse Statement ver- bunden. Im C-Schema aggregiert das LabeledStatement die Klasse Statement, wäh- rend im Referenzschema die Klasse Label von der Klasse Statement aggregiert wird.

Da aber in beiden Schemata eine Beziehung zwischen Label und Statement bzw. zwischen LabeledStatement und Statement besteht, wird Label als Superklasse von LabeledStatement definiert.

3.3.2. Klassen des C-Schemas und von RePSS ohne Abbildung

Die Tabelle 3.2 zeigt Klassen beider Schemata, die kein entsprechendes Gegenstück im anderen Schema haben. Dies kann unterschiedliche Ursachen haben:

- Die Schemata sind in manchen Stellen unterschiedlich detailliert.
- Der Funktionsumfang von C ist reichhaltiger als der von EL.

Tabelle 3.2 beschreibt einige Differenzen zwischen den beiden Schemata. In diesem Abschnitt wird das weitere Verfahren bezüglich dieser Differenzen beschrieben.

1 Die Klasse Class in RePSS besitzt im C-Schema kein Gegenstück, da C nicht objektorientiert ist. Siehe dazu auch Abschnitt 3.2.

2 Für die Klasse EmptyStatement existiert ebenfalls keine entsprechende Klasse im C-Schema. Dieser Fall ist jedoch weniger relevant, da das EmptyStatement beim Programmieren keine Relevanz hat.

3 Da UnitFunction von der Klasse UnitFunctionDefinition aggregiert wird, benötigt man im Kontext des Program Slicings nur die Abbildung der Klasse UnitFunctionDefinition. Die entsprechende Abbildung zwischen UnitFunctionDefinition und FunctionDefinition befindet sich in Tabelle 3.1.

4 Im C-Schema gibt es verschiedene Varianten zur Modellierung der Klasse FormalParameter. Zum einen gibt es eine Umsetzung durch beliebig viele IdentifierInstanzen, die verwendet wird, wenn im Declarator eine Instanz von OldStyleFunctionDeclarator genutzt wird. Zum anderen existiert eine Umsetzung durch ParameterDeclaration-Instanzen, die nur in Kombination mit einer NewStyleFunctionDeclarator-Instanz Verwendung findet.

5 Die in Tabelle 3.2 unter 5 gelisteten C-Schema Klassen besitzen alle eine Oberklasse im C-Schema, die Unterklasse einer Klasse im Referenzschema ist, siehe dazu Tabelle 3.1 und Abb. 3.4. Bezüglich dieser Klassen ist das C-Schema detaillierter als RePSS. Im Kontext des Program Slicings können diese Klassen jedoch vernachlässigt werden, da die Abstraktionsebene des Referenzschemas ausreichend ist.

6 Die unter 6 gelisteten C-Schema-Klassen beschreiben Aspekte, die innerhalb des Referenzschemas nicht berücksichtigt werden. Daher sind diese Klassen auch nicht relevant für das Program Slicing nach [Sch07] und können somit vernachlässigt werden.

7 Die Klassen Initializer und SubInitializer sind bei der Berechnung des ACFG von Bedeutung. Da es keine passende Oberklasse im Referenzschema gibt, wird die Klasse Initializer als Unterklasse von ACFGVertex festgelegt. Siehe dazu Abschnitt

8 ParameterDeclaration ist eine der unter 4 angesprochenen Varianten zur Modellierung der Klasse FormalParameter.

3.3.3. Unterschiede zwischen dem C-Schema und RePSS

Tabelle 3.3 zeigt Unterschiede, die teilweise durch relativ schwierige Abbildungen gelöst werden müssen. Diese Unterschiede haben verschiedene Ursachen:

- Beide Schemata sind in manchen Stellen unterschiedlich detailliert.
- RePSS verwendet Mehrfachvererbung.
- Entitäten werden als Attribut oder als eigenständige Klasse in beiden Schemata unterschiedlich eingesetzt.
- Die Vererbungshierarchie des Referenzschemas ist an bestimmten Stellen tiefer als die des C-Schemas.

Tabelle 3.3 enthält nicht nur Klassen, sondern auch Attribute von Klassen. Attribute werden durch das Präfix „-“ gekennzeichnet.

Abbildung in dieser Leseprobe nicht enthalten

Tabelle 3.3.: Unterschiede zwischen RePSS und dem C-Schema

Häufig kommt es zu Unterschieden zwischen beiden Schemata, weil unterschiedlich tiefe Vererbungshierarchien verwendet werden.

1 So gibt es im Referenzschema das CompoundStatementWithTest. Da innerhalb des C-Schemas keine entsprechende Klasse in der gleichen Vererbungshierarchiestufe existiert, müssen alle Klassen in der nächsttieferen Vererbungshierarchiestufe betrachtet werden. Dadurch ergibt sich dann die Abbildung zwischen CompoundStatementWithTest und {SelectionStatement, IterationStatement}. Diese Abbildung wird jedoch nicht explizit im Referenzschema modelliert, da die Spezialisierung bereits auf der tieferen Ebene vorgenommen wurde, siehe Abschnitt 3.3.1.

2 bis 8 Der gleiche Sachverhalt führt zu den Abbildungen

- von NonJumpStatement auf {ExpressionStatement, FunctionCall},
- von StructuredJumpStatement auf {ContinueStatement, BreakStatement},
- von SimpleStatement auf {JumpStatement, ExpressionStatement, FunctionCall},
- von BlockElement auf {Statement, LocalVariableDeclaration},
- von CompoundStatement auf {Block, CompoundStatementWithTest},
- von UnitMember auf {UnitVariableDeclaration, UnitFunctionDefinition} und
- von VariableDeclaration auf {LocalVariableDeclaration, FormalParameter, UnitVariableDeclaration}.

Analog zur Abbildung des CompoundStatementWithTest werden auch diese Abbildungen nicht modelliert.

Die restlichen Einträge der Tabelle 3.1 beschreiben die schwierigeren Abbildungen zwischen dem Referenzschema und dem C-Schema.

9 Die Abbildung zwischen {FunctionCall, Call, CallStatement} und FunctionCall beschreibt einen Fall, in dem RePSS detaillierter als das C-Schema ist. Da aber innerhalb des Referenzschemas eine Vererbungshierarchie mit Call als Superklasse besteht, kann hier FunctionCall als Spezialisierung von Call definiert werden.

10 Die Modellierung des Zeiger-Konzeptes unterscheidet sich im ursprünglichen EL- Schema sehr stark von der Modellierung im C-Schema. Aufgrund dieses Unterschiedes kann keine Abbildung zwischen den beiden Klassen Pointer gefunden werden, so dass eine spezielle Lösung nötig ist. Zum Erkennen von Zeigern gibt es in RePSS die neue Klas- se Pointer, hierzu sei auf Abschnitt 3.2 verwiesen. Durch diese neue Klasse verliert die RePSS-Klasse Variable das Attribut isPointer, so dass nun eine Abbildung zwischen der Klasse Variable und der C-Schema-Klasse Identifier gemacht werden kann. Diese Abbildung ermöglicht das Erkennen von Identifier-Instanzen, die eine Variable oder einen Zeiger repräsentieren.

11 Die unterschiedliche Modellierung von Entitäten als eigenständige Klasse oder als At- tribut einer Klasse führt ebenfalls zu Unterschieden zwischen den beiden Schemata. Eine

Beispiel-Abbildung hierfür ist {Variable, -identifier} mit Identifier. Diese Abbildung lässt sich leicht umsetzen, da im Grunde eine 1:1 Beziehung zwischen zwei Klas- sen vorliegt. Dazu wird das Attribut -identifier im Referenzschema als eigenständige Klasse mit dem Attribut -name modelliert und dann als Superklasse von Identifier definiert. Da in JGraLab keine Attribute überschrieben werden können, muss das Attribut -name von der C-Schema-Klasse Identifier entfernt werden.

3.3.4. Kantenklassen im C-Schema und in RePSS

In den bisherigen Abschnitten wurden die Gemeinsamkeiten und Unterschiede zwischen beiden Schemata im Bezug auf die Knotenklassen diskutiert. Dabei wurde stets die Richtung der Kanten vernachlässigt. In diesem Abschnitt werden nun die Gemeinsamkeiten und Unterschiede bezüglich der Kantenklassen beschrieben.

Analog zu den Abbildungen zwischen den Knotenklassen in beiden Schemata könnte man Abbildungen zwischen den Kantenklassen der unterschiedlichen Schemata vornehmen. Allerdings sprechen zwei entscheidende Gründe dagegen:

1. Kantenklassen, die zwischen aufeinander abgebildeten Knotenklassen verlaufen, ha- ben immer unterschiedliche Richtungen.

2. Die Typ-Bezeichnungen der einzelnen Kantenklassen sind im C-Schema nicht ausrei- chend differenziert.

Im C-Schema sind die Bezeichner und die Richtungen der Kantenklassen immer nach dem Muster „isIn“ aufgebaut. Das bedeutet, dass eine solche Kante immer vom aggregierten Knoten zum aggregierenden Knoten verläuft, da alle Kanten¹ des C-Schemas Aggregationen repräsentieren. Zum Beispiel verläuft von der Knotenklasse Statement eine IsStmtInKantenklasse zu der Knotenklasse CompoundStatement.

Innerhalb des Referenzschema ist die Ausrichtung der Kanten genau spiegelverkehrt zur Kantenausrichtung im C-Schema. Im Referenzschema gibt es im Wesentlichen nur Aggre- gationen und Kompositionen, die verwendeten Assoziationen stehen im Zusammenhang mit der Objektorientierung und können daher keine Abbildung im C-Schema besitzen. Das ver- wendete Muster für die Aggregations- und Kompositionsklassen könnte man mit „contains“ bezeichnen. Das hat zur Folge, dass Kanten immer vom äußeren zum inneren Knoten verlau-

fen und somit eine spiegelverkehrte Ausrichtung zu den Kanten im C-Schema besitzen. Zum Beispiel verläuft eine contains-Kante vom BlockStatement zum BlockElement.

Die Bezeichnungen der Kantenklassen im Referenzschema wurden im Hinblick auf die Ver- wendung innerhalb von JGraLab so gewählt, dass jede Kantenklasse einen individuellen Namen hat. In Abb. 3.2 wurde aus Gründen der Übersichtlichkeit auf die ausführliche Be- zeichnung verzichtet. Tatsächlich besitzt aber jeder Kantenklasse als Präfix die Bezeich- nung der Alpha² -Knotenklasse und als Postfix die Bezeichnung der Omega³ -Knotenklasse. Zum Beispiel ist die tatsächliche Bezeichnung der Kantenklasse, die zwischen den Knoten- klassen BlockStatement und BlockElemement verläuft, ELBlockStatement- ContainsELBlockElement⁴.

Innerhalb des C-Schemas ist die Bezeichnerwahl der Kantenklassen nicht so differenziert wie in RePSS, da bei der Erstellung auf Prä- und Postfixe verzichtet wurde. So existiert zum Beispiel die Kantenklasse IsPointerIn zum einen zwischen den Knotenklassen Pointer und Declarator und zum anderen zwischen Pointer und Pointer.

Würde man nun die Ausrichtung und die Bezeichnung der Kanten innerhalb des C-Schemas oder des Referenzschemas anpassen, so könnte man Abbildungen zwischen den Kantenklas- sen beider Schemata vornehmen. Diese Änderung wird am Referenzschema jedoch nicht durchgeführt, weil somit das Problem der entgegengesetzten Kantenausrichtungen in C- und Referenzschema nicht gelöst wird und bei den Schemata anderer Programmiersprachen er- neut auftauchen kann. Eine Änderung des C-Schemas würde eine entsprechende Anpassung des C-Parsers erfordern. Diese Lösung wird aufgrund des hohen Aufwands nicht umgesetzt.

Damit die Komponenten von RePST dennoch effizient mit Kantenklassen arbeiten können, wird die Superkantenklasse Edge für Berechnungen verwendet. Es gibt zwei Möglichkeiten, um die Problematik bezüglich der Kantenausrichtung anzugehen. Zum einen gibt es die JGraLab-Methoden getThis und getThat, deren Benutzung den gezielten Zugriff auf die Knoten an den beiden Enden einer Kante erlaubt. Zum anderen bietet die Implementierung von RePST Hilfsmethoden (siehe Abschnitt 6.22) an, deren Verwendung die Traversierung eines TGraphen in Richtung der Wurzel oder der Blätter ermöglichen, sofern der TGraph einen abstrakten Parse-Baum beschreibt.

3.4. Datenmodelle des C-Schemas

Zwischen den einzelnen Diensten des Program Slicing Tools fließen Daten, die ein bestimm- tes, zu slicendes Programm beschreiben. Die Beschreibung des Programms geschieht mit Hilfe von Graphen. Daher entspricht der Aufbau dieser Daten einem Graphschema. Das Graphschema setzt sich aus mehreren Graphklassen zusammen. Jede Programmiersprache (C, C++, Java, ...) sowie RePSS hat eine eigene Graphklasse. Dabei erlaubt jede Graphklas- se mehrere, unterschiedliche Sichten auf das zu slicende Programm. Diese Sichten sind im Einzelnen:

- der abstrakte Syntaxgraph (ASG)
- der erweiterte Kontrollflussgraph (ACFG)
- der Points-to-Graph (PG)
- der Aufrufgraph (CG)
- der erweiterte Aufrufgraph (ECG)
- der erweiterte Systemabhängigkeitsgraph (ESDG)

Zum Slicen von C-Programmen muss das Graphschema sowohl das C-Schema als auch das Referenzschema enthalten. In den nächsten Unterabschnitten werden die Sichten auf C-Programme vorgestellt, welche durch die C-Graphklasse möglich sind.

Weiterführende Erklärungen und Beispiele zum Aufbau und zur Bedeutung aller Sichten findet der Leser in [Sch07]. Abschnitt 7.2 beinhaltet ebenfalls Beispiele zu den Teilgraphen aller Sichten.

3.4.1. Abstrakter Syntaxgraph (ASG) für C

Der abstrakte Syntaxgraph repräsentiert die Syntax des zu slicenden Programms. Er dient als Grundlage zur Berechnung der nachfolgend beschriebenen Graphen. Die Abb. 3.3 und 3.4 zeigen das Schema des ASG für die Programmiersprache C. Der ASG wird durch lexikalische und syntaktische Analyse erstellt. Diese Compilerbautechniken arbeiten mit der C-Grammatik [BCM+98]. Daher ist das ASG-Schema für C aus der C-Grammatik hergeleitet worden.

3.4.2. Erweiterter Kontrollflussgraph (ACFG) für C

Ein Kontrollflussgraph beschreibt alle möglichen Abarbeitungsreihenfolgen von Anweisun- gen und lokalen Variablendeklarationen innerhalb eines Funktionsrumpfes. Der ACFG er- weitert diesen Kontrollflussgraphen um weitere Kontrollflusskanten, die zur Berechnung von Kontrollkanten innerhalb eines erweiterten Systemabhängigkeitsgraphen nötig sind.

Eine ACFG-Menge (ACFGSet) besitzt für jede Methode innerhalb des zu beschreibenden Programms einen ACFG (ACFG). Dieser ACFG enthält für jede Anweisung oder lokale Variablendeklaration einen ACFG-Knoten (ACFGVertex). Die einzelnen ACFG-Knoten innerhalb eines ACFG sind durch Kontrollflusskanten (ACFGVertexHasControlFlowEdgeToACFGVertex) miteinander verbunden, wobei von jedem ACFG-Knoten maximal zwei Kontrollflusskanten ausgehen dürfen.

Jede Kontrollflusskante von Knoten s nach Knoten t besitzt ein Attribut label. Dieses legt die Bedeutung der Kontrollflusskante fest. Es gibt vier mögliche Werte für label:

1. always: t wird unmittelbar nach s ausgeführt.
2. never: t würde nur dann nach s (der Typ von s kann Entry oder Unterklasse von JumpStatement sein) ausgeführt werden, wenn s keine Entry- oder Jump- Statement-Instanz wäre.
3. true: t wird unmittelbar nach s (der Typ von s kann hier nur Unterklasse von CompoundStatementWithTest sein) ausgeführt, wenn die Ausdrucksauswertung in s wahr ergibt.
4. false: t wird unmittelbar nach s (der Typ von s kann hier nur Unterklasse von CompoundStatementWithTest sein) ausgeführt, wenn die Ausdrucksauswer- tung in s falsch ergibt.

Abb. 3.5 zeigt die ACFG-Sicht auf die C-Graphklasse. Diese Sicht wird zur Berechnung einer ACFG-Menge für die Programmiersprache C genutzt. Alle Graphelementklassen, außer der Graphelementklasse Initializer, stammen aus RePSS. Diese Klassen besitzen Spezialisierungen in der C-Graphklasse, die durch direkte Abbildungen umgesetzt werden können, siehe dazu Abschnitt 3.3.1.

Die Berechnung der ACFG-Menge für C entspricht der Berechnung der ACFG-Menge des Referenzschemas (siehe dazu [Sch07]). Es gibt Ausnahmen, welche eine spezielle Berechnung auf Basis des C-Schemas benötigen.

Abbildung in dieser Leseprobe nicht enthalten

Abbildung 3.5.: Schema der ACFG-Menge für C

- Die Berechnung der Sprungmarke bei einer Goto-Anweisung kann nicht auf Basis des Referenzschemas durchgeführt werden, da der Pfad vom Goto-Knoten zum Namen der Sprungmarke in RePSS länger als im C-Schema ist.
- Die Suche nach möglichen Folgeknoten innerhalb eines Blocks benötigt eine spezielle Filterfunktion, die auf Basis des C-Schemas geschrieben werden muss.
- In EL ist es unmöglich, Variablen beim Deklarieren einen Wert zuzuweisen. Da dies aber in C möglich ist, muss es auf Basis des C-Schemas gemacht werden. Deshalb wird die C-Klasse Initializer als Unterklasse von ACFGVertex definiert. Da Initializer Oberklasse der C-Klasse Expression ist, muss stets überprüft werden, dass jede ACFGVertex-Instanz ausschließlich mit Expression-Instanzen verknüpft ist, welche eine Kante zu einer InitDeclarator-Instanz besitzen.

3.4.3. Points-to-Graph (PG) für C

Ein Points-to-Graph beschreibt die „zeigt auf“-Beziehungen zwischen Variablen innerhalb einer Methode. Variablen können in diesem Fall Attribute, lokale Variablen und formale Parameter sein. Es ist zwingend notwendig, dass der Points-to-Graph eine konservative Abschätzung der „zeigt auf“-Beziehungen vornimmt. Unter einer konservativen Abschätzung versteht man hier, dass die tatsächlich vorhandenen „zeigt auf“-Beziehungen oder eine Obermenge davon abgebildet werden. Eine Untermenge der tatsächlich vorhandenen „zeigt auf“Beziehungen darf unter keinen Umständen verwendet werden.

Eine PG-Menge (PGSet) besitzt für jede Methode innerhalb des zu beschreibenden Programms einen PG (PG). Der PG enthält alle Variablen. Variablen können Zeiger sein und somit auf andere Variablen zeigen.

Abb. 3.6 zeigt die PG-Sicht auf die C-Graphklasse. Zur Berechnung der PG-Menge für die Programmiersprache C wird diese Sicht benutzt. Die Berechnung der PG-Menge für C un- terscheidet sich von der Berechnung anhand des Referenzschemas, da Variablen und somit auch Zeiger in beiden Schemata unterschiedlich dargestellt werden (siehe dazu Abschnitt 3.3.3).

Die PG-Sicht auf die C-Graphklasse enthält zur Pointer-Erkennung die C-Schema-Klassen Declarator und Pointer. Ein Variable-Objekt ist genau dann eine ELPointer-

Abbildung in dieser Leseprobe nicht enthalten

Abbildung 3.6.: Schema der PG-Menge für C

Instanz⁵, wenn seine Declarator-Instanz per eingehender IsPointerIn-Kante mit einem C-Pointer verbunden ist. C-Pointer und Declarator sind in Abb. 3.6 grau unterlegt, da sie keine Oberklasse in RePSS besitzen.

Das Erkennen von Variablen ist im C-Schema schwieriger als in RePSS, da die Klasse Identifier nicht nur für Variablen benutzt wird sondern zum Beispiel auch für Methodennamen. Eine Identifier-Instanz ist nur dann keine Variable, wenn:

- die Identifier-Instanz eine Kante zu einer LabelStatement-Instanz besitzt.
- die Identifier-Instanz eine Kante zu einer GotoStatement-Instanz besitzt.
- die Identifier-Instanz eine IsFunctionNameIn-Kante besitzt.
- die Identifier-Instanz eine IsOldStyleFunctionDirect- DeclaratorIn-Kante besitzt.
- die Identifier-Instanz eine IsNewStyleFunctionDirect- DeclaratorIn-Kante besitzt.

3.4.4. Aufrufgraph (CG) und erweiterter Aufrufgraph (ECG) für C

Durch einen Aufrufgraph werden die Aufrufbeziehungen zwischen den Funktionen⁶ eines Programms wiedergegeben. Innerhalb eines erweiterten Aufrufgraph werden neben den Aufrufbeziehungen auch die von einer Funktion definierten und benutzten Variablen mit Hilfe von Defines- und Uses-Kanten angezeigt.

Ein ECG (ECG) enthält alle ECG-Knoten (ECGVertex). ECG-Knoten können Instanzen vom Typ Call, Variable oder UnitFunctionDefinition sein.

Abbildung in dieser Leseprobe nicht enthalten

Abb. 3.7 zeigt die ECG-Sicht auf die C-Graphklasse, welche zur Berechnung des ECG für die Programmiersprache C verwendet wird. Diese Sicht unterscheidet sich nicht von der ECG-Sicht auf RePSS, da keine Klassen aus dem C-Schema ohne Oberklasse in RePSS

Abbildung in dieser Leseprobe nicht enthalten

Abbildung 3.7.: Schema des ECG für C

benötigt werden. Da zur Berechnung des ECG die PG-Menge benötigt wird, ist keine erneute Sonderbehandlung zur Erkennung von Variable-Instanzen erforderlich.

Die Kanten des CG werden zwischen UnitFunctionDefinition- und Call-Knoten gezogen, wobei für Graphen zur Beschreibung von C-Programmen gilt:

- Eine Kante von einem UnitFunctionDefinition- zu einem Call-Knoten ist vom Typ UnitFunctionDefinitionContainsCall, wenn sich der AufrufKnoten einer anderen Funktion innerhalb der Funktion befindet, die durch den UnitFunctionDefinition-Knoten repräsentiert wird.
- Eine Kante von einem Call- zu einem UnitFunctionDefinition-Knoten ist vom Typ CallCanCallUnitFunctionDefinition, wenn der Call-Knoten die Ausführung der Funktion zur Folge hat, welche durch den UnitFunction- Definition-Knoten vertreten wird. Da es innerhalb von C-Programmen keine Ver- erbung gibt, kann der Aufruf-Knoten nur eine Funktion aufrufen. In Abb. 3.7 ist dies anders dargestellt, weil durch Polymorphie unter Umständen mehrere, unterschiedli- che Methoden aufrufbar sind.

Innerhalb des ECG für C-Programme werden von UnitFunctionDefinition- nach Variable-Knoten def/use-Kanten gezogen, für die folgendes gilt:

- Eine def/use-Kante ist vom Typ UnitFunctionDefinitionUsesVariable, wenn die Variable-Instanz innerhalb der Funktion genutzt wird. Die Nutzung einer Variable innerhalb einer Funktion erkennt man daran, dass sie einen Pfad, bestehend aus ausgehenden Kanten, zu einer OperatorExpression-Instanz mit =-Operator besitzt und rechts von dem =-Operator steht oder als aktueller Parameter im Funk- tionsaufruf vorkommt. Außerdem darf die Variable-Instanz keine lokale Variable repräsentieren.
- Eine def/use-Kante ist vom Typ UnitFunctionDefinitionDefines- Variable, wenn die Variable-Instanz innerhalb der Funktion definiert wird. Das heißt, dass sie eine Kante zu einer OperatorExpression-Instanz mit =-Operator besitzt und links von dem =-Operator steht. Die Variable-Instanz darf analog zur Uses-Kante keine lokale Variable und außerdem keinen Parameter repräsentieren.

Operatoren zur abkürzenden Schreibweise [BCM+98] können zum einen durch den Preprocessor so ausgeschrieben werden, dass die Regeln zur Bestimmung von def/use-Kanten greifen oder zum anderen mit Hilfe von zusätzlichen Regeln erkannt werden. Wenn man also in C für die Operatoren *=, /=, %=, +=, -=, «=, »=, &=, |=, ˆ=, ++ und -- die Regel definiert, dass globale Variablen auf der linken Seite sowohl definiert als auch benutzt werden, kann man diese Problematik auch ohne Hilfe des Preprocessors lösen.

Variablen, auf die ein Zeiger als Parameter zeigt, werden in dieser Diplomarbeit nicht be- rücksichtigt. Eine Liste aller Einschränkungen für C-Programme ist in Abschnitt 8.2.5 zu finden.

Uses- und Defines-Kanten können auch implizit zwischen einem Funktions-Knoten und einem Variable-Knoten entstehen. Dies passiert immer dann, wenn letzterer eine globale Variable bzw. ein Attribut ist und innerhalb einer direkt oder indirekt aufgerufenen Funktion verwendet oder definiert wird.

Die Klasse ReturnValue repräsentiert Hilfsvariablen, die den Rückgabewert einer Funktion darstellen. Sofern eine Funktion einen Rückgabewert besitzt, wird ein neuer ReturnValue-Knoten erzeugt und der Funktions-Knoten wird per UnitFunction- DefinitionDefinesVariable-Kante mit dem ReturnValue-Knoten verbunden. ReturnValue-Knoten besitzen keine eingehenden UnitFunctionDefinition- UsesVariable-Kanten.

3.4.5. Erweiterter Systemabhängigkeitsgraph (ESDG) für C

Ein erweiterter Systemabhängigkeitsgraph [HRB88] enthält die Knoten aller ACFGs und verbindet diese durch spezielle, auf Kontrollfluss- und def/use-Kanten basierende Kanten miteinander. Dadurch fungiert der ESDG als Grundlage für die eigentlichen SlicingVerfahren, das sind alle Verfahren außer die zur Programmcode-Aufbereitung.

Ein ESDG (ESDG) enthält alle ESDG-Knoten (ESDGVertex). ESDG-Knoten kön- nen Instanzen vom Typ ACFGVertex oder ParameterVertex sein. Exit- Knoten werden jedoch ausgeschlossen, obwohl sie Unterklasse von ACFGVertex sind. Die Klasse der Parameterknoten (ParameterVertex) wird durch die Klas- sen FormalInParameterVertex, FormalOutParameterVertex, ActualIn- ParameterVertex und ActualOutParameterVertex spezialisiert.

Abb. 3.8 zeigt die ESDG-Sicht auf die C-Graphklasse, welche zur Berechnung des ESDG für die Programmiersprache C verwendet wird. Diese Sicht unterscheidet sich nur in einem Detail von der Sicht auf die RePSS-Graphklasse. So ist die Klasse Initializer zusätz- lich Unterklasse von ESDGVertex, weil sie auf Grund eines Unterschiedes zwischen dem C-Schema und RePSS als Spezialisierung der ACFGVertex-Klasse berücksichtigt werden muss.

Neben den ESDG-Knoten gibt es auch noch einige Kanten, welche zur Menge der Grundelemente eines ESDG gehören. Diese Kanten sind:

- Die ESDGVertexHasParameterEdgeToParameterVertex-Kante, welche jedem ParameterVertex-Objekt genau einen ESDG-Knoten zuweist.
- Die EntryCorrespondsToUnitFunctionDefinition-Kante, welche Paare aus zusammengehörigen Entry- und UnitFunctionDefinition-Knoten bil- det.
- Die ReturnStatementHasAssignmentStatement-Kante, welche jedem ReturnStatement-Objekt genau einen AssignmentStatement-Knoten zu- weist.
- Die ParameterVertexHasAssignmentStatement-Kante, welche jedem ParameterVertex-Objekt genau einen AssignmentStatement-Knoten zu- weist.

[...]

---

¹ http://indus.projects.cis.ksu.edu/

² http://www.grammatech.com/products/codesurfer/overview.html

³ Die Begriffe Softwarekomponente und Software-Dienst werden in dieser Arbeit synonym verwendet.

⁴ Bei Verwendung des Begriffs Slicing ist in dieser Diplomarbeit ausschließlich Program Slicing gemeint.

¹ Hier wird eine aufsteigende Ordnung der Zahlen angenommen.

² In [Win00] wurde der Begriff „Referenzmodell“ anstelle von „Referenzschema“ definiert. Nach Absprache mit dem Autor darf im Zitat „Referenzschema“ bzw. „Schema“ anstelle von „Referenzmodell“ bzw. „Modell“ verwendet werden.

¹ Ausnahmen, die im C-Schema als Assoziation dargestellt werden, sind vernachlässigbar, da man sie auch als Aggregation modellieren kann.

² Der Knoten, von dem eine Kante ausgeht, wird in JGraLab als Alpha bezeichnet.

³ Der Knoten, an dem eine Kante eingeht, wird in JGraLab als Omega bezeichnet.

⁴ Knotenklassen innerhalb des Referenzschemas besitzen das Präfix „EL“

⁵ Hier ist das Präfix „EL“ zur einfacheren Differenzierung zwischen der RePSS- und C-Pointer-Klasse ausnahmsweise nicht ausgeblendet

⁶ In dieser Diplomarbeit wird zur Vereinfachung von Funktionen gesprochen, tatsächlich sind aber Funktionen und Prozeduren in prozeduralen Programmiersprachen bzw. Methoden in objektorientierten Programmier- sprachen gemeint.