Unterrichtssequenzen

Zu entwickelnde Kompetenzen

Beispiele, Medien, Materialien

1. Von-Neumann-Architektur und die Ausführung maschinennaher Programme

(a) prinzipieller Aufbau einer von Neumann-Architektur mit CPU, Rechenwerk, Steuerwerk, Register und Hauptspeicher

(b) einige maschinennahe Befehlen und ihre Repräsentation in einem Binär-Code, der in einem Register gespeichert werden kann

(c) Analyse und Erläuterung der Funktionsweise eines einfachen maschinennahen Programms

Die Schülerinnen und Schüler

• erläutern die Ausführung eines einfachen maschinennahen Programms sowie die Datenspeicherung auf einer „Von-Neumann-Architektur“ (A),
• ermitteln bei der Analyse von Problemstellungen Objekte, ihre Eigenschaften, ihre Operationen und ihre Beziehungen (M),
• modellieren Klassen mit ihren Attributen, Methoden und ihren Assoziationsbeziehungen unter Angabe von Multiplizitäten (M),
• modellieren abstrakte und nicht abstrakte Klassen unter Verwendung von Vererbung durch Spezialisieren und Generalisieren (M),
• verwenden bei der Modellierung geeigneter Problemstellungen Möglichkeiten der Polymorphie (M),
• ordnen Klassen, Attributen und Methoden ihre Sichtbarkeitsbereiche zu (M),
• stellen Klassen und ihre Beziehungen in Diagrammen grafisch dar (D),
• analysieren und erläutern objektorientierte Modellierungen (A),
• implementieren Klassen in einer Programmiersprache auch unter Nutzung dokumentierter Klassenbibliotheken (I),
• analysieren und erläutern Algorithmen und Programme (A),
• modifizieren Algorithmen und Programme (I),
• entwickeln iterative und rekursive Algorithmen unter Nutzung der Strategien „Modularisierung“ und „Teilen und Herrschen“ und „Backtracking“ (M),
• implementieren iterative und rekursive Algorithmen auch unter Verwendung von dynamischen Datenstrukturen (I),
• testen Programme systematisch anhand von Beispielen und mit Hilfe von Testanwendungen (I),
• analysieren und erläutern die Eigenschaften endlicher Automaten und Kellerautomaten einschließlich ihres Verhaltens bei bestimmten Eingaben (A),
• ermitteln die Sprache, die ein endlicher Automat oder ein Kellerautomat akzeptiert (D),
• entwickeln und modifizieren zu einer Problemstellung endliche Automaten oder Kellerautomaten (M),
• analysieren und erläutern Grammatiken regulärer und kontextfreier Sprachen (A),
• modifizieren Grammatiken regulärer und kontextfreier Sprachen (M),
• ermitteln die formale Sprache, die durch eine Grammatik erzeugt wird (A),
• entwickeln zu einer regulären oder kontextfreien Sprache eine Grammatik, die die Sprache erzeugt (M),
• modellieren und implementieren Scanner, Parser und Interpreter zu einer gegebenen regulären Sprache (I),
• nutzen das verfügbare Informatiksystem zur strukturierten Verwaltung von Daten, zur Organisation von Arbeitsabläufen sowie zur Verteilung und Zusammenführung von Arbeitsanteilen (K),
• untersuchen und beurteilen Grenzen des Problemlösens mit Informatiksystemen (A).

Beispiele:

Addition von 4 zu einer eingegeben Zahl mit einem Rechnermodell

2. Simulation der Phasen eines Compilers

(a) Prozesse beim Compiler:

• scannen
• parsen
• übersetzen/interpretieren

(b) Arten von Fehlern:

• lexikalischer Fehler
• syntaktischer Fehler
• semantischer Fehler

(c) Einordnung der neuen Begriffe in den Gesamtkontext der formalen Sprachen

• Automaten
• Grammatiken
• Sprachen

Beispiel:

Scanner, Parser und Interpreter einer Konstruktionssprache für geometrische Figuren Anhand einer einführenden Folienpräsentation werden die Begrifflichkeiten definiert.

Ein kleiner Ausschnitt einer Pseudo-Programmiersprache zur Konstruktion von Zeichnungen wird betrachtet. Anfänglich besteht der Sprachumfang aus Programmen mit lediglich einer einzigen Zuweisung.

Die grundlegenden Schritte eines Compilers werden am Beispiel dieser Grammatik nachvollzogen.

3. Die Schritte eines Compilers

(a) Scanner:

• endlicher Automat als Grundlage
• Vorgabe von Symboltabelle und Tokenliste zur Verwaltung und Erkennung des Quelltextes
• Erweiterung des terminalen Alphabets der zu übersetzenden formalen Sprache
• Implementierung als endlicher Automat

(b) Parser:

• reguläre (oder wahlweise kontextfreie) Grammatik als Grundlage
• Vorgabe einer Grundversion des Parsers
• Erweiterung des Sprachumfangs
• Implementierung der Parsermethoden für die Produktionsregeln der kontextfreien Grammatik

(c) Interpreter

• Vorgabe einer Grundversion des Interpreters
• Erweiterung des Sprachumfangs
• Implementierung

Beispiele:

Der Scanner-Automat zur Erkennung der einzelnen Symbole wird als endlicher Automat realisiert. Mithilfe der Symboltabelle wird die Vereinfachung des Automaten deutlich gemacht und der vereinfachte Scanner-Automat wird schrittweise erweitert und implementiert.

In der zweiten Phase wird die der Pseudoprogrammiersprache zugrunde liegende Grammatik analysiert. Die Überprüfung der syntaktischen Korrektheit wird in Form eines Parsers modelliert und implementiert. Dabei wird der Sprachumfang der Pseudo-Programmiersprache schrittweise erweitert.

In der dritten Phase wird ein zu Teilen bereits vorbereiteter Interpreter analysiert und erweitert, welcher Programme der Pseudo-Programmiersprache zur Konstruktion von Zeichnungen in eine Grafik übersetzt.