Browse Prior Art Database

Control Flow Layout Algorithm for Higher Level Language Programs

IP.com Disclosure Number: IPCOM000036526D
Original Publication Date: 1989-Oct-01
Included in the Prior Art Database: 2005-Jan-29
Document File: 2 page(s) / 14K

Publishing Venue

IBM

Related People

Pazel, DP: AUTHOR

Abstract

A process is disclosed for producing the control flow graph of a program written in a higher level procedural language. This higher level language is assumed to contain structured statement types typical of most higher level procedural languages, such as IF, ELSE, CASE, FOR, etc. Contiguous assignment and call statements may be clustered together into basic blocks, and thus such statements need not be considered separately. In addition, the language may contain unstructured statements such as GOTO, BREAK, etc. It is assumed that a presentation paradigm exists whereby structured statements are presented in a well- defined manner and sub-structures are nested.

This text was extracted from a PDF file.
This is the abbreviated version, containing approximately 52% of the total text.

Page 1 of 2

Control Flow Layout Algorithm for Higher Level Language Programs

A process is disclosed for producing the control flow graph of a program written in a higher level procedural language. This higher level language is assumed to contain structured statement types typical of most higher level procedural languages, such as IF, ELSE, CASE, FOR, etc. Contiguous assignment and call statements may be clustered together into basic blocks, and thus such statements need not be considered separately. In addition, the language may contain unstructured statements such as GOTO, BREAK, etc. It is assumed that a presentation paradigm exists whereby structured statements are presented in a well- defined manner and sub-structures are nested. For a given logical sequence of statements in a program, it is assumed that a syntax tree can be produced where each statement is represented by a node and sub- nodes reflect nested language structures. A basic layout algorithm is presented which lays out flow graphs for programs written entirely in structured statements. A small extension to this algorithm takes into account unstructured statements.

The motivation behind the layout algorithm is that with a syntax tree, the most nested language structures of a program are represented by nodes closer to the leaves of the tree. By doing a depth-first left-right scan of the tree, the dimensions of the most deeply nested programming language structures are first determined and from those the dimensions and relative positions of less deeply nested structures can be computed. The layout algorithm consists primarily of dimensioning mathematics for each structured language construct.

The basic layout algorithm applies to programs without unstructured programming statements (GOTOs). The two phases of this algorithm are:

Phase 1: The program is parsed into a syntax tree. Through a top- down left- right traversal of the tree, the dimensions of the flow graph structures are calculated. More precisely, after all language constructs represented by sub- trees of a parent node have been dimensioned, the language construct represented by the parent node can be dimensioned. Furthermore, assuming each language construct has its own coordinate system with the structure entry point being assigned the origin (0,0), the relative location of each sub-structure to the parent structure can be computed based on the parent structure's relative coordinate system.

Phase 2: The syntax tree is traversed again in order to give absolute locations to the sub-structures. First an absolute location is assigned to the top node's structure presentation. Then in a top-down left-right recursive traversal of the tree, absolute locations of each sub-structure are calculated from the its relative location value and...