如何確定給定的DTD是否爲另一個子集？

Question

我需要驗證一個「簡化」的DTD實際上是一個更大的DTD的一個子集，即.e.e.根據「簡化」DTD有效的文檔也將根據較大（或「主」）DTD始終有效。

現在正在編寫簡化的DTD--它是從主DTD派生出來的（反過來，可以簡單地將較小的DTD包含到較大的DTD中）。

如何才能確定簡化的DTD是否來自主DTD？

Answer 1

DTD實際上只是上下文無關的僞裝語法。語法G表示一組可能的合法字符串，其包含語法所代表的未表示的語言L（G）。

你所問的無異於判斷你是否有G1和G2，無論L（G1）是否是L（G2）的一個子集。我的語言理論變得生疏，我不記得這是否一般可以計算，但我的猜測是非常困難的，因爲你必須證明G1中的任意派生總是有G2的派生。

您可以通過證明G1中的每個元素都與每個元素兼容來回答G1是否以這樣的方式構建的問題，即您可以證明L（G1）是L（G2）的子集通過顯示G1中的每個語法規則 在G2中具有對應的規則並且丟棄了元素，本質上是重要的。你對DTD的區分似乎是沿着這條線的，條件是如果差異很大，你就會陷入一般問題而不是簡單問題。至少你問題的特徵（G2是從主DTD派生的）我認爲你有機會。 差異的目的是通過查找最小差異來確定兼容規則。

如果你有語法規則g2 = A;和另一個你聲稱與之相關的g1 = A，你想檢查的 ， 你首先必須證明在G1中派生出來的字符串標記是字符串A的超集 在G2。這看起來就像是比較兩種語言的原始不受限制的問題;我們現在只是比較兩個規則g1和g2的子語言。

所以現在我認爲你必須堅持g1可達到的每個子規則與g2中的相應子規則在結構上是兼容的，這樣才能實用。 我想你可以寫一個遞歸的程序來檢查這個。這個過程最需要幫助的是你傾向於在LALR解析器生成器中找到的所有集合運算符（FirstOf，..）。

在另一方面，我公司製作Smart Differencer工具，根據語言元素和這些元素的編輯操作計算語言結構上的增量。它由語言定義進行參數化。 SmartDifference目前適用於各種常規語言（C，C++，C＃，COBOL，Java，PHP，Python，...）。 XML（和DTD）也是一種語言，爲此我們有一個語言定義，並且我們已經構建了一個實驗性的XML Smart Differencer工具。它應該在DTD上工作得很好。如果您有更直接的興趣，請與我聯繫（請參閱bio）。

編輯：只是爲了笑着，我嘗試了以下兩個的DTD，從另一個派生：

orderform。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」）。