studyklar
GdI 1 · Beispielklausur · Aufgabe 3

Züge prüfen und als Syntaxdiagramm zeichnen

Vier EBNF-Regeln beschreiben, wie ein Zug aus Loks und Wagen-Bausteinen zusammengesetzt sein darf. In Teil (a) prüfen wir zwei Züge Stelle für Stelle gegen diese Regeln. In Teil (b) zeichnen wir jede Regel als Syntaxdiagramm. Rechts steht die Grafik zum aktuellen Schritt. Mit Weiter geht es Schritt für Schritt voran.

Die Aufgabe

Aufgabe 3

Gegeben sind folgende Regeln als EBNF zur Bildung von Zügen:

EBNF der Klausur
Zug = L { L } { <Wagen> } (Z | L)
Wagen = <Großraum> | <Fahrrad>
Großraum = G [G] [G] S
Fahrrad = F F

a) Entscheiden und erläutern Sie kurz, ob die beiden folgenden Züge im Sinne der vorgegebenen EBNF-Regeln gültig sind!

  1. L L L L L
  2. L L G G G S F F S G G Z

b) Zeichnen Sie die angegebenen Regeln als möglichst einfache Syntaxdiagramme!

Ein Zug ist hier ein Wort aus den Buchstaben L, G, S, F und Z, von vorn nach hinten gelesen. Die Position eines Buchstabens heißt hier Stelle, von vorn gezählt. Die EBNF sagt, welche Wörter erlaubt sind. Die Klausur nennt für diese Aufgabe keine Punktzahl.

In (a) ist zu jedem Zug „gültig“ oder „ungültig“ gefragt, mit kurzer Begründung. Es zählt die Begründung: bei gültig, welche Regel welche Stellen abdeckt; bei ungültig, an welcher Stelle es scheitert und warum. In (b) ist für jede der vier Regeln ein Syntaxdiagramm gefragt, so einfach wie möglich. Das heißt: so wenige Kästen und Wege wie nötig.

Aus Blatt 4, Aufgabe 3 („Züge als EBNF: Loks, Wagen und Steuerwagen“): Dort haben wir eine ähnliche Zug-EBNF selbst aufgestellt. Die Regeln der Klausur sind andere: Ein Zug darf hier auch mit L enden, und eine Gruppe hat höchstens drei G.
Merke: Ein Wort ist gültig, wenn es einen Weg durch die Regeln gibt, der genau alle Buchstaben verbraucht. Ungültig ist es erst, wenn jeder Weg scheitert.
  1. Die Regeln lesen: was vorn, was in der Mitte, was hinten stehen darf.
  2. Zug i von vorn nach hinten in Bausteine zerlegen.
  3. Zug ii genauso zerlegen, bis es nicht mehr weitergeht.
  4. Jede Regel als Syntaxdiagramm zeichnen, von Zug bis Fahrrad.

Die Zug-Regel lesen

Startregel
Zug = L { L } { <Wagen> } (Z | L)

Die erste Regel heißt Zug. Sie ist die Startregel: Sie beschreibt den ganzen Zug, die anderen Regeln nur seine Teile. Wir lesen sie von links nach rechts.

  • L { L }: ein L, danach beliebig viele weitere L. Vorn stehen also eine oder mehrere Loks.
  • { <Wagen> }: beliebig viele Wagen-Bausteine, auch keiner.
  • (Z | L): zum Schluss genau ein Z oder genau ein L.

Der erste Buchstabe muss also ein L sein, der letzte ein Z oder ein L. Bei beiden Zügen stimmt das: Zug i beginnt und endet mit L, Zug ii beginnt mit L und endet mit Z. Ob die Mitte passt, klären die nächsten Schritte.

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

Die Regeln für die Wagen-Bausteine lesen

Regeln für die Wagen-Bausteine
Wagen = <Großraum> | <Fahrrad>
Großraum = G [G] [G] S
Fahrrad = F F

<Wagen> ist ein Nichtterminal, also gilt seine eigene Regel: ein Wagen-Baustein ist ein Großraum oder ein Fahrrad.

  • Großraum = G [G] [G] S: ein G fest, dann zweimal ein optionales G, dann S. Das sind 1, 2 oder 3 G, und danach immer ein S.
  • Fahrrad = F F: genau zwei F hintereinander.

Daraus folgt eine Regel zum Prüfen: Jeder Wagen-Baustein beginnt mit G oder mit F. Ein S steht nur am Ende einer G-Gruppe.

Noch 12 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(a) Züge prüfen

Stelle für Stelle von vorn

Zug i, Stellen 1 bis 5
1
2
3
4
5
L
L
L
L
L
Zug ii, Stellen 1 bis 12
1
2
3
4
5
6
7
8
9
10
11
12
L
L
G
G
G
S
F
F
S
G
G
Z
Legendegerade gemeintFehlerDie beiden Züge der Aufgabe, ihre Stellen von vorn nummeriert. Darunter steht, welche Regel welche Stellen abdeckt.