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)

Kommentare:

Michael Lehr hat gesagt…

Herrlich - da googelt man ein bißchen, um sich nochmals genauer über die Begriffe zu informieren - und wo landet man wieder? Richtig: Bei Ihnen im Blog :)

Grüße von einem lernenden Studenten

Patrick O. hat gesagt…

Vielen Dank für diese hervorragende Erläuterung. Auch ich bin Student und habe mich in Google etwas umgesucht, um schließlich hier auf Ihrem Blog zu "landen". :)

Habe etwas gelernt. Dafür bedanke ich mich! ^^

LG
Patrick

dh hat gesagt…

Das wiederum freut mich! Danke für das positive Feedback!

BastelDD hat gesagt…

Hallo, danke für die tollen ausführungen ich neuer 1. sem student in Dresden. Und habe zu den fragen meines Dozenten ein wenig schwierigkeiten.

Dank Ihnen konnte ich ein wenig mehr verstehen....
Hier die Frage:

Erläutern Sie kurz den Zusammenhang zwischen Semantik und syntaktischer Informationsverarbeitung,
verwenden Sie die Begriffe Prozess, System, Operand, Struktur, Datenfluss, Programm, Datenstruktur, Algorithmus, Funktion.

Dazu haben wir folgendes PDF siehe Anhang erhalten..


Ich habe erstmal angefangen Semantik und Syntax allgemein zu formulieren und mich dann an die Begriffe zu wagen jedoch bin ich mir da mehr als unsicher

Meine Ansätze
Syntax und Semantik:
Die Syntax ist die Grammatik für Programmiersprachen. Dabei bezieht sie sich auf die Form und Struktur von Zeichen/Objekten (Struktur= Anorndung von objekten, die untereinander in beziehung stehen)

Während die Semantik sich mit mit der Bedeutung syntaktisch korrekter Zeichenfolgen einer Sprache befasst.


Ich kann jetzt irgendwie die Begriffe schlecht verpacken...

Ein Programm ist ein Algorithmus formuliert in einer Programmiersprache,

Der Prozess: dieser Formulierung ist die Programmierung (also die Programmiersprache) (Definition Prozess im unterricht: zeitllich ablaufender Vorgang; speziell Transformation von von Eingangsoperanden über zwischenoperanden in Ausgangsoperanden)

System: ist der Träger eines Prozesses , somit ist das System die Programmierung???

Semantik ist auch durch Funktionen darstellbar, dabei sind Semantik und Funktion Synonyme für Prozesse. Daber ist das Sytem der Operator (ein träger von prozessen)

Die semantische Richtigkeit nimmt von steuerfluss über datenfluss zur Logik hinzu...

Der Prozeß dieser Formulierung ist die Programmierung, die Formulierungssprache also die Programmiersprache. Die Verarbeitung eines "formulierten" bzw. kodierten Programmes zeigt die folgende Abbildung:


Bin für jede Hilfe/Input dankbar

vg
Sebatian

Anonym hat gesagt…

Bin gerade dabei für meine Prüfung:

"Künstliche Intelligenz" zu lernen und wollte mir die 2 Begriffe nochmal genauer anschauen.
Vor allem in Bezug auf die Ableitung und Kalkül.

WB |= Q und WB|-Q kommen die 2 Begriffe semantisch und syntaktisch vor.

Danke für die gute Erklärung in ihem Blog

Unknown hat gesagt…

Auch ich lerne gerade für meine Prüfungen und landete ebenfalls hier im Blog. Vielen Dank für diese Erklärung

Anonym hat gesagt…


Gute Erklärung:
"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."
Auf dieselbe Thematik stiess ich bei der Definition von Whitebox- vs Blackbox-Testing:
Vereinfachtes Beispiel: Wenn man als Tester nicht weiß, ob ein Eingabe-Datumsfeld als String, int.int.int oder Date implementiert ist, muss man - neben den eigentlichen fachlichen/ semantischen Prüfungen für das Datumsfeld - ebenfalls prüfen, ob überhaupt nur gültige Datümer erfasst werden können. Der Unkenntnis über die verwendeten Datentypen enstpricht in diesem Fall dem mangelnden Wissen über die Syntax. Und in diesem Fall sind dann die Grenzen zwischen BlackBox- und WhiteBox-Testing nicht klar definierbar. Hört sich an wie ein Witz, aber tatsächlich hatten unsere drei bei Projektstart unabhängigen Entwicklerteams die Datentypen im allgemeinen nicht einheitlich definiert.

dh hat gesagt…

Ein sehr schöner und sehr zutreffender Vergleich. Danke für diese Ergänzung.