Method and apparatus for document transformation based on attribute grammars and attribute couplings

• US 5,491,628 A
• Filed: 12/10/1993
• Issued: 02/13/1996
• Est. Priority Date: 12/10/1993
• Status: Expired due to Term

• Current Assignee: Xerox Corporation (Xerox Holdings Corp.)
• Original Assignee: Xerox Corporation (Xerox Holdings Corp.)
• Inventors: Brown, Allen L. Jr., Feng, An, Wakayama, Toshiro, Mantha, Suryanarayana M.
• Primary Examiner(s): Hayes, Gail O.
• Assistant Examiner(s): Poinvil, Frantzy
• Application Number:
  US08/165,785
• Time in Patent Office: 795 Days
• Field of Search: 364/419.08, 364/200 MS, 395/144, 395/145, 395/600
• US Class Current: 704/9
• CPC Class Codes: G06F 40/14 Tree-structured documents parsing G06F40/205; validation G06F40/226
• CPC Class Codes: G06F 40/151 Transformation
• CPC Class Codes: G06F 40/154 Tree transformation for tree-structured or markup documents, e.g. XSLT, XSL-FO or stylesheets
• CPC Class Codes: G06F 40/16 Automatic learning of transformation rules, e.g. from examples

Abstract

A method and apparatus are provided for converting a first document to a second document. The first document is in a first extended attribute grammar, while the second document is in a second extended attribute grammar. An extended attribute coupling grammar couples the first and second extended attribute grammars. The first document is converted to a first tree, which is partially copied to a first copy. The first copy is completed by evaluating it'"'"'s attribute with respect to the extended attribute coupling grammar. The first copy is then a partially attributed tree of the second document. The partially attributed tree is completed to form a second tree based on the second extended attribute grammar. The second tree is then converted to the second document.

Claims

1. A method for converting a first document to a second document, the method comprising the steps of:

specifying the first document in terms of a first extended attribute grammar;

specifying the second document in terms of a second extended attribute grammar;

specifying an extended attribute coupling grammar of the first and second extended attribute grammars; and

transforming the first document into the second document based on the extended attribute coupling grammar.

2. The method of claim 1, wherein the step of specifying a first extended attribute grammar comprises the steps of:

specifying a vocabulary of the first extended attribute grammar; and

specifying at least one production of the first extended attribute grammar.

3. The method of claim 2, wherein the step of specifying the vocabulary of the first extended attribute grammar comprises the steps of:

specifying at least one non-terminal symbol;

specifying at least one terminal symbol; and

specifying one non-terminal symbol as a start symbol.

4. The method of claim 2, wherein the step of specifying the vocabulary of the first extended attribute grammar comprises the steps of:

specifying a plurality of symbols;

specifying at least one logical attribute for each symbol; and

specifying at least one non-logical attribute for each symbol.

5. The method of claim 4, wherein the step of specifying the at least one logical attribute for each symbol comprises the step of specifying at least one tree attribute.

6. The method of claim 5, wherein the step of specifying at least one tree attribute comprises specifying at least one count attribute.

7. The method of claim 4, wherein the step of specifying the at least one non-logical attribute comprises the at least one of steps of:

specifying at least one synthesized attribute;

specifying at least one inherited attribute; and

specifying at least one imported attribute.

8. The method of claim 1, wherein the step of specifying a second extended attribute grammar comprises the steps of:

specifying a vocabulary of the second extended attribute grammar; and

specifying at least one production of the second extended attribute grammar.

9. The method of claim 8, wherein the step of specifying the vocabulary of the second extended attribute grammar comprises the steps of:

specifying at least one non-terminal symbol;

specifying at least one terminal symbol; and

specifying one non-terminal symbol as a start symbol.

10. The method of claim 8, wherein the step of specifying the vocabulary of the second extended attribute grammar comprises the steps of:

specifying a plurality of symbols;

specifying at least one logical attribute for each symbol; and

specifying at least one non-logical attribute for each symbol.

11. The method of claim 10, wherein the step of specifying the at least one logical attribute for each symbol comprises the step of specifying at least one tree attribute.

12. The method of claim 11, wherein the step of specifying at least one tree attribute comprises specifying at least one count attribute.

13. The method of claim 10, wherein the step of specifying the at least one non-logical attribute comprises the at least one of the steps of:

specifying at least one synthesized attribute;

specifying at least one inherited attribute; and

specifying at least one imported attribute.

14. The method of claim 1, wherein the step of specifying the extended attribute coupling grammar comprises the steps of:

specifying a first tree sequence of at least one tree of the first document;

specifying at least one reduction of the first tree sequence;

specifying a second tree sequence of at least one tree of the second document;

specifying at least one reduction of the second tree sequence; and

specifying at least one reduction operator.

15. The method of claim 1, wherein the step of transforming the first document of the second document comprises the step of:

generating a first copy of a first tree of the first document, wherein only imported attributes of the extended attribute coupling grammar are copied with the first copy;

evaluating remaining attributes of the first copy based on the extended attribute coupling grammar;

producing a partially attributed tree of the second document based on the evaluating step;

evaluate remaining attributes of the partial attributed tree based on the second extended attribute grammar generating a second tree of the second document based on the evaluating step; and

generating the second document from the second tree.

16. An apparatus for transforming a first document into a second document, comprising:

means for determining a first extended attribute grammar corresponding to the first document;

means for determining a second extended attribute grammar corresponding to the second document;

means for determining an extended attribute coupling grammar coupling the first extended attribute grammar and the second extended attribute grammar;

means for generating a first tree from the first extended attribute grammar and the first document;

means for generating a second tree from the first tree and the extended attribute coupling grammar; and

means for converting the second tree into the second document.

17. The transformation apparatus of claim 16, wherein the means for determining a first extended attribute comprises:

means for determining a vocabulary of the first extended attribute grammar; and

means for determining at least one production of the first extended attribute grammar.

18. The transformation apparatus of claim 17, wherein the vocabulary determining means comprises:

means for determining at least one terminal symbol;

means for determining at least one non-terminal symbol; and

means for determining a start symbol from the at least one non-terminal symbol.

19. The transformation apparatus of claim 17, wherein the vocabulary determining means comprises:

means for determining a plurality of symbols;

means for determining at least one logical attribute for each of the plurality of symbols; and

means for determining at least one non-logical attribute for each of the plurality of symbols.

20. The transformation apparatus of claim 19, wherein the means for determining at least one non-logical attribute comprises:

means for determining at least one synthesized attribute for the plurality of symbols;

means for determining at least one inherited attribute for the plurality of symbols; and

means for determining at least one imported attribute for at least one of a terminal symbol and a start symbol.