如何确定给定的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”）。