Markup-language document formatting in memory-constrained environment

• US 7,313,758 B2
• Filed: 04/24/2003
• Issued: 12/25/2007
• Est. Priority Date: 04/24/2002
• Status: Expired due to Fees

• Current Assignee: Canon Kabushiki Kaisha (Canon Inc.)
• Original Assignee: Canon Kabushiki Kaisha (Canon Inc.)
• Inventors: Kozlov, Dmitri
• Primary Examiner(s): Hong; Stephen
• Assistant Examiner(s): Queler; Adam M.
• Application Number:
  US10/421,770
• Publication Number:
  US 20030221168A1
• Time in Patent Office: 1,706 Days
• Field of Search: 715/513, 715/517, 715/509, 715/510
• US Class Current: 715/234
• CPC Class Codes: G06F 40/143 Markup, e.g. Standard Generalized Markup Language [SGML] or Document Type Definition [DTD]

Abstract

Methods (600, 700, 900), apparatuses and computer program products are disclosed for parsing and formatting a document encoded using a markup language in a memory-constrained environment. The structure (100) of the document is represented by a tree having one or more nodes (n1-n10). One method (600) includes the steps of, for a current one of the nodes, freeing memory occupied by any previously formatted one of the nodes upon which formatting of the current node, according to a set of formatting rules, is independent; and building a partial document tree (500) using the current node and remaining previously formatted nodes upon which formatting of the current node, according to the set of formatting rules, is dependent. Another method includes the steps of obtaining information about one or more nodes of the document using a lookahead parser, and formatting the one or more nodes using the obtained information.

Claims

1. A method of parsing and formatting a document encoded using a markup language, the structure of said document being represented by a tree having one or more nodes, said method comprising the steps of:

parsing the document to a current node in said tree using a main parser, freeing memory occupied by an previously formatted one of said nodes upon which formatting of said current node, according to a set of formatting rules, is independent and the formatting of said current node being dependent on one or more further nodes that have not yet been formatted, wherein a partial document tree uses the current node and remaining previously formatted nodes upon which formatting of said current node is dependent;

obtaining information about said one or more further nodes of said document using a look-ahead parser operable so as to not interfere with operation of the main parser; and

formatting said current node using said obtained information.

2. The method according to claim 1, further comprising the step of determining which of said one or more nodes is affected by said set of formatting rules.

3. The method according to claim 2, wherein said determining step utilizes one or more sequences of selectors, each sequence of selectors being related to one of said formatting rules, applied to sibling nodes of said document tree.

4. The method according to claim 2, wherein said determining step includes the step of searching each formatting rule in said set of formatting rules for said current node.

5. The method according to claim 1, further comprising the steps of formatting said document using said partial document tree and outputting said formatted document.

6. The method according to claim 1, wherein the look-ahead parser scans the encoded document to obtain information required for formatting the current node.

7. The method according to claim 1, wherein the look-ahead parser builds a skeleton of the tree to store a minimum of the obtained information.

8. The method according to claim 1, wherein the look-ahead parser receives a stream representing the encoded document, and the look-ahead parser restores the stream to a received state where the look-ahead parser has affected the state of the stream.

9. An apparatus for parsing and formatting a document encoded using a markup language, the structure of said document being represented by a tree having one or more nodes, said apparatus comprising:

a memory device;

a main parser for parsing said document to a current node in said tree and freeing memory of the memory device occupied by any previously formatted one of said nodes upon which formatting of said current node, according to a set of formatting rules, is independent, the formatting of said current node being dependent on one or more further nodes that have not yet been formatted, the main parser further forming a partial document tree that uses the current node and remaining previously formatted nodes upon which formatting of said current node is dependent;

an obtaining unit for obtaining information about said one or more further nodes of said document using a look-ahead parser operable so as to not interfere with operation of the main parser; and

a formatting unit for formatting said current node using said obtained information.

10. The apparatus according to claim 9, further comprising means for determining which of said one or more nodes is affected by said set of formatting rules.

11. The apparatus according to claim 10, wherein said determining means utilizes one or more sequences of selectors, each sequence of selectors related to one of said formatting rules, applied to sibling nodes of said document tree.

12. The apparatus according to claim 10, wherein said determining means comprises means for searching each formatting rule in said set of formatting rules for said current node.

13. The apparatus according to claim 9, further comprising means for formatting said document using said partial document tree and outputting said formatted document.

14. A computer readable storage medium having a computer program recorded therein for parsing and formatting a document encoded using a markup language, the structure of said document being represented by a tree having one or more nodes, said computer program comprising the steps of:

parsing said document to a current node in said tree using a main parser, freeing memory occupied by any previously formatted one of said nodes upon which formatting of said current node, according to a set of formatting rules, is independent, and the formatting of said current node being dependent on one or more further nodes that have not yet been formatted, wherein a partial document tree uses the current node and remaining previously formatted nodes upon which formatting of said current node is dependent;

obtaining information about said one or more further nodes of said document using a look-ahead parser operable so as to not interfere with operation of the main parser; and

formatting said current node using said obtained information.

15. The computer readable storage medium according to claim 14 further comprising determining which of said one or more nodes affected by said set of formatting rules.

16. The computer readable storage medium according to claim 15, wherein said determining step utilizes one or more sequences of selectors, each sequence of selectors related to one of said formatting rules, applied to sibling nodes of said document tree.

17. The computer readable storage medium according to claim 15, wherein said determining step comprises searching each formatting rule in said set of formatting rules for said current node.

18. The computer readable storage medium according to claim 14, further comprising the steps of formatting said document using said partial document tree and outputting said formatted document.