Implementation--
Slicer
The slicer changes the source code, read into and stored in the Code List, to a group of lists that SimPlan can more easily use to perform the simulation. These lists include the symbol table, the flow control list and the slice list. First, the slicer finds all 'declare' statements. A program number tag is added to the symbol name and an entry for the symbol is added to the symbol table. Symbols declared as shared between programs receive a program number tag of '#0'. Otherwise, the program number tag is '#n' where n is the program number for the program entered into the program list. If a symbol of the declared name (+ program number tag) and type is present in the symbol table, a second entry is not added. Symbols declared shared are shared amongst all test programs in the simulation, even those that don't declare it. Symbols may be declared with the same name in different programs as the program number tag makes them different symbols. A symbol may not be declared shared in any test program and local in any of them in the same simulation. Next, the slicer finds all flow control statements ('if', 'while', 'goto') and makes the flow control list based on information found in those statements. For 'if' statements with an 'else' part, 4 entries are made to the flow control list: one into the 'then' part, one out of the 'then' part going around the 'else' part, one going around the 'then' part and into the 'else' part and one coming out of the 'else' part. For 'if' statements without an 'else' part, only 3 entries are needed: one into the 'then' part, one out of the 'then' part and one around the 'then' part. For 'while' statements, 4 entries are needed: one to pass the loop by, one to enter the loop, one to exit the loop and one to continue to the next iteration of the loop. For 'goto' statements, only 2 entries are needed: one to make the indicated transfer and one to block the transfer (condition is FALSE) to the next physical statement. The applicable condition expressions are entered with each control transfer entry. Finally, the slicer makes the list of program slices. For concurrent program simulations (several test programs running at the same time in the same simulation), a slice is made for each statement of the test program. If the statement changes the program's state, a reference to the changed variable and the expression that evaluates to the variable's new value is added to the slice information. This allows for the maximum possible extent of interleaving. For single program simulations (one test program running in a simulation), several state changes may occur in a slice. Consecutive assignment statements with no intervening flow control statements will be built into one slice. This lets the simulation run faster and use less memory. If the goal contains an entry for the program counter, the slice containing the program counter value is split into two slices, one ending on the statement of the program counter goal value and one starting at the next statement. This is because SimPlan suspends the simulator to check for goal accomplishment only at the end of a slice.
Related include files:
Return ...
- To my web page.
- To the SimPlan Opening page.
- To the Implementation Overview page.
- To the next page up.
Andrew Tompkins
Beaverton, OR 97006
Last rev: 17 JUL 03
URL: http://home.comcast.net/~andytom/simplan.docs/control/slicer.html
