Parser translator system and method

• US 6,523,172 B1
• Filed: 02/19/1999
• Issued: 02/18/2003
• Est. Priority Date: 12/17/1998
• Status: Expired due to Term

• Current Assignee: Versata Incorporated (ESW Capital, LLC)
• Original Assignee: Evolutionary Technologies International, Inc.
• Inventors: Marshall, David H., Martinez-Guerra, Juan Carlos, Hammer, Katherine G., Timmerman, Tina L.
• Primary Examiner(s): DAM, TUAN QUANG
• Application Number:
  US09/253,158
• Time in Patent Office: 1,460 Days
• Field of Search: 707/4,10,523,102,101,103 Y,103 Z 717/5,8,112,143 709/223 704/9,2
• US Class Current: 717/143
• CPC Class Codes: G06F 8/427 Parsing
• CPC Class Codes: Y10S 707/99934 Query formulation, input preparation, or translation
• CPC Class Codes: Y10S 707/99942 Manipulating data structure, e.g. compression, compaction, compilation

Abstract

A parser-translator technology allows a user to specify complex test and/or transformation statements in a high-level user language, to ensure that such test and/or transformation statements are well-formed in accordance with a grammar defining legal statements in the user language, and to translate statements defined by the user into logically and syntactically correct directives for performing the desired data transformations or operations. Using the parser-translator technology, a user can focus on the semantics of the desired operations and need not be concerned with the proper syntax of a language for a particular system. Instead, grammars (i.e., data) define the behavior of a parser-translator implementation by encoding the universe of statements (e.g., legal test and/or transformation statements) and by encoding translations appropriate to a particular data processing application (e.g., a data conversion program, etc.). Some parser-translator implementations described herein interface dynamically with other systems and/or repositories to query for information about objects, systems and states represented therein, and/or their respective interfaces. Some grammars described herein encode sensitivity to an external context. In this way, context-sensitive prompting and validation of correct specification of statements is provided. A combination of parser technology and dynamic querying of external system state allows users to build complex statements (e.g., using natural languages within a user interface environment) and to translate those complex statements into statements or directives appropriate to a particular data processing application.

Claims

1. An apparatus comprising:

an instance of a parser-translator software component executable to read an input stream encoding at least one business rule and to evaluate said input stream in conjunction with a grammar encoding an external query; and

a software tool operable with said parser-translator instance to receive an output thereof corresponding to said at least one business rule, said output sensitive to an external context by operation of said external query.

2. An apparatus as recited in claim 1, further comprising:

a second software tool integrated with a second instance of said parser-translator software component to receive an external context-sensitive output thereof corresponding to said at least one business rule.

3. An apparatus as recited in claim 1,

wherein said external query includes access to one of a database, a repository and a metadata store external to said parser-translator instance.

4. An apparatus as recited in claim 1,

wherein said external query includes access to a data structure maintained by said software tool.

5. An apparatus as recited in claim 1,

wherein said software tool includes one or more of data conversion or migration, data analysis, data cleansing and data movement or replication components.

6. An apparatus as recited in claim 1,

wherein said external context sensitive output includes a directive for controlling operation of said software tool in accordance with said business rule and in accordance with at least one data or metadata state represented external to said parser-translator instance.

7. An apparatus as recited in claim 1,

wherein said external context sensitive output includes a data transformation statement for use by a program generator in generating a data conversion program.

8. A method of operating a data processing program in accordance with at least one business rule, said method comprising:

reading an input stream encoding said at least one business rule;

evaluating said input stream in accordance with a grammar encoding an external query to least one externally represented data or metadata state;

performing, in the context of said evaluating, said external query; and

supplying an operating directive for said data processing program, said operating directive corresponding to said at least one business rule and sensitive to said at least one externally-represented data or metadata state.

9. A method as recited in claim 8, further comprising:

supplying, via a user interface and in accordance with said grammar, selections for elements of said at least one business rule, wherein said selections supplied are constrained by results of said external query.

10. A method as recited in claim 8, wherein said input stream evaluating includes:

recognizing tokens from said input stream;

parsing said tokens; and

translating a sequence of said tokens to produce said operating directive.

11. A method as recited in claim 10,

wherein said recognizing includes performing said external query to constrain a set of candidate tokens to be recognized.

12. A method as recited in claim 11, further comprising:

supplying, via a user interface and in accordance with said grammar, said constrained set of candidate tokens;

interactively defining said at least one business rule using said constrained set of candidate tokens as selections for elements of said at least one business rule.

13. A method as recited in claim 10,

wherein said recognizing includes performing said external query to validate a token.

14. A method as recited in claim 10,

wherein said translating includes performing said external query to resolve an aspect thereof.

15. A method as recited in claim 8, further comprising:

supplying, via a user interface dynamically created in accordance with said grammar, selections for elements of said at least one business rule, wherein said selections supplied are constrained by results of said external query.

16. A system for providing business rule interoperability in a computing environment, said system comprising:

a computer readable encoding of a grammar including (i) rules descriptive of statements in a data transformation language for transforming between a first format and a second format and (ii) entries descriptive of data transformation language elements in said statements, at least one of said entries specifying an external query to resolve a corresponding data transformation language element at evaluation time; and

a parser-translator component executable to read an input stream encoding at least one business rule and evaluate said input stream in conjunction with said grammar encoding including said external query and, based thereon, to define a data transformation.

17. A system, as recited in claim 16, further comprising:

a second computer readable encoding of a second grammar, readable by said parser-translator component and thereby allowing said parser-translator component to read said input stream and define a second data transformation based thereon.

18. A system, as recited in claim 17,

wherein said first and second grammars specify a formal definition of a same language;

and

wherein said first and second grammars specify translations specific to respective first and second data processing programs.

19. A system, as recited in claim 17,

wherein said first and second grammars specify substantially similar phrase structure rules;

and

wherein said first and second grammars specify external queries specific to respective first and second data processing programs.

20. A system, as recited in claim 16,

wherein said data transformation specifies a transformation from one or more fields represented in one or more source data stores to one or more fields represented in one or more target data stores.

21. A system, as recited in claim 16,

wherein said data transformation specifies a directive to a data processing program for accessing data represented in one or more fields of one or more data stores.

22. A system, as recited in claim 16, wherein said external query specifies an ss to a data or metadata store external to said parser-translator component.

23. A system, as recited in claim 16, wherein said external query specifies an access to a data or metadata store external to both said parser-translator component and a data processing program.

24. A system, as recited in claim 16,

wherein said external query specifies an access to a data or metadata store associated with a data processing program, and

wherein said data or metadata store is external to said parser-translator component.

25. A system, as recited in claim 16, wherein said data transformation is encoded as one of a string, a data structure and a software object.

26. A system, as recited in claim 16, wherein said data transformation includes object code callable by a data processing program.

27. A system, as recited in claim 16, wherein said data transformation includes statements formatted for use by a data processing program.

28. A data-driven system for providing business rule interoperability amongst multiple data processing programs, said system comprising:

first and second grammar encodings respectively specific to first and second data processing programs, both said first and said second grammar encodings including an external query;

an input stream encoding at least one business rule; and

a single parser-translator component for,

based on said first grammar encoding, parsing said input stream and translating said input stream into a first data transformation for use in conjunction with said first data processing program; and

based on said second grammar encoding, parsing said input stream and translating said input stream into a second data transformation for use in conjunction said second data processing program.

29. A system, as recited in claim 28, wherein said input stream includes an interactive stream.

30. A system, as recited in claim 28, wherein said input stream includes a batch stream.

31. A method of interactively specifying a transformation of data from a first representation to a second representation thereof, said method comprising:

supplying a computer readable encoding of a grammar, said grammar including syntax rules descriptive of sequences of tokens in a data transformation language; and

dictionary entries descriptive of terminal ones of said tokens, said dictionary entries including at least a first and a second entry respectively descriptive of at least first and second tokens, said first entry specifying at least one data transformation language element corresponding to said first token, and said second entry specifying an action to dynamically-query an external data source to resolve at least one data transformation language element corresponding to said second token;

based on said grammar encoding, presenting a user with at least one choice for a first element in a data transformation statement in accordance with said syntax rules; and

presenting a user with successive at least one choices for successive elements in said data transformation statement in accordance with said syntax rules, wherein at least one of said successive element presentings includes performing a dynamic query in accordance with said second entry of said dictionary.

32. A computer program product including a grammar encoded by at least one computer readable medium, said grammar comprising:

a set of phrase structure rules defining orderings of tokens in said data transformation language;

a dictionary of entries descriptive of terminal ones of said tokens; and

at least one encoding of a query to an external data or metadata store,

wherein said grammar at least partially defines operation of a parser-translator to allow interactive definition of data transformation statements based in part on information accessed by performing said query.

33. A computer program product as recited in claim 32,

wherein said at least one computer readable medium is selected from the set of a disk, tape or other magnetic, optical, or electronic storage medium and a network, wireline, wireless or other communications medium.

34. A computer program product as recited in claim 32, further comprising:

the parser-translator.

35. A method for interactively specifying a data transformation statement in accordance with a grammar including (i) rules defining orderings of tokens in a data transformation language for transforming between a first data representation in a first data store and second data representation and (ii) dictionary entries descriptive of terminal ones of said tokens, said method comprising:

supplying a computer readable encoding of said grammar, wherein a function identifier is associated with at least one of said dictionary entries, said function identifier encoding a run-time query to one of said first data store and metadata corresponding thereto; and

based on said grammar, presenting a human user with choices for successive elements in said data transformation statement, wherein at least one of said choices is resolved by said run-time query.

36. A data processing system comprising:

a first data store encoding a grammar defining data transformation statements in accordance with a predetermined data transformation language;

a second data store encoding metadata descriptive of a structure of a first data set;

parser-translator means executable to access said first and said second data stores and having a user interface allowing a human user to interactively define a data transformation statement in accordance with said grammar, wherein at least one element of said data transformation statement is selected by said human user from alternatives resulting from a dynamic query of said metadata.

37. A data processing system, as recited in claim 36,

wherein said data transformation statement encodes a transformation of source data represented in said first data set to target data represented in a second data set.

38. A data processing system, as recited in claim 36,

wherein said data transformation statement encodes a transformation between a first data representation in said first data set to a second data representation utilized by a data processing program.

39. A data processing system, as recited in claim 36,

wherein said data transformation statement encodes a transformation between a third data representation utilized by a data processing program and a fourth data representation in said first data set.

40. A data processing system, as recited in claim 36,

wherein said data transformation statement encodes a transformation between source and t target data representation s each in said first data set.

41. A data processing system, as recited in claim 36,

wherein said first data set includes a first database;

and

wherein said metadata includes a schema of said first database.

42. A computer program product including a grammar transmitted in at least one computer readable medium, said grammar at least partially defining actions to be performed by a computer in response thereto, said grammar comprising:

a set of phrase structure rules defining orderings of tokens in said data transformation language;

a dictionary of entries descriptive of terminal ones of said tokens; and

at least one encoding of a query to an external data or metadata store,

wherein said grammar at least partially defines operation of a parser-translator to allow interactive definition of data transformation statements based in part on information accessed by performing said query.

43. A computer program product as recited in claim 42, further comprising:

the parser-translator.