Q3 / Formale Sprachen

Die Sprache PGM

Lösung geprüft

Die Aufgabe der heutigen Stunde ist die Sprache PGM! Nach Backofen und hallihallo jetzt ein echtes Dateiformat: PGM (Portable Graymap) speichert Graustufenbilder als reinen Text. Damit ist es eine formale Sprache, die man tatsächlich benutzt – und man kann eine PGM-Datei im Texteditor aufmachen und lesen.

a) Das Alphabet

Σ = { P, ' ', 1, 2, 3, 4, 5, 6, 7, 8, 9, 0 }

Zwölf Zeichen: das P für den Formatkopf, das Leerzeichen als Trennzeichen und die zehn Ziffern. Mehr braucht es nicht.

Das Leerzeichen ist dabei das interessanteste. Normalerweise denkt man an Leerzeichen als „nichts dazwischen". Hier ist es ein vollwertiges Zeichen des Alphabets, weil es die Bestandteile trennt. Ohne es wäre P2 2 2 3 0 1 2 3 nur noch P2223 0123, und man wüsste nicht mehr, wo eine Zahl aufhört und die nächste anfängt.

Die 2 aus P2 ist übrigens dieselbe Ziffer, die auch als Pixelwert vorkommt. Man braucht sie also nicht zweimal ins Alphabet aufzunehmen – die Bedeutung hängt von der Position ab, nicht vom Zeichen.

b) Das Beispielwort zerlegt

P2   4   2   7   0 1 2 3 4 5 6 7
^^   ^   ^   ^   ^^^^^^^^^^^^^^^
|    |   |   |   8 Pixelwerte (4 · 2)
|    |   |   Maxval = 7
|    |   Hoehe = 2
|    Breite = 4
Formatkennung

Zuerst kommt das P2, welches das Format angibt. Danach folgen Zahlenwerte, welche immer von einem Leerzeichen getrennt sein müssen.

Daran erkennbare Syntaxregeln:

1. Das Wort beginnt zwingend mit P2 – eine feste Kennung am Anfang
2. Die Reihenfolge ist fest: erst Breite, dann Höhe, dann Maxval, dann die Pixel
3. Die Anzahl der Pixelwerte ist nicht frei, sondern ergibt sich aus Breite · Höhe – hier 4 · 2 = 8
4. Jeder Pixelwert muss zwischen 0 und Maxval liegen
5. Zwischen zwei Bestandteilen steht genau ein Leerzeichen

stateDiagram-v2
    [*] --> P2
    P2 : P2 (Formatkennung)
    Breite : Breite
    Hoehe : Höhe
    Maxval : Maxval (1 bis 255)
    Pixel : Pixelwert (0 bis Maxval)
    P2 --> Breite
    Breite --> Hoehe
    Hoehe --> Maxval
    Maxval --> Pixel
    Pixel --> Pixel : noch nicht Breite · Höhe Werte
    Pixel --> [*] : Breite · Höhe Werte erreicht

Regel 3 ist die bemerkenswerte: ein Teil des Wortes bestimmt, wie lang der Rest sein muss. Das ist bei hallihallo nicht so, dort darf n beliebig groß sein. Hier hängen die Bestandteile voneinander ab.

c) Die vier Wörter untersuchen

Die beiden Fehler im Vergleich

Es sind zwei verschiedene Sorten von Regelverstößen, und genau darum geht es bei der Aufgabe:

Das zweite ist das tückischere. Die Form stimmt vollständig: acht Zeichenbestandteile, alles Ziffern, richtig getrennt, die Anzahl passt. Man muss rechnen beziehungsweise vergleichen, um den Fehler zu finden – 4 ist größer als 3.

Beim ersten Wort reicht Abzählen. Deshalb würde ein einfacher Syntaxprüfer, der nur die Struktur anschaut, das erste Wort ablehnen und das zweite womöglich durchwinken.

d) Syntax und Semantik am Beispiel PGM

Die Syntax sind die Regeln, wie im PGM-Format ein Befehl geschrieben werden muss. Stimmt die Syntax nicht, so kann das Bild semantisch nicht interpretiert werden.

Am Wort P2 2 2 3 0 1 2 gezeigt

Nimmt man dieses Wort aus Teil c): die Syntax ist verletzt, weil ein Pixelwert fehlt. Und damit gibt es keine Bedeutung mehr – das Programm weiß nicht, welche Farbe der vierte Pixel haben soll. Es kann auch nicht raten: soll das Feld schwarz sein, weiß, oder ist vielleicht die Höhenangabe falsch?

Genau das meint der Satz „Stimmt die Syntax nicht, so kann das Bild semantisch nicht interpretiert werden". Die Syntax ist die Voraussetzung für die Semantik. Ohne korrekte Form gibt es nichts zu deuten.

Umgekehrt gilt das aber nicht – und das ist der Unterschied zum Backofen. Dort war Wort B syntaktisch korrekt und trotzdem sinnlos. Bei PGM ist jedes syntaktisch korrekte Wort auch automatisch sinnvoll, weil jede gültige Zahlenkombination irgendein Bild ergibt. Ein Bild aus lauter Nullen ist einfach ein komplett schwarzes Bild – merkwürdig, aber nicht sinnlos.

Das Beispielbild

P2 4 2 7  0 1 2 3 4 5 6 7

ergibt ein 4x2-Bild:

  +---+---+---+---+
  | 0 | 1 | 2 | 3 |     0 = schwarz
  +---+---+---+---+
  | 4 | 5 | 6 | 7 |     7 = weiss (= Maxval)
  +---+---+---+---+

Ein Verlauf von schwarz nach weiss, zeilenweise von links nach rechts.

Der Maxval legt fest, was „ganz hell" bedeutet. Bei Maxval 7 ist die 7 weiß; bei Maxval 255 wäre die 7 fast schwarz. Derselbe Pixelwert bedeutet also je nach Maxval etwas völlig anderes – das ist ein schönes Beispiel dafür, dass die Bedeutung eines Zeichens vom Zusammenhang abhängt.

Zusatzleistung – der Vergleich mit dem echten PGM

Die Vereinfachung mit dem einen Leerzeichen ist übrigens genau die, die unsere Sprache als formale Sprache handhabbar macht. Erlaubte man beliebig viele Whitespaces, müsste man in jeder Regel „ein oder mehrere Trennzeichen" schreiben – und die Wörter wären nicht mehr eindeutig aufschreibbar.