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

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

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

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

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

    EDIT: Вероятно, ответ на 1-й вопрос - да, поскольку я сделал это с моим регулярным выражением таким образом, который не зависел от конкретного регулярного выражения (это не доказательство для каждого регулярного выражения).


regex xsd regular-language formal-languages
person Paralife    schedule 31.01.2011    source источник

Ответы (1)


arrow_upward
1
arrow_downward

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

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

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

Регулярный язык имеет довольно простое неофициальное определение:

  • Пустой набор/строка
  • Литералы («одноэлементный язык»), например, «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!(n-k)! ‹= (ne/k)^k) с количеством дочерних элементов, и соответствие регулярному выражению является суперлинейным по этой длине. Распознавание атрибутов страдает от той же проблемы, поскольку порядок атрибутов внутри элемента не ограничивается схемой. Конечно, если вас интересует только существование регулярного выражения, а не его поиск, то это не имеет значения.

person Tim Sylvester    schedule 28.03.2011
comment
all будет в порядке в том случае, когда фактически разрешено произвольное количество каждого элемента в любом порядке. Это соответствует замыканию Клини чередования, с которым RE прекрасно справляются, и это конструкция, которую я довольно часто вижу в схемах в наши дни. - person Donal Fellows; 29.03.2011
comment
@Donal Fellows - это только в том случае, если у вас есть <all minOccurs="0" maxOccurs="unbounded", что может быть разрешено некоторыми процессорами, но технически недопустимо. Согласно спецификации, индикатор all должен иметь minOccurs=0|1 и maxOccurs=1, чтобы каждый элемент мог встречаться не более одного раза. См. w3schools.com/schema/el_all.asp. - person Tim Sylvester; 29.03.2011
comment
На самом деле вы получаете неограниченную последовательность этих 0/1 всех. - person Donal Fellows; 30.03.2011