Systematic enumerating of strings using patterns and rules

• US 6,333,999 B1
• Filed: 11/06/1998
• Issued: 12/25/2001
• Est. Priority Date: 11/06/1998
• Status: Expired due to Fees

• Current Assignee: International Business Machines Corporation
• Original Assignee: International Business Machines Corporation
• Inventors: Brownsmith, Joseph D.
• Primary Examiner(s): Johns, Andrew W.
• Assistant Examiner(s): AZARIAN, SEYED H
• Application Number:
  US09/187,586
• Time in Patent Office: 1,145 Days
• Field of Search: 382/229, 382/228, 382/230, 382/231, 382/227, 382/310, 382/311, 714/38, 714/36, 714/45, 714/46, 714/51, 714/738, 714/739
• US Class Current: 382/229
• CPC Class Codes: G06F 11/2257 using expert systems
• CPC Class Codes: G06F 11/263 Generation of test inputs, e.g. test vectors, patterns or sequences ; with adaptation of the tested hardware for testability with external testers

Abstract

A method, apparatus, article of manufacture, and a memory structure for generating a sequence of character strings is disclosed. This is accomplished by making multiple consecutive variations of a single character-string pattern where each variation differs from the previous one in a systematic way. The pattern is not restricted in form or in content, and the variations can include adding, deleting, and modifying lines and strings in the pattern, and making no change. This is implemented by executing production rules on a template.

In one embodiment, the method herein described begins by defining a template comprising a plurality of template character strings, and defining an ordered series of production rules, each with a comparison field, an operator, and a substitution field comprising a list of elements defining an initial value and a current value. The current value of each production rule is set to the initial value, and the production rules are applied to the template one at a time in execution order. The result of this application of production rules to the template is then enumerated. Finally, the production rules are then iterated in accordance with the operator and substitution field, and again applied to the template.

Claims

1. A method of generating a sequence of character strings, comprising the steps of:

(a) defining a template comprising a plurality of template character strings;

(b) defining an ordered series of production rules, each production rule comprising a comparison field, an operator, and a substitution field comprising a list of elements and defining an initial value and a current value;

(c) setting the current value of each production rule to the initial value;

(d) applying a production rule to the template by applying the production rule current value to the template characters when the production rule comparison field matches the template character string;

(e) repeating step (d), applying each production rule in order until each production rule has been applied to the template; and

(f) enumerating the template.

2. The method of claim 1, wherein the method further comprises the steps of:

(g) iterating the production rules in accordance with the operator and the substitution fields; and

repeating steps (d) through (g) until a terminating condition on at least one of the production rules is satisfied.

3. The method of claim 2, wherein the terminal condition is satisfied when a number of template enumerations exceeds a stop value.

4. The method of claim 2, wherein:

the production rules are selected from a group comprising an iterate-in-turn production rule; and

the step of iterating the production rules comprises the step of setting the current value for the iterate-in-turn production rule to a next value of the iterate-in-turn production rule each time the template is enumerated and any preceding iterate-in-turn production rule of the ordered series of production rules has completed iteration.

5. The method of claim 4, wherein the substitution field of the iterate-in-turn production rule comprises a terminal value, and the terminating condition is satisfied when the current value exceeds the terminal value.

6. The method of claim 4, wherein:

the production rules are selected from a group further comprising an iterate-every-usage production rule; and

the step of applying the production rule to the template further comprises the step of iterating the iterate-every-usage production rule by setting the current value of the iterate-every-usage production rule to a next value of the iterate-every-usage production rule.

7. The method of claim 1, wherein:

the production rules are selected from a group further comprising an associated production rule; and

the step of iterating the production rules comprises the step of setting the current value for the associated production rule to the next value for the associated production rule each time a production rule immediately preceding the associated production rule in the ordered series of production rules is iterated.

8. The method of claim 1, wherein:

the production rules are selected from a group further comprising an iterate every-time production rule; and

the step of iterating the production rules comprises the step of setting the current value for the iterate-every-time production rule to the next value for the iterate-every-time production rule each time the template is enumerated.

9. The method of claim 1, wherein the production rule is applied to the template by replacing the template character strings with the production rule current value when the production rule comparison field matches the template character string.

10. The method of claim 1, wherein the production rules are organized into a plurality of rule groups, and step (e) comprises the steps of:

(e1) repeating step (d), applying the production rules of a rule group in order until each production rule in the rule group has been applied to the template; and

(e2) repeating step (e1) above for each rule group in order until the production rules of each rule group has been applied to the template.

11. An apparatus for generating a sequence of character strings, comprising:

means for defining a template comprising a plurality of template character strings;

means for defining an ordered series of production rules, each production rule comprising a comparison field, an operator, and a substitution field comprising a list of elements and defining an initial value and a current value;

means for setting the current value of each production rule to the initial value;

means for applying the production rule to the template by applying the production rule current value to the template characters when the production rule comparison field matches the template character string;

means for applying each production rule in order until each production rule has been applied to the template; and

means for enumerating the template.

12. The apparatus of claim 11, further comprising:

means for iterating the production rules in accordance with the operator and the substitution fields; and

means for repeatedly applying the production rules to the template and iterating the production rules in accordance with the operator and the substitution fields until a terminating condition on at least one of the production rules is satisfied.

13. The apparatus of claim 12, wherein the terminal condition is satisfied when a number of template enumerations exceeds a stop value.

14. The apparatus of claim 12, wherein:

the production rules are selected from a group comprising an iterate-in-turn production rule; and

the means for iterating the production rules comprises means for setting the current value for the iterate-in-turn production rule to a next value of the iterate-in-turn production rule each time the template is enumerated and any preceding iterate-in-turn production rule of the ordered series of production rules has completed iteration.

15. The apparatus of claim 14, wherein the substitution field of the iterate-in-turn production rule comprises a terminal value, and the terminating condition is satisfied when the current value exceeds the terminal value.

16. The apparatus of claim 14, wherein:

the production rules are selected from a group further comprising an iterate-every-usage production rule; and

the means for applying the production rule to the template further comprises means for iterating the iterate-every-usage production rule by setting the current value of the iterate-every-usage production rule to a next value of the iterate-every-usage rule.

17. The apparatus of claim 11, wherein:

the production rules are selected from a group further comprising an associated production rule; and

the means for iterating the production rules comprises means for setting the current value for the associated production rule to the next value for the associated production rule each time a production rule immediately preceding the associated production rule in the ordered series of production rules is iterated.

18. The apparatus of claim 11, wherein:

the production rules are selected from a group further comprising an iterate every-time production rule; and

the means for iterating the production rules comprises means for setting the current value for the iterate-every-time production rule to the next value for the iterate-every-time rule each time the template is enumerated.

19. The apparatus of claim 11, wherein the production rule is applied to the template by replacing the template character strings with the production rule current value when the production rule comparison field matches the template character string.

20. The apparatus of claim 11, wherein the production rules are organized into a plurality of rule groups, the means for applying each production rule in order until each production rule has been applied to the template comprises:

means for applying the production rules of a rule group in order and a group at a time, until each production rule in the rule group and each rule group has been applied to the template.

21. A program storage medium, readable by a computer, embodying one or more instructions executable by the computer to perform method steps of generating a sequence of character strings, the method steps comprising the steps of:

(a) defining a template comprising a plurality of template character strings;

(b) defining an ordered series of production rules, each production rule comprising a comparison field, an operator, and a substitution field defining an initial value and a current value;

(c) setting the current value of each production rule to the initial value;

(d) applying a production rule to the template by applying the production rule current value to the template characters when the production rule comparison field matches the template character string;

(e) repeating step (d), applying each production rule in order until each production rule has been applied to the template; and

(f) enumerating the template.

22. The program storage medium of claim 21, wherein the method steps further comprises the method steps of:

(g) iterating the production rules in accordance with the operator and the substitution fields; and

repeating steps (d) through (g) until a terminating condition on at least one of the production rules is satisfied.

23. The program storage medium of claim 22, wherein the terminal condition is satisfied when a number of template enumerations exceeds a stop value.

24. The program storage medium of claim 22, wherein:

the production rules are selected from a group comprising an iterate-in-turn production rule; and

the method step of iterating the production rules comprises the method step of setting the current value for the iterate-in-turn production rule to a next value of the iterate-in-turn production rule each time the template is enumerated and any preceding iterate-in-turn production rule of the ordered series of production rules has completed iteration.

25. The program storage medium of claim 24, wherein the substitution field of the iterate-in-turn production rule comprises a terminal value, and the terminating condition is satisfied when the current value exceeds the terminal value.

26. The program storage medium of claim 24, wherein:

the production rules are selected from a group further comprising an iterate-every-usage production rule; and

the method step of applying the production rule to the template further comprises the method step of iterating the iterate-every-usage production rule by setting the current value of the iterate-every-usage production rule to a next value.

27. The program storage medium of claim 21, wherein:

the production rules are selected from a group further comprising an associated production rule; and

the method step of iterating the production rules comprises the method step of setting the current value for the associated production rule to the next value for the associated production rule each time a production rule immediately preceding the associated production rule in the ordered series of production rules is iterated.

28. The program storage medium of claim 21, wherein:

the production rules are selected from a group further comprising an iterate every-time rule; and

the method step of iterating the production rules comprises the method step of setting the current value for the iterate-every-time production rule to the next value for the iterate-every-time production rule each time the template is enumerated.

29. The program storage medium of claim 21, wherein the production rule is applied to the template by replacing the template character strings with the production rule current value when the production rule comparison field matches the template character string.

30. The program storage device of claim 21, wherein the production rules are organized into a plurality of rule groups, and method step (e) comprises the method steps of:

(e1) repeating step (d), applying the production rules of a rule group in order until each production rule in the rule group has been applied to the template; and

(e2) repeating step (e1) above for each rule group in order until the production rules of each rule group has been applied to the template.

31. A method of generating a sequence of character strings, comprising the steps of:

defining a template comprising a plurality of template character strings;

defining a production rule set comprising an ordered series of production rules, each production rule comprising a comparison field having at least one comparison character and a substitution field having at least one substitution character; and

applying the series of production rules to the template one at a time by applying the substitution character of each production rule to the template when the comparison character of the production rule matches the template character string.

32. A memory for use in generating a sequence of character strings, comprising:

a first memory portion for storing a template comprising a plurality of template strings; and

a second memory portion for storing an ordered series of production rules, each production rule comprising a character field, an operator, and a substitution field comprising a list of elements and defining an initial value and a current value.