Programmierkurs Java WS 98/99 Vorlesung 2 Dietrich Boles 28/10/98Seite 1 Programmierkurs Java Vorlesung im WS 1998/1999 am FB Informatik der Universität

Programmierkurs Java WS 98/99 Vorlesung 2 Dietrich Boles 28/10/98 Seite 1

Programmierkurs Java

Vorlesung

im WS 1998/1999

am FB Informatik

der Universität Oldenburg

Vorlesung 2

Dietrich Boles


Gliederung von Vorlesung 2

• Programmierung– Terminologie

– Algorithmen

– Programme

• Programmiersprachen– Klassifikation

– Abstraktionsebenen

– Syntaxdiagramme

– Backus-Naur-Form

• Programmentwicklung– Entwicklungsphasen

– Entwicklungswerkzeuge

– Compilation

• Computer– Arbeitsweise

– Hardware

– Software

– Speicher

• Aussagenlogik– Aussagen

– Eigenschaften von Aussagen


Programmierung / Terminologie

Programmierung: Erstellung von Computerprogrammen

Softwareentwicklung: Methoden zum Lösen von Problemen mit dem Computer

Algorithmus: Arbeitsanleitung für einen Computer

Programmiersprache: computerverständliche Notation zur Formulierung von Algorithmen

Programm: in einer Programmiersprache formulierter Algorithmus

„Programmieren im Kleinen“: Lösen kleiner Probleme

„Programmieren im Großen“: Lösen komplexer Probleme

Softwareengineering: Vorgehensmodelle, Entwicklungsmethoden, Entwicklungsumgebungen,

Projekt-, Qualitäts- und Konfigurationsmanagement


Programmierung / Algorithmus / Motivation

Arbeitsanleitungen: – Kochrezepte

– Bastelanleitungen

– Partituren

– Spielregeln

Aufbau:– Menge von Anweisungen

Charakteristika:– Anweisungssequenzen

– bedingte Anweisungen

– Anweisungsschleifen

– Zutaten / Voraussetzungen

– „schwammige“ Formulierungen


Programmierung / Algorithmus / Definition

Definition: – Arbeitsanleitung zum Lösen eines Problems bzw. einer Aufgabe, die so

präzise formuliert ist, daß sie von einem Computer ausgeführt werden kann

Formulierung von Algorithmen:– Umgangssprachlich

– Programmiersprache

– Programmablaufpläne

– Struktogramme

Ausführung von Algorithmen:– durch einen Prozessor (Mensch / Computer) Prozeß

– Computer:• schnell

• zuverlässig

• hohe Speicherfähigkeit


Programmierung / Algorithmus / Formulierung

Beispiel: Berechnung der Summe aller Zahlen von 1 bis n

Umgangssprachliche Formulierung:

Addiere für eine vorgegebene natürliche Zahl ndie Zahlen von 1 bis n. Dies ist das Resultat.

Programmiersprache:

int n = readInt();int erg = 0;int i = 0;while (i <= n) { erg = erg + i; i = i + 1;}printInt(erg);



Programmablaufpläne / Flußdiagramme:

erg = 0

Anfang

i = 0

Eingabe n

i <= nja nein

erg = erg + i

i = i + 1

Ausgabe erg

Ende

Anfang

Ende

Bedingungja nein

Aktion

Eingabe Ausgabe



Struktogramme / Nassi-Shneiderman-Diagramme:

erg = erg + i

i = i + 1

while i <= n

print (erg)

read (n)

erg = 0

i = 0

Aktion

Aktion 1

Aktion 2

...

Aktion n

Bedingung

ja nein

Aktion 1 Aktion 2

while Bedingung

Aktion

Anweisung

Anweisungs-sequenz

bedingteAnweisung

Schleife


Programmierung / Algorithmus / Eigenschaften

theoretisch:

– Eindeutigkeit

– Parametrisierbarkeit

– Finitheit

– Ausführbarkeit

– Terminierung

– Determiniertheit

– Determinismus

praxisrelevant:

– korrekt

– vollständig

– effizient (Zeit)

– sparsam (Speicher)

– erweiterbar

– wiederverwendbar

– portabel

– verständlich


Programmierung / Programme

Programm: ein in einer Programmiersprache formulierter Algorithmus

Programmieren: Erstellen von Programmen

Programmierer: Entwickler von Programmen

Programmcode, Quellcode, Sourcecode: Programmbeschreibung

ausführbares Programm: Programm in maschinenverständlicher Form

Programmaufruf: Ausführung eines ausführbaren Programms


Programmiersprachen / Klassifikation

Anwender:

– Anfänger

– ExpertenParadigmen:

– imperativ

– funktional

– prädikativ

– regelbasiert

– objektorientiert

Abstrahierungsgrad:

– maschinennah

– problemorientiert

Komplexität:

– problemspezifisch

– „general-purpose“


Programmiersprachen / Abstraktionsebenen

Lexikalik: gültige Zeichen und Wörter der Sprache

Syntax: korrekter Aufbau von Sätzen der Sprache

Semantik: Bedeutung von Sätzen der Sprachen

Pragmatik: Einsatzbereich einer Sprache

Quell-programm

Token-folge

Ableitungs-baum

Ziel-programm

LexikalischeAnalyse

(Scanner)

SyntaktischeAnalyse(Parser)

SemantischeAnalyse/

Codegenerierung


Programmiersprachen / Lexikalische Analyse

• Entfernung von Trennzeichen und Kommentaren• Erkennung von Token (Zeichen, die bedeutungsmäßig zusammengehören):

– Schlüsselwörter– Konstanten– Bezeichner– Symbole– Zeichenketten– ...

• Grundbaustein: endlicher Automat• Beschreibung: reguläre Ausdrücke

while n > 0 do n := n-1;

whilen>0don

:=n-1;

PASCAL


Programmiersprachen / Syntaktische Analyse

• Überführung einer Tokenfolge in Ableitungsbaum

• Untersuchung auf syntaktische Korrektheit

• Beschreibung: kontextfreie Grammatiken

• Darstellung: Syntaxdiagramme, BNF

n:=3+i

Zuweisung

Variable := Ausdruck

Term Term

Konstante Variable

3

+

i

n


Programmiersprachen / Semantische Analyse

• Überprüfung des Ableitungsbaums auf Fehler

(kontextsensitive Zusatzbedingungen)

• Vorbereitung der Codeerzeugung

• Nutzung einer Symboltabelle

• attributierte Syntaxbäume


Programmiersprachen / Syntaxdiagramme

• Technik zur graphischen Darstellung kontextfreier Grammatiken• Elemente:

– Knoten• Ellipsen (Token, Terminale)

• Rechtecke (Nichtterminale)

– Kanten• knotenverbindende Pfeile

• eintretender Pfeil (Eingangskante)

• austretender Pfeil (Ausgangskante)

• Interpretation: Durchläuft man ein Syntaxdiagramm von der Eingangs- zur Ausgangskante entlang den Pfeilen, dann ist die Folge der Knoteninhalte, die dabei „aufgesammelt“ werden, aus dem Syntaxdiagramm ableitbar.



Syntaktisch korrekt:Schlangen Delphine

Schlangen Elephanten Pinguine Delphine

Schlangen Elephanten Pinguine Affen Delphine

Schlangen Elephanten Pinguine Elephanten Pinguine Delphine

Syntaktisch nicht korrekt:Elephanten Delphine

Schlangen Pinguine

Schlangen Elephanten Affen Delphine

Schlangen Pinguine Schlangen Delphine

ZooSäugetiere„Schlangen“ „Delphine“

„Pinguine“

„Elephanten“

„Affen“

Säugetiere



Definition:

– Jedes Syntaxdiagramm (SD) besitzt eine Bezeichnung

– Elemente eines Syntaxdiagramms sind Knoten (Ellipsen, Rechtecke) und

Kanten (Pfeile)

– Rechtecke enthalten die Bezeichnung eines (anderen) Syntaxdiagramms

– Ellipsen enthalten Token

– in jeden Knoten führt genau ein Pfeil hinein

– aus jedem Knoten führt genau ein Pfeil hinaus

– Pfeile dürfen sich aufspalten bzw. zusammengezogen werden

– jedes SD besitzt genau eine eintretende Kante (kein Ausgangsknoten)

– jedes SD besitzt genau eine austretende Kante (kein Eingangsknoten)



a b DS

cD

Syntaktisch korrekt oder nicht ?

• abababccc• ababcccabab• aba• ccccccc

• abDc• bababac• ababcdcd• ABABABc



a bS

S

Syntaktisch korrekt oder nicht ?

• aSb• aab• aaabbb• abbbbbbb• aaabbbaaa

L (S) = ?



L = {a (b c) d } | n ist natürliche Zahl oder Null; i ist natürliche Zahl}

2 n i


Programmiersprachen / BNF

Backus-Naur-Form:– Technik zur textuellen Darstellung kontextfreier Grammatiken

– Verwendung von Ersetzungsregeln (Produktionen)

– besitzen linke und rechte Seite

– linke Seite: Nichtterminalsymbol

– Nichtterminalsymbol: durch < > gekennzeichnet

– Alternativen: durch | gekennzeichnet

– e (Epsilon): leere Alternative

EBNF:– Erweiterung der BNF (Abkürzungsmöglichkeiten)

– [...] bedeutet: Symbole in Klammern können auch wegfallen

– {...} bedeutet: Symbole in Klammern können beliebig oft wiederholt werden



BNF:

<Zoo> ::= „Schlangen“ <Säugetiere-und-mehr>

<Säugetiere-und-mehr> ::= <Säugetiere> „Pinguine“ <Säugetiere-und-mehr> | <Säugetiere> „Delphine“

<Säugetiere> ::= „Elephanten“ | „Affen“ | e



EBNF:

<Zoo> ::= „Schlangen“ <Säugetiere> {„Pinguine“ <Säugetiere>} „Delphine“

<Säugetiere> ::= „Elephanten“ | „Affen“ | e


Programmentwicklung / Entwicklungsphasen

Dokumentation

Problem

Programm

Implementierung

Analyse

Entwurf

Test



Analyse:– Untersuchung des Problems und des Problemumfelds

– Diskussion mit anderen Personen

– Fragestellungen / Tätigkeiten:• Problemstellung exakt und vollständig

• gegebene Initialzustände und Eingabeparameter

• gewünschte Endzustände und Ausgabewerte

• Randbedingungen, Constraints

Entwurf:– Entwicklung des Algorithmus

– kreativer Prozeß (Auffassungsgabe, Intelligenz, Erfahrung)

– Fragestellungen / Tätigkeiten:• existierende Lösungen für vergleichbare Probleme

• allgemeinere Probleme

• rekursive Aufteilung des Problems in Teilprobleme

• Durchführung des Entwurfsprozeß für Teilprobleme

• Zusammensetzen der Lösungen der Teilprobleme zur Lösung des Gesamtproblems



Implementierung:– Übertragung des Entwurfs in eine Programmiersprache

– Fragestellungen / Tätigkeiten:• Editieren

• Compilieren

Test:– Überprüfung des Programms auf logische und technische Fehler

– man kann nur die Existenz von Fehlern nachweisen, nicht die Abwesenheit!

– Fragestellungen / Tätigkeiten:• Korrektheit

• Vollständigkeit

• Debugging

– Teststrategien:• andere Personen testen lassen

• Testmengen konstruieren (Randfälle/Grenzwerte finden)

• nach Fehlerbeseitigung erneut testen



Dokumentation:– Exakte Problemstellung

– Beschreibung der generellen Lösungsidee

– Beschreibung des Algorithmus

– Programmcode

– Beschreibung der Testmengen

– Protokolle der Testläufe

– aufgetretene Probleme

– alternative Lösungsansätze

Weitere Tätigkeiten:– Effizienzverbesserung

– Wartung

– Portierung


Programmentwicklung / Entwicklungswerkzeuge

Editore: Manipulation des Programmcodes

Compiler: Transformation eines Quellprogramms in ein Zielprogramm

Interpreter: inkrementelle Abarbeitung des Quellcodes

Debugger: Erkennung von Laufzeitfehlern

Dokumentationshilfen: Erstellung von Teilen der Dokumentation

Laufzeitsystem: Hilfsprogramme bei der Programmausführung

Programmbibliotheken: Sammlungen fertiggestellter Programme


Programmentwicklung / Compilation

lexikalischeAnalyse

syntaktischeAnalyse

semantischeAnalyse

Zwischen-code-

Erzeugung

Code-Optimierung

Code-Generierung

Folgevon

Token

Syntaxbaum

attributierterSyntaxbaum

Drei-Adreß-Code

optimierterDrei-Adreß-

Code

Assembler-Code

reguläreAusdrücke

BNFGrammatik

Übersetzungs-schemata /attributierteGrammatik

Optimierungs-regeln

Code-Generierungs-anweisungen

Code-Generierungsanweisungen

a := b + 10 * c

(ID,s[1])...(NUM,10)...

s[1]

:=+

*s[2]s[3]10

temp1 := inttoreal(10)temp2 := temp1 * s[3]temp3 := s[2] + temp2s[1] := temp3

temp1 := 10.0 * s[3]s[1] := s[2] + temp1

MOVF s[3],R2MULF #10.0,R2MOVF s[2],R1ADDF R2,R1MOVF R1,s[1]

Quellcode Symboltabelle s

1 a real2 b real3 c real4

s[1]

:=+

*

inttoreals[2]

s[3]

10


Computer

• Gerät zur automatischen Verarbeitung von Daten

• Computer setzen sich zusammen aus– Hardware (physikalische Geräte; Zentraleinheit plus periphere Geräte)

– Software (Programme)

• Arbeitsweise:

Eingabe AusgabeComputer

Programm

Lies eine Zahl ein.

Addiere alle natürlichen Zahlenvon 1 bis zur eingegebenen Zahl.

Gib dieses Ergebnis auf den Bildschirm aus.

5 15Computer


Computer / Hardware

Von-Neumann-Rechnerarchitektur:

Eingabewerk Speicher Ausgabewerk

Rechenwerk

Steuerwerk

Steuersignale Daten


Computer / Hardware

Von-Neumann-Prinzipien:– Computer besteht aus fünf Funktionseinheiten

– Unabhängigkeit von zu bearbeitenden Problemen

– Steuerung mit Hilfe von Programmen

– Programme und Daten werden im Speicher abgelegt

– Binäre Codierung aller Daten

– Unterteilung des Speichers in gleichgroße Zellen

– aufeinanderfolgende Befehle in aufeinanderfolgenden Zellen

– (sequentieller) Zugriff durch Steuerwerk (via Befehlsadresse)

– Sprungbefehle

– arithmetische Befehle (Addition, Multiplikation, ...)

– logische Befehle (Negation, Konjunktion, Vergleiche, ...)

– Transportbefehle

– Schiebeoperationen

– Ein-/Ausgabebefehle


Computer / Software

Spiele

Compiler Editoren Interpreter

Betriebssystem

Prozeß-verwaltung

Speicher-verwaltung

Datei-verwaltung

Geräte-verwaltung

Maschinensprache

Mikroprogrammierung

Physikalische Geräte

Lernsoftware Adreßverwaltung

...

...

...

Anwendungssoftware

Systemsoftware

Hardware


Computer / Software

• Betriebssystem: Menge aller Programme, die den Betrieb eines Computer bewältigt:– Prozeßverwaltung

– Speicherverwaltung

– Dateiverwaltung

– Geräteverwaltung

– ...

• Festplatte: billiger Hintergrundspeicher

• Dateien: logische Behälter zum Speichern von Daten

• Verzeichnisse: Hilfsmittel für eine übersichtliche Strukturierung von Dateien

• Window-System: Aufteilung des Bildschirm in unabhängige „Windows“

• Window-Manager: Verwalter von „Windows“– Anlegen

– Verschieben

– Vergrößern

– ...


Computer / Speicher

• Speicher: Aufbewahrung von Programmen und Daten

• 1 Bit: kleinstes Speicherelement (2 Zustände: 0 und 1)

• 1 Byte:8 Bit (2 Zustände) Speicherzelle

• 1 Wort: 4 oder 8 Speicherzellen

• mathematische Grundlage: Dualsystem

• 2 anstelle von 10 Ziffern (Dezimalsystem)

• Operationen (Addition, Multiplikation, ...) wie gewohnt

• Umrechung:

8

18 : 2 = 9 R 0 9 : 2 = 4 R 1 4 : 2 = 2 R 0 2 : 2 = 1 R 0 1 : 2 = 0 R 1

1101= 1*2 + 0*2 * 1*2 + 1*2 =13

30 1 2

2

10


Aussagenlogik / Aussagen

• Aussage (boolescher Ausdruck): – Satz, dem eindeutig ein Wahrheitswert wahr (true, T) oder falsch (false, F)

zugeordnet werden kann• „Ein Tisch ist ein Möbelstück“• „Geh nach Hause“ (keine Aussage)

• Verknüpfung von Aussagen durch Operatoren: – Negation („!“)

– Konjunktion („&&“)

– Disjunktion („||“)

• Wahrheitstafeln:

P Q P && Q

TF

TFTF

TFFF

P Q P || Q

TTFF

TFTF

TTTF

!P

FT

P

TTFF


Aussagenlogik / Aussagen

Syntax von Aussagen:

boolscherAusdruck

boolscherAusdruck

boolscherAusdruck

&&

boolscherAusdruck

boolscherAusdruck

||

boolscherAusdruck

!

boolscherAusdruck

( )

„einfache Aussage“

• !P

• P && Q

• P || Q

• P || (!Q)

• (P || (!Q && P)

• P || !Q && R

• P || !(Q && R)

• (P || Q) && R


Aussagenlogik / Eigenschaften von Aussagen

• Kommutativgesetz• Assoziativgesetz• Distributivgesetz

• Priorität: ( ! > && > || )• Assoziativität: (!: rechts; &&, ||: links)• Tautologie: P || !P (immer true)• Widerspruch: P && !P (immer false)

Q

TFTF

P

TTFF

P&&Q Q&&P P||Q

TFFF

TFFF

TTTF

TTTF

Q||P

Q

TTFFTTFF

P

TTTTFFFF

Q&&R

TTTTTFFF

R

TFTFTFTF

P||(Q&&R) P||Q P||R (P||Q)&&(P||R)

TFFFTFFF

TTTTTTFF

TTTTTFTF

TTTTTFFF


Aussagenlogik / Eigenschaften von Aussagen

zu zeigen: !P && !Q <=> !(P || Q)

Documents

Programmierkurs Java WS 98/99 Vorlesung 2 Dietrich Boles 28/10/98Seite 1 Programmierkurs Java Vorlesung im WS 1998/1999 am FB Informatik der Universität