Context-free grammar

• US 8,397,157 B2
• Filed: 10/20/2006
• Issued: 03/12/2013
• Est. Priority Date: 10/20/2006
• Status: Active Grant

• Current Assignee: Adobe Inc.
• Original Assignee: Adobe Systems Incorporated (Adobe Inc.)
• Inventors: Levy, Philip
• Primary Examiner(s): YEN, ERIC L
• Application Number:
  US11/584,217
• Publication Number:
  US 20080097744A1
• Time in Patent Office: 2,335 Days
• Field of Search: 704/1, 704/9, 715/201, 715/234
• US Class Current: 715/234
• CPC Class Codes: G06F 40/143 Markup, e.g. Standard Generalized Markup Language [SGML] or Document Type Definition [DTD]
• CPC Class Codes: G06F 40/211 Syntactic parsing, e.g. based on context-free grammar [CFG] or unification grammars
• CPC Class Codes: G06F 40/221 Parsing markup language streams streaming G06F40/149
• CPC Class Codes: G06F 40/56 Natural language generation

Abstract

In one embodiment, a method comprising accessing a first data object and a second data object of a data structure representing electronic content, the second data object being associated with the first data object, selecting, based on first content included in the first data object, a grammar rule included in a grammar, the grammar rule including a grammar rule item, and based on second content included in the second data object, selecting the grammar rule item included in the grammar rule, and based on the second content and the grammar rule item, generating a portion of a textual representation of the electronic content.

Claims

1. A method comprising:

accessing, in at least one of a memory device and a data storage device, a first data object and a second data object of a data structure, the data structure representing a page description language document that includes page description language document content and non-page description language document content included or referenced in data objects of the page description language document, the second data object being associated with the first data object;

selecting, based on first content included in the first data object, a grammar rule included in a grammar, the grammar rule including a grammar rule item, the grammar being a descriptive specification composed of grammar rules used to computationally determine content types to facilitate selection of grammar rules suitable to translate electronic content to a desired form utilizing grammar rule items;

based on second content included in the second data object, selecting the grammar rule item included in the grammar rule, the second content being non-page description language document content;

based on the second content and the grammar rule item, executing instructions on a computer processor to generate a portion of a markup language document representation of the page description language document; and

wherein the non-page description language document content is at least one of digital video, frames or sets of frames of digital video, digital audio, an animation, an image, and a media stream.

2. The method of claim 1, wherein the second data object is a direct child of the first data object.

3. The method of claim 1, wherein the second data object is an indirect child of the first data object.

4. The method of claim 1, wherein the grammar rule includes a plurality of grammar rule items.

5. The method of claim 1, wherein the grammar rule includes a rule-level pre-processing instruction, and wherein the method further includes executing the rule-level preprocessing instruction in response to the selection of the grammar rule.

6. The method of claim 1, wherein the grammar rule includes a rule-level post-processing instruction, and wherein the method further includes executing the rule-level post-processing instruction after the generation of the portion of the markup language document representation.

7. The method of claim 1, wherein the second data object is contained in the first data object.

8. The method of claim 1, wherein the first content included in the first data object includes a type of the second data object, the type matching a type of the grammar rule.

9. The method of claim 1, wherein the grammar rule item includes output control instructions, and wherein the generating of the portion of the markup language document representation is according to the output control instructions.

10. The method of claim 9, wherein the portion of the markup language document representation includes content generated from the second content according to the output control instructions.

11. The method of claim 9, wherein the output control instructions are literally included within the grammar rule item.

12. The method of claim 9, wherein the output control instructions are implicit in the grammar rule item.

13. The method of claim 1, wherein the selecting of the grammar rule includes accessing a type of the second data object and matching a type of the grammar rule to the type of the second data object.

14. The method of claim 1, wherein the content of the data structure includes the second content.

15. The method of claim 1, wherein the second data object is included within the first data object.

16. The method of claim 1, wherein the second data object is a separate object from the first data object.

17. The method of claim 1, wherein the grammar rule is composed by inclusion of a plurality of grammar rules.

18. A system comprising:

at least one processor;

at least one memory device;

at least one data storage device;

a grammar store on the at least one data storage device storing a grammar rule, the grammar rule including a grammar rule item, the grammar being a descriptive specification composed of grammar rules used to computationally determine content types to facilitate selection of grammar rules suitable to translate electronic content to a desired form utilizing grammar rule items;

a data structure parsing module retrievable from the at least one data storage device to the at least one memory device and executable by the at least one processor to access a first data object and a second data object of a data structure, the data structure representing a page description language document that includes page description language document content and non-page description language document content included or referenced in data objects of the page description language document, the second data object being associated with the first data object, to select, based on first content included in the first data object, the grammar rule, to select, based on second content of the second data object, the grammar rule item, and to generate, based on the second content and the grammar rule item, a portion of a first markup language document representation of the page description language document, the second content is non-page description language document content;

a textual representation parsing module retrievable from the at least one data storage device to the at least one memory device and executable by the at least one processor to access a second markup language document representation of electronic content, the second markup language document representation including a first textual element semantically containing a second textual element, to select the grammar rule and to create a third data object for inclusion in a second page description language document, the selection of the grammar rule and the creation of the third data object being based on at least the first textual element, to select, based on at least third content in the second textual element, the grammar rule item, and to associate, according to the grammar rule item, a data element with the third data object, the data element including fourth content in the second textual element; and

wherein the non-page description language document content is at least one of digital video, frames or sets of frames of digital video, digital audio, an animation, an image, and a media stream.

19. The system of claim 18, wherein the grammar rule includes a plurality of grammar rule items.

20. The system of claim 18, wherein the grammar rule includes a rule-level preprocessing instruction, and wherein the data structure parsing module is to execute the rule-level preprocessing instruction in response to the selection of the grammar rule.

21. The system of claim 18, wherein the grammar rule includes a rule-level post-processing instruction, and wherein the data structure parsing module is to execute the rule-level post-processing instruction after the generation of the portion of the markup language document representation.

22. The system of claim 18, wherein the second data object is contained in the first data object.

23. The system of claim 18, wherein the first content included in the first data object includes a type of the second data object, the type matching a type of the grammar rule.

24. The system of claim 18, wherein the grammar rule item includes output control instructions.

25. The system of claim 24, wherein the data structure parsing module is to generate the portion of the first markup language document representation according to the output control instructions.

26. The system of claim 25, wherein the portion of the first markup language document representation includes content generated from the second content according to the output control instructions.

27. The system of claim 24, wherein the output control instructions are literally included within the grammar rule item.

28. The system of claim 24, wherein the output control instructions are implicit in the grammar rule item.

29. The system of claim 24, wherein the textual representation parsing module is to select the grammar rule item based upon determining that the second textual element is generable according to the output control instructions.

30. The system of claim 18, wherein the data structure parsing module is to access a type of the second data object and to match a type of the grammar rule to the type of the second data object.

31. The system of claim 18, wherein the content of data structure includes the second content.

32. The system of claim 18, wherein the data element is a scalar data element.

33. The system of claim 18, wherein the data element is a compound data element.

34. The system of claim 33, wherein the data element is a data object.

35. The system of claim 18, wherein the grammar rule item includes an identifier and wherein the textual representation parsing module is to select the grammar rule item further based on the first content matching the identifier.

36. The system of claim 35, wherein the associating of the data element with the data object is facilitated by the identifier.

37. The system of claim 18, wherein the first textual element is a first markup language opening tag paired with a markup language closing tag, and wherein the second textual element is a second markup language opening tag located in the second markup language representation between the first markup language opening tag and the markup language closing tag and located within the next containment level below the first textual element.

38. The system of claim 18, wherein the second markup language representation is stored on a computer-readable medium.

39. The system of claim 18, wherein the grammar rule has an object type, and the data object is suited to the object type.

40. The system of claim 18, wherein the third content and the fourth content are the same content.

41. A non-transitory machine-readable medium embodying instructions, which when executed by a machine, cause the machine to perform a method including:

accessing a first data object and a second data object of a data structure, the data structure representing a page description language document that includes page description language document content and non-page description language document content included or referenced in data objects of the page description language document, the second data object being associated with the first data object;

selecting, based on first content included in the first data object, a grammar rule included in a grammar, the grammar rule including a grammar rule item, the grammar being a descriptive specification composed of grammar rules used to computationally determine content types to facilitate selection of grammar rules suitable to translated electronic content to a desired form utilizing grammar rule items;

based on second content included in the second data object, selecting the grammar rule item included in the grammar rule, the second content being non-page description, language document content;

based on the second content and the grammar rule item, generating a portion of a markup language document representation of the page description language document; and

wherein the non-page description language document content is at least one of digital video, frames or sets of frames of digital video, digital audio, an animation, an image, and a media stream.