주어진 DTD가 다른 DTD의 서브 세트인지 어떻게 알 수 있습니까?

Question

"단순화 된"DTD가 실제로 더 큰 DTD의 하위 집합임을 확인해야합니다. "단순화 된"DTD에 따라 유효한 문서는 항상 더 큰 (또는 "마스터") DTD에 따라 유효합니다.

이제 단순화 된 DTD가 쓰여지고 있습니다. 마스터 DTD에서 파생되었습니다 (다른 방법으로 작은 DTD를 큰 DTD에 포함시킬 수 있음).

단순화 된 DTD가 마스터 DTD에서 파생되었는지 어떻게 확인할 수 있습니까?

Answer 1

DTD는 실제로 컨텍스트없는 문법입니다. 문법 G는 문법이 나타내는 무명의 언어 L (G)를 구성하는 가능한 법령 집합을 나타냅니다.

당신이 묻는 것은 당신이 G1과 G2를 가졌는지, L (G1)이 L (G2)의 부분 집합인지를 결정하는 것입니다. 제 언어 이론은 녹슬고 있습니다. 일반적으로 계산할 수 있는지 여부는 기억이 나지 않습니다.하지만 내 추측은 어렵습니다. 왜냐하면 G1의 임의 유도가 항상 G2에서 파생된다는 것을 입증해야하기 때문입니다.

G1이 각 요소가 각 요소와 호환된다는 것을 보여줌으로써 L (G1)이 L (G2)의 하위 집합임을 입증 할 수있는 방법으로 G1이 구성되어 있는지 여부에 대한 질문에 대답 할 수 있습니다 G1의 각 문법 규칙 이 G2에서 해당 규칙을 삭제하고 있음을 보여줌으로써 essentialy가 G2의 요소를 삭제합니다. DTD를 diffing한다는 아이디어는이 라인에있는 것처럼 보입니다. 단, diff가 크면 더 단순한 문제가 아닌 일반적인 문제에 얽매어 야합니다. 적어도 당신이 문제를 특징 짓는 방식 (G2는 마스터 DTD에서 파생 된 것입니다.) 나는 당신에게 기회가 있다고 생각합니다. diff의 목적은 가장 적은 차이점을 찾아서 호환 가능한 규칙을 식별하는 것입니다.

문법 규칙 g2 = A; 그리고 당신이 주장하고자하는 또 다른 g1 = A와 확인하고 싶은 을 확인하려면 먼저 G1에서 파생 된 A가 토큰 문자열 A의 상위 집합 인 문자열 토큰임을 입증해야합니다 G2에서. 이것은 두 개의 langauges를 비교하는 원래의 제약되지 않은 문제와 같습니다. 우리는 이제 두 규칙 g1과 g2에 대한 하위 언어를 비교하고 있습니다.

그래서 이제 g1이 도달 할 수있는 각 subrule이 g2의 해당 subrule과 구조적으로 호환 가능해야한다고 주장해야한다고 생각합니다. 아마 이것을 확인하기 위해 재귀 프로 시저를 작성할 수 있다고 생각합니다. 이 프로 시저가 대부분 도움이되는 것은 LALR 파서 생성기에서 찾을 수있는 모든 집합 연산자 (FirstOf, ..)입니다.

다른 측면에서 우리 회사는 말의 요소와 편집 작업에 관한 언어 구성 요소에 대한 델타를 계산하는 Smart Differencer 도구를 만듭니다. 언어 정의에 의해 매개 변수화됩니다. SmartDifference는 현재 다양한 다양한 언어 (C, C++, C#, COBOL, Java, PHP, Python 등)에서 작동합니다. XML (및 DTD)은 언어 정의를위한 언어이기도하며 실험적인 XML Smart Differencer 도구를 구축했습니다. 그것은 DTD에서 잘 작동해야합니다. 나에게 직접적인 관심이있는 경우 오프라인으로 문의하십시오 (바이오를 참조하십시오).

편집 :

orderform : 그냥 싱긋 웃음을 위해, 나는 다음과 같은 두 가지 DTD를, 다른에서 파생 된 하나를 시도했다.XML :

<?xml version='1.0' ?> 
<!DOCTYPE orderform [ 

<!ELEMENT orderform (name,company,address,items) > 
<!ELEMENT name (firstname, lastname)> 
<!ELEMENT firstname (#PCDATA)> 
<!ELEMENT lastname (#PCDATA)> 
<!ELEMENT company (#PCDATA)> 
<!ELEMENT address (street, city, country)> 
<!ELEMENT street (#PCDATA)> 
<!ELEMENT city(#PCDATA)> 
<!ELEMENT country (zipcode | nation)> 
<!ELEMENT zipcode (#PCDATA)> 
<!ELEMENT nation (#PCDATA)> 
<!ELEMENT items (item)+ > 
<!ELEMENT item (partnumber, quantity, unitprice)> 
<!ELEMENT partnumber (#PCDATA)> 
<!ELEMENT quantity (#PCDATA)> 
<!ELEMENT unitprice (#PCDATA)> 
]> 

<done/> 

및 orderform2.xml : 당신이 차이 스스로를 발견 할 수있는 경우

<?xml version='1.0' ?> 
<!DOCTYPE orderform [ 

<!ELEMENT orderform (name,company,location,item) > 
<!ELEMENT name (firstname, lastname)> 
<!ELEMENT firstname (#PCDATA)> 
<!ELEMENT lastname (#PCDATA)> 
<!ELEMENT company (#PCDATA)> 
<!ELEMENT location (street, city, country)> 
<!ELEMENT street (#PCDATA)> 
<!ELEMENT city(#PCDATA)> 
<!ELEMENT country (zipcode | nation)> 
<!ELEMENT zipcode (#PCDATA)> 
<!ELEMENT nation (#PCDATA)> 
<!ELEMENT item (partnumber, unitprice)> 
<!ELEMENT partnumber (#PCDATA)> 
<!ELEMENT quantity (#PCDATA)> 
<!ELEMENT unitprice (#PCDATA)> 
]> 

<done/> 

는 [참조, 첫 번째 :-)

그리고는 XML SmartDifferencer을 실행 :

C:\DMS\Domains\XML\Analyzers\SmartDifferencer\Source>DMSSmartDifferencer XML -SuppressSourceCodeForRenamings C:\DMS\Domains\XML\Tool 
s\DTD2COBOL\orderform.xml C:\DMS\Domains\XML\Tools\DTD2COBOL\orderform2.xml 
Copyright (C) 2009 Semantic Designs; All Rights Reserved 
XML SmartDifferencer Version 1.1.1 
Copyright (C) 2009 Semantic Designs, Inc; All Rights Reserved; SD Confidential 
Powered by DMS (R) Software Reengineering Toolkit 
*** Unregistered SmartDifferencer Version 1.1 
*** Operating with evaluation limits. 

*** Parsing file C:/DMS/Domains/XML/Tools/DTD2COBOL/orderform.xml ... 
*** Parsing file C:/DMS/Domains/XML/Tools/DTD2COBOL/orderform2.xml ... 
*** Creating suffix tree ... 
*** Determining maximal pairs ... 
*** Sorting maximal pairs ... 
*** Determining differences ... 
*** Printing edits ... 
Rename 4.1-9.44 to 4.1-9.45 with 'address'->'location' and 'items'~>'item' 
Delete 15.1-15.25 merging 15.18-15.21 into 4.44-4.47 
<<!ELEMENT items (item)+ > 
Delete 16.30-16.38 merging 16.30-16.38 into 15.18-15.28 with 'quantity'~>'partnumber' 
<        quantity, 

네, 그게 제가 한 일입니다. 그 파생 된 것. (표기법 N.M은 "선 N, 열 M"을 의미 함).