비 결정적 XML 스키마를 결정적으로 다시 작성하는 방법?

Question

왜 이것이 비 결정적이며이를 수정하는 이유는 무엇입니까?

<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>로 시작하지만 중 하나에 끝낼 수 <from><till>의 순서를 포함 뜻한다.

Answer 1

스키마는 같은 요소로 시작하는 두 가지가있는 경우 비 결정적입니다. 간단한 예제는 ab|ac입니다. a이 표시되면 어떤 분기를 사용해야할지 알 수 없습니다. 루프의 경우 "분기점"은 루프를 반복할지 또는 그 후에 계속할지 여부입니다. 예를 들면 a*a입니다. 루프를 반복하고 a을 읽으면 루프를 반복할지 또는 계속할지 모를 수 있습니다.

예제 스키마를 보면 방금 <till>을 구문 분석했으며 이제는 <from>을 구문 분석해야한다고 상상해보십시오. <from><till> 루프 또는으로 끝 부분을 <from>으로 파싱 할 수 있습니다. <from>을 보면 어떤 분기를 사용할 지 알 수 없습니다. 앞으로 나아갈 방향으로 만 말할 수 있습니다.

---

나쁜 소식 : 나는 그것을 결정 론적으로 표현하는 불가능 것을, 당신의 예제 스키마는 매우 드문 일이라고 생각!여기

는 (내가 a = <from>...</from> 및 b = <to>...</to> 각 요소에 대한 단일 문자 사용하는데 동의 할 XML 문서입니다.

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

... 당신은 아이디어를 얻을를 문제는 모든 문자가 시퀀스의 마지막 문자가 될 수 있다는 것입니다. 또는 루프의 일부가 될 수 있습니다. 다음 문자를 미리보아야한다는 것을 제외하고는 어떤 문자인지 알 수있는 방법이 없습니다. 이 선견지명 (정의에 의한)을하지 않으면, 원하는 언어를 결정 론적으로 표현할 수 없습니다.

스키마를 단순화하면 (ab)*a?과 비슷한 방식으로 시도하지만 두 분기는 모두 a으로 시작합니다. 또 다른 접근 방식은 a(ba)*b?입니다. 이제 두 가지 브랜치가 모두 b으로 시작됩니다. 우리는 이길 수 없어!

기술적으로 스키마에서 허용 할 모든 문서 집합을 해당 스키마의 언어이라고합니다. 언어를 표현할 수있는 결정적인 스키마가 없으면 언어을 "1 개의 모호한"이라고합니다. 이론적 논의

는 Bruggemann - 클라인 논문 시리즈 표시 (예 Deterministic Regular LanguagesOne-Unambiguous Regular Languages와 ). 그녀는 모호하지 않은 언어에 대한 공식 테스트를 포함합니다.

Answer 2

이것은 간단한 코드 편집입니다.

<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을 완화해야합니다.
• 하위 시퀀스도 단일/대일의 대/소문자를 처리합니다. 주석 기자가 언급했듯이 minOccurs='0'을 사용한 두 번째 편집은 두 개의 "종료"시퀀스의 종료를 허용했습니다. 당신이 그 요소 (으) 보지 않고 응시하는 지점 말할 수 있도록 -