DTD на самом деле являются просто скрытыми грамматиками без контекста. Грамматика G представляет собой набор возможных допустимых строк, которые составляют неустановленный язык L (G), который представляет грамматика.
То, что вы спрашиваете, равносильно определению, есть ли у вас G1 и G2, является ли L (G1) подмножеством L (G2). Моя теория языка становится ржавой, и я не помню, является ли она вычислимой вообще или нет, но я предполагаю, что это действительно сложно, потому что вы должны продемонстрировать, что произвольный вывод в G1 всегда имеет вывод в G2.
Возможно, вы сможете ответить на вопрос о том, структурирована ли G1 таким образом, что вы можете продемонстрировать, что L (G1) является подмножеством L (G2), продемонстрировав, что каждый элемент G1 совместим с каждым элементом G2, в основном, показывая, что каждое правило грамматики
в G1 есть соответствующее правило в G2 с пропущенными элементами. Ваша идея создания DTD, похоже, соответствует этой линии, при условии, что если различия большие, вы застряли в общей проблеме, а не в более простой. По крайней мере, как вы охарактеризовали проблему (G2 получен из основного DTD), я думаю, у вас есть шанс.
Целью сравнения будет определение совместимых правил путем наименьшего различия.
Если у вас есть правило грамматики g2 = A; и другой g1 = A, который вы бы заявили, связаны и
что вы хотели бы проверить,
Сначала вы должны продемонстрировать, что строковые токены, полученные в G1, являются надмножеством
цепочки токенов A, полученных в G2. Это выглядит так же, как исходная безусловная проблема сравнения двух языков; теперь мы просто сравниваем подъязыки для двух правил g1 и g2.
Так что теперь я думаю, что вы должны настаивать на том, чтобы каждая подправила, достижимая g1, была структурно совместима с соответствующим подправилом в g2, чтобы сделать это практичным.
Я думаю, что вы можете написать рекурсивную процедуру, чтобы проверить это. Для этой процедуры в основном нужна помощь - все операторы множеств (FirstOf, ..), которые вы обычно находите в генераторе синтаксического анализатора LALR.
С другой стороны, моя компания производит Smart Differencer инструменты, которые вычисляют дельты по языковым конструкциям в терминах элементов языка и операций редактирования этих элементов. Он параметризован определениями языка. SmartDifference в настоящее время работает для различных традиционных языков (C, C ++, C #, COBOL, Java, PHP, Python, ....). XML (и DTD) также являются языком, для которого у нас есть определение языка, и мы создали экспериментальные инструменты XML Smart Differencer. Это должно работать на DTD просто отлично. Свяжитесь со мной в автономном режиме (см. Био), если у вас есть дальнейший прямой интерес.
РЕДАКТИРОВАТЬ: Просто для ухмылки, я попробовал следующие два 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»).