EINI-I Einführung in die Informatik für Naturwissenschaftler und Ingenieure I Kapitel 1 Gisbert Dittrich; Claudio Moraga FBI Unido [email protected]

EINI-IEINI-IEinführung in die Informatik Einführung in die Informatik für Naturwissenschaftler und für Naturwissenschaftler und

Ingenieure Ingenieure II

Kapitel 1

Gisbert Dittrich; Claudio Moraga

FBI Unido

[email protected]

2

Kapitel 1: Erste SchritteVorl “EINI-I"

29.10.1999

Gliederung Kap. 1Gliederung Kap. 1

• Vorgehensweise bei Programmkonstruktion• Grundlegendes Scenario• Erstes Programm• ...• Elementare Datentypen• ...• Einführung zu kontextfreien Grammatiken

3


29.10.1999

Übliche Vorgehensweise bei der Übliche Vorgehensweise bei der ProgrammkonstruktionProgrammkonstruktion

Programm-Wartung und Pflege

Analyse des Problems

Entwurf einer Lösung

Test/Verifikation des Programms

Problem

Programm

Realisierung eines Programms

4


29.10.1999

Zur Realisierung eines ProgrammsZur Realisierung eines Programms

Idee zurLösungeines

Problems

Idee zur Lösung

eines Problems

Formulierung eines Programms

ausführbares Programm

(Maschinensprache)

Übersetzung

Laufzeit- System

Aus-führung

Bibliotheken

5


29.10.1999

Erstes C++-ProgrammErstes C++-Programm

Prog-1

6


29.10.1999

Erstes C++ - Programm - AnatomieErstes C++ - Programm - Anatomie

int main() {

int hoehe = 3; int grundseite = 5;

double flaeche = grundseite * hoehe * 0.5;

cout << "Flaeche des Dreiecks: "

<< flaeche << '\n';

return 0;

}

Vereinbarungen

Rechnung

AusgabeAusgabe

Rückgabewert

Haupt-programm

7


29.10.1999

Erstes C++ - Programm (Forts.)Erstes C++ - Programm (Forts.)

• Lexikalische Elemente des Programms• Bezeichner

• Schlüsselwörter/Interpunktion

• Literalkonstanten

• Operatoren (Liste: s. u.)

• Trenner: Leerzeichen, \t (d. h. Tabulatoren), Zeilenendezeichen \n, Seitenvorschübe, Kommentare

8


29.10.1999

Erstes C++ - Programm (Forts.) Erstes C++ - Programm (Forts.)

• Kommentare/*---*/ mehrere Zeilen

// bis Zeilenende

• Bezeichner Buchstabe

gemäß Bauplan Bezeichner Buchstabe Bezeichner ZifferOderSo

• Hierbei– Buchstabe: a ... z A ... Z, – ZifferOderSo: 0 ... 9 _

Interpretation ?

Unterstrich

9


29.10.1999

Erstes Beispiel (Forts.)Erstes Beispiel (Forts.)

• Randbedingungen:– Schlüsselwörter/Interpunktion: s. Liste

• Schlüsselwörter sind reserviert und dürfen nicht als Bezeichner verwendet werden.

– Operatoren: s. Liste

(= Zeichenfolgen mit vordefinierter Bedeutung)

10


29.10.1999

Schlüsselwörter in C++Schlüsselwörter in C++

Die folgenden Schlüsselwörter sind in C++ reserviert und dürfen nicht anderweitig (z. B. als Bezeichner) benutzt werden:

asm do inline short typeidauto double int signed typenamebool dynamic_cast long sizeof unionbreak else mutable static unsignedcase enum namespace static_cast usingcatch explicit new struct virtualchar extern operator switch voidclass false private template volatileconst float protected ´ this wchar_tconst_cast for public throw whilecontinue friend register truedefault goto reinterpret_cast trydelete if return typedef main

Eine Art abgekürzter Schlüsselwörter sind die Interpunktionszeichen von C++: ; { } , ( ) < > : ... = \ ´ "

11


29.10.1999

Operatoren in C++Operatoren in C++

In C++ steht eine Vielzahl von Operatoren zur Verfügung - das sind Symbole, die verschiedene Operationen auf ihren Argumenten, den sog. Operanden, ausführen:

! % ^ & * () + = | ~

[] < > ?: / ¸ · > ++ ·*

>* << >> <= >= == != && || *= /=

%= += = <<= >>= &= ^= |= ::

12


29.10.1999

• Header-Dateien: – dienen dazu, an anderer Stelle definierte Bezeichner

bekannt zu machen (z. B. ist cout in der Datei iostream.h definiert).

– Der Kenner weiß: – #include <...> : die <Datei> ist in einem festen,

vordefinierten Verzeichnis zu finden– #include " ... " : die <Datei> wird zunächst im

aktuellen Verzeichnis, dann im o.g. vordefinierten Verzeichnis gesucht

• Was passiert eigentlich bei #include ?

Erstes Beispiel (Forts.)Erstes Beispiel (Forts.)

13


29.10.1999

Elementare DatentypenElementare Datentypen

• C++ hat fest eingebaute Datentypen, aus denen alle anderen zusammengesetzt werden können. Vordefiniert sind – der Typ void– arithmetische Typen

• ganzzahlige Typen : short int, int, long int, char

• Gleitpunkttypen: float, double, long double

• „Kleinster“ Typ ist char, stellt die Zeichen des Zeichensatzes dar (meist ASCII)

14


29.10.1999

Elementare Datentypen (Forts.)Elementare Datentypen (Forts.)

• Standardfunktion sizeof gibt für jeden Typ seine Größe (als Vielfaches der Größe von char) an. Es gilt stets :

1 = sizeof(char)

sizeof(short int) sizeof(int) sizeof(long int)

Prog-2

15


29.10.1999

Elementare Datentypen (Forts.)Elementare Datentypen (Forts.)

• Eingebaut sind für ganzzahlige Typen und für Gleitpunkttypen Konstanten, die jeweils die größte und kleinste darstellbare Zahl angeben:

• Beispiel:

• Beachte: #include <limits.h>

#include <float.h>

Prog-3

16


29.10.1999

• unsigned char vs. signed char• unsigned short int vs. signed short int

• unsigned int vs. signed int• unsigned long int vs. signed long int• Unsigned:

– Wertebereich beginnt bei 0– doppelt so große Obergrenze wie entsprechender signed-Typ

– ohne Angaben: vorzeichenbehaftete (also signed) Version

Prog-2A

• Bei ganzzahligen Typen: Bei ganzzahligen Typen: Variante Variante unsigned/signedunsigned/signed, also:, also:

17


29.10.1999

unsigned unsigned (Forts.)/ (Forts.)/ floatfloat

• Es gilt:sizeof (T) = sizeof (unsigned T)

= sizeof (signed T)

• Behandlung ziemlich maschinenabhängig

18


29.10.1999

Datentyp voidDatentyp void

• Datentyp void: – hat leere Wertemenge – also gibt es keine Variablen vom Typ void!

• Dennoch nützlich zur: – Beschreibung von Funktionen, die keinen Wert

zurückgeben.

19


29.10.1999

Anmerkungen zum Thema Anmerkungen zum Thema VariablenVariablen

• char xlegt fest, daß der Wert von x ein Zeichen ist.

• Technisch: im Speicher wird für x eine Speicherzelle reserviert, und es wird vermerkt, daß diese Speicherzelle nur Daten von Typ char aufnehmen darf .

• die Zuweisung: x = 'a' bewirkt, daß dieser Wert in der Speicherzelle für x gespeichert wird.

20


29.10.1999

VariablenVariablen (Forts.) (Forts.)

hier wird ein Datum

vom Typ chargespeichert

die Vereinbarungchar xbewirkt:

x

Reservierung einerSpeicherzelle

die Zuweisung x = 'a' bewirkt

a

21


29.10.1999

VariablenVariablen (Forts.) (Forts.)

'a'y

hier wird ein Datum


...

x

hier wird ein Datum


...

char x, y;

x = 'a'; y = x; hat als Wirkung:

a

a

22


29.10.1999

Einführung in die Verwendung von Einführung in die Verwendung von GrammatikenGrammatiken

• Ziel: Beschreibung von (Teilen von) syntaktisch korrekten C++-Programmen (über [speziell dargestellte] kontextfreie Grammatiken).

Konkreter:

Sie sollten lernen, die im „Ellis-Stroustrup“ in Kap. 17 beschriebene Grammatik am Ende der Veranstaltung lesen und für Ihre Zwecke verwenden zu können.

23


29.10.1999

Einführung in die Beschreibung Einführung in die Beschreibung mittels (kontextfreier) Grammatikenmittels (kontextfreier) Grammatiken

• Zu obigem Ziel nötig:– Sei A = {a1, a2, ....., an} eine endliche Menge von

Zeichen (Alphabet).• Beispiel: A1:= {0,1,2}

• Vorsicht: Zeichen eines Alphabets können selbst zusammengesetzt sein!

– Sei A* die Menge aller endlichen Wörter über dem Alphabet A.

• Am Beispiel: A1* := {0, 1, 2, 00, 01, 02, 10, ...., 000, 001, 002,..., 100, .., 0000,..}

24


29.10.1999

Einführung in ...... GrammatikenEinführung in ...... Grammatiken

– Das Hintereinanderhängen von Zeichen wird häufig -wie auch hier- ohne ein explizites Operatorzeichen, also allein durch das Hintereinanderschreiben von links nach rechts ausgedrückt.

– Länge eines Wortes aus A*: Anzahl der vorhan-denen Zeichen/Buchstaben unter Berücksichtigung der Vielfachheit des Vorkommens.

– Man nimmt auch das sog. "leere" Wort der Länge 0, z. B häufig bezeichnet durch , hinzu!

25


29.10.1999


• Aufgabe: – Zu einem gegebenen Alphabet A (Menge von

Zeichen) beschreibe eine geeignete Teilmenge von A* in möglichst kompakter Form.

– Beispiel:

Sei T(A1*): Menge aller Wörter, die mit einer 1 beginnen und einer 1 enden, sonst aber keine 1 mehr aufweisen. Kompakte Darstellung?

– (Übung: Darstellung über [speziell dargestellte] kontextfreie Grammatik).

26


29.10.1999


• Eine Lösung: – Je eine (kontextfreie) Grammatik G beschreibt eine

ausgezeichnete Teilmenge der Menge aller Zeichenketten über einem gegebenen Alphabet (den Terminalzeichen T). Dies geschieht durch einen Erzeugungsprozeß. Die durch diesen Erzeugungs-prozeß eindeutig festgelegte Teilmenge von T* heißt "Sprache" von G.

27


29.10.1999


• Darstellung der Grammatik: – Als 4-Tupel (N, T, P, S) aus

• endlicher Menge von Nichtterminalzeichen (N),

• endlicher Menge von Terminalzeichen (T),

• endlicher Menge von Produktionen/Regeln (P) und

• Startsymbol (S).– (Meist nur explizite Angabe der Produktionen.)

• Hilfsgrößen: • (sog. Nichtterminale) hier notiert durch Bezeichner. Stellen

"Zwischengrößen" dar, die durch weitere Anwendung von Regeln (im Endeffekt) in Wörter über Terminalzeichen überführt werden. Wie? Vgl. unten.

28


29.10.1999


• Regeln (Produktionen): [Darstellung angepaßt an Ellis-Stroustrup, Kap. 17]

– Allgemeiner Aufbau einer Regel

Linke Seite :

Rechte Seite

• Linke Seite wird durch genau ein Nichtterminal-zeichen gebildet.

• Beispiel: Bezeichner1

• Rechte Seite: i. a. Wort über (N T),

d.h. (N T)*.– [Später werden zusätzliche Sonderzeichen erlaubt, s.u.]

29


29.10.1999


• Eine Regel – beschreibt die Überführung von Nichtterminalzeichen

(dargestellt auf der linken Seite :) in Wörter aus Terminal- und/oder Nichtterminalzeichen.

• Startsymbol: – stellt das Nichtterminalzeichen dar, von dem aus sog.

Ableitungen gestartet werden.

Zu Ableitungen später nach Einführung eines Beispiels.

• Kommentare – wollen wir (u.a.) durch /*... */ notieren.

30


29.10.1999


• Beispiel: – Grammatik für zulässige Namen (nach der

Namenskonvention von C++ (eingeschränkt))

• Menge der Terminalzeichen = {a,..., z, A,..., Z, 0,...,9, _}

• Menge der Nichtterminalzeichen: {NameDcl, Buchstabe, RestNameOpt, RestName, Ziffer}[Nichtterminalzeichen werden also kursiv dargestellt.

Vorsicht: Nichtterminal"zeichen" können also selbst aus mehreren Zeichen bestehen !]

31


29.10.1999


• Beispiele für Regeln (in dieser Beispielgrammatik): • Buchstabe : Diese drei Regeln werden

a zusammengefaßt zu:• Buchstabe : Buchstabe :

b a• Buchstabe : b

c c

oder auch: Buchstabe : one of

a | b | c

32


29.10.1999

Einführung in ...... Grammatiken Einführung in ...... Grammatiken

RestName :

Buchstabe RestName

• RestName wird abgeleitet zu Buchstabe, gefolgt von RestName.

• bedeutet:

33


29.10.1999

Einführung in ...... GrammatikenEinführung in ...... Grammatiken1 NameDcl :

Buchstabe RestNameOpt

2 Buchstabe : one of

A | ... | Z | a | ... | z| _

3 RestNameOpt : one of RestName | /* ist "leeres Wort" */

4 RestName :

Buchstabe | Ziffer

Buchstabe RestName

Ziffer RestName

5 Ziffer : one of 0|... |9

34


29.10.1999


• Startsymbol: NameDcl

• Beispiele von Ableitungen (immer Start mit NameDcl ) :

• Abgeleitet: Verwendete Regel:• 1. NameDcl /*NameDcl :Buchstabe RestNameOpt

*/

Buchstabe RestNameOpt /*Buchstabe: A|.... */

A RestNameOpt /*RestNameOpt :RestName | */

A /*A T*; A ist durch diese Grammatik

ableitbarer Bezeichner */

35


29.10.1999


• 2. NameDcl /* NameDcl : Buchstabe RestNameOpt*/

Buchstabe RestNameOpt /*Buchstabe : a |...|z |A |... |Z|_*/

N RestNameOpt /*RestNameOpt : RestName| */

N RestName /*RestName :.. |Buchstabe RestName|..*/

N Buchstabe RestName /*Buchstabe : a |...|z |A |... |Z|_*/

Nr RestName /*RestName :.. |Buchstabe RestName|..*/

Nr Buchstabe RestName /*Buchstabe : a |...|z |A |... |Z|_*/

Nr_RestName /*RestName :.. | Ziffer RestName */

Nr_Ziffer RestName /*RestName :.. | Ziffer RestName */

Nr_ Ziffer Ziffer RestName /* RestName : .. |Ziffer|...*/

Nr_ Ziffer Ziffer Ziffer /* Ziffer : 0 |... |9*/

Nr_ Ziffer 0 Ziffer /* Ziffer :0 |... |9*/

Nr_Ziffer 07 /*Ziffer :0 |... |9*/

Nr_007 /* abgeleiteter Bezeichner, da nur noch Terminale !*/

36


29.10.1999


• Man spricht von der Ableitung eines Wortes

w = t1 ...tn (ti Terminalzeichen (!!) für i = 1, ..., n; n0), wenn sich w aus dem Startsymbol durch endlich viele Anwendungen von Regeln der Grammatik (, d.h. jeweils durch lokales Ersetzen von Nichtterminalzeichen auf der linken Seite durch (evtl. Teile) einer Zeile der rechten Seite einer Regel) erzeugen läßt.

37


29.10.1999


• Die durch eine Grammatik G erzeugte Wortmenge: Menge aller Wörter (allein) aus Terminalzeichen, zu

denen Ableitungen in G existieren.

• Übung: Sind ‘Variable1’, ‘1.Variable’, ‘1_Variable’, ‘Variable_1’

ableitbare Namen gemäß obiger Grammatik?

38


29.10.1999

Regeln in Stroustrup-GrammatikRegeln in Stroustrup-Grammatik

• /*Expressions, kleiner Auszug aus der Gesamtgramma-tik von C++, vgl. Stroustrup, Kap.17.2*/

expression: additive-expression

more

additive-expression: multiplicative-expression

additive-expression + multiplicative-expression

additive-expression - multiplicative-expression

multiplicative-expression: primary-expression

multiplicative-expression * primary-expression

multiplicative-expression / primary-expression

multiplicative-expression % primary-expression

39


29.10.1999

Regeln in Stroustrup-GrammatikRegeln in Stroustrup-Grammatik

primary-expression: literal

more

( expression )

name

name: identifier

more

literal: integer-constant

character-constant

floating-constant

string-literal

40


29.10.1999

Ableitung in Stroustrup-GrammatikAbleitung in Stroustrup-Grammatik

• Frage: Ist "( x +5 )" ein Ausdruck (Expression) ?• Ableitung: expression /*expression: additive-expression*/

additive-expression /*additive-expression:multiplicative-expression*/

multiplicative-expression

/*multiplicative-expression: primary-expression*/

primary-expression /* primary-expression: ( expression )*/

( expression ) /*expression: additive-expression*/

( additive-expression )

/*additive-expression: additive-expression + multiplicative-expression*/

41


29.10.1999

Ableitung in Stroustrup-GrammatikAbleitung in Stroustrup-Grammatik

( additive-expression + multiplicative-expression )

/* additive-expression: multiplicative-expression*/

( multiplicative-expression + multiplicative-expression )

/*multiplicative-expression: primary-expression*/ 2X

( primary-expression + primary-expression )

/*primary-expression: literal |name*/ 2X

( name + literal ) /* name: identifier */

( x + literal ) /* literal: integer-constant */

( x + 5 ) /*Hurra !!!*/

Documents

EINI-I Einführung in die Informatik für Naturwissenschaftler und Ingenieure I Kapitel 1 Gisbert Dittrich; Claudio Moraga FBI Unido [email protected]