Download Referat (ca. 250KB)!

Viel Spaß!!

Werbung

Theoretische Informatik

1. Einführung
2. Wierholung Maschinensprache und "PROSI"
3. Endliche Automaten, Compiler, Parser, Programmiersprachen
1. Mittel und Wege der Darstellung
2. Endliche Automaten
3. Formale Sprachen
4. Scanner
5. Parser
6. Compiler
7. Programmiersprachen /Erklärungen zu AOC
8. Programmbeispiele in Pascal
4. Schlußwort

Die theoretische Informatik stellt heutzutage eine wichtige Grundlage in der Informatik dar und findet in vielen Bereichen wichtige Anwendungen. So muß man sich z.B. bevor man einen Capuccinoautomaten baut, auch darüber Gedanken machen, wie dessen Schaltlogik aussieht. Dabei gibt es zahlreiche Wege, um sich an das Gebiet heranzunähern, denn für solche simple Probleme eine Logik zu entwickeln, scheint zwar vordergründig banal, es ist aber ein komplizierter Prozeß, der unter den heute zum Alltag gehörenden Maschinen da abläuft.

Zum anderen gibt uns dieses Teilgebiet der Informatik tiefere Einblicke in die Funktionsweise von Programmiersprachen. Anhand von Compilersimlationsprogrammen wird einem leicht klar, daß ein Programm zuerst mehrfach umgeschrieben werden muß, bevor es vom eigentlichen PC gelesen und ausgeführt werden kann. So, jetzt soll den weiteren Ausführungen nichts mehr im Wege stehen, so daß wir uns mit diesem Gebiet auseinandersetzen können....

Maschinensprache :

Darunter versteht man eine Objektsprache bzw. eine Programmiersprache, die nur Binärzahlen verwendet und deren Befehle (Maschinencode) daher von der Zentraleinheit eines bestimmten Computers direkt verstanden werden. Es ist sehr schwierig, ein fehlerfreies Programm in Maschinensprache zu schreiben, daher werden meist andere Programmiersprachen verwendet und diese dann in Maschinensprache übersetzt. Diese Aufgabe übernimmt ein Compiler – ein Hilfsprogramm, das ein in einer höheren Programmiersprache geschriebenes Programm in ein Programm in Maschinensprache übersetzt, die der Rechner dann direkt versteht (siehe weiter unten !). Ein Interpreter kann diese Aufgabe während des Programmablaufs durchführen, wodurch zwar langsamer, ein dialogorientiertes, interaktives Arbeiten erst möglich wird.

Der Modellprozessor :

Mit Hilfe dieses Prozessors werden Programmeingabe, -Speicherung und –ablauf auf dem Bildschirm veranschaulicht. Der Prozessor wird auf einem "IBM-kompatiblen Personal Computer durch das Programm "Prosi" emuliert. Der große Vorteil einer solchen Emulation liegt vor allem darin, daß alle Arbeitsabläufe auf dem Bildschirm simultan verfolgt werden können; katastrophale Fehler werden abgefangen und kommentiert; ein Absturz des Systems in jedem Falle vermieden. Dem Lernenden wird der Einstieg in die Welt des Mikroprozessors auch dadurch wesentlich erleichtert, daß sich der Befehlssatz einerseits auf die wesentlichen Befehle von Prozessoren beschränkt, andererseits aber so mächtig und an den realen Prozessoren orientiert ist, daß keine Abstriche an der Spannbreite der bearbeitbaren Probleme erforderlich sind. Die von den PROSI benutzten mnemotechnischen Codes (s.u.) sind mit denen der Intel-Prozessoren Intel 8088 bzw. 80?86 identisch; Prosi-programme können daher mit geringfügigen Änderungen bzw. Zusätzen auf den genannten Prozessoren zum Laufen gebracht werden. Der Modellprozessor arbeitet mit einem 32kByte Speicher, d.h. zur Speicherung der Daten stehen 32268_10 Bytes (= 32*1024 Byte) mit den Hexadezimaladressen (Nummern) 0000 bis 8000 zur Verfügung. Datenworte sind grundsätzlich 2Byte lang : Ihr dezimaler Wert liegt also stets zwischen 0 und 65535 (dual) bzw. zwischen –32768 und +32767 (konegativ).

Zur Erläuterung : 32kByte Speicher = 2^15Byte = 32268 Byte

2^15 = 2^(3+12) = 2^3*16^3 = 8000_16

Die Speicheradressierung orientiert sich bei den Intelprozessoren an den ehemals 16-Bit Leitungen, d.h. man muß den Speicher in Segmente aufteilen à 64kByte (2^8 Byte).

Die Minimalzahl der Adressleitungen ist 20 und 2^20 = 1MB, d.h. der Minimalspeicher kann über 16 Segmente angesprungen werden.

Aufteilung :

• 10 Segmente (640K) sind davon frei für Programme (inkl. Teile des Betriebsystems).
• Die oberen Segmente (384K) werden zur Peripheriesteuerung des Computers benötigt, z.B. BIOS (Basic Input and Output System), ferige programme für Eingabe und Ausgabe usw.

• Kurze Programme gehen in ein einziges Segment rein und sind daher sehr zuverlässig. Daten dieser Programme können selbstverständlich in anderen Segmenten abgespeichert werden. Diese Programme haben als Endung ".com".
• Größere Programme müssen in mehreren Segmenten untergebracht werden und benötigen daher zusätzlich einen Steuermechanismus zur Ansteuerung der einzelnen Segmente. Sie haben die Endung ".exe".

Mit dem mit DOS mitgelieferten Programm DEBUG kann man Assemblerprogramme des Typs ".com" herstellen und bearbeiten.

Unser Problem besteht darin, daß wir die Funktionsweise von Automaten, in unserem Fall von einem Getränkeautomaten verstehen wollen.

Hierzu zunächst eine kurze Legende, die es ermöglicht, die folgenden Darstellungen besser zu verstehen:

Knoten

Zielknoten

Kante

Mit diesen wenigen Symbolen lassen sich ohne weiteres für jedes Problem in diesem Bereich Diagramme herstellen: Man spricht dann von einem gerichteten Graphen. Dies ist die eine Möglichkeit.

Man kann aber auch Tabellen erstellen, die man dann als Automatentafeln bezeichnet.

Zudem kann man das Problem über ein Pascalprogramm lösen.

Schließlich gibt es noch die Möglichkeit, für jenen Zweck eine Maschine zu konstruieren.

Dies ist dann ein mechaniches ggf. auch ein elektr./mechanisches System.

Den Übergang von einem Zustand zum anderen beschreibt dann eine sogenannte Übergangsfunktion. Schließlich gibt es noch eine Ausgabefunktion.

Ein Automat besitzt innere Zustände und befindet sich immer genau in einem Zustand. Zu Beginn im Anfangszustand, am Schluß im Zielzustand. Durch äußere Eingaben kann er von einem in den anderen Zustand gebracht werden. Solch einen Automaten kann man in einer Tabelle oder in einem gerichteten Graphen darstellen. Solch ein Automat besitzt auch eine Eingabe-, Ausgabe- und Zustandsmenge.

Bsp. 1: ein Getränkeautomat

Er nimmt 50 Pf und Einmarkstücke an.

Eingabemenge E = { 50Pf, 1Dm, Korrekturtaste, Warenhebel }

Ausgabemenge A = { %, Ware, Rückgabe von 50pf, Rückgabe 1Dm, Rückgabe 1.50Dm }

Zustandsmenge Z = { % eingeworfen, 50 Pf eingeworfen, 1Dm eingeworfen, 1.50Dm eing.}

Gerichteter Graph:

Automatentafel:

 
 

	Nichts	50Pfg	1 DM	1,5
50Pfg	0,5	1 DM	1.50DM	Zurück 0,50
1 DM	1 DM	1.50DM	Zurück 1DM	Zurück 1DM
Ware	/	/	/	Ware
Korr.	/	0,5	1 DM	1,5

 

Bsp. 2: derselbe Getränkeautomat, aber mit Geldrückgabe.

 
 

	Nichts	50Pfg	1 DM	1,50 DM	2 DM
50Pfg	0,5	1 DM	1,5	2 DM	Zurück 0,50
1 DM	1 DM	1,5	2 DM	Zurück 1DM	Zurück 1DM
Ware	/	/	/	Ware	Ware + 0,5
Korr.	/	0,5	1 DM	1,5	2 DM

 

In 3.8 gibt‘s noch ein Programm in Pascal, das das Problem ebensogut lösen kann:

Bsp. 3: ein Getränkeautomat, der 2 verschiedene Waren zu je 50 Pf. und einer Mark ausgibt.

Anmerkung:

Es gibt auch Automaten, die keine Ausgabe haben. Man nennt diese Akzeptoren. Sie haben statt des Zielzustands einen Endzustand.

Bsp.: Tresorschloß, Endzustand ist "offen".

Bestimme die akzeptierten Worte:

Lösung: a, bba, baba, bbb, baaaa, baaba, baaab, baabb, babb

Die Grammatik formaler Sprachen:

Eine formale Sprache muß eine Grammatik haben.

Diese besteht aus der Menge der nichtterminalen Symbolen (N), der Menge der terminalen Symbolen (T), dem Regelsystem (R).

Bsp.: Nichtterminale Symbole (N):

Program, Anweisung, Zahl, Wort

Startsymbol in Pascal wäre ‚Program‘.

Bsp.: Terminale Symbole (T):

Load, Store, Halt, Add, 0, 1...

Reguläre Sprachen:

Hier können nur lineare Symbolfolgen aufgebaut werden.

Kontextfreie Sprachen:

Sprachen mit Klammwerstruktur (z.B. Computersprachen); es wird ersetzt, ohne auf den Zusammenhang zu achten.

Allgemeine Regelsprachen:

Ersetzungsregeln hängen vom Kontext des Gesamtwortes ab.

Bsp.: Die folgende Grammatik beschreibt eine formale Sprache:

T = { Der_Bauer, der_Gärtner, er, sie, schneidet, rasiert, mäht, die_Wiese, die_Haare,

den_Pelz }

N = { Satz, Subjekt, Prädikat }

• 3 Möglichkeiten :
• Der Bauer schneidet den Pelz.
• Der Gärtner rasiert den Pelz.
• Sie mäht die Wiese.

Komplexität formaler Sprachen:

Bsp.: ineinander geschachtelte Klammern mit den Regeln für Klammerterme aus der

Mathematik.

T = { ( Produkt ) }

Wohlgeformte Worte:

((p)) oder (((p)(p)))

Die einfachsten kontextfreien Sprachen werden durch einen Kellerspeicher (Stapel, Stack) erweitert.

Anlegen einer Information: push

Abfragen der obersten Information: pop

• LIFO- Prinzip (Last-In-First_out)

Klammerschließen heißt also im Endeffekt, eine geöffnete Klammer vom Stapel abholen.

Auch hierzu gibt’s in 3.8 noch ein PASCAL-Beispiel.

Begriffsklärung: "to scan" (engl.) = abtasten

Def.: Darunter versteht man einen Programmteil, der die einzelnen Zeichen des Quellcodes zu

Begriffsklärung: "to parse" = einen Satz grammatikalisch zergliedern, bestimmen (engl.)

Def.: Einen Parser bezeichnet man demnach als einen Programmteil, der zunächst überprüft, ob die vom Scanner (Def. Siehe unten) abgeliefertem Symbole in syntaktisch korrektem Zusammenhang stehen, Methode des rekursiven Abstiegs in die Syntaxprozeduren. Scanner und Parser werden durch Prozeduren zur Erstellung der Symboltabelle und zur AOC-Code-Generierung zu einem vollständigen Compiler ausgebaut.

Zu einem Parser gehört:

• Die Eingabemenge eines Akzeptors ( sie wird Alphabet genannt ).
• Eine endliche Folge aus Zeichen des Alphabets ( eine solche Folge heißt Wort über dem Alphabet ).
• Die Worte, die einen Akzeptor vom Anfangszustand in den Endzustand überführen ( = akzeptierte Worte ).
• Die Menge aller akzeptierten Worte ( Sprache des Akzeptors ).

Bsp.: Pascal

1. Das Alphabet: Zeichen vom Typ Char und zwar Groß- und Kleinbuchstaben in Englisch und einige Sonderzeichen.
2. Ein Wort über dem Alphabet: Ein Wort darf maximal 255 Zeichen haben, also jede Zeichenfolge, die diese Bedingung erfüllt.
3. Ein akzeptiertes Wort: Ein Wort, das den Pascalparther vom Zustand "neutral" in "correct" überführt ( begin, while, end ).
4. Die Sprache des Akzeptors: Die Menge aller korrekt gebildeten Bezeichner (Kunstsprache: endliche Menge ).

Syntaxdiagramm Pascal:

Gerichteter Graph Pascal:

Struktur eines Compilers:

Quellprogramm

Objektprogramm

( 3.6 Compiler )

Man bezeichnet ihn auch als Übersetzer.

Es wird grundsätzlich ein Quellprogramm in ein Objekt oder in ein Zielporogramm übersetzt.

Ein Programm, welches die Quellsprache ausführt, ohne ein Objektprogramm zu erzeugen, nennt man einen Interpreter.

Bsp.: Basic, CAS-Programme,...

Zusammenfassend kann man sagen:

• Man braucht einen Scanner für die lexikalische Analyse.
• Man braucht einen Parser für die Syntaxanalyse.
• Man braucht eine Symboltabelle, in der Typ und Sorte für Bezeichner aufgeführt sind. Es dürfen Bezeichner nicht zweimal verwendet werden.

PASCAL: Definition der Variablen, TYPE

Werdegang / Entstehung des fertigen Programms:

Bei der Umwandlung eines Programms vom Quellprogramm ins Objektprogramm wird ein Zwischencode oder auch Pseudo-Code ( hier der AOC-Code ) benutzt. Die Abkürzung LAN steht als Namenserweiterung für den Begriff Language und bildet die Ausgangssituation für ein AOC-Programm, wobei man sagen muß, daß solche Quellprogramme mit einem DOS-Editor oder auch mit TP geschrieben werden können. Die Abkürzung AOC steht für AlgoObjectCode.

Desweiteren sind die Abkürzungen SP (Stackpointer), als Zeiger auf das oberste Element des Kellerspeichers, und PC (PROGRAM Counter), als Zeiger auf den aktuellen AOC_befehl, bedeutsam.

Ein Beispiel für eine formale Sprache wäre die Programmiersprache LAN. Ihr Zeichenumfang besteht aus der Menge aller Kleinbuchstaben , aus der Menge der Dezimalziffern (DIGIT) und aus den Sonderzeichen (SPECIAL), wie z.B. die Klammern , die Zeichen ><, :, ;, und einigen mathematischen Symbolen.

Da die Sprache praktisch als ein gekürztes PASCAL aufgefaßt werden kann, finden wir hier große Übereinstimmungen zwischen den beiden formalen Sprache, wie z.B. eine ähnliche Syntax und ein ähnlicher Programmaufbau. Das Programm wird mit einem "Begin" angefangen, dem folgt ein Deklarations- und Variablenteil und ein Pascal-ähnlicher Anweisungsbereich, bei dem die Begriffe READ, WRITE, ELSE, WHILE genau wie in Pascal verwendet werden können. Der wichtigste Unterschied sei darin zu sehen, daß man in LAN die Schleifen, die mit IF oder DO eingeleitet werden, mit den Gegenwörtern FI und OD wieder Schließen muß. Das Programm schließt mit einem end, worauf noch evtl. ein Klammeraffe (@) folgen könnte.

Das Quellprogramm wird in eine Befehlsfolge umgewandelt, und hierbei ist nun der Kellerspeicher und dessen Funktionsweise bedeutsam:

Beim Kellerspeicher wird auf das i-te Register mit der Variable Store [i] vom Typ Integer verwendet. Der Stackpointer zeigt stets auf das oberste Element dieses Speichers.

Merke!!!

Der Stack läuft von oben nach unten.

Wie einige dieser Instruktionen aus dem Pseudo-Code aussehen, kann man sehr gut im Anhang sehen (à Listing Seite 4).

Im nächsten Schritt wird dann der neu erzeugte Pseudo-Code in die Maschinensprache umgeschrieben. Die Abkürzungen AX, BX, CX, DX, BP und SP stehen für die interner 16 Bit Register der Intel 80xx-Serie. SP steht für Stackpointer, BP ist Basepointer; er zeigt auf den entsprechenden Stack.

Man sollte bedenken, daß der Stack der Intel 80xx vonm Speicheranfang in Richtung Speicherende wächst, wobei sich dementsprechend der SP um 2 (2Byte) erniedrigt, wenn der AOC-Stapel um 1 (ein Integer) wächst. In BP wird der Stand des SP zu Beginn der Abarbeitung des Maschinencodes eingefroren: damit ist der Anfang des für die Maschinenroutine nutzbaren Stacks (AOC-Keller) festgelegt.

Auch die Aufzählung einiger wichtiger Codes der Maschinensprache ist aus dem dem Anhang beigefügten Listing (ab Seite 7) ersichtlich. Desweiteren wäre da die Ausarbeitung aus 12/2 empfehlenswert.

Anhand der nachfolgenden Beispielprogramme, die in LAN geschrieben sind, wird klar, wie sehr diese Sprache PASCAL ähnelt und es wird gezeigt, mit welch recht simplen Methoden man einfache Probleme bearbeiten kann. Das sSchöne dabei ist, daß man anhand der AOC-Simulationen noch die Schritte des PCs nachvollziehen kann, bevor er die Programme ausführt.

Bsp.: Programm zur Multiplikation mit einer Konstanten

begin "Multi000.LAN"

const pi=3;

var x;

x:= 10;

x:= 3*pi*x;

write x

end@

Bsp.: Programm, um Wurzel einer Zahl zu ziehen

Begin "Heron Wurzel.lan"

Const x0=181; "Startwert"

Var radikand;

Var x1; "Näherungswert"

Var x2; "verbesserter Wert"

Var d; "Differenz abs(x2-x1)"

Read radikand;

x1:=x0;

d:=2;

While d>1 Do

x2:= (radikand/x1+x1)/2;

d:= x2-x1;

if d<0 then d:=-d fi;

x1:=x2

od;

write x2; write –x2

end@

Ein AOC_Programm, das aus solch einem LAN-Programm erstellt werden soll, ist eine Folge von AOC-Befehlen und Labeldefinitionen. In jeder Zeile steht genau ein AOC-Befehl bzw. eine LABELdefiniton. Ein solcher Befehl besteht aus mindestens einer Leerstelle , einem AOC-Mnemocode , mindestens einer Leerstelle und einem Parameter. Ein solcher Parameter kann entweder eine ganze Zahl oder ein Label sein, d.h. eine mit einer Zahl markierten Stelle im Programm , zu der gesprungen werden kann. Labels beschreibt man mit einem L und einer darauf folgenden max. dreistelligen Zahl.

Für die Übersetzung linearer Programme gilt folgendes : Die Konstantenwerte werden in der Reihenfolge ihrer Deklarationen in den Speicher abgelegt und anschließend wird mit INCs n die Anzahl n der Datenspeicheradressen der danach deklarierten Variablen reserviert, Eingaben erolgen durch die Befehlskette LC C, READ, ST, Ausgaben durch LC C, CONT, PRINT, wobei Zuweisungen durch LC C, die entsprechende Variablendefinition und ST ausgedrückt werden.

Ausdrücke werden wie folgt berechnet: Bei Faktoren werden diese, wenn sie eine Zahl darstellen, mit LC <Wert> auf den Keller geschrieben. Sind es jedoch Bezeichner, so wird ihr Wert mit LC <Nummer> und CONT auf den Stapel gesetzt und im Falle eines ganzen Ausdrucks wird die entsprechende Befehlsfolge erzeugt. Bei Termen muß man zwischen einzelnen Faktoren differenzieren (Zerlegung in Zahl, Bezeichnung oder Ausdruck in Klammern). Bei den ersten Elementen wird der Befehl MULT angewendet. Bei ganzen Ausdrücken, also einzelnen Termen oder Summen, werden zunächst die beiden ersten Summanten ausgewertet und anschließend mit ADD weitergeführt.

Das "Wurzelprogramm" zeigt uns im Beispiel die Anwendung von Schleifen. Sie genügen prinzipiell der Form : while <boolescher Ausdruck> do, <Anweisungen>, od. Sobald der boolesche Ausdruck den Wert false erhält, wird zum Schleifenende gesprungen und solange die Anweisungsfolge noch TRUE ist, ergibt sich eine Endlosschleife.

Die Wirkung der einzelnen Befehle läßt sich sehr gut anhand von Kellertabellen, die man in den IN 13 Handreichungen im Anhang findet, verdeutlichen.

Die Codeerzeugung kann auch anhand von gerichteten Graphen bzw. Syntxgraphen hervorgehoben werden, was uns auch in der o. g. Quelle im Anhang dokumentiert wird.

Anmerkung : Im der AOC-Simulation zum Interpreter kann man sehr gut die Arbeit des Scanners nachvollziehen. Die gescannten Begriffe erhalten ein –s am Ende und können erst so witer verarbeitet werden.

(nicht enthalten in Online-Version)

• Pascal-Programm, um eine natürliche Zahl in Worten auszudrücken

• Simulation des Getränkeautomaten ( ohne Getränk !!! )

• Simulation eines Aufzugs

• Zufallsgedichte

• Klammercheck

• Readme.txt zu AOC-Simulationen ("Listing")

• Handreichungen IN 13

Natürlich war dieser Einblick in die theoretische Informatik nur oberflächlich, aber um wichtige Grundlagen zu vermitteln, die einer evtl. Vertiefung zu späterem Zeitpunkt nützlich sein können, bietet der Inhalt des Pamphlets sicher reichlich Anhaltspunkte. Alltagsübliche Maschinen werden heute immer komplexer und verbesserte Programmiersprachen sind ohnehin sehr stark nachgefragt. Insofern ist es also wichtig, daß man sich auch mit dieser Materie intensiv auseinandersetzt.

Bei diesem Dokument wurden folgende Quellen zur Hilfe genommen:

• Unterlagen Kurs Ziebert 13/1
• Unterlagen zu AOC-Programmen
• Handreichungen IN 13

Das Dokument wurde am PC erstellt. Folgende Programme dienten zur Realisierung:

• Microsoft Office, Word 97
• Microsoft Office, Excel 97
• Corel Draw 8.0

Viel Spaß beim Lesen !