Testen und Analysieren von Software Fehlerbehebung und Re-Engineering Vorbemerkungen zu Themen #04 -...

Testen und Analysieren von Software

Fehlerbehebung und Re-Engineering

Vorbemerkungen zu Themen #04 - #06

WS 2002/2003

Univ.-Prof. em. Dr. H.-J. Hoffmann(Stand 14. November 2002)


2

Was wird angesprochen? (I)

• Wo treten Zeichenreihen auf ?• Übersetzer <==> Interpreter / Gliederung• Zeichenreihen als Eingabe• Grundzeichen und Phrasenzeichen• Baumstrukturen als Ausgabe• Endliche Automaten• Keller zur Aufnahme von Zeichen• Strategien der Zerlegung von Zeichenreihen:

- zielgericht (top-down)- rückschauend (bottom-up)

• Semantische Analyse als vorgezogene Interpretation


3

Was wird angesprochen ? (II)

• Formale Sprachen- ich lasse hier die Formalismen weg, siehe Literaturangaben -

• Formale Spezifikation und Beschreibung der Sprachen- Grammatiken, siehe Literaturangaben -

• Automaten• Formale Spezifikation und Beschreibung der

Verhaltensweise der Automaten- Zerlegungsalgorithmen, siehe Literaturangaben -

Diese Vorbemerkungen versuchen, plausibel zu machen,was zur Bearbeitung der Themen #03 - #06 bekannt

und verstanden sein sollte


4

Übersetzer <==> Interpreter (I)

Analyse /Front end

Synthese (Generator) / Back end

\_________________/Übersetzer

“AusführendeMaschinerie”(z.B. Virtual machine)

Interpreter

Zeichenreihe Baum “Befehle” Ergebnisse

Daten

(z.B.Bytecode)


5

Übersetzer <==> Interpreter (II)(Sonderfall)

Analyse /Front end

Synthese (generator) / Back end

\_________________/Übersetzer

“AusführendeMaschinerie”

Interpreter

Zeichenreihe Baum “Befehle” Ergebnisse

u.U.

Daten


6

Gliederung (idealisiert, auf Analyse bezogen)

•••

Zeichen- Bezeichner- syntakt. semant.- Gütever-analyse analyse Analyse Analyse besserung

sequentiell, unabhängig “Zwischensprachen”synchronisiert als (orientiert an)Verbraucher/Produzent/Verbraucher, “Baumstruktur”“verschränkt” / Koroutinen


7

Zeichenreihen als Eingabe ?

public class hello { public static void main (String args []) { System.out.println ("Hello World"); }}

...static¤void¤main¤(String¤args¤[])¤{|¤¤¤¤¤¤System.out.prin...

Leerzeichen

Zeilenwechsel

Textende


8

Was ist mit Zeichenreihen zu tun ?

• Entfernen typographischer Zeichen(z.B. Leerzeichen, Zeilenwechsel - nicht Textende ! -)

• Abgrenzen der “Token”

• Schlüsselworttoken

• Operatortoken

• Bezeichnertoken (einschl. Konstantentoken)

public class hello { public static void main (String args []) { System.out.println ("Hello World"); }}


9

Grundzeichen und Phrasenzeichen

• Grundzeichen- diese finden Sie auf der Tastatur -

• Phrasenzeichen- repräsentieren während der Analyse eine zusammengefaßte Reihe von Grundzeichen und/oderGrund- und Phrasenzeichen -

• Zwei Beispiele:

public class hello { public static void main ( <Parameterliste> ) { <Funktionsbezeichner> ( <Ausgabetext> ) ; } } class-end

public class hello <Klassenrumpf> class-end


10

Baumstrukturen (als Ausgabe)

public class hello <Klassenrumpf> class-end

<Klassendefinition>

<Klassentyp>

<Klassen-bezeichner>

Ein ziemlichwillkürlichesBeispiel (ineiner Zwischen-stufe)


11

Endliche Automaten (I)

(für Zeichenanayse)

Grund-zustand

? Buchstaben

Buchstaben

Operator

Ziffer

Bezeichner bzw.Wortsymbol

Bezeichner

?

Ziffer

•

Ziffer ?

Ganze Zahl

Gleitpunktzahl

?Ziffer

?

?

?

Regeln der Form:

alter Zusta

nd anstehendes Z

eichen

==> neuer Zusta

nd

Fehlerbehandlung ?

(siehe Referat #

04)


12

Endliche Automaten (II)(für Zeichenanalyse)

• Siehe Beispiel (hier nicht gezeigt)

• Bedeutung des “Trennzeichens” der Token(häufig das Leerzeichen !)

• Leistungsfähigkeit der Analyse ?(keine geschachtelten / geklammerten Textstrukturen,warum ?)

• Tabellensteuerung


13

Bezeichneranalyse

Im Seminar nicht behandelt !


14

Keller zur Aufnahme von Zeichen

• Wie sind geschachtelte / geklammerte Strukturen zu analysieren ?

• Früheres (von links her) Auftreten bestimmter Zeichen (z.B. von Klammern) muß hinsichtlich Zahl und Stel-lung in die Analyseentscheidungen eingehen können

• Also müssen früher aufgetretene Zeichen (vorüber-gehend) gespeichert werden können

Kellerung dieser Zeichen• Grundlage der syntaktischen Analyse


15

Strategien der syntaktischen Analyse

- der Dijkstra’sche Verschiebebahnhof -

Keller

?1

Es entstehtPostfix-Notation

x’xxx............xx?

Was muß hierstehen ?

- Entscheidungen bei ?1 und ?2 - Welche Zeichen werden ge- kellert ?

?2

yyyy...............yy

z’zz...z

Sind hier schließlichwieder alle Zeichen ?

Keine Phrasenzeichen !

Leserichtung

(Anfang der) Ausgabe

(Ende der) Eingabe

Fehlerbehandlung ?

(siehe Referat #

05)


16

Beispiel zur Postfixnotation A := B + C * ( D [ I + 1 ] - E ) / F ( X , Y + Z ) endA B C D I 1 + []1 E - * F X Y Z + f2 / + := end ---------- ------------ indizierte Funktions- Variable Aufruf (ein Index) (zwei Parameter)

Welche Zeichen fehlen in der Ausgabe, welche könntendazukommen ?

Eingabe(Token nachZeichenanalyse)

Ausgabeneue Operatoren


17

Strategien der syntaktischen Analyse- zielgerichtete Analyse (top-down) (I) -

Keller mit noch nicht erfüllten Zielen, hier? --> “Vergleichen und Wegwerfen des erfüll-ten Ziels (falls Grund-zeichen)”

?xxxx............xxx

xxxx...............xx

zzz...z

Leserichtung

(nicht mehr benötigter Anfang der) Eingabe

(Ende der) Eingabe

Zur Reduktion anstehen-de , das “Ende” repräsen-tierende Zeichenreihe aus Grund- und Phrasenzei-chen

Leserichtung


18

Strategien der syntaktischen Analyse- zielgerichtete Analyse (top-down) (II) -

Zur Reduktion anstehen-de , das “Ende” repräsen-tierende Zeichenreihe aus Grund- und Phrasenzei-chen

Keller mit Phrasenzei-chen z’ an oberster Stelle, hier ? --> “Absetzen neuer Ziele z1 z2... zn”

?

xxxx............xxx

xxxx...............xx

z’z:

:zz

Leserichtung


z1 z2 :zn

(Ende der) Eingabe

Leserichtung


19


- zielgerichtete Analyse (top-down) (III) -

• Oberstes Ziel, als erstes auf dem Keller abgelegt:<Programm>. Erfolg, wenn am Schluß Keller leer

• Aus den “Produktionen” für ein sich an oberster Stelle des Keller befindliches Ziel z’ wird durch Vergleich links an erster Stelle der Produktion mit anstehendem (Grund-)Zeichen r1 entschieden, welche “Gabel” (d.h. rechte Seite der Produktion z’ ::= r1 ... rn) erwartet wird, und diese dann im Keller abgesetzt (stark vereinfacht).

• “Lesen” der Gabel, schließlich Ziel z’ erfüllt.• Üblicherweise k = 1 (Anzahl der auf der Eingabe zur

Entscheidungsfindung betrachteten Zeichen)

(siehespäter)


20

Strategien der syntaktischen Analyse- zielgerichtete Analyse (top-down) (IV) -

• Zeichen (Ziele bzw. Zwischenziele) in Gabeln im Keller werden bei Übereinstimmung von oben nach unten entfernt

• Ausgabe erfolgt bei einer Reduktion• Aufbau des “Zerlegungsbaums”• Dieser entsteht ausgehend von der Wurzel

(Knoten<Programm>)

• Realisierung durch rekursivenAbstieg (recursive descent, in Anlehnung an endliche Automaten)

Fehlerbehandlung ?

(siehe Referat #04)


21

Strategien der syntaktischen Analyse- rückschauende Analyse (bottom-up) (I) -

Eine “reduzierte” / den “Anfang” reprä-sentierende Zeichen-reihe aus Grund- und Phrasenzeichen

?xxxx............xxx

xxxx...............xx

zzz...z

Leserichtung

(Ende der) Eingabe

Keller mit bis jetzt noch nicht voll gelesenen Gabeln, hier ? --> “Weiterlesen”



22

Strategien der syntaktischen Analyse- rückschauende Analyse (bottom-up) (II) -

“reduzierte” / den “An-fang” repräsentierende Zeichenreihe aus Grund- und Phrasenzeichen

Keller an oberster Stel-le mit eingelesener Gabel, hier ? --> “Reduzieren” und “Ab-setzen von z’ (ein Phrasen-zeichen !) als Repräsentant der eingelesenen Gabel ! )”

?

xxxx............xxx

xxxx...............xx

zzz...z

Leserichtung


z’ (Ende der)

Eingabe


23


- rückschauende Analyse (bottom-up) (III) -

• Keller anfänglich leer. Erfolg, wenn am Schluß allein<Programm> im Keller

• Reduziert wird, wenn eine vollständige Gabel gelesen ist- d.h. Entscheidung über Zerlegung zum spätmöglichsten Zeitpunkt ! - (stark vereinfacht).

• shift /reduce• Üblicherweise k = 1 (Anzahl der auf der Eingabe zur

Entschei-dungsfindung betrachteten Zeichen)

(siehefrüher)


24

Strategien der syntaktischen Analyse- rückschauende Analyse (bottom-up) (IV) -

• Ausgabe erfolgt bei einer Reduktion• Aufbau des “Zerlegungsbaums”• Dieser entsteht ausgehend von (vielen)

Zweigen, die schließlich zur Wurzel (Knoten <Programm>) zusam-mengefaßt sind

• Verschränkung mit semantischer Analyse (für syntheti-sierte Attribute leicht) möglich

• Realisierung durch LR-Analyse(in Anlehnung an endlicheAutomaten) Fehlerbehandlung ?

(siehe Referat #05)


25

• Typische “sprachspezifische” Aufgaben der seman-tischen Analyse:- Auflösung überladener Operationen (u.ä.)- Typüberprüfung- Umstellungen zur Güteverbesserung (u.ä.)- Speicherabbildung- Adressierung

• “lokales”, an Reihung in ursprünglich vorgelegtem Text orientiertes Vorgehen <==>

am Zerlegungsbaum orientiert• Erweiterung um “maschinenspezifische” Aufgaben• Als Einstieg gezeigt an Interpretation von Postfix-

Notation

Semantische Analyse als vorgezogene Interpretation


26


- der Dijkstra’sche Verschiebebahnhof -

(Ende der) Eingabe

(Anfang der) Ausgabe

Operatorkeller

?1

Es entstehtPostfix-Notation

x’xxx............xx?

- Entscheidungen bei ?1 und ?2 - Welche Zeichen werden ge- kellert ?

?2

yyyy...............yy

z’zz...z

LeserichtungZur

Erinnerung !


27

Beispiel zur Postfixnotation A := B + C * ( D [ I + 1 ] - E ) / F ( X , Y + Z ) endA B C D I 1 + []1 E - * F X Y Z + f2 / + := end ---------- ------------ indizierte Funktions- Variable Aufruf (ein Index) (zwei Parameter)

Eingabe(Token nachZeichenanalyse)

Ausgabeneue Operatoren

Zur

Erinnerung !


28

(Ende der) Eingabe

Operandenkeller

p p p p p p p ....... p p p p p p

?ooo::oo

Leserichtung


- gezeigt an Interpretation von Postfix-Notation (I) -

generierte Befehle

? Übernehmen von Operanden, solange bis Operator auftritt, dann? Operator + zugehörige Operanden entnommen

?


29

A B C D I 1 + []1 E - * F X Y Z + f2 / + := endEingabe


- gezeigt an Interpretation von Postfix-Notation (II) -

Ausgabe I + 1 ==> H1D [ H1 ] ==> H2H2 - E ==> H3C * H3 ==> H4Y + Z ==> H5float ( H5 ) ==> H6F ( X , H6 ) ==> H7H4 / H7 ==> H8B + H8 ==> H9H9 ==> A

Irrtumvorbehalten !

Typüberprüfungbeim jeweiligenGenerieren !

Einfach gehaltene Speicherabbildung


30

A B C D I 1 + []1 E - * F X Y Z + f2 / + := endEingabe


- gezeigt an Interpretation von Postfix-Notation (III) -

Ausgabe I + 1 ==> H1D [ H1 ] ==> H1H1 - E ==> H1C * H1 ==> H1Y + Z ==> H2float ( H2 ) ==> H2F ( X , H2 ) ==> H2H1 / H2 ==> H1B + H1 ==> AIrrtum

vorbehalten !

Typüberprüfungbeim jeweiligenGenerieren !

Verbesserte Speicherabbildung


31


- gezeigt an Interpretation von Postfix-Notation (IV) -

I + 1 ==> H1D [ H1 ] ==> H1H1 - E ==> H1C * H1 ==> H1Y + Z ==> H2float ( H2 ) ==> H2F ( X , H2 ) ==> H2H1 / H2 ==> H1B + H1 ==> A

Irrtumvorbehalten !

Befehle könnten sofort ausge-führt werden; keine Befehls-generierung erforderlich

Operandenkeller wird zur Lauf-zeit ein

Verbesserte Speicherabbildung

Wertekeller !


32

• “Attributierung” an den Knoten der Zerlegungsbaums==> “attributierter Baum”

• Beispiele von Attributen:- Typ des durch den Knoten repräsentierten Laufzeit- werts- Speicherbedarf dieses Werts- Speicheradresse dieses Werts- In Programmschleifen Aussage über Art der Wert- änderung (z.B. Eignung für lineare Adreßfortschaltung)

• ererbte und synthetisierte Attribute• Berechnungsregeln für Attribute• Baumdurchwanderung zur Berechnung der Attribute /

vorab bestimmtes “Attributberechnungsprogramm”

Semantische Analyse (I)


33

• “Attributierung” an den Knoten der Zerlegungsbaums==> “attributierter Baum”

• Beispiele von Attributen:- Typ des durch den Knoten repräsentierten Laufzeit- werts- Speicherbedarf dieses Werts- Speicheradresse dieses Werts- In Programmschleifen Aussage über Art der Wert- änderung (z.B. Eignung für lineare Adreßfortschaltung)

• Berechnungsregeln für Attribute• Baumdurchwanderung zur Berechnung der Attribute /

vorab bestimmtes “Attributberechnungsprogramm”

Semantische Analyse (II)

Fehlerbehandlung ?

(siehe Referat #06)


34

ENDEder Vorbemerkungen

Fragen ?


35

Date post:	05-Apr-2015
Category:	Documents
Upload:	emil-ehart
View:	104 times
Download:	0 times

Testen und Analysieren von Software Fehlerbehebung und Re-Engineering Vorbemerkungen zu Themen #04 -...

Documents