studyklar
GdI 1 · Übungsblatt 4 · Aufgabe 1

Ganze Zahlen ohne führende Nullen: Syntaxdiagramm und EBNF

Wie schreibt man eine Regel auf, die genau die erlaubten Zahlwörter beschreibt, etwa „42“ und „-7“, aber nicht „007“? Dafür gibt es zwei gleichwertige Schreibweisen: die EBNF als Text und das Syntaxdiagramm als Bild. Rechts steht das Syntaxdiagramm, der aktuelle Teil ist hervorgehoben. Mit Weiter geht es Schritt für Schritt voran.

Die Aufgabe

Aufgabe 4.1

Geben Sie jeweils ein Syntaxdiagramm und eine EBNF an zur Beschreibung der …

a) … ganzen Zahlen, wobei führende Nullen nicht zugelassen sind;

b) … vierstelligen, positiven, ganzen Dezimalzahlen ohne führende Nullen und nur genau die.

Gesucht sind zwei Regelwerke, jedes zweimal aufgeschrieben: als Syntaxdiagramm und als EBNF. Das erste beschreibt alle ganzen Zahlen, also auch negative und die Null. Das zweite nur Zahlen von 1000 bis 9999. In beiden darf vorn keine überflüssige Null stehen.

EBNF heißt „Erweiterte Backus-Naur-Form“: eine Textschreibweise für solche Regeln. Ein Syntaxdiagramm zeigt dieselbe Regel als Schienennetz. Jeder Weg vom Eingang zum Ausgang ergibt ein erlaubtes Wort.

Merke: Eine Regel ist erst richtig, wenn sie jedes erlaubte Wort erzeugt und kein verbotenes. Darum prüft man sie an Beispielen von beiden Seiten.
  1. a) Regeln für einzelne Ziffern aufstellen.
  2. a) Erste Ziffer, Null, Vorzeichen: die Regel für ganze Zahlen.
  3. a) Beispielwörter prüfen.
  4. b) Dieselben Bausteine für genau vier Stellen.
  5. b) Beispielwörter prüfen und die Wörter zählen.

Die Bausteine: Ziffern mit und ohne Null

EBNF der Ziffern
ZifferOhneNull = 1 | 2 | ... | 9
Ziffer = 0 | <ZifferOhneNull>

Jede Zahl ist eine Folge von Ziffern. Wir brauchen gleich zwei Sorten: alle Ziffern 0 bis 9 und die Ziffern ohne Null, 1 bis 9. Darum zwei Regeln. Die Regel Ziffer greift auf ZifferOhneNull zurück und fügt nur die 0 hinzu.

Aus Skript 3, Folie 3-33 („EBNF“): Eine Regel hat die Form „linke Seite = rechte Seite“. Links steht genau ein Nichtterminal, rechts Terminale (die Zeichen selbst) und Nichtterminale in spitzen Klammern <…>. | trennt Alternativen, [ ] heißt „optional“, { } heißt „beliebig oft, auch null Mal“.
Aus Skript 3, Folie 3-29 („Syntaxdiagramm“): Terminale stehen in Ovalen, Nichtterminale in Rechtecken. Pfeile verbinden sie; jede Regel hat genau einen Eingang und einen Ausgang.

Keine führende Null: die erste Ziffer ist 1 bis 9

Zahlen ab 1, ohne führende Null
<ZifferOhneNull> { <Ziffer> }

Eine führende Null ist eine Null ganz vorn, vor weiteren Ziffern: „007“ oder „05“. Sie ändert den Wert nicht und ist darum verboten. Verhindern lässt sie sich an einer einzigen Stelle: Die erste Ziffer kommt aus ZifferOhneNull.

Danach ist jede Ziffer erlaubt, auch 0, und zwar beliebig viele: „1“, „10“, „1000“. Das leisten die geschweiften Klammern. Im Diagramm ist es die Schleife, die zurück vor den Kasten Ziffer führt.

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 1a) Ganze Zahlen

ohne führende Nullen

GanzeZahl0-ZifferOhneNullZifferZifferOhneNull12…9Ziffer0ZifferOhneNull
Legendegerade gemeintSyntaxdiagramm für ganze Zahlen ohne führende Nullen.