Gibt es einen Algorithmus, um festzustellen, ob der Satz aller gültigen XML -Instanzen in Bezug auf ein bestimmtes XSD -Schema eine reguläre Sprache ist oder nicht?

Question

Im Wesentlichen möchte ich wissen, ob ein bestimmtes XSD -Schema durch einen regulären Ausdruck ersetzt werden kann oder nicht. Ich weiß, dass die XML-Schema-Sprache XSDs produzieren kann, deren Satz gültiger XML-Instanzen von jeder Art von Sprache (sogar kontextempfindlich) sein kann. Ich möchte die Schemata identifizieren, die "regex-äquivalent" sind. Ich hatte diese Frage, nachdem ich das folgende Problem angesprochen hatte:

Ich musste ein bestimmtes Textformat analysieren und ausprobiert zuerst reguläre Ausdrücke und ich sah, dass Regexp ausreicht, um es zu analysieren. Ich wollte dann eine XML -Darstellung für die Nachrichten vornehmen, die ich in diesem Format erhalten habe, also habe ich Regex -Gruppen mit XML -Elementen abgebildet. Ich habe dann manuell ein XSD -Schema erstellt, das auf der Struktur des Regex basiert. Am Ende hatte ich ein Schema, das meine Regex in dem Sinne ersetzen konnte, dass der ursprüngliche Regex aus dem Schema konstruiert werden konnte. Ich habe es auch geschafft, das Gegenteil zu tun: Erstellen Sie das Schema automatisch aus dem Regex. So konnte ich die Nachricht in XML umwandeln und sie gleichzeitig validieren. Meine Fragen sind:

1. Kann jeder Regex durch ein XSD -Schema dargestellt werden? (Ich meine, ein Regex, um ein XSD -Schema produzieren zu können)

2. Gibt es bei einem willkürlichen XSD -Schema eine Möglichkeit, festzustellen, ob es eine Regex gibt, deren Darstellung das gegebene Schema ist?

   Bearbeiten: Wahrscheinlich ist die Antwort auf die erste Frage Ja, da ich es mit meinem Regex auf eine Weise getan habe, die nicht von der spezifischen Regex abhing (Dies ist kein Beweis für jeden Regex).

Answer 1

Die XML-Schema-Sprache ist eine super eingestellte reguläre Sprachen, aber natürlich nur innerhalb der Domäne von XML-Dokumenten.

Für Nr. 1: Mit der zusätzlichen Bedingung, dass der Regex mit einem gut geformten XML-Dokument übereinstimmt und sonst nichts, ja.

Für #2: Ja, es geht darum, nach Funktionen von XSD zu überprüfen, die in einer regulären Sprache erlaubt sind. Der reguläre Ausdruck zu finden wäre viel mehr Arbeit.

Eine reguläre Sprache hat informell eine ziemlich einfache Definition:

• Die leere Menge/Zeichenfolge
• Literale (eine "Singleton -Sprache"), z. B. "x"
• Für eine reguläre Sprache A ist A* auch eine reguläre Sprache
• Für die regulären Sprachen A und B sind A | B (Union) und AB (verkettet) regelmäßig.

Grundsätzlich sind alle Verkettungen und Alternativen in Ordnung, aber die Rekursion ist unmöglich und es gibt keine Rückenreferenzen oder "Gedächtnis". Kein Elementtyp kann enthalten choice/all/element Elemente, die sich selbst oder übergeordnete Typen beziehen, und Sie können keine Informationen verwenden, die Sie früher im Analyseprozess gefunden haben.

Die Einschränkung der Rekursion erstreckt sich auf die any Element, das verboten wäre. Per Definition akzeptiert es jedes Element, einschließlich Elemente mit Unterelementen. Da Sie die Nisttiefe dieses unbekannten Elements nicht kennen, benötigen Sie ein rekursives Muster, um sie zu entsprechen, und das können Sie nicht in einer regulären Sprache tun.

Die Einschränkung der Rückverweise bedeutet, dass Sie Dinge wie "eine Anzahl von 'a' nicht tun können, gefolgt von der gleichen Anzahl von 'b'" (a {n} b {n}). Ich denke nicht, dass dies in XSD überhaupt möglich ist, zumindest kann ich nicht denken, wie Sie es tun würden.

Die Einschränkung der numerischen Werte (z. B. Mininclusive) wäre in einer Regex nicht möglich.

Das all Element wäre insofern problematisch, als es alle möglichen Bestellung von untergeordneten Elementen akzeptieren müsste, wodurch der Regex exponentiell erweitert werden müsste (Binomialkoeffizient, (N/K)^k <= n!/k! (nk)! <= <= (ne/k)^k) mit der Anzahl der Kinderelemente, und die Übereinstimmung mit dem Regex ist auf dieser Länge superlinear. Das Erkennen von Attributen leidet unter demselben Problem, da die Reihenfolge von Attributen innerhalb eines Elements nicht durch das Schema eingeschränkt wird. Wenn Sie sich nur darum kümmern, ob eine Regex existiert und nicht, es zu finden, dann spielt es keine Rolle.