Polymorphic regular expressions

• US 7,496,892 B2
• Filed: 04/05/2004
• Issued: 02/24/2009
• Est. Priority Date: 05/06/2003
• Status: Active Grant

• Current Assignee: Andrew Nuss
• Original Assignee: Andrew Nuss
• Inventors: Nuss, Andrew
• Primary Examiner(s): Zhen; Wei Y
• Assistant Examiner(s): RAMPURIA, SATISH
• Application Number:
  US10/818,346
• Publication Number:
  US 20050097514A1
• Time in Patent Office: 1,786 Days
• Field of Search: 717/106, 717/108, 717/112, 717114-119
• US Class Current: 717/114
• CPC Class Codes: G06F 8/31 Programming languages or programming paradigms
• CPC Class Codes: G06F 8/315 Object-oriented languages
• CPC Class Codes: G06F 8/425 Lexical analysis
• CPC Class Codes: G06F 8/427 Parsing

Abstract

New polymorphic advantages by combining OO elements of the Java™ and C++ languages with built-in support for regular expressions (in terms of class definitions, inheritance, member functions) and by applying the principle of virtual class membership to production rules are presented. Virtual member production rules are incorporated into a ‘V-table’ concept. Instantiated production rules are type-compatible embodiments of regular expressions. Polymorphic regular expressions are leveraged through the ‘document design pattern’.

Claims

1. A computer-implemented method of encapsulating regular expressions as polymorphic, virtual members of a programmer defined struct/class, the method comprising the steps of:

defining a grammar for creating object-oriented style structs similar to the grammar of C++;

defining a grammar for the algebraic composition of regular expressions in the grammar;

defining a grammar for creating side-effects of regular expressions such as capture, called CapturePatterns, and the more general statement embedding side-effects, called DoPatterns;

defining a grammar for the encapsulation rules of regular expressions in such a way that they are reusable based on their rule names and parameters;

instantiating the encapsulation as a regular expression that binds to the struct instance; and

declaring the encapsulation as virtual members and therefore subclassable members of a struct such that the regular expression encapsulation has access to all of the data members and virtual members of the struct instance for both composition and side-effects.

2. The method of claim 1, further comprising the step of declaring a regular expression encapsulation as a virtual and therefore subclassable member of the struct, such that all aspects (both composition and side-effect) of the regular expression encapsulation have access to the data and function members of this struct instance as well as other virtual regular expression encapsulations defined in this struct.

3. The method of claim 2, further comprising the step of composing a virtual regular expression encapsulation in terms of matching characteristics from other virtual regular expression encapsulations defined in the struct.

4. The method of claim 2, further comprising the step of including capture semantics in a virtual regular expression encapsulation whereby matches or sub-matches of the encapsulated regular expression can be stored into data member variables of the struct instance.

5. The method of claim 2, further comprising the step of including general side-effect generating statements, DoPatterns, in a virtual regular expression encapsulation whereby the DoPattern'"'"'s side-effect statements have access to all of the data member variables and member functions of the struct instance.

6. The method of claim 2, further comprising the steps of:

a) defining a high-level matching regular expression as a virtual regular expression encapsulation of a struct; and

b) then decomposing the virtual regular expression encapsulation of the struct into, and based upon, other virtual regular expression encapsulations within the same struct, in such a way that subclasses of the struct can polymorphically insinuate new derived behaviors, both matching and side-effect, to any of the decomposed regular expression encapsulations, whereby the high-level matching regular expression of the subclass both inherits the regular expression behaviors of superclass encapsulations and derives additional regular expression behaviors for the high-level matching expression in the subclass.

7. The method of claim 6, further comprising the step of deriving, for a subclass of a struct, a new definition to a particular virtual regular expression encapsulation, such that the derived definition has new matching and composition characteristics, normally augmenting the matching characteristics of the corresponding virtual regular expression definition in the superclass, and such that any virtual encapsulations that depend on the derived encapsulation inherit the new matching behavior of the changed encapsulation.

8. The method of claim 6, further comprising the step of giving a subclass of a struct a new derived definition to a particular virtual regular expression encapsulation, such that the derived behavior now updates data members of the struct instance, both through CapturePatterns and DoPatterns, and such that any virtual encapsulations that depend on the derived encapsulation inherit the new side-effect behavior of the changed encapsulation.

9. A computer system for interpreting or compiling and then executing a programming language with support for regular expression encapsulations defined as virtual members of a struct/class, the system comprising:

at least one computer processor;

a programming language with means for a regular expression grammar, the grammar comprising means for

     1) for creating object-oriented style structs similar to the grammar of C++,

     2) for the algebraic composition of. regular expressions in the grammar,

     3) for creating side-effects of regular expressions such as capture, called CapturePatterns, and the more general statement embedding side-effects, called DoPatterns;

     4) for defining a grammar for the encapsulation rules of regular expressions in such a way that they are reusable based on their rule names and parameters,

     5) for instantiating the encapsulation as a regular expression that binds to the struct instance; and

     6) for declaring the encapsulations as virtual members and therefore subclassable members of a struct such that the regular expression encapsulation has access to all of the data members and virtual members of the struct instance for both composition and side-effects;

means for executing computer program modules or scripts written in the programming language and, while the computer program is being hosted by the computer processor, the computer program is also the host for the computer program scripts which are its target executables;

means for data input providing a user-defined program module or script written by user according to the grammatical rules of the programming language to the host computer programs;

means for data input providing a source of data to be processed by the scripts; and

a set of virtual machine instructions, into which instructions the scripts are translated, and which instructions include aspects for composing and executing virtual regular expression encapsulations.

10. The system of claim 9, further comprising host computer program support for associating the instance “

this”

variable of a struct to a use-instantiation of a virtual regular expression encapsulation, such that the “

this”

variable becomes a hidden parameter of the virtual regular expression encapsulation.

11. The system of claim 10, further permitting the hidden “

this”

parameter of an instantiation of a virtual regular expression encapsulation to be accessed at composition time to allow other virtual regular expression encapsulations of the struct instance to be used in composition of the virtual regular expression encapsulation.

12. The system of claim 10, further permitting the hidden “

this”

parameter of an instantiation to be found at “

side-effect time”

so that the virtual machine can store the side-effects of a match, such as CapturePatterns and DoPatterns, into the correct instance of the struct.

13. A computer-implemented method of encapsulating regular expressions as polymorphic members of a struct, the method comprising the steps of:

defining a grammar for creating object-oriented style structs similar to the grammar of C++;

defining a grammar for the composition of regular expressions in the grammar;

defining a grammar for creating side-effects of regular expressions such as capture, called CapturePatterns, and more general statement embedding side-effects, called DoPatterns;

defining a grammar for the encapsulation of regular expressions in such a way that they are reusable based on their names and parameters;

declaring a regular expression encapsulation as a virtual member of the struct, such that all aspects of the regular expression encapsulation has access (once instantiated relative to a specific struct instance) to the data members of a struct instance as well as other virtual regular expression encapsulations defined in the struct;

defining high-level matching regular expression(s) as a virtual regular expression encapsulation of a struct;

decomposing the virtual regular expression encapsulation of the struct into, and based upon, other virtual regular expression encapsulations of the same struct, in such a way that subclasses of the struct can polymorphically give new derived behaviors, both matching and side-effect, to any of the decomposed regular expression encapsulations, whereby the high-level matching regular expression of the subclass both inherits the regular expression behaviors of superclass encapsulations and derives additional regular expression behaviors for the high-level matching expression in the subclass; and

declaring the encapsulation as virtual members of a struct such that the regular expression encapsulation has access to all of the data members and virtual members of the struct instance for both composition and side-effects.