XML Schema kontextfrei?

Wissenschaft Informatik
#1

Hallo,

ich bin grad am lernen für die Abschlußprüfung und da wird öfters mal gefragt (Prüfung über Elektronisches Publizieren, XML, …) ob DTD und XML Schema kontextfrei sind.

Bei DTD steht zumindest in den Vorlesungsunterlagen, dass es kontextfrei ist. Ich bin mir aber nicht sicher ob meine Begründung richtig ist:
Für eine kontextfreie Grammatik gilt dass links immer ein Nichtterminal und rechts beliebiges (Terminal, Nichtterminal, beides, nichts) steht. Wenn man jetzt für XML die Elemente als Nichtterminale, und #PCDATA oder #CDATA als Terminal nimmt, und die DTD-Elementdefinitionen als Regeln der Grammatik interpretiert stehen als xxx immer Elementnamen (und somit Nichtterminale) auf der linken Seite (da yyy das angibt was xxx enthalten darf) und yyy kann dann eben ein Ausdruck über Elementnamen, #PCDATA etc. sein.
Ist das einigermaßen korrekt so? Oder gehts gar noch einfacher zu erklären?

Wie ist das aber dann bei XML Schema? Google findet da mal, dass es kontextfrei ist, und mal dass es eben nicht kontextfrei ist.
Und warum ist es dann (nicht) kontextfrei?

Vielen Dank,
Tobi

#2

Hallo,

ich bin grad am lernen für die Abschlußprüfung und da wird
öfters mal gefragt (Prüfung über Elektronisches Publizieren,
XML, …) ob DTD und XML Schema kontextfrei sind.

Kontextfreie Spreachen erlauben es schon mal gar nicht so etwas wie AA zu erkennen, wobei A ein beliebig langes Wort ist. Wenn also XML beliebig lange Tag-Namen erlaubt ist es schon aus diesem Grund nicht Kontextfrei (weil man damit nicht überprüfen kann, ob Tags korrekt verschachtelt sind).

HTH,
Moritz

#3

ich bin grad am lernen für die Abschlußprüfung und da wird
öfters mal gefragt (Prüfung über Elektronisches Publizieren,
XML, …) ob DTD und XML Schema kontextfrei sind.

Hallo Tobi,

das ist eine interessante Fragestellung!

Wenn es beliebig viele Tagnamen gibt, dann ist XML nicht kontextfrei. Dies läßt sich mit dem Odgens Lemma zeigen.

Auf die Länge der Tagnamen kommt es hierbei nicht an, sondern nur, das es belibig viele sind.

Falls aber das spezielle XML-Dateiformat nur konstant viele Tagnamen enthält, dann läßt sich hierzu eine kontextfreie Grammatik angeben. (z.B. Zu jedem Tagnamen wird ein Nicht-Terminal eingeführt, das diesen Tagnamen erzeugt)

Die Frage ist also vielmehr, ob zum Zeitpunkt der Compilierung des XML-Parsers alle Tagnamen bekannt sind, oder aber erst zur Laufzeit erzeugt werden. Für die meisten Dateiformate müßte ersteres eigentlich geben sein.

Also: Ein XML mit konstant-gesetzten Tagnamen ist kontextfrei.

Dein Lösungansatz, die XML-Definitionen in Produktionsregeln zu überführen, ist auf jeden Fall richtig.

Grüße
Thorsten

#4

Hallo,

Die Frage ist also vielmehr, ob zum Zeitpunkt der Compilierung
des XML-Parsers alle Tagnamen bekannt sind, oder aber erst zur
Laufzeit erzeugt werden.

Richtig.

Für die meisten Dateiformate müßte
ersteres eigentlich geben sein.

Wenn man ein Schema dafür hat, ja. Aber weiss man das vorher auch fürs Schema?
Das ist der Punkt, an dem mich mein XML-Wissen verlässt.

Also: Ein XML mit konstant-gesetzten Tagnamen ist kontextfrei.

Agreed.

Grüße,
Moritz

#5

Hi,

danke schon mal für die Antworten… zum weiteren Verständnis:

Also: Ein XML mit konstant-gesetzten Tagnamen ist kontextfrei.

Agreed.

d.h. mit DTD bzw. XML-Schema definiere ich ja die gültigen Tags und somit stellen DTD/XML-Schema kontextfreie Grammatiken dar, da sie mir einen endlichen Tagvorrat vorgeben?

Jetzt hab ich auf Wikipedia noch was zu kontextfreien Sprachen gelesen, das mich stutzig macht:

„Grenzen der kontextfreien Sprachen liegen bei kontextrelevanten Eigenschaften, wie z. B. der Typüberprüfung in Programmiersprachen, die sich nur durch kontextsensitive Grammatiken darstellen lassen.“

da ich mit XML-Schema auch Datentypen definieren kann (aber mit DTD nicht) wäre dann XML-Schema doch nicht kontextfrei?

Eine andere Überlegung von mir ist, dass XML ja in erster Linie korrekt geklammert/geschachtelt sein muss, was wiederum für kontextfreie-Grammatiken spricht…

#6

Hi,

„Grenzen der kontextfreien Sprachen liegen bei
kontextrelevanten Eigenschaften, wie z. B. der Typüberprüfung
in Programmiersprachen, die sich nur durch kontextsensitive
Grammatiken darstellen lassen.“

da ich mit XML-Schema auch Datentypen definieren kann (aber
mit DTD nicht) wäre dann XML-Schema doch nicht kontextfrei?

auch mit DTD kannst du Datentypen definieren, allerdings nicht so viele verschiedene (ID, IDREF, NTOKEN, …). Wenn du jetzt eine DTD mit ID/IDREF-Beziehungen hast, hast du ein Problem: Die so beschriebene Sprache (Teilmenge aller XML-Dokumente) ist dann nicht mehr kontextfrei: Jeder Wert eines IDREF-Attributs darf nur einen Wert haben, der irgendwo im Dokument als Wert eines ID-Attributs vorkommt; und diese Eigenschaft lässt sich nicht durch eine kontextfreie Grammatik beschreiben.

Denselben Fall kannst du mit einem XML-Schema konstruieren. Wenn man mal von solchen Arten von Beziehungen absieht, kann ein XML-Schema ein Modellierungselement enthalten, das in DTDs nicht möglich ist, nämlich , mit dem Elemente mit beliebigen Namen zugelassen werden. Das wäre dann das Argument gegen Kontextfreiheit, das hier schon diskutiert wurde.

Davon abgesehen denke ich, dass du bei Aussagen wie „DTD/XML-Schema ist kontextfrei“ aufpassen musst, was du wirklich meinst. Jede einzelne DTD und jedes XML-Schema-Dokument stellt eine Grammatik dar und definiert eine eigene Sprache, die kontextfrei sein kann oder auch nicht. (Und ich behaupte mal, dass sowohl bei DTDs als auch XML-Schemas beide Fälle auftreten können.)

Viele Grüße,

Andreas