Method and System for State Machine Translation

• US 20080263524A1
• Filed: 09/09/2005
• Published: 10/23/2008
• Est. Priority Date: 09/09/2005
• Status: Active Grant

• Current Assignee: International Business Machines Corporation
• Original Assignee: International Business Machines Corporation
• Inventors: O'Farrell, William Gerald, Martens, Axel, Adams, Gregory D., Bennett, Jonathan David, Giffen, Perry Randolph
• Granted Patent: US 8,495,593 B2
• Time in Patent Office: Days
• US Class Current: 717/127
• CPC Class Codes: G06F 8/00 Arrangements for software engineering testing or debugging G06F11/36; administrative, planning or organisation aspects of software project management G06Q10/06

Abstract

A state machine program is generated from a state machine. The state machine has states, transitions and events. A basic structure for the state machine program is generated. The basic structure has therein a structure that operates in non-final states. A statement is generated within the structure for detecting an event. A statement is generated within the structure for evaluating the detected event based on a current state to identify if the current state is valid for the detected event. A statement is generated within the structure for determining a next state if the current state is valid. A statement is generated within the structure for transitioning the current state to the next state.

Claims

1. A method of translating a state machine into a state machine program comprising:

identifying relationships between states, transitions and events in the state machine;

generating a state machine program having a structure that operates in non-final states; and

generating statements within the structure for detecting an event,

evaluating the detected event based on a current state to identify if the current state is valid for the detected event, and

determining a next state if the current state is valid.

2. The method of claim 1 wherein the step of identifying comprises:

determining the states and transitions in the state machine; and

generating a tree structure representing the state machine by associating events in the state machine with the determined states and transitions.

3. The method of claim 2 wherein the step of determining comprises the following steps:

(a) merging an initial state into a states list;

(b) identifying transitions from the state merged into the states list;

(c) merging the identified transitions into a transitions list;

(d) merging end states of the identified transitions into the states list; and

(e) repeating steps (b) to (d) until the end states are the state machine'"'"'s final states.

4. The method of claim 3 further comprising the following steps:

(f) locating composite states in the states list; and

(g) replacing the located composite states with a composite entry state and a composite end state in the states list.

5. The method of claim 3 further comprising the following steps:

(f) locating unreachable states based on the states list and the transitions list; and

(g) creating a transition from the initial state to the located unreachable states in the transitions list.

6. The method of claim 2 wherein the step of generating a tree structure comprises:

determining all events in the state machine;

correlating the events with states in the state machine; and

correlating the event correlated states with transitions in the state machine to form the tree structure.

7. The method of claim 1 wherein the step of generating a state machine program comprises:

generating a basic form for the state machine program; and

generating the structure where the structure is a loop that operates for non-final states.

8. The method of claim 1 wherein the step of generating statements within the structure comprises:

generating an iterative structure within the structure to perform the steps of detecting and evaluating until either the detected event is valid for the current state or an error occurs.

9. The method of claim 8 wherein the step of determining the next state is performed at the end of the structure,

wherein the step of generating statements within the structure further comprises:

generating a statement within the structure to transition the current state to the next state prior to the iterative structure being performed, and

wherein the structure operates until the next state is one of the final states.

10. The method of claim 8 wherein the step of determining the next state is performed at the end of the structure,

wherein the step of generating statements within the structure further comprises:

generating a statement within the structure to transition the current state to the next state after the iterative structure is performed, and

wherein the structure operates until the current state is one of the final states.

11. The method of claim 1 wherein the step of generating statements within the structure includes generating statements within the structure for performing an entry action for the current state upon transitioning into the current state and performing an exit action for the current state prior to transitioning to the next state.

12. The method of claim 1 further comprising:

generating a timer to identify timeout conditions and generate an event for the identified timeout conditions.

53. A computer readable medium having stored thereon computer-executable instructions for executing a state machine program, said instructions having been generated by implementing the method steps of claims 1.

54. A computer program product comprising a computer useable medium having a computer readable program embodied in said medium, the computer readable program having been generated by implementing the method steps of claim 1 whereby, when executed on a computer, causes said computer to operate as a state machine having states, transitions and events.

13. A method of translating a state machine into a state machine program comprising:

identifying relationships between states, transitions and events in the state machine;

generating a state machine program having a structure that operates in non-final states; and

wherein during execution the structure performs the functions of detecting an event,

evaluating the detected event based on a current state to identify if the current state is valid for the detected event, and

transitioning the current state to the next state.

14. The method of claim 13 wherein the step of identifying comprises:

determining the states and transitions in the state machine; and

generating a tree structure representing the state machine by associating events in the state machine with the determined states and transitions.

15. The method of claim 14 wherein the step of determining comprises the following steps:

(a) merging an initial state into a states list;

(b) identifying transitions from the state merged into the states list;

(c) merging the identified transitions into a transitions list;

(d) merging end states of the identified transitions into the states list; and

(e) repeating steps (b) to (d) until the end states are the state machine'"'"'s final states.

16. The method of claim 14 wherein the step of generating a tree structure comprises:

determining all events in the state machine;

correlating the events with states in the state machine; and

correlating the event correlated states with transitions in the state machine to form the tree structure.

17. The method of claim 13 wherein the step of generating statements within the structure comprises:

generating an iterative structure within the structure to perform the steps of detecting, evaluating and determining until either the detected event is valid for the current state or an error occurs.

18. The method of claim 17 wherein the step of determining the next state is performed at the end of the structure, the step of transitioning is performed prior to the iterative structure and the structure operates until the next state is one of the final states.

19. The method of claim 17 wherein the step of determining the next state is performed at the end of the structure, the step of transitioning is performed after the iterative structure is performed and the structure operates until the current state is one of the final states.

20. The method of claim 13 wherein the step of generating statements within the structure includes generating statements within the structure for performing an entry action for the current state upon transitioning into the current state and performing an exit action for the current state prior to transitioning to the next state.

21. The method of claim 13 further comprising:

generating a timer to identify timeout conditions and generate an event for the identified timeout conditions.

22. A method of generating a state machine program from a state machine, the state machine having states, transitions and events, said method comprising:

generating a basic structure for the state machine program, the basic structure having therein a structure that operates in non-final states;

generating a statement within the structure for detecting an event;

generating a statement within the structure for evaluating the detected event based on a current state to identify if the current state is valid for the detected event;

generating a statement within the structure for determining a next state if the current state is valid; and

generating a statement within the structure for transitioning the current state to the next state.

23. The method of claim 22 further comprising:

generating an iterative structure within the structure to enclose the statement for detecting an event, the statement for evaluating the detected event and the statement for determining the next state to perform these statements until either the detected event is valid for the current state or an error occurs.

24. The method of claim 23 wherein the statement for determining the next state is performed at the end of the structure, the statement for transitioning is performed prior to the iterative structure and the structure operates until the next state is one of the final states.

25. The method of claim 23 wherein the statement for determining the next state is performed at the end of the structure, the statement for transitioning is performed after the iterative structure is performed and the structure operates until the current state is one of the final states.

26. The method of claim 22 further comprising:

generating a statement within the structure for performing an entry action for the current state upon transitioning into the current state; and

generating a statement within the structure for performing an exit action for the current state prior to transitioning to the next state.

27. The method of claim 22 further comprising:

generating a timer to identify timeout conditions and generate an event for the identified timeout conditions.

28. A system for translating a state machine into a state machine program comprising:

a lexical analyzer for determining states and transitions in the state machine;

a parser for determining relationships between events and the determined states and transitions; and

a program generator for generating a state machine program, said program generator comprising;

a state process component for generating a structure in the state machine program that operates in non-final states, said state process component comprising;

an events component for generating a statement within the structure for detecting an event;

an event determination component for generating a statement within the structure for evaluating the detected event based on a current state to identify if the current state is valid for the detected event; and

a transition component for generating a statement within the structure for determining a next state if the current state is valid.

29. The system of claim 28 wherein the lexical analyzer comprises:

a state detection component for identifying states in the state machine and establishing a states list with the identified states; and

a transition detection component for identifying transitions from the identified states and establishing a transitions list with the identified transitions.

30. The system of claim 29 wherein the lexical analyzer further comprises:

a state modification component for replacing the composite states in the states list with a composite entry state and a composite end state, and creating a transition from the initial state to an unreachable states in the transitions list.

31. The system of claim 28 wherein the parser comprises:

a state mapping component for correlating events in the state machine with states in the state machine; and

a transition mapping component for correlating the event correlated states with transitions in the state machine to form the tree structure.

32. The system of claim 28 wherein the state program generator further comprises:

a program component for generating a basic form for the state machine program that encompasses the structure generated by the state process component.

33. The system of claim 28 wherein the state program generator further comprises

a timeout component for identifying timeout conditions and generating an events for the identified timeout conditions.

34. The system of claim 28 wherein the statement for determining the next state generated by the transition component is performed at the end of the structure,

wherein the state process component further generates a statement within the structure to transition the current state to the next state prior to the event being detected, and

wherein the structure operates until the next state is one of the final states.

35. The system of claim 28 wherein the statement for determining the next state generated by the transition component is performed at the end of the structure,

wherein the state process component further generates a statement within the structure to transition the current state to the next state after the next state being determined, and

wherein the structure operates until the current state is one of the final states.

36. A computer readable medium having stored thereon computer-executable instructions for translating a state machine into a state machine program, the computer-executable instructions implementing the steps comprising:

identifying relationships between states, transitions and events in the state machine;

generating a state machine program having a structure that operates in non-final states; and

generating statements within the structure for detecting an event,

evaluating the detected event based on a current state to identify if the current state is valid for the detected event, and

determining a next state if the current state is valid.

37. The computer-executable instructions of claim 36 wherein the step of identifying comprises:

determining the states and transitions in the state machine comprising the following steps;

(a) merging an initial state into a states list;

(b) identifying transitions from the state merged into the states list;

(c) merging the identified transitions into a transitions list;

(d) merging end states of the identified transitions into the states list; and

(e) repeating steps (b) to (d) until the end states are the state machine'"'"'s final states;

generating a tree structure representing the state machine comprising;

determining all events in the state machine;

correlating the events with states in the state machine; and

correlating the event correlated states with transitions in the state machine to form the tree structure.

38. The computer-executable instructions of claim 36 wherein the step of generating a state machine program comprises:

generating a basic form for the state machine program; and

generating the structure where the structure is a loop that operates for non-final states, and

wherein the step of generating statements within the structure comprises;

generating an iterative structure within the structure to perform the steps of detecting and evaluating until either the detected event is valid for the current state or an error occurs.

39. The computer-executable instructions of claim 38 wherein the step of determining the next state is performed at the end of the structure,

wherein the step of generating statements within the structure further comprises:

generating a statement within the structure to transition the current state to the next state prior to the iterative structure being performed, and

wherein the structure operates until the next state is one of the final states.

40. The computer-executable instructions of claim 38 wherein the step of determining the next state is performed at the end of the structure,

wherein the step of generating statements within the structure further comprises:

generating a statement within the structure to transition the current state to the next state after the iterative structure is performed, and

wherein the structure operates until the current state is one of the final states.

41. The computer-executable instructions of claim 36 further comprising:

generating a timer to identify timeout conditions and generate an event for the identified timeout conditions.

42. A computer readable medium having stored thereon computer-executable instructions for translating a state machine into a state machine program the computer-executable instructions implementing the steps comprising:

identifying relationships between states, transitions and events in the state machine;

generating a state machine program having a structure that operates in non-final states; and

wherein during execution the structure performs the functions of detecting an event,

evaluating the detected event based on a current state to identify if the current state is valid for the detected event, and

transitioning the current state to the next state.

43. The computer-executable instructions of claim 42 wherein the step of identifying comprises:

determining the states and transitions in the state machine comprising the following steps;

(a) merging an initial state into a states list;

(b) identifying transitions from the state merged into the states list;

(c) merging the identified transitions into a transitions list;

(d) merging end states of the identified transitions into the states list; and

(e) repeating steps (b) to (d) until the end states are the state machine'"'"'s final states;

generating a tree structure representing the state machine comprising;

determining all events in the state machine;

correlating the events with states in the state machine; and

correlating the event correlated states with transitions in the state machine to form the tree structure.

44. The computer-executable instructions of claim 42 wherein the step of generating a state machine program comprises:

generating a basic form for the state machine program; and

generating the structure where the structure is a loop that operates for non-final states, and

wherein the step of generating statements within the structure comprises;

generating an iterative structure within the structure to perform the steps of detecting and evaluating until either the detected event is valid for the current state or an error occurs.

45. The computer-executable instructions of claim 44 wherein the step of determining the next state is performed at the end of the structure,

wherein the step of generating statements within the structure further comprises:

generating a statement within the structure to transition the current state to the next state prior to the iterative structure being performed, and

wherein the structure operates until the next state is one of the final states.

46. The computer-executable instructions of claim 44 wherein the step of determining the next state is performed at the end of the structure,

wherein the step of generating statements within the structure further comprises:

generating a statement within the structure to transition the current state to the next state after the iterative structure is performed, and

wherein the structure operates until the current state is one of the final states.

47. The computer-executable instructions of claim 42 further comprising:

generating a timer to identify timeout conditions and generate an event for the identified timeout conditions.

48. A computer readable medium having stored thereon computer-executable instructions for generating a state machine program from a state machine, the state machine having states, transitions and events, the computer-executable instructions implementing the steps comprising:

generating a basic structure for the state machine program, the basic structure having therein a structure that operates in non-final states;

generating a statement within the structure for detecting an event;

generating a statement within the structure for evaluating the detected event based on a current state to identify if the current state is valid for the detected event;

generating a statement within the structure for determining a next state if the current state is valid; and

generating a statement within the structure for transitioning the current state to the next state.

49. The computer-executable instructions of claim 48 wherein the step of generating a state machine program comprises:

generating a basic form for the state machine program; and

generating the structure where the structure is a loop that operates for non-final states, and

wherein the step of generating statements within the structure comprises;

generating an iterative structure within the structure to perform the steps of detecting and evaluating until either the detected event is valid for the current state or an error occurs.

50. The computer-executable instructions of claim 49 wherein the step of determining the next state is performed at the end of the structure, the step of transitioning is performed prior to the iterative structure and the structure operates until the next state is one of the final states.

51. The computer-executable instructions of claim 49 wherein the step of determining the next state is performed at the end of the structure, the step of transitioning is performed after the iterative structure is performed and the structure operates until the current state is one of the final states.

52. The computer-executable instructions of claim 48 further comprising:

generating a timer to identify timeout conditions and generate an event for the identified timeout conditions.