Accession Number:

ADA065265

Title:

Parsing Flowcharts and Series-Parallel Graphs

Descriptive Note:

Technical rept.

Corporate Author:

STANFORD UNIV CA DEPT OF COMPUTER SCIENCE

Personal Author(s):

Report Date:

1978-11-01

Pagination or Media Count:

235.0

Abstract:

The main results presented in this work are an algorithm for the recognition of General Series Parallel GSP digraphs and an approach to the structural analysis of the control flow graphs of programs. The GSP recognition algorithm determines in Onm steps whether an acyclic diagraph with n vertices and m edges is GSP, and if it is, describes its structure in terms of two simple operations on diagraphs. The algorithm is based on the relationship between GSP diagraphs and the more standard class of TTSP multidigraphs. Our approach to the analysis of flow graphs uses the triconnected components algorithm to find single-entry, single-exit regions. Under certain conditions -- that we identify -- this method will produce structural information suitable for the global flow analysis of control flow graphs in time proportional to the number of vertices and edges of the graph being analyzed.

Subject Categories:

  • Theoretical Mathematics
  • Computer Programming and Software
  • Computer Systems

Distribution Statement:

APPROVED FOR PUBLIC RELEASE