1. Einleitung / Abgrenzung

• Algorithmen und Datenstrukturen
• Paradigmen und Konzepte
• Syntax und Semantik
• Ausblick: Visuelle Programmierung
  Visual Basic, Delphi, Java Beans

Literatur:

• David A. Watt, Programmiersprachen, Hanser 1996
• Tremblay, Sorenson, Compiler Writing, McGraw-Hill, 1987
• N. Wirth, Compilerbau, Teubner 1984
• E. Fehr, Semantik von Programmiersprachen, Springer 1988
• Aho, Sethi, Ullman, Compilers: Prinziples, Techniques and Tools, Addison-Wesley 1986
• Rechenberg, Pomberger, Informatik-Handbuch, Teil D: Praktische Informatik, Hanser 1997

1.1. Algorithmen und Datenstrukturen

• Programiersprache zum Ausdrücken, Aufschreiben
• angepasst an Algorithmen (z.B. FORTRAN)
• angepasst an Datenstrukturen (z.B. Cobol)
• hier nur als Beispiele
• --> "Algorithmen" von Sedgewick oder Knuth

1.2. Paradigmen und Konzepte

Verbindungen und Einflüsse

• Rechnerarchitektur
• Betriebsysteme
• Datenbanksysteme
• Softwaretechnik
• Mensch-Maschine Interface

Anforderungen

• universell: jedes Problem, soll programmierbar sein Rekursion
• natürlich: alles für jeweilige Anwendung
• implementierbar: menschliche Sprache, Mathematik
• effizient: Annehmbarkeit, Aufwand der Programmierung

Konzepte

• Werte
• Speicher
• Bindungen
• Abstraktion
• Kapselung
• Ablaufsteuerung
• Nebenläfugkeit

Paradigmen

• imperative Programmierung
• funktionale Programmierung
• logische Programmierung
• objektorientierte Programmierung
• nebenläufige Programmierung

1.3. Syntax und Semantik

• Form und Bedeutung
• Erweitere Backus-Naur-Form EBNF
• informelle Semantik
• operationale Semantik
• denotationelle Semantik
• axiomatische Semantik
• Pragmatik

1.3.1. Erweitere Backus-Naur-Form EBNF

• name bezeichnet syntaktisches Element
• {} bezeichnet Folgen von Elementen (evtl. leer)
• () bezeichnet notwendige Elemente
• | bezeichnet Auswahl
• [] bezeichnet optionale Elemente
• "terminal" bezeichnet Terminalsymbole
• = bezeichnet Produktionen

• Zeichenvorrat: 7bit ASCII, UTF-8, UTF-16, UCB-4, Unicode
• Tokens: :=, Bezeichner (identifier), Kommentare, Zahlen, Zeichenketten, White-Space

Beispiel:

program      = block"."
block        = { "VAR" identlist  ":" ident [string] ";"
               | "PROCEDURE" ident ["( "[identlist]
                                   [";" "VAR" identlist] ")"]
                             [":" ident]";" block ident ";"
               }
               statement
statement    = [ident ":=" listexpr |
               ident [ "(" [actualparms] ")" ] |
               "RETURN" [ "(" [ expression ] ")" ]
               "BEGIN" statementseq "END" |
               "IF" condition "THEN" statementseq 
                             ["ELSE" statementseq] "END" |
               "WHILE" condition "DO" statementseq "END" |
               "REPEAT" statementseq "UNTIL" condition ]
listexpr     = "{" expression {"," expression} "}" | expression
identlist    = ident {"," ident}
actualparms  = listexpr {"," listexpr}
statementseq = statement {";" statement}
condition    = "NOT" condition |
               "(" condition ")" ("AND"|"OR") "(" condition ")" 
               expression ("="|"#"|"<"|"<="|">"|">=") expression
expression   = ["+"|"-"] term {("+"|"-") term}
term         = power {("*"|"/"|"%") power}
power        = factor [ ("^"|"**") number ]
factor       = ident ["("[actualparms]")"] |
               number | string [ ":" typeexpr ] |
               "(" expression ")"
string       = ('"' {character} '"' | "'" {character} "'")
ident        = letter {letter|digit}
number       = digit {digit}

Fragen

statement    = [ ident ":=" expression |
               "WHILE" condition "DO" statements "END" ]

1.3.2. informelle Semantik

Beschreibung der Speicherveränderungen und des Ein-/Ausgabeverhaltens eines Programmes.
Variablen bezeichnen Speicheradressen.

syntaktische Einheit	semantische Einheit
ident	I
condition	B
expression	T
statement	C
statements	{C} = C;...;C

Semantik

• Bedeutung von 1234 ist 1234
• Bedeutung eines arithmetischen Ausdrucks ist sein Wert

  12+3*4 bedeutet 24

• Bedeutung von I:=T

  Der Speicher wird so verändert, dass der Wert von T in einem Speicherplatz mit der symbolischen Adresse I abgelegt wird.

• Bedeutung von WHILE B DO C END

  Falls der Wert des booleschen Ausdrucks B wahr ergibt, so wird die Anweisung C und anschliessend noch einmal die gesammte Anweisung WHILE B DO C END ausgeführt.

  Falls der Wert des booleschen Ausdrucks B falsch ergibt, so bleibt der Speicher unverändert und die Ausführung der gesammten Anweisung WHILE B DO C END wird beendet.

1.3.3. operationale Semantik

Beschreibung von Zustandsänderungen einer abstrakten Maschine.

1. Zustandsmenge Z = ( Stack, Speicher, Programmteile, Eingabe, Ausgabe )

2. Anfangszustand z0 = ( leer, leerer Speicher, Programm, Eingabe, leer )

   für die Kombination (Programm, Eingabe)

3. Funktion der Zustandsänderungen F : Z --> Z

mit den folgenden Bezeichnungen:

• k.St bezeichnet den Stack, der durch hinzufügen von k zu St entsteht

• p.P bezeichnet das Programm, das durch hinzufügen von p zu P entsteht

• Sp(x) bezeichnet den Inhalt der Variablen x im Speicher Sp

  Sp[n/I] bezeichnet den Speicher Sp, der an der Stelle I den Wert n hat

  Sp[n/I](x) = n falls x die Stelle I bezeichnet, Sp(x) sonst

  z1 --> z2 bezeichnet F(z1) = z2

Semantik

• F ( n1.n2.St, Sp, op.P, E, A ) = ( m.St, Sp, P, E, A )

  wobei m der Wert von n1 op n2 ist

  zum Beispiel: F ( 3.4.St, Sp, +.P, E, A ) = ( 12.St, Sp, P, E, A )

• F ( St, Sp, I:=T.P, E, A ) = ( n.St, Sp, assign(I).P, E, A )

  wobei n der Wert von T ist

  F ( n.St, Sp, assign(I).P, E, A ) = ( St, Sp[n/I], P, E, A )

  zum Beispiel:
  ( St, Sp, x:=3.P, E, A )
  --> ( 3.St, Sp, assign(x).P, E, A )
  --> ( St, Sp[3/x], P, E, A )

• F ( St, Sp, C1;C2.P, E, A ) = ( St, Sp, C1.C2.P, E, A )

• F ( St, Sp, WHILE B DO C END.P, E, A ) = ( w(B).St, Sp, while(B,C).P, E, A )

  F ( true.St, Sp, while(B,C).P, E, A ) = ( St, Sp, C.WHILE B DO C END.P, E, A )

  F ( false.St, Sp, while(B,C).P, E, A ) = ( St, Sp, P, E, A )

  zum Beispiel:
  ( St, Sp[0/x], WHILE x<1 DO x:=x+1 END.P, E, A )
  --> ( true.St, Sp[0/x], while(x<1,x:=x+1).P, E, A )
  --> ( St, Sp[0/x], x:=x+1.WHILE x<1 DO x:=x+1 END.P, E, A )
  --> ( St, Sp[1/x], WHILE x<1 DO x:=x+1 END.P, E, A )
  --> ( false.St, Sp[1/x], while(x<1,x:=x+1).P, E, A )
  --> ( St, Sp[1/x], P, E, A )

1.3.4. denotationelle Semantik

• Zustand = ( Speicher, Eingabe, Ausgabe )

• Speicher : Id --> Zahl
  Speicher(x) = n, falls Speicher[n/x]

• T: (Term, Zustand) --> ( Zahl, Zustand )

  Notation: T[[ T ]] z = ( n, z' )

• C: (Programmteil, Zustand) --> ( Zustand )

  Notation: C[[ P ]] z = z'

Semantik

• T[[ T1 + T2 ]] z = ( n1+n2, z2 ) falls

  T[[ T1 ]] z = ( n1, z1 ) und T[[ T2 ]] z1 = ( n2, z2 )

• C[[ I := T ]] z = ( Sp[n/I], e', a ) falls

  T[[ T ]] z = ( n, ( Sp, e', a ) )

• C[[ C1; C2 ]] z = C[[ C2 ]] ( C[[ C1 ]] z )

• C[[ WHILE B DO C END ]] z =
  

  C[[ C; WHILE B DO C END ]] z'	falls T[[ B ]] z = ( true, z' )
  z'	falls T[[ B ]] z = ( false, z' )

1.3.5. axiomatische Semantik

Prädikate beschreiben die Bedeutung.

Axiomenschema: { Q } C { R }

Falls Q für einen Zustand z erfüllt ist und C im Zustand z mit z' terminiert, dann gilt R im Zustand z'.

• { Q[t/I] } I:=T { Q }
  syntaktische Substitution Q[t/x] und t die Bedeutung von T

• { Q } C1 { R }, { R } C2 { S }

  ------------------------------------

  { Q } C1; C2 { S }

• sei b die Bedeutung von B

  { Q and b } C { Q }

  ---------------------------------------------------

  { Q } WHILE B DO C END { Q and not b }

  Beispiel

  { x < 1 } x:=x+1 { }

  ---------------------------------------------------

  { } WHILE x < 1 B x:=x+1 END { x >= 1 }

• Konsequenzregel

  Q --> Q1, { Q1 } C { R1 }, R1 --> R

  -----------------------------------------

  { Q } C { R }

1.3.6. Pragmatik

• Arithmetik, z.B. Addition
• bedingte Kompilierung
• Optimierung, z.B. i486, i586
• Register, Volatile

1.4. Ausblick

• Visual Basic
• Delphi
• Java Beans

• einzelne Pixel
• Widgets
• Toolkits
• Beans