Method and system for state machine translation

• US 8,495,593 B2
• Filed: 09/09/2005
• Issued: 07/23/2013
• Est. Priority Date: 09/09/2005
• Status: Expired due to Fees

• Current Assignee: International Business Machines Corporation
• Original Assignee: International Business Machines Corporation
• Inventors: Bennett, Jonathan David, Giffen, Perry Randolph, Martens, Axel, O'Farrell, William Gerald, Adams, Gregory D
• Primary Examiner(s): Khatri, Anil
• Application Number:
  US12/065,105
• Publication Number:
  US 20080263524A1
• Time in Patent Office: 2,874 Days
• Field of Search: 717124-131, 717136-144
• US Class Current: 717/136
• 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 computer-implemented method of translating a state machine into an executable state machine program, the method comprising:

determining states and transitions in a state machine;

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

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

generating statements within the second 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; and

wherein the step of generating a first 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 first structure.

2. The method of claim 1 wherein the first structure is a tree structure.

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

merging an initial state into a states list;

identifying transitions from the state merged into the states list;

merging the identified transitions into a transitions list;

merging end states of the identified transitions into the states list; and

repeating identifying transitions, merging the identified transitions, and merging end states of the identified transitions until the end states are final states of the state machine.

4. The method of claim 3 further comprising:

locating composite states in the states list; and

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:

locating unreachable states based on the states list and the transitions list; and

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

6. The method of claim 1 wherein the generating an executable state machine program comprises:

generating a basic form for the executable state machine program; and

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

7. The method of claim 1 wherein the generating statements within the second structure comprises:

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

8. The method of claim 7 wherein the determining the next state is performed at an end of the second structure, wherein the generating statements within the second structure further comprises:

generating a statement within the second structure to transition the current state to the next state prior to the iterative structure being performed, and wherein the second structure operates until the next state is one of the final states.

9. The method of claim 7 wherein the determining the next state is performed at an end of the second structure, wherein the generating statements within the second structure further comprises:

generating a statement within the second structure to transition the current state to the next state after the iterative structure is performed, and wherein the second structure is configured to operate until the current state is one of the final states.

10. The method of claim 1 wherein the generating statements within the second structure includes generating statements within the second 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.

11. The method of claim 1 further comprising:

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

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

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

14. A method of translating a state machine into an executable state machine program comprising:

determining states and transitions in a state machine;

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

generating an executable state machine program having a second structure that operates in non-final states wherein during execution the second structure performs 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 a next state; and

wherein the step of generating a first 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 first structure.

15. The method of claim 14 wherein the first structure is a tree structure.

16. The method of claim 14 wherein the determining comprises:

merging an initial state into a states list;

identifying transitions from the state merged into the states list;

merging the identified transitions into a transitions list;

merging end states of the identified transitions into the states list; and

repeating the identifying transitions, merging the identified transitions, and merging the end states of the identified transitions until the end states are final states of the state machine.

17. The method of claim 14 further comprising:

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

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

19. The method of claim 17 wherein the transitioning is performed after the iterative structure is performed and wherein the second structure is configured to operate until the current state is one of the final states.

20. The method of claim 14 further comprising:

generating statements within the second 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 14 further comprising:

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

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

determining states and transitions in a state machine;

associating events in the state machine with the determined states and transitions;

generating a basic structure for an executable 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; and

wherein the step of generating a first 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 first structure.

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, and wherein 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, and wherein 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 an executable state machine program comprising:

a processor configured to execute a state machine translator which includes;

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

a parser for associating events and the determined states and transitions in the state machine; and

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

a state process component for generating a structure in the executable 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, the events component comprising;

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; and

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.

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 state program generator further comprises:

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

32. 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.

33. 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.

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 after the next state being determined, and wherein the structure operates until the current state is one of the final states.

35. A computer readable storage medium having stored thereon computer executable instructions for translating a state machine into an executable state machine program, the computer-executable instructions implementing a method comprising:

determining states and transitions in a state machine;

associating events with the determined states and transitions in the state machine;

generating an executable 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; and

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.

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

determining the states and transitions in the state machine comprising;

merging an initial state into a states list;

identifying transitions from the state merged into the states list;

merging the identified transitions into a transitions list;

merging end states of the identified transitions into the states list; and

repeating identifying transitions, merging the identified transitions, and merging end states of the identified transitions until the end states are the state machine'"'"'s final states; and

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.

37. The computer-executable instructions of claim 35 wherein the generating an executable state machine program comprises:

generating a basic form for the executable state machine program; and

generating the structure where the structure is a loop that operates for non-final states, and wherein the generating statements within the structure comprises;

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

38. The computer-executable instructions of claim 37 wherein the determining the next state is performed at the end of the structure, and wherein the 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.

39. The computer-executable instructions of claim 37 wherein the determining the next state is performed at the end of the structure, wherein the 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.

40. The computer-executable instructions of claim 35 further comprising:

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

41. A computer readable storage medium having stored thereon computer-executable instructions for translating a state machine into an executable state machine program the computer-executable instructions implementing a method comprising:

determining states and transitions in a state machine;

associating the determined states and transitions with events in a state machine;

generating the executable state machine program having a structure that operates in non-final states, wherein during execution the structure is configured to perform 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 a next state;

wherein generating the executable state machine program comprises;

generating a basic form for the executable state machine program; and

generating the structure where the structure is a loop that operates for non-final states, and wherein the generating statements within the structure comprises;

generating an iterative structure within the structure to perform the detecting and

evaluating until either the detected event is valid for the current state or an error occurs.

42. The computer-executable instructions of claim 41 wherein the determining the states and transitions in the state machine comprises:

merging an initial state into a states list;

identifying transitions from the state merged into the states list;

merging the identified transitions into a transitions list;

merging end states of the identified transitions into the states list; and

repeating identifying transitions, merging the identified transitions, and

merging end states of the identified transitions until the end states are the state machine'"'"'s final states.

43. The computer-executable instructions of claim 41 wherein the determining the next state is performed at the end of the structure, and wherein the 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.

44. The computer-executable instructions of claim 41 wherein the determining the next state is performed at the end of the structure, wherein the 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.

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

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

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

determining states and transitions in a state machine;

associating events in the state machine with the determined states and transitions;

generating a basic structure for the executable 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; and

wherein the generating the executable state machine program comprises;

generating a basic form for the executable state machine program; and

generating the structure where the structure is a loop that operates for non-final states, and wherein the generating statements within the structure comprises;

generating an iterative structure within the structure to perform detecting and

evaluating until either the detected event is valid for the current state or an error occurs.

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

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

49. The computer-executable instructions of claim 46 further comprising:

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