studyklar
GdI 1 · Übungsblatt 4 · Aufgabe 3

Züge als EBNF: Loks, Wagen und Steuerwagen

Ein Zug besteht aus Lokomotiven und Wagen in einer bestimmten Reihenfolge. Fünf Regeln sagen, was erlaubt ist. Daraus wird eine EBNF, also eine Schreibweise, die genau die erlaubten Züge erzeugt. Rechts steht sie als Syntaxdiagramm; der gerade gemeinte Teil ist hervorgehoben. Mit Weiter geht es Schritt für Schritt voran.

Die Aufgabe

Aufgabe 4.3

Erstellen Sie eine EBNF-Beschreibung für Züge einer fiktiven Bahngesellschaft. Züge bestehen aus Lokomotiven (L), Speisewagen (S), Fahrrad/Gepäckwagen (F), Grossraumwagen (G), Steuerwagen (Z). (Daneben ist das Foto eines Steuerwagens abgebildet.)

Regeln:

  1. Eine oder mehrere Lokomotiven (L) führen den Zug an.
  2. Den Schluss bildet ein Steuerwagen (Z).
  3. Fahrrad&Gepäckwagen (F) werden immer paarweise eingesetzt, also FF, FFFF, …
  4. Es können nicht mehr als vier Grossraumwagen (G) in einer Reihe (direkt hintereinander) im Zug sein.
  5. Nach jeder Gruppe von Grossraumwagen (G) und nur dann folgt ein Speisewagen.

Beispiele:

  • LZ – legal, kürzester Zug
  • LLLFFZ – legal (aber kein Platz für Passagiere)
  • LGGSFFGSFFFFZ – legal, Zug mit allen Wagentypen
  • LLFF – illegal, Zug ohne Steuerwagen
  • LGGGGFFZ – illegal, kein Speisewagen nach Gruppe Grossraumwagen
  • LGGSFFFZ – illegal, ungerade Anzahl Fahrrad&Gepäckwagen
  • LGGGGGSZ – illegal, > 4 Grossraumwagen hintereinander

Jeder Zug ist ein Wort aus den Buchstaben L, S, F, G und Z, von vorn nach hinten gelesen. Gesucht ist eine EBNF, die alle Züge nach den fünf Regeln erzeugt und keinen anderen. Die sieben Beispiele dienen als Probe: Die drei legalen müssen sich erzeugen lassen, die vier illegalen nicht.

Merke: Jede Regel der Aufgabe wird zu einem Stück EBNF. „Eine oder mehrere“ ist eine Wiederholung, „kann“ eine Option, „entweder … oder“ eine Alternative.
  1. Das Gerüst: Loks vorn, Steuerwagen hinten, Wagen dazwischen.
  2. Je eine Regel für Loks, Fahrradwagen und Großraumwagen.
  3. Die Wagen als Alternative zusammensetzen.
  4. Die sieben Beispiele prüfen.

Das Gerüst: Loks, Wagen, Steuerwagen

Startregel
Zug = <Loks> { <Wagen> } Z

Regel 1 sagt, was vorn steht: Lokomotiven. Regel 2 sagt, was hinten steht: genau ein Z. Dazwischen kommen beliebig viele Wagen, auch keiner (der kürzeste Zug LZ hat keinen). „Beliebig viele, auch keiner“ ist in EBNF { }.

Für die Loks und die Wagen schreiben wir Nichtterminale. Sie bekommen gleich eigene Regeln. So bleibt die Startregel Zug kurz und lesbar. Startregel heißt die erste Regel: Sie beschreibt das Ganze, die anderen nur seine Teile.

Aus Skript 3, Folie 3-33 („EBNF“): Nichtterminale stehen in spitzen Klammern <…> und brauchen eine eigene Regel. | trennt Alternativen, [ ] ist optional, { } heißt beliebig oft, auch null Mal.

Regel 1: eine oder mehrere Loks

Regel für die Loks
Loks = L { L }

„Eine oder mehrere“ heißt: mindestens eine. { L } allein wäre falsch, denn das erlaubt auch null Loks. Darum steht ein L fest vorn, und die geschweiften Klammern fügen beliebig viele weitere hinzu. Im Diagramm ist das ein L mit einer Schleife zurück.

Noch 8 Schritte bis zum Ergebnis
Den ganzen Lösungsweg sehen Studierende und Lehrende der HS KL. Registriere dich mit deiner Adresse @stud.hs-kl.de oder @hs-kl.de, dann geht es hier direkt weiter.
Registrieren

Abbildung 1

ZugLoksWagenZLoksLWagenFahrradGrossraumFahrradFFGrossraumGGGGS
Legendegerade gemeintDie EBNF für Züge als Syntaxdiagramm. Ovale sind Wagen, Rechtecke verweisen auf eine andere Regel.