Существует ли алгоритм для определения, является ли набор всех допустимых экземпляров XML в отношении конкретной схемы XSD регулярным языком или нет? - PullRequest
Новая
       32

Существует ли алгоритм для определения, является ли набор всех допустимых экземпляров XML в отношении конкретной схемы XSD регулярным языком или нет?

3 голосов
/ 31 января 2011

По сути, я хочу знать, может ли конкретная схема XSD быть заменена регулярным выражением или нет. Я знаю, что язык XML Schema может создавать XSD, чей набор допустимых экземпляров XML может быть любого типа языка (даже контекстно-зависимый). Я хочу идентифицировать те схемы, которые "эквивалентны регулярному выражению". Я пришел к этому вопросу после решения следующей проблемы:

Мне нужно было проанализировать определенный текстовый формат, и я сначала попробовал регулярные выражения, и я увидел, что регулярного выражения достаточно для его анализа. Затем я хотел создать представление XML для сообщений, которые я получил в этом формате, поэтому я сопоставил группы регулярных выражений с элементами XML. Затем я вручную создал схему XSD на основе структуры регулярного выражения. В конце концов, у меня была схема, которая могла заменить мое регулярное выражение, в том смысле, что исходное регулярное выражение можно было построить из схемы. Мне также удалось сделать обратное: создать схему автоматически из регулярного выражения. Таким образом, я мог бы преобразовать сообщение в XML и проверить его одновременно. Мои вопросы:

  1. Может ли каждое регулярное выражение быть представлено схемой XSD? (Я имею в виду, учитывая регулярное выражение для создания схемы XSD)

  2. Учитывая произвольную схему XSD, есть ли способ определить, существует ли регулярное выражение, представлением которого является данная схема?

    РЕДАКТИРОВАТЬ: Вероятно, ответ на 1-й вопрос - да, так как я сделал это с моим регулярным выражением способом, который не зависел от конкретного регулярного выражения (это не доказательство для каждого регулярного выражения).

1 Ответ

1 голос
/ 29 марта 2011

Язык XML-схемы - это супернабор обычных языков, но, очевидно, только в области XML-документов.

Для # 1: с дополнительным условием, что регулярное выражение соответствует правильно сформированному XML-документуи ничего больше, да.

Для # 2: да, это вопрос проверки любых возможностей XSD, которые разрешены на обычном языке.Найти регулярное выражение было бы намного труднее.

Обычный язык имеет довольно простое определение, неофициально:

  • Пустое множество / строка
  • Литералы (a"singleton language"), например, "x"
  • Для обычного языка A, A * также является обычным языком
  • Для обычных языков A и B, A | B (union) иAB (сцепленные) являются регулярными.

В принципе, все объединения и чередования в порядке, но рекурсия невозможна, и нет обратных ссылок или «памяти».Ни один тип элемента не может содержать choice / all / element элементов, ссылающихся на себя или родительские типы, и вы не можете использовать любую информацию, найденную ранее в процессе анализа.

Ограничение нарекурсия распространяется на элемент any, что было бы запрещено.По определению он принимает любой элемент, включая элементы с подэлементами.Поскольку вы не знаете глубину вложения этого неизвестного элемента, вам нужен рекурсивный шаблон для сопоставления с ним, и вы не можете сделать это на обычном языке.

Ограничение обратных ссылок означает, что вы можете 't делать такие вещи, как «некоторое число« A », за которым следует такое же количество« B »» (A {n} B {n}).Я не думаю, что это даже возможно в XSD, однако, по крайней мере, я не могу думать, как бы вы это сделали.

Ограничение числовых значений (например, minInclusive) было бы невозможно в регулярном выражении.

Элемент all был бы проблематичным в том смысле, что ему пришлось бы принимать все возможные упорядочения дочерних элементов, что заставило бы регулярное выражение расширяться экспоненциально (биномиальный коэффициент, (n / k) ^ k <= n!/ k! (nk)! <= (ne / k) ^ k) с количеством дочерних элементов, и соответствие регулярному выражению является суперлинейным на этой длине.Распознавание атрибутов страдает той же проблемой, поскольку порядок атрибутов внутри элемента не ограничен схемой.Конечно, если вы заботитесь только о том, существует ли регулярное выражение, а не о его нахождении, тогда это не имеет значения. </p>

...