Comment puis-je déterminer si une DTD donnée est un sous-ensemble d'une autre?

Question

Je dois vérifier qu'une DTD "simplifiée" est vraiment un sous-ensemble d'une DTD plus grande, par exemple. les documents qui sont valides selon la DTD "simplifiée" seront également toujours valides selon la DTD la plus grande (ou "maîtresse"). La DTD simplifiée est en cours d'écriture - elle est dérivée de la DTD maître (dans l'autre sens, on pourrait simplement inclure la DTD la plus petite dans la DTD principale).

Comment serais-je en mesure de déterminer si la DTD simplifiée est dérivée de la DTD maître?

Answer 1

Les DTD sont vraiment des grammaires sans contexte déguisées. Une grammaire G représente l'ensemble des chaînes légales possibles qui composent le langage non déclaré L (G) que représente la grammaire. Ce que vous demandez équivaut à déterminer si vous avez G1 et G2, si L (G1) est un sous-ensemble de L (G2). Ma théorie de la langue se rouille et je ne me souviens pas si cela est calculable en général ou pas, mais je suppose que c'est très difficile, car vous devez démontrer qu'une dérivation arbitraire dans G1 a toujours une dérivation dans G2. Vous pourriez être en mesure de répondre à la question de savoir si G1 est structuré de telle sorte que vous pouvez démontrer que L (G1) est un sous-ensemble de L (G2) en démontrant que chaque élément de G1 est compatible avec chaque élément de G2, essentiellement en montrant que chaque règle de grammaire dans G1 a une règle correspondante dans G2 avec des éléments abandonnés. Votre idée de différences DTDs semble être le long de cette ligne, à condition que si les différences sont grandes, vous êtes coincé avec le problème général plutôt que le plus simple. Au moins la façon dont vous avez caractérisé le problème (G2 est dérivé de la DTD maître), je pense que vous avez des chances. Le but de la diff serait d'identifier les règles compatibles en trouvant les moindres différences.

Si vous avez la règle de grammaire g2 = A; et un autre g1 = A que vous allèguez être lié et que vous voulez vérifier, vous devez d'abord démontrer que les jetons de chaîne A dérivés de G1 sont un surensemble de la chaîne de jetons A en G2. Cela ressemble au problème original non contraint de comparer deux langages; nous ne faisons que comparer les sous-langages pour les deux règles g1 et g2. Donc maintenant je pense que vous devez insister sur le fait que chaque sous-graphe accessible par g1 est compatible structurellement avec une sous-fonction correspondante dans g2 pour que cela soit pratique. Je pense que vous pouvez probablement écrire une procédure récursive pour vérifier cela. Ce que cette procédure a le plus besoin d'aide, c'est tous les opérateurs set (FirstOf, ..) que vous avez tendance à trouver dans un générateur d'analyseur LALR. Sur un autre front, mon entreprise fabrique des outils Smart Differencer, qui calculent des deltas sur des constructions de langage en termes d'éléments langauge et d'opérations d'édition sur ces éléments. Il est paramétré par les définitions de langue. La SmartDifference fonctionne actuellement pour une variété de langages conventionnels (C, C++, C#, COBOL, Java, PHP, Python, ....). XML (et les DTD) sont aussi un langage pour lequel nous avons une définition de langage, et nous avons construit un outil expérimental XML Smart Differencer. Il devrait très bien fonctionner sur les DTD. Contactez-moi hors ligne (voir bio) si vous avez d'autres intérêts directs.

EDIT: Juste pour des grimaces, j'ai essayé les deux suivants, un DTD dérivé de l'autre:

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/> 

et 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/> 

[Voir si vous pouvez repérer les différences vous, d'abord :-)

Et a couru le 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, 

Oui, c'est ce que j'ai fait pour g et le dérivé. (La notation N.M signifie "ligne N, colonne M").