SBI00643 Fachbezogene Fortbildung für
Fachberater im Fach Informatik an
Gymnasien
„Theoretische Informatik (TI) – Theoretische Grundlagen
von Programmiersprachen“ mit der Lernumgebung AtoCC
Sächsisches Bildungsinstitut, F+T-Zentrum Meißen
Christian Wagenknecht, Michael Hielscher Meißen, 09.04.-11.04.08
Das Wichtigste zuerst!
Vielen Dank an
Herrn Wolfgang Rafelt
Erster Kontakt: 25.05.07
2
Zeitplan und Ziele 3
Mittwoch, 09.04.08, 15:00-17:30: Einführung, Installation, ZR-Compiler (TDiag)
Donnerstag, 10.04.08, 09:00-10:30: Formale Grammatik für ZR inkl. Grundbegriffe (kfGEdit)11:00-12:30: DEA für Zahl und Farbwert (AutoEdit), reguläre Ausdrücke13:30-15:00: DKA für kfS (AutoEdit), Beispiel: WH n [...]15:15-17:30: Compiler = Analyse + Synthese (VCC)
Analyse: Scanner, Parser; Zielsprache: PS; TDiagramm
Freitag, 11.04.08,09:00-10:30: Projekt "Notensprache" – Quellsprache, Zielsprache,
Werkzeuge; Übersetzungsmodell, Grammatiken, reduzierte Gramm.11:00-12:30: DEA, reguläre Ausdrücke, Compiler, TDiag (Projektende)13:30-14:00: Turingmaschinen, Hinweis auf Automaten mit Ausgabe
(Mealy-, Moore-Automaten, nicht LP-Gegenstand)Ende des Kurses
Lehrplan Ziele und Inhalte
4
Nr. Bundesland Lehrplaninhalt (Lernbereich) Pflichtbestandteil
1 Baden-Württemberg Bereich der theoretischen Informatik (Automaten, Berechenbarkeit) nein
2 Bayern 3. Formale Sprachen (noch Entwurf) 3 Berlin 4.4 Sprachen und Automaten ja (auch GK)4 Brandenburg 4.4 Sprachen und Automaten Ja (auch GK)
5 Bremen Grundlagen der Theoretischen Informatik (Automaten, formale Sprachen) nein
6 Hamburg Formale Sprachen, endliche Automaten, Kellerautomaten, Scanner, Parser, Ableitungsbaum
nein
7 Hessen Formale Sprachen und Grammatiken Automaten, Fakultativ: Übersetzerbau ja (auch GK)
8 Mecklenburg-Vorpommern 4.4 Sprachen und Automaten ja (auch GK)
9 Niedersachsen Eigenschaften endlicher AutomatenAspekte formaler Sprachen nein
10 Nordrhein-Westfalen Endliche Automaten und formale Sprachen nein
11 Rheinland-Pfalz Formale Sprachen und Automaten zur Sprachbeschreibung und Spracherkennung ja (nur LK)
12 Saarland Automaten und formale Sprachen Fakultativ: Übersetzerbau ja (auch GK)
13 Sachsen 8 A: Formale Sprachen, Kellerautomat, Akzeptor nein 14 Sachsen-Anhalt Endliche Automaten und formale Sprachen nein 15 Schleswig-Holstein Automaten als mögliches Themengebiet nein16 Thüringen Themenbereich 7.3: Einblick in formale Sprachen nein
In den meisten Bundesländern sind ausgewählte Inhalte der TI Lehrplaninhalt der Sek. II:
Lehrplanauszug Hessen
Verbindliche Unterrichtsinhalte/Aufgaben: Formale Sprachen und Grammatiken
reguläre und kontextfreie Grammatiken und Sprachen Anwendung mit Syntaxdiagrammen Chomsky-Hierarchie (LK) kontextsensitive Sprachen (LK)
Endliche Automaten Zustand, Zustandsübergang, Zustandsdiagramm Zeichen, Akzeptor Simulation realer Automaten (z. B. Getränkeautomat) Anwendung endlicher Automaten (z. B. Scanner) deterministische und nicht-deterministische Automaten (LK) reguläre Ausdrücke (LK) Mensch-Maschine-Kommunikation (LK)
Kellerautomaten (LK, GK fakultativ)
Automat mit Kellerspeicher kontextfreie Grammatiken Klammerausdrücke, Rekursion
Turing- oder Registermaschine (LK, GK fakultativ)
Turing- oder registerberechenbar Churchsche These Computer als universelle symbolverarbeitende Maschine Verhältnis Mensch-Maschine
Fakultative Unterrichtsinhalte/Aufgaben: Übersetzerbau Scanner, Parser, Interpreter und Compiler
z. B. Steuersprache für Roboter, LOGO, Plotter oder miniPASCAL
5
Lernbereich 8 A (Sächs. Lehrplan)6
GK Informatik f. Jahrgangsstufen 11 und 12, wird ab Schuljahr 2008/09 wirksam
endlicher Automat
TI-Inhalte in der Schulinformatik:Probleme und Chancen
Blick in die Lehrpläne verschiedener Bundesländer• totale Überfrachtung mit Fachinhalten• Formulierung von Wunschvorstellungen (z.B. TI + Compiler)
(geringe didaktische Erfahrung)• Besondere Spezifik der TI (mathematische Denktechniken
vs. ingenieurwissenschaftlicher Arbeitskontext der SE) wird nicht ausreichend berücksichtigt
Inhalts/Zeit-Relation Verinnerlichung von Inhalten
Kompetenz und Motivation des Lehrpersonals
7
Gefühlssituation der Lehrenden
"TI wollte ich nie machen." "TI hat mich nie richtig interessiert." "TI war mir immer zu theoretisch und abstrakt." "Die TI-Dozenten waren suspekt – TI im
postgradualen Studium erinnere ich mit Grausen."
"Die TI-Inhalten helfen mir nicht, wenn das Schulnetzwerk mal wieder zusammenbricht."
...
8
TI-Inhalte in der Schulinformatik:Probleme und Chancen
Zeit-Problem, Inhalte-Problem (Zusammenfassung von oben)
Manche Lehrende mögen es nicht. – Motivationsproblem Manche Lehrende können es nicht richtig. -
Qualifikationsproblem SchülerInnen/Studierende fragen gelegentlich: "Wann geht es
denn nun endlich richtig los mit der Informatik? Ach so, das ist es schon." - Vermittlungsproblem
"Ergebnis": Wenn möglich, TI weglassen. FALSCH!!!
Chance: Informatik als Wissenschaft repräsentieren! (wie Mathematik und Naturwissenschaften)
Sonst: Studienabbrecher als konkrete Folge!!!
9
Didaktische Software für TI
in Schulen: diverse Simulationstools oder Lernumgebungen, wie Kara; meist von enthusiastischen LehrerInnen entwickelt
in Hochschulen: Systeme für die Lehre, wie JFLAP
LEX und YACC für die Hand des Ingenieurs
10
Simulationstool – Bildungsserver Hessen
Unsere Ziele – nicht ohne AtoCC!!!11
1. Belastbare Motivation für TI-Inhalte durch herausfordernde
Start-Fragestellung mit Praxisrelevanz und Modellierung
eines Zielsystems (Sprachübersetzer) am Anfang
2. Vermittlungs-/Anwendungszyklen für TI-Wissen mit Projekt-
bezug (Praxis nicht als "Anhängsel" zur Theorie)
3. Komplexe Anwendung von TI-Inhalten auf sehr hohem
Abstraktionsniveau (automatisierte Compiler-Generierung),
Rückkehr zur und Konkretisierung der Modellierungsebene
Behauptung: Dabei ist AtoCC ein unverzichtbares Hilfsmittel.
Beispiel: ZR – eine Sprache für einen Zeichenroboter
12
Praxisnahe (echte!) Aufgabe mit grafischer (akustischer) Ausgabe:Entwickeln Sie einen Compiler, der die Sprache ZR (ZeichenRoboter) in PDF übersetzt. (Schülergerecht formulieren!)
Eingabewort (in ZR): WH 36 [WH 4 [VW 100 RE 90] RE 10]
Sprachelemente:VW n VorWärts n SchritteRE n Rechts um n GradWH n [ ... ] WiehderHole n-mal [...]FARBE f StiftFARRBE fSTIFT n Strichstärke n
Aufgabe: Verwenden Sie den fertigen Compiler zr2pdf blume.zr (konsole.bat aufrufen, blume.zr ansehen)
Beispiel: ZR – eine Sprache für einen Zeichenroboter
13
Der Zeichenroboter kann auch mehr: BunteBlume.zr
Beispiel: ZR – eine Sprache für einen Zeichenroboter
14
Weiterer Ablauf:
1.Modellierung der Problemlösung mit TDiag
2.Syntax-Definition von ZR: formale Grammatik, Ableitungsbaum mit kfGEdit
3.Parser Akzeptoren Automatenmodelle (EA, KA) mit AutoEdit
4.Arbeitsteilung: Scanner, Parser
5.Zielsprachenbezug automatisierte Compiler-Entwicklung mit VCC
6.Teilsysteme werden in Modellierung eingebracht (TDiag)
7.Ergebnis: lauffähiger (nichttrivialer) Übersetzer, den man benutzen kann!
TDiag, kfGEdit, AutoEdit, und VCC sind Bestandteile von AtoCC.
Beispiel: ZR – eine Sprache für einen Zeichenroboter
Wir wollen zunächst den Übersetzungsprozess entwerfen modellieren
Verwendung von T-Diagrammen: T-Diagramme bestehen aus 4 Bausteintypen. Compilerbaustein, Programmbaustein,
Interpreterbaustein und Ein/Ausgabe-Baustein
15
Compiler Programm Interpreter Ein/Ausgabe an Programmbaustein
Beispiel: ZR – eine Sprache für einen Zeichenroboter
T-Diagramm: 1. Entwurf16
ZR2PDF möchte niemand schreiben!!!
Beispiel: ZR – eine Sprache für einen Zeichenroboter
T-Diagramm: 2. Entwurf17
ZR2PS werden wir entwickeln, PS2PDF und Acrobat Reader wird vom System bereitgestellt.
Beispiel: ZR – eine Sprache für einen Zeichenroboter
Nachdem wir nun wissen, wie unser Compiler später zur Übersetzung eingesetzt werden soll, wenden wir uns der Entwicklung des Compilers zu.
Sprache näher betrachten Terminale und Nichtterminale festlegen formale Grammatik definieren Ableitungsbäume erzeugen
18
Beispiel: ZR – eine Sprache für einen Zeichenroboter
Betrachten wir die Sprache ZR und versuchen wir ihren Aufbau zu beschreiben: VW 50 RE 270 RE 45 WH 2 [VW 100] WH 4 [VW 100 RE 100] WH 36 [WH 4 [VW 100 RE 90] RE 10]
Magnetkarten an der Tafel
19
Beispiel: ZR – eine Sprache für einen Zeichenroboter
Beschreiben wir den Baustein Zahl genauer: 0 soll in ZR keine Zahl sein, da VW 0 oder RE 0
keine Veränderung herbeiführen. Vorangestellte Nullen, wie bei 0815, wollen wir
auch nicht erlauben. Ergänzen wir unsere Grammatik um:
Zahl ErsteZiffer ZiffernZiffern Ziffer Ziffern | Ziffer 0 | 1 | ... | 9 ErsteZiffer 1 | 2 | ... | 9
20
Beispiel: ZR – eine Sprache für einen Zeichenroboter
21
Beispiel: ZR – eine Sprache für einen Zeichenroboter
22
Beispiel: ZR – eine Sprache für einen Zeichenroboter
23
Beispiel: ZR – eine Sprache für einen Zeichenroboter
Programm Anweisungen Anweisungen Anweisung Anweisungen | EPSILONAnweisung VW Zahl | RE Zahl | WH Zahl [ Anweisungen ] | FARBE Farbwert | STIFT ZahlFarbwert rot | blau | gruen | gelb | schwarzZahl ErsteZiffer ZiffernZiffern Ziffer Ziffern | EPSILONZiffer 0 | 1 | ... | 9 ErsteZiffer 1 | 2 | ... | 9
24
Kontextfreie Grammatik
25
Hervorzuhebendes Problem bei kfG: Mehrdeutigkeit;Eingabewort: if a1 then if a2 then s1 else s2
S -> if E then S | if E then S else S | s1 | s2E -> a1 | a2
kfG, d.h. Regeln haben die Gestalt X b, mit |x| |b| Hinweis auf Chomsky-Hierarchie (s. TI-Vorlesungen);
Grammatik-Transformationen in Betracht ziehen
Grammatikdefinitionen immer vollständig angeben! G=(N,T,P,s)
Dangling else
Lösung:S -> S1 | S2S1 -> if E then S1 else S1 | s1 | s2S2 -> if E then S | if E then S1 else S2E -> a1 | a2
Beispiel: ZR – eine Sprache für einen Zeichenroboter
Automaten als Akzeptoren für Sprachen Akzeptor prüft, ob ein Wort zur Sprache gehört oder
nicht. (Keine Ausgabe Wort akzeptiert) (Thema: Programmiersprachen und Syntaxfehler)
Wir nehmen zwei Ausschnitte aus den Produktionen:Zahl ErsteZiffer ZiffernZiffern Ziffer Ziffern | EPSILONZiffer 0 | 1 | ... | 9 ErsteZiffer 1 | 2 | ... | 9
Anweisungen Anweisung Anweisungen | EPSILONAnweisung VW Zahl | WH Zahl [ Anweisungen ]
26
Beispiel: ZR – eine Sprache für einen Zeichenroboter
Kleiner Sprachausschnitt:Zahl ErsteZiffer ZiffernZiffern Ziffer Ziffern | EPSILONZiffer 0 | 1 | ... | 9 ErsteZiffer 1 | 2 | ... | 9
27
Beispiel: ZR – eine Sprache für einen Zeichenroboter
28
Übungsaufgabe
1. Geben Sie eine (reguläre) Grammatik für die Sprache der Uhrzeiten an.
2. Entwerfen/Erzeugen Sie einen Automaten.
Vorgehen (allgemein):Beispielwörter, Beispiel-Nichtwörter, Muster, Muster
spezifizieren, Grammatik entwerfen, Beispielwörter testen, Grammatik "justieren" bzw. transformieren bzw. nach alternativer Idee neu entwerfen, Automat generieren (hier: regGr NEA DEA)
29
Lösung der Übungsaufgabe
Muster: ab : cd, a=0,1,2; b=0,1,2,3,4,5,6,7,8,9, wenn a=0,1 b=0,1,2,3, wenn a=2 c=0,1,2,3,4,5; d=0,1,2,3,4,5,6,7,8,9
U -> A : C A -> 0 B | 1 B | 2 Q B -> 0 | 1 | 2 | 3 | 4 | 5 | 6 | 7 | 8 | 9 Q -> 0 | 1 | 2 | 3 C -> 0 B | 1 B | 2 B | 3 B | 4 B | 5 B
... ist nicht regulär (Prüfknopf in kfGEdit) – erste Regel! (aber eine schöne kfG)
30
Lösung der Übungsaufgabe
Regelbildung – rechte Seiten: Erstes Zeichen (Terminal) und Rest (Nichtterminal)
U -> 0 H | 1 H | 2 K H -> 0 B | 1 B | 2 B | 3 B | 4 B | 5 B | 6 B | 7 B | 8 B | 9 B B -> : C C -> 0 Z | 1 Z | 2 Z | 3 Z | 4 Z | 5 Z Z -> 0 | 1 | 2 | 3 | 4 | 5 | 6 | 7 | 8 | 9 K -> 0 R | 1 R | 2 R | 3 R R -> : C
31
Vollständige Definition angeben! s. kfGEdit
Lösung der Übungsaufgabe
32
DEA für die Sprache der Uhrzeiten: regGr NEA DEA
Lösung der Übungsaufgabe
33
Ein zugehöriger NEA ist konzeptionelle wesentlich übersichtlicher, erfordert aber eine grundlegende Behandlung des Nichtdeterminismus.
Beispiel: ZR – eine Sprache für einen Zeichenroboter
Anweisungen Anweisung Anweisungen | EPSILONAnweisung VW n
| WH n [ Anweisungen ]
34
DKA für obigen Grammatik-Ausschnitt
Beispiel: ZR – eine Sprache für einen Zeichenroboter
35
Beispiele für DKA und NKA
36
Musterbeispiele:
1.Sprache der Palindrome über {0,1}2.Sprache der Palindrome über {0,1} mit (durch !) markierter Wortmitte
Für 1 gibt es keinen DKA, für 2 NKA und DKA.
Studienaufgabe: DKA für (n>0).n na b
Beispiele für DKA und NKA
37
Lösung:Sprache der Palindrome über {0,1} mit (durch !) markierter Wortmitte
Beispiel: ZR – eine Sprache für einen Zeichenroboter
Aus der Kombination von kleinen endlichen Automaten und einem Kellerautomaten wird später unser Compiler bestehen.
Für EA-Sprachen können auch reguläre Ausdrücke verwendet werden: Beispiel Zahl (nicht 0, ohne Vornullen): [1-9][0-9]*
38
Reguläre Ausdrücke für reguläre Sprachen
39
Reguläre Ausdrücke für reguläre Sprachen
40
Reguläre Ausdrücke für reguläre Sprachen
Reguläre Ausdrücke zur Definition regulärer SprachenZahlen in ZR: [1-9][0-9]*
41
Aktuelle Syntax von RegExp ist dem Gebrauch als Filter in vielen PS
angepasst. Z.B. [...] Zeichenauswahl – genau ein Zeichen aus ...
s. Arbeitsblatt: Reguläre Ausdrücke in Programmiersprachen.pdf
Achtung: Rückwärtsreferenzen führen aus der Klasse der regulären Sprachen heraus.
Arbeitsweise des Compilers
42
Arbeitsweise eines Scanners
43
Ein- und Ausgabe des Scanners:
Viele kleine endliche Automaten entscheiden welche Schlüsselworte im Quelltext stehen.
Quelltext besteht aus Zeichen und der Rechner weiß noch nicht wie diese zusammengehören.
Token als Paare[Tokenname, Lexem] z.B.: [Wiederhole, "WH"][Zahl, "12"][KlammerAuf, "["]
Beispiel: ZR – eine Sprache für einen Zeichenroboter
Programm Anweisungen Anweisungen Anweisung Anweisungen | EPSILONAnweisung VW Zahl | RE Zahl | WH Zahl [ Anweisungen ] | FARBE Farbwert | STIFT Zahl
Farbwert : rot|blau|gruen|gelb|schwarzZahl : [1-9][0-9]*
44
Reguläre Grammatik NEA DEA
45
farbwert.txt
Beispiel: ZR – eine Sprache für einen Zeichenroboter
Endliche Automaten (RegExp) für alle unsere Terminale:KlammerAuf : \[KlammerZu : \]Wiederhole : WHRechts : REVor : VWStift : STIFTFarbe : FARBEFarbwert : rot|blau|gruen|gelb|schwarzZahl : [1-9][0-9]*
46
S, T, I, F, T
Beispiel: ZR – eine Sprache für einen Zeichenroboter
47
Beispiel: ZR – eine Sprache für einen Zeichenroboter
48
per Hand ergänzen
Arbeitsweise des Parsers
49
Ein- und Ausgabe des Parsers:
#false erfolgt meinst durch Ausgabe von „Syntax Error“
Grammatik von ZR in Form eines Kellerautomaten Prüft ob Wort zur Sprache gehört
Beinhaltet die aufgetretenen Terminale der Grammatik des Parsers
Beispiel: ZR – eine Sprache für einen Zeichenroboter
Entwicklung des ZR2PS Compilers in VCC Übertragen der EA in die Scannerdefinition Übertragen der vereinfachten Grammatik in die
Parserdefinition Entwickeln so genannter S-Attribute für die
Zielcodegenerierung
50
Beispiel: Postscript als Zielsprache des ZR-Compilers
51
ZR PS PDF
Eingabewort (in ZR): WH 36 [WH 4 [VW 100 RE 90] RE 10]
Ausgabewort (in PS):%!PS-Adobe-2.0/orient 0 def /xpos 0 def /ypos 0 def 0 0 0 setrgbcolor/goto { /ypos exch def /xpos exch def xpos ypos moveto} def/turn { /orient exch orient add def} def /draw { /len exch def newpath xpos ypos moveto /xpos xpos orient sin len mul add def /ypos ypos orient cos len mul add def xpos ypos lineto stroke } def 300 400 goto100 draw 90 turn 100 … turn 10 turn
Beispiel: Zielcodegenerierung für ZR
Zielcodegenerierung: Der Compiler soll PostScript erstellen nicht nur
#true und #false ausgeben. Entwicklung von S-Attributen S-Attribute sind kleine Quelltextfragmente die für
jede rechte Regelseite definiert werden können. Wird eine Regel angewendet wird auch das
entsprechende Quellcodefragment ausgeführt.
52
Beispiel: ZR – eine Sprache für einen Zeichenroboter
Die Platzhalter $1 bis $n: In S-Attributen verwenden wir Platzhalter für die
Ergebnisse der einzelnen Regelbausteine.
53
$1 $2
VW 20
Eingabewort sei: VW 20 RE 10Eingabewort sei: VW 20 RE 10
Von einem Token ist $n immer des Lexem des Tokens !
Von einem Nichtterminal ist $n immer das Ergebnis $$ des Nichtterminals !
$$ = "20 draw "
Von einem Token ist $n immer des Lexem des Tokens !
Von einem Nichtterminal ist $n immer das Ergebnis $$ des Nichtterminals !
Beispiel: ZR – eine Sprache für einen Zeichenroboter
Die Platzhalter $1 bis $n: In S-Attributen verwenden wir Platzhalter für die
Ergebnisse der einzelnen Regelbausteine.
54
$1 $2
WH 4
Eingabewort sei: WH 4 [ VW 20 ]
$3
[
$5
]
$4
20 draw
$$ = "20 draw 20 draw 20 draw 20 draw " Alle $n und $$ sind vom Datentyp String !!!
Arbeitsweise des Compilers
55
Programm Anweisungen Anweisungen Anweisung Anweisungen | Anweisung VW Zahl | RE Zahl | WH Zahl [ Anweisungen ] | FARBE Farbwert | STIFT Zahl
WH 36 [WH 4 [VW 100 RE 90] RE 10]
[Wiederhole, "WH"][Zahl, "12"][KlammerAuf" "["]…
%!PS-Adobe-2.0/orient 0 def /xpos 0 def /ypos 0 def 0 0 0 setrgbcolor/goto { /ypos exch def /xpos exch
def xpos ypos moveto} def…
Beispiel: ZR – eine Sprache für einen Zeichenroboter
Anwenden des Compilers auf der Modellierungsebene der T-Diagramme in TDiag.
56
Beispiel: Musiksprache
Das Beispiel soll Ihnen die Möglichkeit geben, die gezeigten Inhalte noch einmal selbst anzuwenden.
Ein Beispiel für sehr einfache Musiksprachen sind ältere Handyklingeltöne.
57
Beispiel für Musiksprachen
http://www.audio-ware.com/midi/coding-workshop-ringtone-converter.htm
58
Die Musiksprache ML
Wir wollen unsere eigene Notensprache entwickeln für monophone Lieder (nur eine Stimme)
Programmbeispiel:C1-2 G1-8 A0-4 A0-8G0-4 G0-8 C0-8 P-2
59
Die Musiksprache ML
Die Sprache ist so einfach, dass sie sogar regulär ist.
Eine etwas komplexere Sprache könnte etwa Wiederholungen enthalten:
[C1-2 G1-8 [A0-4 A0-8]] P-2
(typisches Klammerbeispiel für Kellerautomaten)
60
Die Musiksprache ML
Erforschen Sie ML: Öffnen Sie den Ordner„Songs“ und starten Sie
Console.bat
61
Aufgabe: Ändern Sie den Inhalt einer ML Datei um sich besser mit ML vertraut zu machen.
Vorgehensmodell62
Implementierungs-ebene
Modellebene
Problemebene
Software entwickeln Software nutzen
Entwicklung eines ML Interpreters
Lösungsschritte:
1) Ein T-Diagramm erstellen
2) Eine formale Grammatik für ML erstellen
3) Eine Scanner- und Parserdefinition entwickeln
4) S-Attribute für die Regeln im Parser aufstellen
5) Den ML Interpreter generieren lassen
6) Den Interpreter mit Hilfe des T-Diagramms testen
63
Arbeitsblatt 1
Ein T-Diagramm für den ML Interpreter
Verfassen Sie ein T-Diagramm für den ML Interpreter (geschrieben in Java Bytecode) welcher auf ein ML Programm angewendet wird.
64
Ein T-Diagramm für den ML Interpreter65
Eine Grammatik für ML erstellen
Den mittleren Teil des Diagramms (den ML Interpreter) wollen wir herstellen.
Dafür müssen wir den Aufbau (Syntax) von ML beschreiben. Wir verwenden eine kontextfreie Grammatik GML (in BNF).
Betrachten wir einfache Beispiele der Sprache und leiten eine Grammatik ab: G0-4 G1-2 A0-1 D1-32 P-16 A-8 P-2 C0-16 C1-8 F0-1 H1-2 P-1
66
Beginnen Sie mit:Song NotesNotes ?
Eine Grammatik für ML erstellen67
Eine Grammatik für ML erstellen68
Eine Grammatik für ML erstellen69
Einen Interpreter für ML entwickeln
Prinzipell können wir sagen, dass ein Interpreter sehr ähnlich wie ein Compiler arbeitet. Er erstellt nur keinen Zielcode.
Wir werden deshalb im Folgenden einen Compiler herstellen, denn wir als Interpreter verwenden wollen.
70
Wie funktioniert ein Interpreter ?71
Für einen Interpreter wollen wir keine Ausgabe wir wollen direkt Befehle ausführen.
Einen Interpreter für ML entwickeln72
Wir müssen den Scanner und Parser beschreiben wie diese arbeiten sollen.
Wir beginnen mit der Scannerdefinition. Wir definieren Tokenklassen mit Expressions (Pattern –
RegExp.) Einfachste Lösung: Für jedes Terminal in GML
verwenden wir genau eine Tokenklasse. Komplexe Pattern erleichtern aber die Arbeit des
Parsers später erheblich. wir versuchen dem Scanner auch Arbeit zu geben
Einen Interpreter für ML entwickeln73
duration values (full, half, ¼, …)
all keynames
allowed octaves Token-klassen Liste1
1
Einen Interpreter für ML entwickeln
Wir müssen dafür sorgen, dass sich Tokenklassen nicht überlappen.
In echten Programmier-sprachen ist das aber häufig der Fall: Keyword: beginIdentifier: [a-z]+
Um dieses Problem zu lösen ist die Reihenfolge der Tokenklassen wichtig!
74
Einen Interpreter für ML entwickeln75
Wir können eine vereinfachte Grammatik G’ML unter Verwendung der Token erstellen:
Wir haben 6 Tokenklassen:KeyName, Token0, Token1, Token2_32, P und -
Einen Interpreter für ML entwickeln76
Wir können die RegExp. der Tokenklassen auch wieder durch endliche Automaten darstellen:
Token2_322|4|8|16|32
KeyName C|D|E|F|G|A|H
Einen Interpreter für ML entwickeln77
Einen Interpreter für ML entwickeln78
Wir bennen die Tokenklassen sinnvoll um.
Einen Interpreter für ML entwickeln79
Die regulären Ausdrücke müssen eingetragen werden.
Einen Interpreter für ML entwickeln80
Einen Interpreter für ML entwickeln
Wir können jetzt einen Compiler erstellen lassen (Scanner + Parser) und auf ein Programm in ML anwenden:
Wir wollen aber Töne abspielen es fehlt also noch etwas
81
Einen Interpreter für ML entwickeln
Für jede Regel müssen wir ein S-Attribut erstellen.
Erinnerung: S-Attribute sind kleine Quelltextfragmente die bei der Anwendung einer Regel ausgeführt werden.Jede Regel liefert ihr Ergebnis in $$ zurück indem das Quelltextfragment abgearbeitet wird (wir müssen $$ bei Bedarf einen Wert zuweisen).
82
Einen Interpreter für ML entwickeln
Wiederholung Platzhalter $1 bis $n: In S-Attributen können wir Platzhalter verwenden, die
jeweils für das Ergebnis eines Elements auf der rechten Regelseite stehen.
83
$1 $2
C1 -
Input word: C1-8 C1-4Input word: C1-8 D1-4
Von einem Token $n ist dies immer das Lexem!
Von einem Nichtterminal ist $n immer dessen Ergebnis $$!
$$ = "C1-8"
$2
8
Einen Interpreter für ML entwickeln
Wiederholung Platzhalter $1 bis $n: In S-Attributen können wir Platzhalter verwenden, die
jeweils für das Ergebnis eines Elements auf der rechten Regelseite stehen.
84
Alle $n und $$ haben den Datentyp String !!!
$1 $2
C 1
Input word: C1-8 C1-4Input word: C1-8 D1-4
$$ = "C1"
Von einem Token $n ist dies immer das Lexem!
Von einem Nichtterminal ist $n immer dessen Ergebnis $$!
$1
C1
Einen Interpreter für ML entwickeln
Nun können wir uns den S-Attributen zuwenden für: Was passiert wenn die Regel Note… auftritt?
Auf finden wir 3 Hilfsfunktionen um MIDI Noten in Java abzuspielen.
Wir müssen den Notennamen wie C0 in die entsprechende MIDI Taste übersetzen und playNote aufrufen.
85
Arbeitsblatt 1
Einen Interpreter für ML entwickeln86
Einen Interpreter für ML entwickeln87
Wir erstellen erneut den Interpreter
Das T-Diagramm ausführen88
Einen MLSVG Compiler entwickeln
Lösungsschritte:
1) Ein T-Diagramm erstellen
2) Eine Scanner- und Parserdefinition erstellen
3) S-Attribute für die Regeln im Parser aufstellen
4) Den MLSVG Compiler generieren lassen
5) Den Compiler mit Hilfe des T-Diagramms testen
89
Arbeitsblatt 2
Ein T-Diagramm für den MLSVG Compiler erstellen
90
Einen MLSVG Compiler entwickeln91
Das T-Diagramm ausführen
Wir können unseren Compiler dem T-Diagramm zuweisen und dieses ausführen:
92
Zusammenfassung93
C1-8 E1-4 D0-2 …[KeyName, "C"][Token1, "1"][Minus, "-"]…
<?xml version="1.0" ?><!DOCTYPE svg PUBLIC
"-//W3C//DTD SVG 20010904//EN" "http://www.w3.org/TR/2001/REC-SVG-...
Turing-Maschine (EINE Definition)94
Turing-Maschine95
Aufbau und Arbeitsweise: TM-Modell
TM als Akzeptor:
Start: auf erstem Zeichen des Eingabewortes
Stopp: per crash (falls die TM überhaupt anhält)
Turing-Maschine96
Beispiel:n n na b c , mit n 0
Didaktische Kommentierung: ECHTE Beispiele sind problematisch.
Turing-Maschine in der Berechenbarkeitstheorie
97
Hinweis auf das Buch
Wagenknecht, Chr.; Hielscher, M.:Sprachen, Automaten und Compiler:Ein Arbeitsbuch zur theoretischen Informatik.Teubner, 2008
98