SYSTEM AND METHOD FOR RECOGNIZING STRUCTURE IN TEXT

• US 20100088674A1
• Filed: 03/31/2009
• Published: 04/08/2010
• Est. Priority Date: 10/06/2008
• Status: Abandoned Application

• Current Assignee: Microsoft Technology Licensing LLC (Microsoft Corporation)
• Original Assignee: Microsoft Corporation
• Inventors: Keiser, John Braden, Walter, Douglas Allen, Lucco, Steven Edward, Szyperski, Clemens Alden, Della-Libera, Giovanni Moises
• Application Number:
  US12/415,553
• Publication Number:
  US 20100088674A1
• Time in Patent Office: Days
• US Class Current: 717/114
• CPC Class Codes: G06F 40/205 Parsing

Abstract

A method, system, and computer product for processing information embedded in a text file with a grammar programming language is provided. A text file is parsed according to a set of rules and candidate textual shapes corresponding to potential interpretations of the text file are provided by compiling a script. An output is provided, which may include either a processed value corresponding to a particular textual shape, or a textual representation of the text file that includes generic data structures that facilitate providing any of the candidate textual shapes, where the generic data structures are a function of the set of rules.

Claims

1. A method for processing information embedded in a text file with a grammar programming language, including:

receiving a text file, the text file including a plurality of input values;

parsing each of the plurality of input values according to a set of rules;

compiling a script so as to produce a plurality of candidate textual shapes, each of the plurality of candidate textual shapes corresponding to a potential interpretation of the plurality of input values; and

providing an output, the output including at least one of;

a processed value, the processed value corresponding to a particular textual shape, the particular textual shape selected from the plurality of candidate textual shapes;

or

a textual representation of the text file, the textual representation including a plurality of generic data structures that facilitate providing any of the plurality of candidate textual shapes, the generic data structures being a function of the set of rules.

2. The method of claim 1 further comprising identifying a syntactical ambiguity, the set of preferred rules providing a preference for resolving the syntactical ambiguity.

3. The method of claim 2, the compiling step further comprising analyzing the syntactical ambiguity according to at least a subset of the preferred rule and a plurality of alternative rules so as to compile a plurality of candidate syntactical resolutions, the output being a function of a prioritization of the plurality of candidate syntactical resolutions.

4. The method of claim 3, the prioritization including identifying a preferred syntactical resolution, the output being a function of the preferred syntactical resolution if the preferred syntactical resolution conforms with the at least a subset of the preferred rule, the output being a function of an alternative syntactical resolution selected from a remaining set of candidate syntactical resolutions if the preferred syntactical resolution does not conform with the at least a subset of the preferred rule, the alternative syntactical resolution selected as a function of the prioritizing step.

5. The method of claim 1 further comprising identifying a token ambiguity, the identifying step including matching each of a set of tokens representing all tokens included in the grammar programming language against a text value, the text value including a subset of the plurality of input values.

6. The method of claim 5, the matching step being performed sequentially on each of the subset of plurality of input values so as to generate a first set of remaining tokens, the method further comprising:

determining whether a first type of token ambiguity exists within the first set of remaining tokens, the first type of token ambiguity existing if the first set of remaining tokens includes at least two tokens;

resolving each of an existing first type of token ambiguity based on a match length so as to generate a second set of remaining tokens, the second set of remaining tokens being a subset of the first set of remaining tokens;

determining whether a second type of token ambiguity exists, the second type of token ambiguity existing where each of the second set of remaining tokens have the same match length; and

resolving each of an existing second type of token ambiguity by determining whether one of the second set of remaining tokens is a token marked final, the resolving step selecting the token marked final if present, the resolving step retaining each of the second set of remaining tokens and matching a new token against the text value starting with a first input value that has not already been matched if the token marked final is not present.

7. The method of claim 1, the parsing step further comprising parsing a first portion of the text file in a first lexical space and parsing a second portion of the text file in a second lexical space.

8. The method of claim 7 further comprising:

identifying a first syntactic marker, the first syntactic marker demarcating the beginning of a nested language;

transitioning to the second lexical space upon identifying the first syntactic marker;

parsing the nested language in the second lexical space;

identifying a second syntactic marker, the second syntactic marker demarcating the end of the nested language;

transitioning back to the first lexical space upon identifying the second syntactic marker; and

parsing a subsequent portion of the text file in the first lexical space, the subsequent portion of the text file immediately following the second syntactic marker.

9. The method of claim 1 further comprising providing a rule parameter, the providing step including:

defining a pattern with at least one argument;

calling the pattern, the calling step comprising substituting an arbitrary term for at least one of the at least one arguments; and

parsing the plurality of input values as a function of the arbitrary term.

10. The method of claim 1, the parsing step further comprising:

ascertaining a criteria for a set of checkpoint locations in the text file;

parsing the text file a single time for all locations matching the criteria;

tagging each of the locations matching the criteria as a checkpoint location; and

providing a map of the set of checkpoint locations, the map configured to allow a user to parse a portion of the text file, the portion of the text file either beginning or ending with a checkpoint location.

11. The method of claim 1 further comprising interleaving whitespace including:

identifying at least one token, each of the at least one tokens corresponding to a unique textual value;

defining an interleave whitespace rule;

parsing the text file for each of the at least one tokens, the parsing step interleaving a whitespace as a function of the interleave whitespace rule; and

returning a set of text values, the set of text values corresponding to each of the at least one tokens parsed out of the text file.

12. A computer-readable storage medium comprising instructions for facilitating processing information embedded in a text file with a grammar programming language, including:

a first module, the first module including instructions for receiving the text file as an input, the text file including a plurality of input values;

a second module, the second module including instructions for providing a library, the library including a plurality of constructs for interpreting a textual shape of the text file;

a third module, the third module including instructions for providing a script editor, the script editor configured to facilitate generating a script of the grammar programming language, the script including at least one of the plurality of constructs;

a fourth module, the fourth module including instructions for compiling the script as a function of the text file, the compiling instructions facilitating generating a plurality of candidate textual shapes, each of the plurality of candidate textual shapes corresponding to a potential interpretation of the plurality of input values; and

a fifth module, the fifth module including instructions for providing an output, the output including at least one of;

a processed value, the processed value corresponding to a particular textual shape, the particular textual shape selected from the plurality of candidate textual shapes;

or

a textual representation of the text file, the textual representation including a plurality of generic data structures that facilitate providing any of the plurality of candidate textual shapes, the generic data structures being a function of the script.

13. The computer-readable storage medium of claim 12, the fourth module further comprising instructions for compiling a syntactical ambiguity into a plurality of candidate syntactical resolutions.

14. The computer-readable storage medium of claim 13, the fourth module further comprising instructions for compiling the syntactical ambiguity according to each of a preferred rule and at least one alternative rule, the output being a function of a prioritization of the plurality of candidate syntactical resolutions.

15. The computer-readable storage medium of claim 14, the fourth module further comprising instructions for identifying a preferred syntactical resolution, the output being a function of the preferred syntactical resolution if compilation of the preferred syntactical resolution yields one of the plurality of candidate textual shapes, the output being a function of an alternative syntactical resolution selected from a remaining set of candidate syntactical resolutions if the preferred syntactical resolution does not yield one of the plurality of candidate textual shapes, the alternative syntactical resolution selected as a function of the prioritization.

16. The computer-readable storage medium of claim 12, the fourth module further comprising instructions for identifying a token ambiguity, the identifying instructions including instructions for matching each of a set of tokens representing all tokens included in the grammar programming language against a text value, the text value including a subset of the plurality of input values.

17. The computer-readable storage medium of claim 16, the matching instructions including instructions for matching each of the set of tokens sequentially on each of the subset of plurality of input values so as to generate a first set of remaining tokens, the matching instructions further comprising instructions for:

determining whether a first type of token ambiguity exists within the first set of remaining tokens, the first type of token ambiguity existing if the first set of remaining tokens includes at least two tokens;

resolving each of an existing first type of token ambiguity based on a match length so as to generate a second set of remaining tokens, the second set of remaining tokens being a subset of the first set of remaining tokens;

determining whether a second type of token ambiguity exists, the second type of token ambiguity existing where each of the second set of remaining tokens have the same match length; and

resolving each of an existing second type of token ambiguity by determining whether one of the second set of remaining tokens is a token marked final, the resolving step selecting the token marked final if present, the resolving step retaining each of the second set of remaining tokens and matching a new token against the text value starting with a first input value that has not already been matched if the token marked final is not present.

18. The computer-readable storage medium of claim 12, the fourth module further comprising instructions for parsing a first portion of the text file in a first lexical space and parsing a second portion of the text file in a second lexical space.

19. The computer-readable storage medium of claim 18, the parsing instructions further comprising instructions for:

identifying a first syntactic marker, the first syntactic marker demarcating the beginning of a nested language;

transitioning to the second lexical space upon identifying the first syntactic marker;

parsing the nested language in the second lexical space;

identifying a second syntactic marker, the second syntactic marker demarcating the end of the nested language;

transitioning back to the first lexical space upon identifying the second syntactic marker; and

parsing a subsequent portion of the text file in the first lexical space, the subsequent portion of the text file immediately following the second syntactic marker.

20. The computer-readable storage medium of claim 12, the second module further comprising instructions for providing at least one construct that facilitates implementing a rule parameter, the providing instructions including instructions for:

defining a pattern with at least one argument;

calling the pattern, the calling step comprising substituting an arbitrary term for at least one of the at least one arguments; and

parsing the plurality of input values as a function of the arbitrary term.

21. The computer-readable storage medium of claim 12, the fourth module further comprising instructions for parsing the text file incrementally, the parsing instructions including instructions for:

ascertaining a criteria for a set of checkpoint locations in the text file;

parsing the text file a single time for all locations matching the criteria;

tagging each of the locations matching the criteria as a checkpoint location; and

providing a map of the set of checkpoint locations, the map configured to allow a user to parse a portion of the text file, the portion of the text file either beginning or ending with a checkpoint location.

22. The computer-readable storage medium of claim 12, the fourth module further comprising instructions for interleaving whitespace, the interleaving instructions including instructions for:

identifying at least one token, each of the at least one tokens corresponding to a unique textual value;

defining an interleave whitespace rule;

parsing the text file for each of the at least one tokens, the parsing step interleaving a whitespace as a function of the interleave whitespace rule; and

returning a set of text values, the set of text values corresponding to each of the at least one tokens parsed out of the text file.

23. A system executed by one or more processors for facilitating processing information embedded in a text file with a grammar programming language, including:

means for receiving a text file, the text file including a plurality of input values;

means for parsing each of the plurality of input values according to a set of rules;

means for identifying at least one syntactical ambiguity;

means for identifying at least one token ambiguity;

means for prioritizing a plurality of candidate textual shapes, the plurality of candidate textual shapes including at least one candidate resolution to the at least one syntactical ambiguity;

means for resolving the at least one token ambiguity;

means for compiling a script so as to produce the plurality of candidate textual shapes, each of the plurality of candidate textual shapes corresponding to a potential interpretation of the plurality of input values; and

means for providing an output, the output including at least one of;

a processed value, the processed value corresponding to a particular textual shape, the particular textual shape selected from the plurality of candidate textual shapes;

or

a textual representation of the text file, the textual representation including a plurality of generic data structures that facilitate providing any of the plurality of candidate textual shapes, the generic data structures being a function of the set of rules.