inf-schule | Grammatiken

Einstieg

Wie prüft ein Computer E-Mail-Adressen?

Du tippst in ein Formular deine E-Mail-Adresse ein. Sofort erscheint die Meldung „Ungültige Adresse“. Woher weiß der Computer das? Jemand hat ihm genau gesagt, wie gültige Adressen aufgebaut sind.

Wir betrachten wieder vereinfachte Adressen, die nur aus den Zeichen b, @ und . bestehen, zum Beispiel bb@b.bbb. Ihren Aufbau legen die sieben Syntaxdiagramme aus dem Kapitel „Syntaxdiagramme“ fest. Du findest sie im Kasten unten. Lass ihn offen, du brauchst die Diagramme gleich mehrmals.

Die Syntaxdiagramme für vereinfachte Adressen

Aufgabe 1 - Adressen herstellen: eine Erinnerung

Stelle bb@b.bb her.
Beschreibe, was von einer Zeile zur nächsten passiert. Was ändert sich, was bleibt gleich?
Ein Programm kann kein Bild ansehen. Wie könnte man ihm den Aufbau der Adressen trotzdem mitteilen? Sammle Ideen.

Ersetzungen aufschreiben

Jede neue Zeile entsteht, indem ein Nichtterminalsymbol durch die Symbole eines Weges durch sein Diagramm ersetzt wird. Ein Programm kann keine Diagramme ansehen, wohl aber Text lesen. Die Ersetzungen müssen also als Text aufgeschrieben werden.

Aufgabe 2 - Ersetzungen aufschreiben

Die Maschine darf Emailadresse durch User @ Domain ersetzen. Entwirf eine kurze Schreibweise dafür, die ein Programm lesen könnte.
So schreibt man es in der Informatik
```
Emailadresse → User @ Domain
```
Der Pfeil heißt „wird ersetzt durch“. Links steht das Nichtterminalsymbol, rechts, was an seine Stelle tritt. So eine Zeile heißt Regel. Was ist bei deiner Schreibweise gleich, was anders?
Schreibe ebenso die Regeln für diese Diagramme auf. Pfeil: -> oder →. Zwischen zwei Symbolen steht ein Leerzeichen.
- User:
- Domain:
- Topleveldomain:
- Buchstabe:

Aufgabe 3 - Und die Schleifen?

Die Diagramme Name und Subdomains haben eine Schleife. Wie wird sie zur Regel?

Lea schlägt vor: Name → Buchstabe Name. Teste ihre Regel (zusammen mit Buchstabe → b). Was fällt dir auf?

Du kommst nicht weiter?

Schau nach jedem Schritt: Steht noch ein Nichtterminalsymbol in der Zeile? Wird die Zeile irgendwann fertig?
Im Diagramm kann man die Schleife auch verlassen. Ergänze eine zweite Regel für Name:
- zum Aufhören:
- zum Weitermachen: Name → Buchstabe Name (Leas Regel)
Warum braucht Name zwei Regeln? Welche Entscheidung steckt in der Schleife?
Schreibe ebenso die beiden Regeln für Subdomains:
- zum Aufhören:
- zum Weitermachen:

Aufgabe 4 - Ein Diagramm, das auf sich selbst verweist

Im Kapitel „Syntaxdiagramme“ hast du dieses Diagramm für geschachtelte Klammern (), (()), ((())), … kennengelernt:

Es gibt zwei Wege vom Eingang zum Ausgang. Beschreibe beide.
Schreibe für jeden Weg eine Regel auf:
- Weg durch das Nichtterminalsymbol Klammer:
- Weg, der daran vorbeiführt:
Vergleiche mit den beiden Regeln für Name aus Aufgabe 3. Was haben eine Schleife und ein Diagramm, das auf sich selbst verweist, in Regeln gemeinsam?

Mit Regeln herstellen

Jetzt hast du alle Regeln. Wir nummerieren sie, damit man sie benennen kann:

(1) Emailadresse → User @ Domain
(2) User → Name
(3) Domain → Subdomains Topleveldomain
(4) Subdomains → Name .
(5) Subdomains → Name . Subdomains
(6) Topleveldomain → Name
(7) Name → Buchstabe
(8) Name → Buchstabe Name
(9) Buchstabe → b

Aufgabe 5 - Mit Regeln herstellen

Probiere die Regeln in der Maschine aus. Klicke ein Nichtterminalsymbol an und wähle eine der leuchtenden Regeln. Der Doppelpfeil ⇒ steht für einen Ersetzungsschritt.

Stelle bb@b.bb her. Was passiert in der Regelliste, wenn du ein Nichtterminalsymbol anklickst?
Fahre mit der Maus über eine fertige Zeile. Was zeigt dir die Nummer am Zeilenende?
Stelle bb@b.bb noch einmal her, ersetze die Nichtterminalsymbole aber in anderer Reihenfolge. Entsteht dieselbe Adresse?
Warum lässt sich bbb@bbb mit diesen Regeln nicht herstellen? Begründe mit den Regeln.

Aufgabe 6 - Kürzer schreiben und genau hinsehen

Lange Namen machen die Zeilen mühsam. In der Informatik kürzt man sie meist mit einzelnen Großbuchstaben ab. Auch Werkzeuge, die Regeln verarbeiten, erwarten kurze Namen.

Kürze die sieben Nichtterminalsymbole mit je einem Großbuchstaben ab. Kein Buchstabe darf doppelt vorkommen. Notiere deine Zuordnung als Legende.

Unser Vorschlag

Nichtterminalsymbol Abkürzung

Emailadresse S (Start)

User U

Domain D

Subdomains K (Kette von Namen)

Topleveldomain L (Top-Level)

Name M (naMe)

Buchstabe B

Die Buchstaben sind frei gewählt. Zu abgekürzten Regeln gehört darum immer eine Legende.

Nichtterminalsymbol	Abkürzung
Emailadresse	`S` (Start)
User	`U`
Domain	`D`
Subdomains	`K` (Kette von Namen)
Topleveldomain	`L` (Top-Level)
Name	`M` (naMe)
Buchstabe	`B`

Stelle b@b.b noch einmal her und schreibe jede Zeile mit deinen Abkürzungen auf.

Lösungsvorschlag mit unseren Abkürzungen

S ⇒ U @ D ⇒ M @ D ⇒ B @ D ⇒ b @ D ⇒ b @ K L ⇒ b @ M . L
⇒ b @ B . L ⇒ b @ b . L ⇒ b @ b . M ⇒ b @ b . B ⇒ b @ b . b

Sieh dir deine Zeilen an. Woran erkennst du sofort, was noch ersetzt wird und was schon endgültig ist?
Womit beginnt jede Herstellung? Warum?
Was steht links vom Pfeil, was rechts? Beschreibe die Form aller Regeln.

Das hast du entdeckt

Syntaxdiagramme lassen sich als Ersetzungsregeln lesen:

Syntaxdiagramm	Ersetzungsregeln
Nichtterminalsymbol (eckig)	steht links vom Pfeil und wird ersetzt
Terminalsymbol (rund, hier `b`, `@`, `.`)	bleibt stehen
Folge	Symbole nebeneinander rechts vom Pfeil
Verzweigung	mehrere Regeln für dasselbe Nichtterminalsymbol, eine pro Zweig
Weg, der an etwas vorbeiführt	eine zusätzliche Regel, in der das Übersprungene fehlt
Schleife	zwei Regeln: eine zum Aufhören und eine zum Weitermachen. In der zweiten steht das Nichtterminalsymbol rechts noch einmal.
Rekursion: Das Diagramm verweist auf sich selbst	Das Nichtterminalsymbol steht auch rechts vom Pfeil, so wie bei der Schleife.
Startdiagramm (hier `Emailadresse`)	Jede Herstellung beginnt mit seinem Nichtterminalsymbol.

Ein solches Regelwerk heißt Grammatik. Eine Zeichenkette gehört zur Sprache genau dann, wenn man sie mit den Regeln herstellen kann.

Das kann auch ein Werkzeug

Regeln lesen, Wörter herstellen, Adressen prüfen: Das alles hast du bisher von Hand gemacht. Ein Programm kann es automatisch. Das Werkzeug FLACI kann das für Regelwerke wie deines.

Aufgabe 7 - Das Werkzeug FLACI erkunden

Öffne FLACI und lege eine neue Grammatik an. Tippe die neun Regeln mit deinen Abkürzungen aus Aufgabe 6 ein. Schreibe den Pfeil als -> und lass zwischen zwei Symbolen ein Leerzeichen.
Gib das Wort bb@b.bb ein (ohne Leerzeichen) und leite es ab. Nimm „Einzelschritt“. Vergleiche die Zeilen mit deiner Herstellung aus Aufgabe 5. Was fällt dir auf?
Teste in FLACI auch Zeichenketten, die keine gültigen Adressen sind, zum Beispiel b.b@b.b und b@bb.. Was meldet FLACI?

Du hast Syntaxdiagramme in Regeln übersetzt und ein Werkzeug damit arbeiten lassen. Im Fachkonzept bekommen die Bausteine einer Grammatik ihre Fachbegriffe.