Einleitung

Programme und Algorithmen

Deutsch als Programmiersprache

§6 (2) …Der Zuteilungsdivisor ist so zu bestimmen, dass insgesamt so viele Sitze auf die Landeslisten entfallen, wie Sitze zu vergeben sind. Dazu wird zunächst die Gesamtzahl der Zweitstimmen aller zu berücksichtigenden Landeslisten durch die Zahl der jeweils nach Absatz 1 Satz 3 verbleibenden Sitze geteilt. Entfallen danach mehr Sitze auf die Landeslisten, als Sitze zu vergeben sind,…

§6 (5) Die Zahl der nach Absatz 1 Satz 3 verbleibenden Sitze wird so lange erhöht, bis jede Partei bei der zweiten Verteilung der Sitze nach Absatz 6 Satz 1 mindestens die bei der ersten Verteilung nach den Absätzen 2 und 3 für sie ermittelten zuzüglich der in den Wahlkreisen errungenen Sitze erhält, die nicht nach Absatz 4 Satz 1 von der Zahl der für die Landesliste ermittelten Sitze abgerechnet werden können.

http://www.gesetze-im-internet.de/bwahlg/__6.html

Beispiel: mehrsprachige Projekte

ein typisches Projekt besteht aus:

und das ist noch nicht die ganze Wahrheit:

nenne weitere Sprachen, die üblicherweise in einem solchen Projekt vorkommen

In / Into

Sprache

Wie unterschiedlich sind Sprachen?

Konzepte

Paradigmen

Ziele der LV

Arbeitsweise: Methoden, Konzepte, Paradigmen

Ziel:

Beziehungen zu anderen LV

Sprachen für bestimmte Anwendungen, mit bestimmten Paradigmen:

Organisation

Literatur

Zum Vergleich/als Hintergrund:

Inhalt

(nach Sebesta: Concepts of Programming Languages)

Übungen

1. Anwendungsgebiete von Programmiersprachen, wesentliche Vertreter

zu Skriptsprachen: finde die Anzahl der "*.java"-Dateien unter $HOME/workspace, die den Bezeichner String enthalten. (Benutze eine Pipe aus drei Unix-Kommandos.)

Lösungen:

find workspace/ -name "*.java" | xargs grep -l String       | wc -l
find workspace/ -name "*.java"   -exec grep -l String {} \; | wc -l

2. Maschinenmodelle (Bsp: Register, Turing, Stack, Funktion)

funktionales Programmieren in Haskell (http://www.haskell.org/)

ghci
:set +t
length $ takeWhile (== '0') $ reverse $ show $ product [ 1 .. 100 ]

Kellermaschine in PostScript.

42 42 scale 7 9 translate .07 setlinewidth .5 setgray/c{arc clip fill
setgray}def 1 0 0 42 1 0 c 0 1 1{0 3 3 90 270 arc 0 0 6 0 -3 3 90 270
arcn 270 90 c -2 2 4{-6 moveto 0 12 rlineto}for -5 2 5{-3 exch moveto
9 0 rlineto}for stroke 0 0 3 1 1 0 c 180 rotate initclip}for showpage

Mit gv oder kghostview ansehen (Options: watch file). Mit Editor Quelltext ändern. Finden Sie den Autor dieses Programms!

(Lösung: John Tromp, siehe auch http://www.iwriteiam.nl/SigProgPS.html)

3. http://99-bottles-of-beer.net/ (top rated …)

Übung: Beispiele für Übersetzer

2pt

Java:

javac Foo.java # erzeugt Bytecode (Foo.class)
java Foo       # führt Bytecode aus (JVM)

Einzelheiten der Übersetzung:

javap -c Foo   # druckt Bytecode

C:

gcc -c bar.c   # erzeugt Objekt(Maschinen)code (bar.o)
gcc -o bar bar.o # linkt (lädt) Objektcode (Resultat: bar)
./bar         # führt gelinktes Programm aus

Einzelheiten:

gcc -S bar.c # erzeugt Assemblercode (bar.s)

Aufgaben:

gcc für Java (gcj):

gcj -c Foo.java # erzeugt Objektcode
gcj -o Foo Foo.o --main=Foo # linken, wie oben

Syntax von Programmiersprachen

Programme als Bäume

Token-Typen

alle Token eines Typs bilden eine formale Sprache.

Formale Sprachen

Beispiele:

Spezifikation formaler Sprachen

man kann eine formale Sprache beschreiben:

Sprach-Operationen

Aus Sprachen \(L_1, L_2\) konstruiere:

Def: Sprache regulär \(:\iff\) kann durch diese Operationen aus endlichen Sprachen konstruiert werden.

Satz: Durchschnitt und Differenz braucht man dabei nicht.

Reguläre Sprachen/Ausdrücke

Die Menge \(E(\Sigma)\) der regulären Ausdrücke
über einem Alphabet (Buchstabenmenge) \(\Sigma\)
ist die kleinste Menge \(E\), für die gilt:

Jeder solche Ausdruck beschreibt eine reguläre Sprache.

Beispiele/Aufgaben zu regulären Ausdrücken

Wir fixieren das Alphabet \(\Sigma=\{a,b\}\).

Erweiterte reguläre Ausdrücke

  1. zusätzliche Operatoren (Durchschnitt, Differenz, Potenz),

    die trotzdem nur reguläre Sprachen erzeugen

    Beispiel: \(\Sigma^* \setminus ( \Sigma^* ab \Sigma^*)^2\)

  2. zusätzliche nicht-reguläre Operatoren

    Beispiel: exakte Wiederholungen \(L^{\fbox{\)k\(}} := \{ w^k \mid w\in L \}\)

    beachte Unterschied zu \(L^k\)

  3. Markierung von Teilwörtern, definiert (evtl. nicht-reguläre) Menge von Wörtern mit Positionen darin

wenn nicht-reguläre Sprachen entstehen können, ist keine effiziente Verarbeitung (mit endlichen Automaten) möglich.

auch reguläre Operatoren werden gern schlecht implementiert (http://swtch.com/~rsc/regexp/regexp1.html)

Bemerkung zu Reg. Ausdr.

Wie beweist man \(w\in \operatorname{L}(X)\)?

(Wort \(w\) gehört zur Sprache eines regulären Ausdrucks \(X\))

Beispiel: \(w = abba, X = (ab^*)^*\).

\(w = abb\cdot a = ab^2 \cdot a b^0 \in ab^* \cdot ab^* \subseteq (ab^*)^2 \subseteq (ab^*)^*\).

Übungen Reg. Ausdr.

Wort-Ersetzungs-Systeme

Berechnungs-Modell (Markov-Algorithmen)

Regelmenge \(R \subseteq \Sigma^* \times \Sigma^*\)

Regel-Anwendung: \(u \to_R v \iff \exists x,z\in\Sigma^*, (l,r) \in R: u = x \cdot l\cdot z \wedge x \cdot r \cdot z = v\).

Beispiel: Bubble-Sort: \(\{ba \to ab, ca \to ac, cb \to bc\}\)

Beispiel: Potenzieren: \(ab \to bba\)

Aufgaben: gibt es unendlich lange Rechnungen für: \(R_1 = \{ 1000 \to 0001110 \}, R_2= \{ aabb \to bbbaaa \}\)?

Grammatiken

Grammatik \(G\) besteht aus:

Grammatik
  { terminale 
       = mkSet "abc"
  , variablen
       = mkSet "SA"
  , start = 'S'
  , regeln = mkSet
       [ ("S", "abc")
       , ("ab", "aabbA")
       , ("Ab", "bA")
       , ("Ac", "cc")
       ]
  }

von \(G\) erzeugte Sprache: \(L(G) = \{ w \mid S \to_R^* w \wedge w \in \Sigma^* \}\).

Formale Sprachen: Chomsky-Hierarchie

Tokenklassen sind meist reguläre Sprachen.

Programmiersprachen werden kontextfrei beschrieben (mit Zusatzbedingungen).

Typ-3-Grammatiken

(\(=\) rechtslineare Grammatiken)

jede Regel hat die Form

(vgl. lineares Gleichungssystem)

Beispiele

Sätze über reguläre Sprachen

Für jede Sprache \(L\) sind die folgenden Aussagen äquivalent:

Beweispläne:

Kontextfreie Sprachen

Def (Wdhlg): \(G\) ist kontextfrei (Typ-2), falls \(\forall (l,r) \in R(G): l \in V\).

geeignet zur Beschreibung von Sprachen mit hierarchischer Struktur.

Anweisung -> Bezeichner = Ausdruck
    | if Ausdruck then Anweisung else Anweisung
Ausdruck -> Bezeichner | Literal
    | Ausdruck Operator Ausdruck

Bsp: korrekt geklammerte Ausdrücke: \(G = ( \{ a,b\}, \{S\}, S, \{ S \to aSbS, S \to \epsilon \} )\).

Bsp: Palindrome: \(G = ( \{ a,b\}, \{S\}, S, \{ S \to aSa, S \to bSb, S \to \epsilon )\).

Bsp: alle Wörter \(w\) über \(\Sigma=\{a,b\}\) mit \(|w|_a = |w|_b\)

Klammer-Sprachen

Abstraktion von vollständig geklammerten Ausdrücke mit zweistelligen Operatoren

(4*(5+6)-(7+8)) \(\Rightarrow\) (()()) \(\Rightarrow aababb\)

Höhendifferenz: \(h : \{a,b\}^* \to \mathbb{Z}: w \mapsto |w|_a - |w|_b\)

Präfix-Relation: \(u \le w :\iff \exists v: u\cdot v = w\)

Dyck-Sprache: \(D=\{w \mid h(w)=0 \wedge \forall u\le w: h(u)\ge 0\}\)

CF-Grammatik: \(G = (\{a,b\},\{S\},S,\{S\to\epsilon,S\to aSbS\})\)

Satz: \(L(G)=D\). Beweis (Plan):

\(L(G)\subseteq D\) Induktion über Länge der Ableitung

\(D\subseteq L(G)\) Induktion über Wortlänge

Übungen

(erweiterte) Backus-Naur-Form

Backus-Naur-Form (BNF) \(\approx\) kontextfreie Grammatik

<assignment> -> <variable> = <expression>
<number> -> <digit> <number> | <digit>

Erweiterte BNF

kann in BNF übersetzt werden

Ableitungsbäume für CF-Sprachen

Def: ein geordneter Baum \(T\) mit Markierung \(m: T \to \Sigma\cup\{\epsilon\}\cup V\) ist Ableitungsbaum für eine CF-Grammatik \(G\), wenn:

Ableitungsbäume (II)

Def: der Rand eines geordneten, markierten Baumes \((T,m)\) ist die Folge aller Blatt-Markierungen (von links nach rechts).

Beachte: die Blatt-Markierungen sind \(\in \{\epsilon\} \cup \Sigma\), d. h. Terminalwörter der Länge 0 oder 1.

Für Blätter: \(\operatorname{rand}(b)=m(b)\), für innere Knoten: \(\operatorname{rand}(k)=\operatorname{rand}(k_1) \operatorname{rand}(k_2)\ldots \operatorname{rand}(k_n)\)

Satz: \(w \in L(G) \iff\) existiert Ableitungsbaum \((T,m)\) für \(G\) mit \(\operatorname{rand}(T,m)=w\).

Eindeutigkeit

Def: \(G\) heißt eindeutig, falls \(\forall w \in L(G)\) genau ein Ableitungsbaum \((T,m)\) existiert.

Bsp: ist \(\{ S \to aSb | SS | \epsilon \}\) eindeutig?

(beachte: mehrere Ableitungen \(S \to_R^* w\) sind erlaubt, und wg. Kontextfreiheit auch gar nicht zu vermeiden.)

Die naheliegende Grammatik für arith. Ausdr.

expr -> number | expr + expr | expr * expr

ist mehrdeutig (aus zwei Gründen!)

Auswege:

Assoziativität

Assoziativität (II)

X1 + X2 + X3 auffassen als (X1 + X2) + X3

Grammatik-Regeln

Ausdruck -> Zahl | Ausdruck + Ausdruck

ersetzen durch

Ausdruck -> Summe 
Summe    -> Summand | Summe + Summand
Summand  -> Zahl

Präzedenzen

\[(3+2)*4 \stackrel{?}{=} 3+2*4 \stackrel{?}{=} 3+(2*4)\]

Grammatik-Regel

summand -> zahl

erweitern zu

summand -> zahl | produkt
produkt -> ...

(Assoziativität beachten)

Zusammenfassung Operator/Grammatik

Ziele:

Festlegung:

Realisierung in CFG:

Übung Operator/Grammatik

Übung:

Das hängende else

naheliegende EBNF-Regel für Verzweigungen:

<statement> -> if <expression> 
    then <statement> [ else <statement> ]

führt zu einer mehrdeutigen Grammatik.

Dieser Satz hat zwei Ableitungsbäume:

if X1 then if X2 then S1 else S2

Semantik von Programmiersprachen

Statische und dynamische Semantik

Semantik \(=\) Bedeutung

Attributgrammatiken (I)

Attributgrammatiken (II)

ein Ableitungsbaum mit Annotationen ist
korrekt bezüglich einer Attributgrammatik, wenn

Plan:

Ursprung: Donald Knuth: Semantics of Context-Free Languages, (Math. Systems Theory 2, 1968)

technische Schwierigkeit: Attributwerte effizient bestimmen. (beachte: (zirkuläre) Abhängigkeiten)

Donald E. Knuth

http://www-cs-faculty.stanford.edu/~uno/

Arten von Attributen

Wenn Abhängigkeiten bekannt sind, kann man Attributwerte durch Werkzeuge bestimmen lassen.

Attributgrammatiken–Beispiele

Konkrete und abstrakte Syntax

unwesentlich sind z. B. die Knoten, die zu Hilfsvariablen der Grammatik gehören.

abstrakter Syntaxbaum kann als synthetisiertes Attribut konstruiert werden.

E -> E + P  ;  E.abs = new Plus(E.abs, P.abs)
E -> P      ;  E.abs = P.abs

Regeln zur Typprüfung

…bei geschachtelten Funktionsaufrufen

Beispiel

class C {
  static class A {}  static class B {}
  static B f (A y) { .. }
  static A g (B x) { .. }
  .. 
  .. C.g (C.f (new C.A()))  .. }

Übung Attributgrammatiken/SableCC

Bemerkungen (häufige/nicht offensichtliche Fehlerquellen)

Kommentar: in Java fehlen: algebraische Datentypen, Pattern Matching, Funktionen höherer Ordnung. Deswegen muß SableCC das simulieren — das sieht nicht schön aus. Die richtige Lösung sehen Sie später im Compilerbau.

Abstrakter Syntaxbaum, Interpreter: http://www.imn.htwk-leipzig.de/~waldmann/edu/ws11/cb/folien/main/node12.html, Kombinator-Parser: http://www.imn.htwk-leipzig.de/~waldmann/edu/ws11/cb/folien/main/node70.html

Dynamische Semantik

Bsp. Operationale Semantik (I)

arithmetischer Ausdruck \(\Rightarrow\) Programm für Kellermaschine

\(3*x + 1\) \(\Rightarrow\) push 3, push x, mal, push 1, plus

Der erzeugte Code ist synthetisiertes Attribut!

Beispiele: Java-Bytecode (javac, javap),
CIL (gmcs, monodis)

Bemerkung: soweit scheint alles trivial—interessant wird es bei Teilausdrücken mit Nebenwirkungen, Bsp. x++ - --x;

Bsp: Operationale Semantik (II)

Schleife

while (B) A

wird übersetzt in Sprungbefehle

   if (B) ...

(vervollständige!)

Aufgabe: übersetze for(A; B; C) D in while!

Denotationale Semantik

Beispiele

Vorteile denotationaler Semantik:

Vorteil deklarativer Programierung:

Programmiersprache ist Beschreibungssprache

Beispiele Denotationale Semantik

Beispiel: Semantik von Unterprogr.

Unterprogramme definiert durch Gleichungssysteme.

Sind diese immer lösbar? (überhaupt? eindeutig?)

Geben Sie geschlossenen arithmetischen Ausdruck für:

f (x) = if x > 52 
        then x - 11 
        else f (f (x + 12))

g(x,y) = 
  if x <= 0 then 0 
  else if y <= 0 then 0
  else 1 + g (g (x-1, y), g (x, y-1))

Axiomatische Semantik

Notation für Aussagen über Speicherbelegungen:

{ V } A { N }

Beispiel:{ x >= 5 } y := x + 3 { y >= 7 }

Gültigkeit solcher Aussagen kann man

Beachte: {x >= 5} while (true) ; {x == 42}

Eiffel

Bertrand Meyer, http://www.eiffel.com/

class Stack [G]     feature 
    count : INTEGER
    item : G is require not empty do ... end
    empty : BOOLEAN is do .. end
    full  : BOOLEAN is do .. end
    put (x: G) is
       require not full do ...
       ensure not empty
              item = x
              count = old count + 1

Beispiel sinngemäß aus: B. Meyer: Object Oriented Software Construction, Prentice Hall 1997

Hoare-Kalkül

Kalkül: für jede Form der Anweisung ein Axiom, Beispiele:

Axiom für Schleifen

wenn  { I and B } A { I },
dann  { I } while (B) do A { I and not B }

Beispiel:

Eingabe int p, q; 
// p = P und q = Q
int c = 0;
// inv: p * q + c = P * Q 
while (q > 0) { 
   ???
}
// c = P * Q

Moral: erst Schleifeninvariante (Spezifikation), dann Implementierung.

Übungen (Stackmaschine)

Schreiben Sie eine Java-Methode, deren Kompilation genau diesen Bytecode erzeugt: a)

  public static int h(int, int);
    Code:
       0: iconst_3      
       1: iload_0       
       2: iadd          
       3: iload_1       
       4: iconst_4      
       5: isub          
       6: imul          
       7: ireturn       

b)

  public static int g(int, int);
    Code:
       0: iload_0       
       1: istore_2      
       2: iload_1       
       3: ifle          17
       6: iload_2       
       7: iload_0       
       8: imul          
       9: istore_2      
      10: iload_1       
      11: iconst_1      
      12: isub          
      13: istore_1      
      14: goto          2
      17: iload_2       
      18: ireturn       

Übungen (Invarianten)

Ergänze das Programm:

Eingabe: natürliche Zahlen a, b;
// a = A und b = B
int p = 1; int c = ???;
// Invariante:  c^b * p = A^B
while (b > 0) {
    ???
    b = abrunden (b/2);
}
Ausgabe: p; // p = A^B