Как переписать эту недетерминированную XML-схему в детерминистскую? - PullRequest
Новая
       69

Как переписать эту недетерминированную XML-схему в детерминистскую?

1 голос
/ 23 декабря 2009

Почему это недетерминировано и как это исправить? 

 <xs:element name="activeyears">
        <xs:complexType>
            <xs:sequence minOccurs="0" maxOccurs="1">
                <xs:sequence minOccurs="0" maxOccurs="unbounded">
                    <xs:element ref="from" minOccurs="1" maxOccurs="1"/>
                    <xs:element ref="till" minOccurs="1" maxOccurs="1"/>
                </xs:sequence>
                <xs:element ref="from" minOccurs="0" maxOccurs="1"/>
            </xs:sequence>
        </xs:complexType>
    </xs:element>

Предполагается, что <activeyears> либо пусто, либо содержит последовательность <from><till>, которая начинается с <from>, но может заканчиваться либо.

Ответы [ 2 ]

7 голосов
/ 24 декабря 2009

Схема является недетерминированной , когда есть две ветви, начинающиеся с одного и того же элемента - так что вы не можете сказать, какую ветвь выбрать, не заглядывая в будущее после этого элемента. Простой пример - ab|ac - когда вы видите a, вы не знаете, какую ветку взять. Для циклов «ветвь» - это повторение цикла или продолжение после него. Примером этого является a*a - когда вы находитесь в цикле и читаете a, вы не знаете, повторить ли цикл или продолжить.

Глядя на вашу примерную схему, представьте, что она только что проанализировала <till>, и теперь ей нужно проанализировать <from>. Вы можете проанализировать его с помощью <from><till> loop или с финальным <from>. Вы не можете сказать, какую ветку использовать, просто взглянув на это <from>. Вы можете сказать только с дальнейшим прогнозом.

Плохие новости: я думаю, что ваша примерная схема очень редкая, что невозможно выразить детерминистически!

Вот XML-документы, которые вы хотите принять (я использую одну букву для каждого элемента, где a = <from>...</from> и b = <to>...</to>: 

*empty*
a
ab
aba
abab
ababa
ababab
...

... вы поняли идею. Проблема в том, что любая буква может быть последней буквой в последовательности или , она может быть частью цикла. Нет никакого способа определить, каким он будет, кроме как заглянуть в следующее письмо. Поскольку «детерминистический» означает, что вы не делаете этого заблаговременно (по определению), нужный вам язык не может быть выражен детерминистически.

Упрощая вашу схему, она использует подход, аналогичный (ab)*a? - но обе ветви начинаются с a. Другой подход - a(ba)*b? - теперь обе ветви начинаются с b. Мы не можем победить!

Технически, набор всех документов, которые принимает схема, называется языком этой схемы . Если не существует детерминированной схемы, способной выразить язык, язык называется «однозначным».

Теоретическое обсуждение см. В серии статей Бруггемана-Кляйна (например, Детерминированные регулярные языки и Однозначные регулярные языки ). Она включает формальный тест для однозначных языков.

0 голосов
/ 23 декабря 2009

Это простое редактирование вашего кода; Я не пробовал это: 

 <xs:element name="activeyears">
        <xs:complexType>
            <xs:sequence minOccurs="0" maxOccurs="1">
                <xs:element ref="from" minOccurs="1" maxOccurs="1"/>
                <xs:sequence minOccurs="0" maxOccurs="unbounded">
                    <xs:element ref="till" minOccurs="1" maxOccurs="1"/>
                    <xs:element ref="from" minOccurs="0" maxOccurs="1"/>
                </xs:sequence>
            </xs:sequence>
        </xs:complexType>
    </xs:element>

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

Итак, конкретные изменения, которые я сделал:

  • Я оставил ваше внешнее sequence без изменений; он контролирует требование "пусто или имеет определенный контент".
  • Если есть контент, он должен начинаться с «from»; так что я сделал это первым element в последовательности, с явным счетчиком вхождений
  • Поскольку я использовал «from» в качестве явного элемента, мне пришлось изменить порядок подпоследовательности.
  • И если вы не хотите указать, что за каждым «до» должен следовать «от», вам нужно ослабить minOccurs в подпоследовательности.
  • В подпоследовательности также обрабатывается случай сингла from / till - как заметил комментатор, мое второе редактирование с minOccurs='0' позволило завершить последовательность из двух «to» s.
...