Informatik · Klasse 13

Ideen für aktives Lernen

Kontextfreie Grammatiken

Aktive Auseinandersetzung mit kontextfreien Grammatiken hilft Schülern, abstrakte Produktionsregeln greifbar zu machen. Durch das Entwerfen eigener Grammatiken und das Konstruieren von Parse-Bäumen verstehen sie, wie Syntax in Programmiersprachen funktioniert und warum rekursive Strukturen für echte Sprachen essenziell sind.

• KMK Bildungsstandards
• KMK: Sekundarstufe II - Formale Sprachen und Automaten
• KMK: Sekundarstufe II - Strukturieren und Vernetzen

• 25–45 Min.
• Partnerarbeit → Ganze Klasse
• 4 Aktivitäten

Aktivität 01

• Gruppenpuzzle
• 35 Min. · Partnerarbeit

Paararbeit: Grammatik entwerfen

Paare erhalten eine einfache arithmetische Sprache, z. B. Ausdrücke mit +, *, Klammern. Sie formulieren 5-7 Produktionsregeln in BNF und testen mit 10 Beispielsätzen auf Gültigkeit. Abschließend tauschen sie Grammatiken und validieren gegenseitig.

Erklären Sie, wie kontextfreie Grammatiken die Syntax von Programmiersprachen definieren.

Moderationstipp

Bei der Paararbeit zum Grammatikentwerfen darauf achten, dass beide Partner konkrete Beispiele aus Python (z.B. if-else-Strukturen) in Regeln übersetzen und gegenseitig überprüfen.

Worauf zu achten ist

Geben Sie den Schülerinnen und Schülern eine einfache kontextfreie Grammatik (z.B. für boolesche Ausdrücke) und eine Zeichenkette. Bitten Sie sie, einen Parsebaum für die Zeichenkette zu zeichnen oder zu erklären, warum die Zeichenkette nicht von der Grammatik abgeleitet werden kann.

• Verstehen
• Analysieren
• Bewerten
• Beziehungsfähigkeit
• Selbststeuerung

Aktivität 02

• Gruppenpuzzle
• 45 Min. · Kleingruppen

Gruppenrotation: Parse-Trees konstruieren

Drei Stationen: 1. Regelanalyse, 2. Linkes Derivieren, 3. Baumzeichnen. Gruppen rotieren alle 10 Minuten, bearbeiten Sätze und vergleichen Ergebnisse. Plenum diskutiert Abweichungen.

Vergleichen Sie die Ausdrucksstärke von regulären Sprachen und kontextfreien Sprachen.

Moderationstipp

Bei der Gruppenrotation zum Parse-Tree-Konstruieren eine klare Zeitvorgabe pro Station setzen und sicherstellen, dass jede Gruppe ihr Ergebnis auf einer Folie oder einem Whiteboard präsentiert.

Worauf zu achten ist

Stellen Sie eine Liste von Zeichenketten und eine kontextfreie Grammatik bereit. Die Schülerinnen und Schüler sollen für jede Zeichenkette angeben, ob sie von der Grammatik erzeugt werden kann. Diskutieren Sie anschließend die Ergebnisse und die Begründungen für die Klassifizierung.

• Verstehen
• Analysieren
• Bewerten
• Beziehungsfähigkeit
• Selbststeuerung

Aktivität 03

• Gruppenpuzzle
• 30 Min. · Ganze Klasse

Klassenvergleich: Regulär vs. kontextfrei

Ganze Klasse teilt Beispielsätze ein: regulär (z. B. a*b) oder kontextfrei (z. B. a^n b^n). Jeder schlägt Automat oder Grammatik vor, Klasse stimmt ab und rechtfertigt.

Designen Sie eine kontextfreie Grammatik für eine einfache arithmetische Sprache.

Moderationstipp

Den Klassenvergleich zwischen regulären und kontextfreien Grammatiken mit einer Tabelle beginnen, in der Schülerinnen und Schüler Gemeinsamkeiten und Unterschiede sammeln, bevor sie Beispiele diskutieren.

Worauf zu achten ist

Diskutieren Sie in Kleingruppen: 'Warum sind reguläre Sprachen für die Beschreibung der Syntax von Programmiersprachen oft nicht ausreichend, während kontextfreie Sprachen dies meist sind? Geben Sie konkrete Beispiele für Sprachkonstrukte, die dies verdeutlichen.'

• Verstehen
• Analysieren
• Bewerten
• Beziehungsfähigkeit
• Selbststeuerung

Aktivität 04

• Gruppenpuzzle
• 25 Min. · Einzelarbeit

Individual: Parsing-Challenge

Jeder Schüler parst fünf Code-Snippets mit gegebener Grammatik und zeichnet Derivationsbäume. Peer-Review folgt, um Fehler zu besprechen.

Erklären Sie, wie kontextfreie Grammatiken die Syntax von Programmiersprachen definieren.

Moderationstipp

Für die individuelle Parsing-Challenge eine Fehleranalyse einbauen: Schüler sollen nicht nur korrekte Snippets klassifizieren, sondern auch die Regel identifizieren, die verletzt wurde.

Worauf zu achten ist

Geben Sie den Schülerinnen und Schülern eine einfache kontextfreie Grammatik (z.B. für boolesche Ausdrücke) und eine Zeichenkette. Bitten Sie sie, einen Parsebaum für die Zeichenkette zu zeichnen oder zu erklären, warum die Zeichenkette nicht von der Grammatik abgeleitet werden kann.

• Verstehen
• Analysieren
• Bewerten
• Beziehungsfähigkeit
• Selbststeuerung

Einige Hinweise zum Unterrichten dieser Einheit

Erfahrungsgemäß verstehen Schüler kontextfreie Grammatiken besser, wenn sie selbst Regeln entwerfen und deren Auswirkungen direkt sehen. Vermeiden Sie reine Definitionen ohne Anwendung, da sonst die Verbindung zu Programmiersprachen verloren geht. Nutzen Sie visuelle Hilfsmittel wie Parse-Bäume, um die rekursive Natur der Regeln zu verdeutlichen. Forschung zeigt, dass praktische Fehleranalysen (z.B. 'Warum scheitert dieser Code?') das Verständnis vertiefen und Misconceptions vorbeugen.

Am Ende können Schülerinnen und Schüler Produktionsregeln in BNF formulieren, Parse-Bäume für gegebene Code-Snippets erstellen und den Unterschied zwischen regulären und kontextfreien Grammatiken mit Beispielen erklären. Sie erkennen auch die Grenzen kontextfreier Grammatiken in realen Programmiersprachen.

---

Vorsicht vor diesen Fehlvorstellungen

• Während der Gruppenrotation beim Parse-Tree-Konstruieren beobachten Sie...

  Verweisen Sie auf Strukturen wie a^n b^n (z.B. { und } in verschachtelten Schleifen) und lassen Sie die Schüler versuchen, dafür einen endlichen Automaten zu bauen. Scheitern sie, wird der Unterschied zu kontextfreien Grammatiken direkt erlebbar.

• Während der Paararbeit beim Grammatikentwerfen achten Sie auf...

  Fordern Sie die Schüler auf, eine Grammatik für Python-Funktionsdeklarationen zu entwerfen. Diskutieren Sie gemeinsam, warum Typprüfungen (z.B. def func(int x)) nicht ohne zusätzliche Regeln funktionieren und verweisen Sie auf Attributgrammatiken.

• Während der individuellen Parsing-Challenge fällt auf...

  Lassen Sie Schüler ein gültiges Snippet (z.B. 1 + 2) und ein semantisch falsches (z.B. 1 + true) parsen. Fragen Sie nach, ob die Grammatik die Semantik erkennen kann, und führen Sie das Konzept der Semantik als Erweiterung der Syntax ein.

---

In dieser Übersicht verwendete Methoden

• Gruppenpuzzle