Montag, November 17, 2008

Syntax und Semantik

Was ist Syntax, was ist Semantik? Diese zwei Begriffe beschäftigen mich immer wieder, siehe zum Beispiel auch "Uniform Syntax" (23. Feb. 2007). Beide Begriffe spielen eine entscheidende Rolle bei jeder Art von maschinell-verarbeitbarer Sprache. Vom Dritten im Bunde, der Pragmatik, will ich an dieser Stelle ganz absehen.

Die Syntax bezieht sich auf die Form und die Struktur von Zeichen in einer Sprache, ohne auf die Bedeutung der verwendeten Zeichen in den Formen und Strukturen einzugehen. Syntaktisch korrekte Ausdrücke werden auch als "wohlgeformt" (well-formed) bezeichnet.

Die Semantik befasst sich mit der Bedeutung syntaktisch korrekter Zeichenfolgen einer Sprache. Im Zusammenhang mit Programmiersprachen bedeutet Semantik die Beschreibung des Verhaltens, das mit einer Interpretation (Auslegung) eines syntaktisch korrekten Ausdrucks verbunden ist.

[Die obigen Begriffserläuterungen sind angelehnt an das Buch von Kenneth Slonneger und Barry L. Kurtz: Formal Syntax and Semantics of Programming Languages -- A Laboratory Based Approach, Addison-Wesley, 1995, Kapitel 1.]

Die Grenze zwischen Syntax und Semantik ist fließend und lässt sich schön am Beispiel mit Hilfe regulärer Ausdrücke erläutern. Spezifizieren wir eine Syntax für die Angabe der Uhrzeit. Gemeint sind minutengenaue Zeitangaben im 24-Stunden-Format.

Ein einfacher regulärer Ausdruck beschreibt die Syntax sehr direkt: "\d\d:\d\d" -- dieser Ausdruck kam schon in der Einführung "Reguläre Ausdrücke" zur Anwendung und ist dort ausführlich beschrieben. Dieser reguläre Ausdruck ist zu allgemein, denn die Angabe "14:72" wäre genauso möglich wie "25:13". Das sind keine Uhrzeitangaben. Ein regulärer Ausdruck, der nur gültige, 4-stellige Zeitangaben erlaubt, ist "([01]\d)|(2[0-3]):[0-5]\d".

Worauf es mir hier ankommt, ist Folgendes: Der erste reguläre Ausdruck spezifiziert eine Uhrzeitsyntax, die so allgemein gefasst ist, dass eine Nachverarbeitung (Teil der Semantik(!)) prüfen muss, ob die Kombination von Stunden und Minutenangaben eine gültige Uhrzeit ist. Der zweite reguläre Ausdruck hingegen erfasst gültige, vierstellige Uhrzeitangaben vollständig syntaktisch. Jegliche Weiterverarbeitung, sprich jegliche Semantik kann sich darauf verlassen, mit ausschließlich gültigen Uhrzeitangaben zu arbeiten.

Wir beobachten an diesem Beispiel, dass es einen Spielraum gibt, was Syntax und was Semantik in einer Sprache ist. Je allgemeiner die Syntax, desto mehr Form- und Strukturwissen muss als Teil der Semantik behandelt werden. Je spezifischer die Syntax ist, desto weniger muss sich die Semantik um eine Erkennung bemühen. Im Idealfall ist die Semantik von aller Klärung befreit, wenn die Syntax eindeutig ist.

Im Fall der Uhrzeit ist es relativ leicht möglich, Uhrzeitangaben vollständig syntaktisch zu spezifizieren. Das geht nicht immer. Nehmen wir Datumsangaben. Eine vollständige syntaktische Spezifikation, welche Monate 30 bzw. 31 Tage haben, ist noch machbar -- ob sie sinnvoll ist, ist die Frage. Denn spätestens für den Monat Februar ist mit regulären Ausdrücken nicht mehr entscheidbar, ob 28 oder 29 Tage die korrekte Angabe sind. Es sind 29 Tage, sofern das Jahr ein Schaltjahr, also durch 4 teilbar ist. Es bleibt jedoch bei 28 Tagen, wenn die Jahreszahl durch 100 teilbar ist, nicht jedoch durch 400. Eine Datumsangabe kann nicht vollständig syntaktisch erkannt werden -- es sei denn, die Syntax hätte Rechenfähigkeiten.

Und damit sind wir genau an dem Punkt angelangt, was Syntax von Semantik unterscheidet: Syntax ist der Anteil einer Sprachdefinition, der gültige Zeichenfolgen einer Sprache erkennt (Form- und Strukturerkennung) und zwar mit einem Formalismus, der keine Rechenfähigkeit hat, sprich, der nicht Turing-äquivalent ist. Dieser syntaktische Anteil liefert die Vorverarbeitung. (In der Theorie der formalen Sprachen sind damit reguläre (Typ-3) bzw. kontextfreie (Typ-2) Grammatiken gemeint, siehe Chomsky-Hierarchie.). Die Semantik betrifft alle weitere Symbol-Verarbeitung, die mit einem Formalismus beschrieben ist, der Turing-äquivalent ist.

Mit diesem Verständnis von Syntax und Semantik kann man sinnvoll den Begriff der syntaktischen Obergrenze definieren: Die syntaktische Obergrenze reizt die Form- und Strukturerkennung aus und minimiert den semantischen Anteil, der eventuell notwendig ist, um die Erkennung von Formen und Strukturen eindeutig zu machen. Zum Beispiel beschreibt ein regulärer Ausdruck die syntaktische Obergrenze für eine Datumsangabe im Format "Tag-Monat-Jahr" (TT-MM-JJJJ), wenn semantisch einzig die Tagesangabe für den Februar überprüft werden muss. Das Muster "\d\d-\d\d-\d\d\d\d" liegt offensichtlich nicht an der syntaktischen Obergrenze. Der Semantik-Anteil muss umfangreiche Gültigkeitsprüfungen vornehmen.

Man kann in diesem konkreten Beispiel auch auf einen Formalismus für die Syntax zurückgreifen, der zwar Rechenfähigkeiten hat, in seinem Verarbeitungshorizont jedoch strikt begrenzt ist. Dann liegt eine kontextsensitive Grammatik vor (Typ-1). Kontextsensitive Grammatiken sind eher die Ausnahme. (Anmerkung: Grundsätzlich ist auch ein Formalismus für die Syntax denkbar, der Turing-äquivalent ist (Typ-0), allerdings fällt dann die Grenzziehung zwischen Syntax und Semantik schwer. Ein anderes Kriterium muss dann gefunden werden.)

Meine These ist, dass diese Zerlegung einer Verarbeitung in einen Anteil, der aus einem nicht Turing-äquivalenten Mechanismus und einem Turing-äquivalenten Mechanismus besteht, ein stets wiederkehrendes Thema in der Informatik ist. Pipe-Filter-Architekturen sind ein Beispiel, die Zerlegung eines Programms in Interfaces und Verhalten ein anderes. Interessanterweise habe ich bislang keinen Hinweis darauf gefunden, dass dieses Zerlegungsmuster bereits von jemand anderem postuliert worden wäre. Ich glaube, man könnte dieses Zerlegungsmuster sehr viel systematischer in der Software-Entwicklung einsetzen.

Ein Anmerkung, siehe im vorletzten Absatz, ist hinzu gekommen, um die Diskussion etwas abzurunden. (2008-11-18)

Dienstag, November 04, 2008

Studieren mit der PS3


Ungefähr 1000 PS3-Spielkonsolen dürften in etwa der Rechenleistung unseres Gehirns gleichkommen. Vielleicht ist das eine gewagte Schätzung, so ganz seriös sind solche Computer/Hirn-Vergleiche nie. Aber wer als "Niko" Bellic in die Welt von GTA IV eintaucht, dem wird diese Zahl vermutlich gar nicht so abwegig vorkommen. Es ist unglaublich, wieviel Welt so eine Spielkonsole simulieren kann.

In der PS3 leistet ein Spezialprozessor, der Cell-Chip, diese beachtliche Arbeit. Ein etwa 10 Jahre altes Rechenzentrum im Schachtelformat. Mehrere Einheiten arbeiten parallel und fressen Zahlen, was das Zeug hält.

Es hat eine ganz eigene Faszination, wenn man Linux auf die PS3 installiert und sich die Konsole zum ersten Mal meldet. Man hat Kontakt mit dieser geballten Rechenkraft aufgenommen. Plötzlich gehorcht sie einem aufs Wort. Und irgendwie hört man die Maschine nach Arbeit rufen. Das bisschen Linux, die paar Befehle, die über die Konsole reinwandern, die machen so ein Maschinchen nicht müde. Da steht ein Apparat, der es gewohnt ist, Sie durch Häuserschluchten zu jagen, Ihnen Aliens aufzuhetzen, Sie unter Beschuss zu nehmen und Ihnen wilde Verfolgungsjagden zu liefern. Diese Maschine hat Hunger! Diese Maschine sucht die Herausforderung und die Auseinandersetzung!

Nehmen Sie die Herausforderung an?

Geben Sie der Maschine Futter, programmieren Sie die PS3 selbst! Jagen Sie die PS3 mit Ihren Programmen an den Rand des Machbaren! Fangen Sie da an, wo der PC schlapp macht!

Einen Start bietet Ihnen unsere Webseite http://ps3.hs-heilbronn.de.