All geek questions in one place

Is there an algorithm to determine if the set of all valid XML instances for a particular XSD schema is a regular language or not?

Essentially, I want to know if a particular XSD schema can be replaced with a regular expression or not. I know that the XML Schema language can create XSD, the set of valid XML instances can be any type of language (even context-sensitive). I want to identify those patterns that are equivalent to regular expressions. I asked this question after solving the following problem:

I needed to parse a specific text format, and I first tried regular expressions, and I saw that the regular expression is enough to parse it. Then I wanted to create an XML view for messages received in this format, so I displayed regular expression groups with XML elements. Then I manually created an XSD schema based on the regular expression structure. In the end, I had a circuit that could replace my regular expression in the sense that the original regular expression could be built from a circuit. I also managed to do the opposite: automatically create a schema from a regular expression. So I could convert the message to XML and check it at the same time. My questions:

  • Can any regular expression be represented by an XSD schema? (I mean that with regular expression you can create an XSD schema)

  • For an arbitrary XSD scheme, is there a way to determine if there is a regular expression whose representation is this scheme?

    EDIT: Probably the answer to the first question is yes, since I did it with my regular expression so that it was not dependent on a particular regular expression (this is not proof for every regular expression).

+3
source share
1 answer

An XML schema language is a super-set of regular languages, but only within an XML document domain, obviously.

# 1: , XML- , .

# 2: , XSD, . .

, :

  • /
  • ( "singleton language" ), "x"
  • A, A *
  • A B, A | B () AB () .

, , , "". choice/all/element, , - , .

any, . , . , , .

, , " " A ", " B "(A {n} B {n}). , XSD, , , , .

(, minInclusive) .

all , , ( , (n/k) ^ k <= n!/k! (nk)! <= (ne/k) ^ k) , . , . , , , .

+1

Source: https://habr.com/ru/post/1788954/

More articles:


All Articles