恡楍档-FiniteModels.ppt

(c) Mauro Pezzè Michal Young 2003 Finite Models Learning objectives Understand goals and implications of finite state abstraction Learn how to model program control flow with graphs Learn how to model the software system structure with call graphs Learn how to model finite state behavior with finite state machines Properties of Models Compact: representable and manipulable in a reasonably compact form What is reasonably compact depends largely on how the model will be used Predictive: must represent some salient characteristics of the modeled artifact well enough to distinguish between good and bad outcomes of analysis no single model represents all characteristics well enough to be useful for all kinds of analysis Semantically meaningful: it is usually necessary to interpret analysis results in a way that permits diagnosis of the causes of failure Sufficiently general: models intended for analysis of some important characteristic must be general enough for practical use in the intended domain of application Graph Representations: directed graphs Directed graph: N (set of nodes) E (relation on the set of nodes ) edges Graph Representations: labels and code We can label nodes with the names or descriptions of the entities they represent. If nodes a and b represent program regions containing assignment statements, we might draw the two nodes and an edge (a,b) connecting them in this way: Multidimensional Graph Representations Sometimes we draw a single diagram to represent more than one directed graph, drawing the shared nodes only once class B extends (is a subclass of) class A class B has a field that is an object of type C Finite Abstraction of Behavior an abstraction function suppresses some details of program execution (Intraprocedural) Control Flow Graph nodes = regions of source code (basic blocks) Basic block = maximal program region with a single entry and single exit point Often statements are grouped in single regions to get a compact model Sometime sin