Unravel: A CASE Tool to
Assist Evaluation of
High Integrity Software
Volume 1: Requirements and Design

Current practice for examination of a high integrity software artifact is often a manual process that is slow, tedious, and prone to human errors. This report describes a Computer Aided Software Engineering (CASE) tool, unravel, that can assist evaluation of high integrity software by using program slices to extract computations for examination. The tool can currently be used to evaluate software written in ANSI C and is designed such that other languages can be added.

Program slicing is a static analysis technique that extracts all statements relevant to the computation of a given variable. Program slicing is useful in program debugging, software maintenance and program understanding. Application of program slicing to evaluation of high integrity software reduces the effort in examining software by allowing a software reviewer to focus attention on one computation at a time. Once a software reviewer has identified a variable for further investigation, the reviewer directs unravel to compute a program slice on the variable. Instead of examining the entire program, only the statements in the slice need to be examined by the reviewer. By speeding up the process of locating relevant code for examination by the reviewer, a larger sample of the software can be inspected with greater confidence that some relevant section of source code has not been missed.

The source code for unravel is available and requires a UNIX or POSIX environment, an ANSI C compiler and the MIT X Window System, version 11 release 5 or later.

Volume 1 of this report describes the requirements, design and evaluation of unravel. Volume 2 is a user manual and tutorial for the unravel software.

Unravel is a prototype Computer Aided Software Engineering (CASE) tool that can be used to statically evaluate ANSI C source code using program slicing. Development of unravel was funded by both the United States Nuclear Regulatory Commission (NRC) and the National Communications System (NCS) under contracts RES-92-005, FIN #L24803, and DNRO46115, respectively. Under the terms of those contracts, the National Institute of Standards and Technology (NIST) supplied the prototype to both funding parties.

Program slicing is a static analysis technique that extracts all statements relevant to the computation of a given variable. Program slicing is useful in program debugging, software maintenance and program understanding. Application of program slicing to evaluation of high integrity software reduces the effort in examining software by allowing a software reviewer to focus attention on one computation at a time.

By combining program slices using logical set operations, unravel can identify code that is executed in more than one computation. This information is immediately useful for addressing issues of high integrity software, since a failure involving this code may lead to a malfunction of more than one logical software component. In the case of safety systems, which commonly use several computations for protection, common code among them can provide a single point of failure. In the case of security, what may have been perceived as a secure path may be penetrated by an otherwise unsuspected approach. The identification of common code enables the developer to consider redesign or to emphasize verification and validation activities in those regions to provide assurance of the program.

Unravel was evaluated in the context of reviewing safety system software for quality. The evaluation considered the size of slices produced, time to compute slices and usability by a novice user. The objectives of the evaluation were to determine the following:

1. Are program slices smaller than the original program to an extent that is useful to a software reviewer evaluating a program?
2. Can program slices be computed quickly enough to be useful?
3. Is unravel usable by a novice user?

Two examples of typical safety system code were used to test and refine unravel. Demonstration of unravel using these and other examples were given to software reviewers. The demonstrations resulted in improvements to the user interface and in the identification of features to be explained in more depth in the user manual or to be included in a later version of unravel.

Examination of software is often a manual process that is slow, tedious, and prone to human errors. With unravel, once a reviewer has identified a variable for further investigation, the reviewer directs unravel to compute a program slice on the variable. Instead of examining the entire program, the reviewer only needs to examine the statements in the slice. By speeding up the process of locating relevant code for examination by the reviewer, a larger sample of the software can be inspected with greater confidence that some relevant section of source code has not been missed.

Without any tool, a reviewer evaluates the software for common code by manually searching for code shared between two computations until it is determined that there is no common code, or that the common code present will not compromise the mission of the safety critical software. With unravel, once two computations that could be vulnerable to common mode failure have been identified, program slices can be computed to find statements relevant to each computation. Source program statements that have potential to cause common mode failure would be present in the intersection of the program slices.

Unravel consists of three main components, called the analyzer, linker and slicer. The analyzer and linker components can process up to 100,000 lines of source code in less than 10 minutes. The linear behavior of the analyzer and linker leads to stable run time performance. The slicer component does not use a linear algorithm, but rather uses a quadratic algorithm that can have significant run time variability. It should be noted that there is potential for significant algorithm improvement. For example, after one small change in the slicer code the longest time on a SPARCstation 2 to compute a slice on code from a 4,000 line actual safety system dropped, from 10 hours to 3 hours. Other areas that can be improved include loop analysis and procedure calls.

Table Of Contents

1 Introduction

This report describes the design and development of unravel, developed at the National Institute of Standards and Technology (NIST). Development of unravel was funded by both the United States Nuclear Regulatory Commission (NRC) and the National Communications System (NCS) under contracts RES-92-005, FIN #L24803, and DNRO46115, respectively. Unravel is a Computer Aided Software Engineering (CASE) tool that can be used to statically evaluate ANSI C[1] source code using program slicing. Unravel may also be used to examine software code for computer security functions. The tool can currently be used to evaluate software written in ANSI C and is designed such that other languages can be added.

Program slicing is a static analysis technique[3] that extracts all statements relevant to the computation of a given variable. Program slicing is useful in program debugging[4], software maintenance[5] and program understanding[6]. Application of program slicing to evaluation of high integrity software reduces the effort in examining software by allowing a software reviewer to focus attention on one computation at a time. Once a software reviewer has identified a variable for further investigation, the reviewer directs unravel to compute a program slice on the variable. Instead of examining the entire program, only the statements in the slice need to be examined by the reviewer. By speeding up the process of locating relevant code for examination by the reviewer, a larger sample of the software can be inspected with greater confidence that some relevant section of source code has not been missed.

Unravel is intended to support the understanding and evaluation of software by allowing the user to investigate a program through program slices.

To achieve the goal of making unravel a portable and easy to use slicing tool, the following general requirements were met:

• The user must be able to execute unravel with minimal knowledge of the platform on which it resides.
• The user must be able to interactively specify criteria for computing program slices.
• The user must be able to view program slices on-screen.
• The user must be able to perform logical set operations (e.g., intersections) on program slices.
• The user must be able to use unravel without needing to understand the intrinsics of the program; hence a user manual and user interface must contain all operational information.
• The implementation must comply with the following standards: POSIX[9] operating system interface, ANSI C, and the X Window System[10].

The source code for unravel is available and requires a UNIX or POSIX environment, an ANSI C compiler and the MIT X Window System, version 11 release 5 or later.

Section 2 discusses slicing ANSI C. Section 3 contains the requirements for building unravel. Section 4 consists of the design of unravel. Section 5 provides the system evaluation and performance report. Appendices A and B contain the Language Independent Format and the Yacc ANSI C grammar respectively. Volume 2 is the unravel user manual.

2 Slicing ANSI C

Program slicing can be used to transform a large program into a smaller one containing only those statements relevant to the computation of a given variable. Program slices have been shown to aid program understanding, program debugging, program maintenance, and automatic integration of program variants[7].

This section contains definitions relevant to program slicing.

Active Set.

The active set at statement n for slicing criterion <L, V> is a set of program variables, active(n), such that the value of any member of active(n) just before execution of statement n could influence the value of V just before execution of statement L. Informally, the active set is the set of variables that determine the value of the criterion variable at the criterion location.

Code Generator.

See Compiler.

Code Improver.

See Compiler.

Compiler.

Production of an object program from a source program is often modeled with concepts from linguistics. A source program is viewed as consisting of words from a vocabulary. The words are assembled into valid sentences of the language that form program statements. Each sentence is used to generate object code corresponding to each program statement. Modern compilers are usually designed in four components:

1. Scanner reads the program source code and collects strings of characters into the fundamental vocabulary units of the programming language called tokens. This vocabulary contains language key words, operators, text strings and identifiers.
2. Parser takes the tokens produced by the scanner and a grammar describing the language and checks that the sequence of tokens represents valid sentences in the language. A sequence of tokens that is not a valid sentence of the language grammar is a syntax error.
3. Code Generator is called by the parser for each valid sentence the parser recognizes to produce corresponding object code.
4. Code Improver Uses data-flow analysis to revise the produced object code so that the run-time execution is faster or requires less memory. This step is usually called code optimization.

Data-Flow Analysis.

Using information about program structure, variable initialization, assignment of values to variables, and use of program variable values to answer questions about the behavior of program variables. Data-flow analysis is often used in compiler optimization of generated object code.

Defs(n).

The set of variables defined (assigned to) at statement n. In data-flow analysis, modification of a variable is called a definition of the variable.

Dependence Graph.

A program representation, defined by Ferrante[8], with many applications to program manipulation including program slicing. The PDG (program dependence graph) has the same nodes as a flow-graph but the edges represent control and data dependence within a program.

Flow Graph.

A representation of the control structure of a program as a directed graph. The nodes of the graph correspond to statements or contiguous tokens of a source program. The edges correspond to program control flow.

Idefs(n).

The set of variables specifying indirect assignment by a pointer at statement n. Each idef entry is a pair indicating a variable and a level of indirection. Level 0 represents a direct assignment to the variable. Level 1 represents an assignment to a variable whose address is contained in the idef entry variable.

Irefs(n).

The set of variables specifying indirect reference by a pointer at statement n. Each iref entry is a pair indicating a variable and a level of indirection. Level 0 represents a direct reference to the variable. Level 1 represents a reference to a variable whose address is contained in the iref entry variable.

Parser.

See Compiler.

Pointer.

A variable that contains the address of a variable or other program object such as a procedure.

Pred(n).

The set of statements that can be executed immediately before statement n. The predecessors of n.

Program Slice.

Given a syntactically correct source program P, in some programming language, and a slicing criterion C = <L,V>. Where L is a location in the program and V is a variable in the program. S is a slice of program P for criterion C if the following are true.

1. S is derived from P by deleting zero or more tokens from P.
2. S is syntactically correct.
3. The value of V just before control reaches location L is the same for EXECUTE(P) as EXECUTE(S).

Program Dice.

The result of application of logical set operation to two or more program slices is a program dice. The intersection of two slices yields the statements in common to both computations. A software fault in the common code can be a single point of failure for both computations. The intersection of one slice with a logical complement of a second slice yields the set of statements in the first slice that has no influence on the second computation. This is useful when trying to isolate a fault in the second computation.

Refs(n).

The set of variables referenced at statement n.

Requires(n).

A set of nodes that is required to also be included in a slice along with node n. The set is used to specify control statements (e.g., if or while) enclosing statement n or other tokens that are syntactically part of statement n but are not contiguous with the main group of tokens comprising the statement.

Scanner.

See Compiler.

Slicing criterion.

A slicing criterion, for a program is a tuple <L,V> where L is a statement in the program and V is a variable. A program slice is computed on V, at statement L. Where the meaning is clear from context, V is extended to a subset of program variables.

Succ(n).

The set of statements that can be executed immediately after statement n.

Token.

The output of the scanner and input to the parser; the fundamental lexical units of a language.

2.2 General Description

2.2.1 Program Slicing Algorithm

A program slicing algorithm must locate all statements relevant to a given slicing criterion. The essence of a slicing algorithm is the following: Starting with the statement specified in the slicing criterion, include each predecessor that assigns a value to any variable in the slicing criterion and generate a new slicing criterion for the predecessor by deleting the assigned variables from the original slicing criterion and adding any variables referenced by the predecessor. The slicing algorithm considers the following language features:

  1    Expression statements
  2    Compound control statements
  3    Structure variables
  4    Indirect assignment by pointer
  5    Indirect reference by pointer
  6    Dynamic structures
  7    References to structure members by pointer
  8    Assignment to structure members by pointer
  9    Procedure calls

2.2.1.1 Expression Statements

An expression statement is the primary method in ANSI C of expressing an assignment of a computed value to a variable. For expression statement n, a predecessor of statement m, the defs(n) set and the slicing criterion determine if an expression statement is included in a slice. Statement n is included in a slice for criterion <m, v> if statement n assigns a value to variable v.

     1  main()
     2  {
     3      int red, green, blue, yellow;
     4      int sweet,sour,salty,bitter;
     5      int i;
     6
     7      red = 1;
     8      blue = 5;
     9      green = 8;
    10      yellow = 2;
    11
    12      red = 2*red;
    13      sweet = red*green;
    14      sour = 0;
    15      i = 0;
    16      while ( i < red) {
    17          sour = sour + green;
    18          i = i + 1;
    19      }
    20      salty = blue + yellow;
    21      yellow = sour + 1;
    22      bitter = yellow + green;
    23
    24      printf ("%d %d %d %d\n",
    25          sweet,sour,salty,bitter);
    26      exit(0);
    27  }

2.2.1.2 Compound Control Statements

A compound control statement is a statement that has a condition directly controlling the execution of another statement (possibly also a compound statement). Control statements such as if, switch, while, for, and do ... while should be included in a program slice whenever any statement governed by the control statement is included in a slice. When control statement k is added to a program slice, the slice on the criterion <k, refs(k)> is added to the original slice computation.

A requires set is maintained for each statement to specify an enclosing control statement or to specify other statements and tokens that should always be included with the statement in a slice.

The rules for representing C statements as flow-graph nodes and for specifying requires sets are as follows:

1. A statement that is composed of noncontiguous tokens is divided into two or more data- flow nodes such that each group of contiguous tokens is one or more nodes. Examples are the matching braces of a compound statement and the do ... while statement.
2. An additional data-flow node is used to represent each C prefix (++x), postfix (x++) or comma (x+y, z) operator in an expression. A conditional operator uses three additional data-flow nodes.
3. Any compound statement that is represented with more than one data-flow node has one node designated for inclusion in requires sets. Any node controlled by the compound statement references the designated node in its requires set. The other nodes of the compound statement are referenced in the requires set of the designated node. This strategy reduces the size of the requires sets.

The rule for slicing expression statements with given in section 2.2.1.1 is actually a special case of an empty requires set from the following rule:

The above rule states that when add the following to the slice:

• statement n,
• the slice on each member of refs(n) at statement n, and
• for each statement k, a member of requires(n), slice on each variable referenced in statement k.

2.2.1.3 Structure Variables

4.2.3.2 Procedure Headers

A procedure header, function_name (f1,f2,...fn), uses the following LIF codes:

# define LIF_PROC_START  1  /*  1(node,pid,name)              */
# define LIF_PROC_END    2  /*  2(node[,S][,R])               */
# define LIF_FORMAL_ID   3  /*  3(id,name[,A][,P])            */

The LIF_PROC_END indicates a static declared procedure with an S flag. Procedures that return an expression are indicated with an R flag.

For formal parameters, the variable attributes pointer and array are indicated by the codes: P and A in the LIF_FORMAL_ID record.

All local variable declarations, (LIF_LOCAL_ID), and flow graph node related LIF codes appear between the LIF_PROC_START and the LIF_PROC_END. The following is an example of a procedure header and generated LIF codes:

add_to_result(int a, int *b, int c[]){ ... body ...}

1(13,5,add_to_result)
3(1,a)
3(2,b,P)
3(3,c,A)
... body ...
2(30)

4.2.3.3 Declarations

Declarations generate the following:

# define LIF_LOCAL_ID    4  /*  4(id,name[,S][,P][,X][,A])    */
# define LIF_GLOBAL_ID   5  /*  5(id,name[,S][,P][,X][,A])    */

Declarations generate a positive, id-code for each variable. Each global variable (declared outside a procedure) is allocated a unique id-code. Each procedure has a separate set of id-codes for local variables and formal parameters, starting from 1. All local variable declarations, (LIF_LOCAL_ID), appear between the LIF_PROC_START and the LIF_PROC_END. Global variable declarations, (LIF_GLOBAL_ID) may appear anywhere outside of a LIF_PROC_START and LIF_PROC_END pair. The variable attributes, static, pointer, external, and array are indicated by the codes: S, P, X and A. An example of LIF codes generated for declarations follows:

static int a,*b,c[10];
extern x;
fun(int y)
{
int u,v,w,x;
}

proc(int *z)
{
int a,w;
}

1(1,1,fun)
3(1,y)
4(2,u)
4(3,v)
4(4,w)
4(5,x)
2(2)
1(3,2,proc)
3(1,z,P)
4(2,a)
4(3,w)
2(4)
5(1,a,S)
5(2,b,S,P)
5(3,c,S,A)
5(4,x,X)

4.2.3.4 Expressions

Expressions generate the following LIF codes for variables referenced and variables assigned at a node.

# define LIF_AREF       24  /* 24(node,addr)                   */
# define LIF_ADDRESS    25  /* 25(addr,pid,id)                 */
# define LIF_REF         7  /*  7(node,id[,level])             */
# define LIF_DEF         8  /*  8(node,id[,level])             */
# define LIF_GREF        9  /*  9(node,id[,level])             */
# define LIF_GDEF       10  /* 10(node,id[,level])             */

An expression generates one flow node for the expression plus one flow node for each postfix (x++), prefix (++x) or comma operator (x+y,z) in the statement. The nodes are ordered in the flow-graph as follows: prefix operators from left to right, the expression flow node, and the postfix operators from left to right.

LIF_REF code is generated for local variables whose values are used. LIF_GREF code is generated for global variables whose values are used. Variables that are assigned a new value generate LIF_DEF for assignment to local variables and LIF_GDEF for assignment to global variables.

The level indicates the level of indirection of the ref or def. A level of zero, no indirection, is omitted. A level of -1 indicated the address of operator (&). An LIF_ADDRESS is generated for each object of the address of operator, indicating the variable, the procedure where the variable is declared (zero for global declaration) and a unique address id. Address ids are assigned sequentially from 1. An example of expressions and corresponding LIF codes follows:

int x,y; /* global ids 23 (x) and 24 (y) */
...
int a,b,*c; /* local ids 18(a), 19(b) and 20(c) */
...
c = &x;      /* node 46, x is address 14 */
x = y - (b++) + *c; /* nodes 47 and 48  */

16(46,47)
9(46,23,-1)
8(46,20)
25(14,0,23)
24(46,14)
16(47,48)
7(47,19)
8(47,19)
9(48,24)
7(48,19)
7(48,20,1)
10(48,23)

4.2.3.5 Procedure Calls

Procedure calls are handled as part of an expression and use the following LIF codes:

# define LIF_CALL_START 11  /* 11(node,pid)                   */
# define LIF_ACTUAL_SEP 12  /* 12    *** void ***             */
# define LIF_CALL_END   13  /* 13    *** void ***             */

The actual parameters are listed as expressions in order separated by LIF_ACTUAL_SEP entries.

int x,y,z;                    /* local ids x(72) y(73) z(74) */
...
x = fun(x+y,*z);           /* node 47, fun is pid 18 */

11(47,18)
7(47,72)
7(47,73)
12
7(47,74,1)
13
8(47,72)

4.2.3.6 Structure Fields

Structure fields generate the following LIF codes:

# define LIF_CHAIN      19  /* 19(node,chain,id)              */
# define LIF_GCHAIN     20  /* 20(node,chain,id)              */
# define LIF_FIELD      21  /* 21(node,chain,seq,fid,field)   */
# define LIF_CREF       22  /* 22(node,chain)                 */
# define LIF_CDEF       23  /* 23(node,chain)                 */
# define LIF_STRUCT     26  /* 26(pid,id,offset)              */

At an expression node, each reference or assignment through a pointer to the fields of a structure generates a chain (LIF_CHAIN or LIF_GCHAIN). The chains of a node are given a chain number sequentially from 1. The variable at the head of the chain is specified in the id field of the LIF_CHAIN for local variables and in the id field of the LIF_GCHAIN for global variables.

LIF_CREF and LIF_CDEF indicate if the chain specifies a reference or a define. LIF_FIELD is used to specify each field of a chain by sequence number. The fid is the sequence number of the field within the data structure and field is the field name.

LIF_STRUCT indicates that the variable identified by the pid and id is a structure with offset members. For example, consider the following:

typedef struct a_struct a_rec,*a_ptr;
typedef struct b_struct b_rec,*b_ptr;
struct a_struct {a_ptr  a1; b_ptr a2; int a3};
struct b_struct {b_ptr  b1; int b3};

a_rec   ar; /* Global ID 9(ar) 10(ar.a1) 11(ar.a2) 12 (ar.a3)*/
a_ptr   a;  /* Global ID 13(a) fields 1(a1) 2(a2) & 3(a3) */
. . .
b_ptr   b;  /* Local ID 7(b) fields 1(b1) 2(b2) & 3(b3) */

. . .

a->a3 = b->b3 + a->a1->a2->b1->b3;      /* node 88 */

26(0,9,3)       structure ar has 3 fields
20(88,1,13)     a->a3
19(88,2,7)      b->b3
20(88,3,13)     a->a1->a2->b1->b3
23(88,1)
22(88,2)
22(88,3)
21(88,1,1,3,a3)     ->a3
21(88,2,1,3,b3)     ->b3
21(88,3,1,1,a1)     ->a1->
21(88,3,2,2,a2)     ->a2->
21(88,3,3,1,b1)     ->b1->
21(88,3,4,3,b3)     ->b3

4.2.4 File.T

The .T file is produced by the analyzer at the same time as the .LIF file. The purpose of the .T file is to provide for sizing of dynamic objects by the linker and slicer. The format of the .T file is as follows:

Example source and .T files:

-----> z.c <-----

# include "a.h"
int     zed,zulu;
main (n,p)
int     n;
char    *p[];
{
int     kappa,lambda,mu;

zircon (kappa+lambda-zed,zulu,z2->zeta,z1.zeta,&z1);
}

-----> a.h <-----

int alpha,beta,omega;
typedef struct zeta_struct zeta_rec, *zeta_ptr;
struct zeta_struct {
int     zeta;
zeta_ptr za,zb,zc;
};
zeta_rec    z1,*z2;
zeta_ptr    z3;

-----> z.T <-----

2 4
1    1    4    5 X main
2   -1    0    0 X zircon
12 1 1
10      17     155 z.c

4.2.5 File.H

A program may have global variables either declared directly in the source files or declared in included header files. If a program has many include files then a large number of global variables could be declared. If the user of unravel needs to select a global variable then the set of global variables should be organized so that it is easy to locate global variables declared in source files and global variables declared in included files.

The purpose of the .H file is to partition the set of global variables according to the location of the variable declaration. The .H file consists of two types of records, file name records and variable name records. The .H file is organized as a series of file name records followed by variable name records for each global variable declared in the file. The same file name may appear more than once in the .H file. A variable may be declared in more than one file.

The format of a file name record is @ file_name with @ in columns one and two and the file name starting in column 3 and extending to the end of the line. The file name is as produced by the C preprocessor for a change of file from a #include statement.

The variable record is a tab character in column 1 followed by the variable name extending to the end of the line. Example .c, .h and .H files follow:

-----> c File (yy.c) <-----

int    a,tip;
# include "a.h"
int    rip,TRIP,sip;

-----> h File (a.h) <-----

int    alpha,beta,omega,z1,z2,z3;

-----> H File (yy.H) <-----

@ yy.c
	a
	tip
@ a.h
	alpha
	beta
	omega
	z1
	z2
	z3
@ yy.c
	rip
	TRIP
	sip

4.2.6 SYSTEM

The arrangement of records in the SYSTEM file to describe a single program divided among several files is as follows:

1 main file record
2 file separator
3 source (.c) files required by the given main file
4 ambiguous procedure separator
5 zero or more procedure name records
6 library separator
7 zero or more procedure name records

The above organization is repeated for additional programs in the current directory.

The following example has two main programs (one in ex-1.c, the other in b.c). The main in ex-1.c uses four library functions and the entire program is contained in one file. The main in b.c uses procedures defined in three other files. One procedure, a4, is ambiguously defined since it has a procedure body defined in more than one source file.

MAIN ex-1.c 1
FILES
	ex-1.c
AMBIG
LIB
	scanf
	printf
	exit
MAIN b.c 4
FILES
	b.c
	bb.c
	bbb.c
	abc.c
	AMBIG
	a4
LIB
	exit

4.2.7 File.K

The linker merges the .H and .T files for all the files of a program into one .K file. The .K file is organized into 4 sections:

1. The first line of the file gives counts for number of global variables, number of procedures, number of address objects, number of pointer chains, number of header files and number of source files. Each value is preceded by an identifying string.
2. One line of procedure description for each procedure. The content is similar to the .T file. Each line contains, procedure id, entry statement, exit statement, number of local variables, static or extern flag as an S or an X, and procedure name.
3. One line of description for each file. Each line contains a file id, number of procedures, number of statements, number of lines, number of characters and file name minus extension.
4. The last section is the merge of the .H files. There should be a file record for each file where global variables are declared. Each file with declared global variables should have only one file record. A file record has two fields, a count of the number of globals declared in the file and the file name. Each file record is followed by a set of global records. A global record has two fields, the id number assigned to the global variable by the linker and the variable name.

4.2.8 File.LINK

The .LINK file contains the merged .LIF files from all the files that are required the main program in file.c.

One LIF code, LIF_FILE, not found in .LIF files is added to the .LINK file to indicate the source file associated with each procedure.

# define LIF_FILE        6  /*  6(file_id,file_name)          */

4.3 Slicer

This section presents by informal pseudo-code the procedures and data structures of the program slicing component. There is one procedure, slice, that serves to control invocation of the other procedures that are used to compute program slices. The slice procedure is invoked from a user interface component that obtains the slicing criterion from the user and displays the program slice to the user.

slice This procedure controls computation of a program slice and is called by the user interface after the slicing criterion has been obtained. The slice is returned to the caller as a set of flow- graph nodes.

slice (criterion c, set slice_set)
{
	clear criteria for each node
	clear slice_set
	set initial criterion
	call main_slice (c, slice_set)
}

main_slice Sweep over the program applying the slicing criteria until no more changes occur (and no more statements are added to the slice.

main_slice (criterion c, set slice_set)
{
	change = 1
	while (change) {
		change = 0
		for each node, n, {
		    for each successor, m, of n{
			change += include_or_not (n,m,slice_set)
		    }
		}
	}
}

include_or_not Test a statement for inclusion in a slice and return a count of changes. The change count is the sum of number of statements added to the slice and number of new criteria generated. If the statement changes a variable in the criteria for the statement's successor then the statement should be added to the slice and additional criteria should be generated.

int include_or_not (node_index n, node_index m, set slice_set)
{
	change = false
	if (defs(n) intersects criteria(m)){
		change += add_to_slice (n, slice_set)
	}
	if (idefs(n) intersects criteria(m)){
		change += add_to_slice (n, slice_set)
		change += add_idef_criteria(n)
	}
	if (cdefs(n) intersects criteria(m)){
		change += add_to_slice (n, slice_set)
		change += add_cdef_criteria(n)
	}
	return change
}

add_to_slice If statement n is not in the slice add n to the slice and adjust slicing criteria. Add any statements in the requires set and return the count of changes.

int add_to_slice (node_index n, set slice_set)
{
	count = 0
	if n already in slice then return 0
	add n to slice_set
	count = 1 + add_criteria(n)
	for each node, r, in requires(n){
		count += add_to_slice(r)
	}
	return count
}

add_criteria Add the criteria generated by inclusion of any statement in a slice. int add_criteria (node_index n) { add refs(n) to criteria(n) add criteria implied by irefs(n) add criteria implied by crefs(n) return change count }

add_idef_criteria Add criteria for variables referenced in the specification of the variable indirectly defined (assigned).

int add_idef_criteria (node_index n)
{
	add criteria implied by idefs(n)
	return change count
}

add_cdef_criteria Add criteria for variables referenced in the specification of the variable indirectly defined (assigned).

int add_cdef_criteria (node_index n)
{
	add criteria implied by cdefs(n)
	return change count
}

4.3.2 Data Structures

The following data structures, built from the files produced by the analyzer and linker, are used to represent the program being sliced.

typedef struct source_file_struct source_file_rec,*source_file_ptr;
typedef struct flow_node_struct flow_node_rec,*flow_node_ptr;
typedef struct proc_struct proc_rec,*proc_ptr;
typedef struct ptr_state_struct ptr_state_rec,*ptr_state_ptr;

typedef struct {
	int             start_line;
	int             start_col;
	int             end_line;
	int             end_col;
} src_map;

struct source_file_struct {
	proc_ptr        procs[];
}

struct flow_node_struct {
	set             refs,defs,irefs,idefs,crefs,cdefs;
	set             successors,requires;
	src_map         source;
	set             criteria;
	chain           chains[];
	ptr_state_ptr   p;
}

struct proc_struct {
	flow_node_ptr   nodes[];
	set             globals_defed,globals_refed;
	set             formals_defed,formals_refed;
}

struct ptr_state_struct {
	set             state[];
}

4.4 Linker

The task of map is to identify all the source files that make up each main program. While this is not solvable in general, it is possible for most situations the user is likely to encounter. It is also possible to identify a situation where map cannot complete its task and the user must provide assistance.

The input to map is the set of all .LIF, .T and .H files in the current directory.

The input to slink is a file name (to identify the main program), the SYSTEM file and the .LIF, .T and .H files that the SYSTEM file indicates belong to the main program.

The user interface displays four control panels and two pop-up information windows. The four control panels are the following:

The Main Control Panel is used to invoke Analyzer Control Panel and Slicer Control Panel and provides relevant information about the current directory. The Analyzer Control Panel allows the user to select files, run the analyzer and automatically run map to scan for main programs.

The Selection Control Panel allows the user to select a main program and runs the linker on the selected main program followed by invoking the Slicer Control Panel for the selected program.

The Slice Control Panel gives the user access to the program slicer, accepts a slicing criterion interactively and displays the source program text in a scrollable window with slice statements highlighted.

All control panels have the following features:

• Control buttons on top row of the panel
• Leftmost button pops-down (exits) the panel
• Rightmost button pops-up the help display for the panel
• Help button sticks to right window edge on resize
• Other buttons keep same distance from left edge on resize
• Panel name in the window title bar
• Last line of panel displays a brief description of the object under the mouse pointer
• Help button short cuts (accelerators): pressing anywhere on the panel outside a text window h, H or ? invokes help
• Exit button short cuts (accelerators): pressing anywhere on the panel outside a text window q or Q exits the panel
• All top level control panel windows are created with an X Windows application class name of Unravel so that X resources can be set for all panels at once (e.g., to set the foreground color to red give the following resource specification to xrdb: *Unravel*Foreground: red).

Two application resources, runningFG and runningBG, are defined. These resources are a foreground and a background color that are used to indicate a lengthy operation is in progress.

The two information pop-ups display a history of user activities and help text for each panel. An information pop-up window consists of a done button to dismiss (pop-down) the window and a scrollable text window.

The user interface keeps the following log files:

1. The file HISTORY.LOG is a log of user analysis and slicing activity in the current directory for past invocations of unravel. The HISTORY.LOG is updated with current activity when the Main Control Panel exits.
2. The file HISTORY is a log of user analysis and slicing activity in the current directory for the current invocation of unravel. The HISTORY file is updated with current analysis activity when the Analyzer Control Panel exits and is updated with slicing activity when the Slicer Control Panel exits.
3. The file HISTORY-A is a log of user analysis activity for the current invocation of the Analyzer Control Panel. Results of analysis of each file is recorded, including syntax errors found in the source code.
4. The file HISTORY-S is a log of user slicing activity for the current invocation of the Slicer Control Panel.

4.4.1 Main Control Panel

The function of the Main Control Panel is to respond to user interaction with the panel.

The Main Control Panel is invoked by running the program unravel. The input to unravel is a single directory name on the command line to specify a working directory. If the command line is empty, the current directory is used as the working directory. After a working directory is obtained, unravel makes the working directory the current directory.

Invoking the Main Control Panel does the following initializations:

1. Change to the directory specified on the command line.
2. Initialize HISTORY-S to No slices computed this session.
3. Initialize HISTORY-A to No analysis done this session.
4. Initialize HISTORY to UNRAVEL directory name current date and time.

The Main Control Panel displays the following information:

• Current directory name.
• Number of source files. This is a count of files with a .c extension.
• Number of files analyzed and up to date. The number of C source files that have .LIF and .T files such that the C file is older than the .LIF and .T files.
• Number of source files not analyzed. This is a count of files with the .c extension that do not have either an .LIF, .T or an .H file.
• Number of files analyzed and out of date. The number of C source files that have either .LIF or .T files such that the C file is younger that either the .LIF or the .T file or both.
• Number of main program files analyzed, i.e., the number of main program files identified in the SYSTEM file.
• Number of main program files linked. This is the number of main program files identified in the SYSTEM file that also have .LINK and .K files.
• Number of duplicate procedures found. This is the number of procedures identified in the SYSTEM file as ambiguous (appearing in more than one file).
• Last line of panel displays a brief description of the object under the mouse pointer.

The Main Control Panel buttons invoke the following actions: Exit The Exit button does the following:

1. Append the file HISTORY to HISTORY.LOG
2. Delete HISTORY
3. Exit

Run Analyzer The Run Analyzer button does the following:

1. Invokes the Analyzer Control Panel, passing the window id of the Run Analyzer button as a command line parameter.
2. When the Run Analyzer button receives a non-maskable event (i.e., xsend from Analyzer Control Panel) the displayed counts are updated.

Run Slicer The Run Slicer button invokes the Selection Control Panel.

Help The Help button runs helpu with the file unravel.help as command line parameter. Current Directory The following is done when the directory is changed:

1. Append the file HISTORY to HISTORY.LOG
2. Delete HISTORY
3. Initialize HISTORY-S to No slices computed this session
4. Initialize HISTORY-A to No analysis done this session
5. Initialize HISTORY to UNRAVEL directory name current date and time

4.4.2 Analyzer Control Panel

The Analyzer Control Panel presents the user with:

• Buttons to control file selection, running the analyzer, clearing analysis files and popping-up a help window.
• A status line to give the user feedback on progress of the analysis of a set of files.
• Two text windows for specifying command line options to the C preprocessor and to the unravel parser.
• A list of selected source files from the current directory.
• A list of other source files in the current directory.
• Last line of panel displays a brief description of the object under the mouse pointer

The Analyzer Control Panel buttons invoke the following actions:

Exit Analyzer This button appends the file HISTORY-A to HISTORY and then exits.

File Selection The File Selection button pops-up a menu with the following four choices and actions:

All Files:

All source file names are placed in the selected list window. The not selected list window will be empty.

No Files:

All source file names are placed in the not selected list window. The selected list window will be empty.

Analyzed Files:

All source file names of files that have older .LIF, .T and .H files are placed in the selected list window. The remaining source file names are placed in the not selected list window.

Files Not Analyzed:

All source file names of files that have older .LIF, .T and .H files are placed in the not selected list window. The remaining source file names are placed in the selected list window.

Analyze Selected Files/Stop Analysis This button runs the analyzer on each selected file, adding the contents of the C preprocessor options window to the C preprocessor command line and adding the contents of the parser options window to the parser command line. When the Analyzer Control Panel button is pushed the button label is changed from Analyze Selected Files to Stop Analysis. If the Stop Analysis button is pressed, do not analyze any more of the selected files after the file currently being analyzed is finished. As each file is analyzed, the file name currently being analyzed is displayed on the status line along with a progress indication. The progress indication is defined by the following: number each file in sequence starting from 1 in the order that the files will be analyzed. Display the file's sequence number and the total number of files. The status line should be set to the foreground and background colors specified in the application resources runningFG and runningBG.

After all selected files have been analyzed, run map.

The Selection Control Panel presents the user with:

• Exit and Help buttons
• A status line
• A list of main program source files from the current directory
• Last line of panel displays a brief description of the object under the mouse pointer

The Exit button pops-down the panel with no further action.

If a file from the list is selected, the file is linked, the Selection Control Panel is popped-down and the slicer is called.

The status line initially indicates that select is waiting for the user to make a selection. After a file is selected, the status line indicates that a file is being linked.

If there is exactly one main program file, the file is linked and the slicer is called without bringing up the selection panel.

The slicer accepts slicing criteria from the user, computes a program slice for each criterion given, saves each slice for later recall and displays the program in a scrollable window. The slicer presents the user with:

• Buttons to exit, to pop-up help and interrupt a lengthy slice calculation.
• A display indicating slice size and slice calculation progress.
• A display of the currently selected slicing criterion variable.
• Menu of selection options for selecting slicing criterion variables, or previously computed slices.
• Menu of operations that can be performed on two selected slices.
• Display describing the contents of the scrollable window.
• Display of program source text in a scrollable window.
• The last line of the panel displays a brief description of the object under the mouse pointer.
• Clicking a mouse button in the text window specifies the statement for the slicing criterion and initiates the slice computation.

Primary slice and secondary slice has no significance other than being convenient names for two slices when an operation such as intersection is performed on two slices.

In addition to interaction with the user through the window interface, the slicer has the following inputs and outputs:

Command Line The slicer takes one command line argument, file.c, the name of a main program file.

Summary Counts The slicer looks for a .K file, file.K, that matches the main program file on the command line where file is the name of the main program file without any extension.

Linked .LIF File The slicer looks for a .LINK file, file.LINK, that matches the main program file on the command line where file is the name of the main program file without any extension.

Computed Slices Each slice that is computed is saved in file.Y as a criterion and set of flow graph node numbers. The file format is as follows:

1. Criterion (four integers): variable id number, procedure id number that variable is local to or zero if global, file id number containing statement and statement number.
2. Partial slice flag (integer): value 0 if slice computation was not interrupted, value 1 if interrupted.
3. File entries (one per file): consists of file id number followed by zero or more statement numbers, terminated by -1. The last file entry is followed by a file id of -1 (i.e., slice entry is terminated by two -1 entries, one to end the statements of the last file of the main program and one to mark end of files in the program for the slice).

HISTORY-S The slicer records information in the following format for each slice computed is placed in HISTORY-S to record the criterion, the slice size in flow graph nodes and the wall clock time to compute the slice:

slice on var name (in procedure name) at line nnn in file name (nnn stmts in mm:ss)

If the variable is global then the word global replaces the procedure name.

The Slice Control Panel buttons do the following: Exit This button appends HISTORY-S to HISTORY and then exits. Interrupt The Interrupt button does the following:

1. Stops computation of the slice and displays partial results.
2. Marks the slice as partial and saves.

The Select menu has the following selections:

Local Variable This entry is a two-step selection. First, a list of procedure names is popped-up for the user to select one item. The list consists of all procedures that are defined somewhere in the main program. Procedures such as library routines that are used, but not defined, are not included in the list. The first entry in the list is No Selection. If a procedure is selected, the procedure header, opening brace and closing brace are highlighted, a list of variables declared local to the selected procedure is popped-up and the list of procedure names is popped-down. If no procedure is selected, the list of procedure names is popped-down. The Criterion Variable Window is updated with the selected items.

Global Variable This entry is a two-step selection. First, a list of file names is popped-up for the user to select one item. The list includes all source files (.c) in the program and all header files (.h) that are included in the program. The first entry in the list is No Selection. If a file is selected, a list of global variables declared in the selected file is popped-up and the file list is popped-down. If no file is selected, the file list is popped-down. The Criterion Variable Window is updated with the selected items.

Mark Proc A list of procedure names is popped-up for the user to select one item. The first entry in the list is No Selection. If a procedure is selected, the procedure header, opening brace and closing brace are highlighted. The list is popped-down.

Show Call Tree A list of procedure names is popped-up for the user to select one item. The first entry in the list is No Selection. If a procedure is selected, the procedure header, opening brace, closing brace and all the call sites for the selected procedure are highlighted. The highlighting continues for each procedure containing a highlighted call site until no more unhighlighted procedures are found. If a call site in controlled by a conditional statement (e.g., if or while), the conditional statement is highlighted. The list is popped-down.

Primary This selection pops-up a list of previously computed slices. The first entry in the list is No Selection. If a slice is selected, it becomes the primary slice and is displayed. The list is then popped-down.

Secondary This selection pops-up a list of previously computed slices. The first entry in the list is No Selection. If a slice is selected, it becomes the secondary slice and is displayed. The list is then popped-down.

The Operation menu has the following selections: The selection Dice highlights the statements of the primary slice that are not members of the secondary slice and updates the Text Description Window.

The selection Dice S-P highlights the statements of the secondary slice that are not members of the primary slice and updates the Text Description Window.

The selection Intersection highlights the statements in both the primary and secondary slice and updates the Text Description Window.

The selection Union highlights the statements in either the primary or secondary slice and updates the Text Description Window.

The selection Clear removes all highlighting and updates the Text Description Window. The Text Window has four actions triggered by the mouse.

1. Clicking a mouse button in the tick bar area scrolls the window to the corresponding area of the program text.
2. The leftmost mouse button computes a primary slice.
3. The middle mouse button computes a secondary slice.
4. The rightmost mouse button highlights the current line.

The source program line under the mouse pointer when the mouse button is clicked specifies the statement for the slicing criterion. If the specified slicing criterion has already been used to compute a slice (without interruption), then the slice is not computed, but is retrieved and displayed.

5 System Evaluation & Performance

Unravel was evaluated in the context of reviewing safety system software for quality. The evaluation considered the size of slices produced, time to compute slices and usability by a novice user.

The objectives of the evaluation were to determine the following:

1. Are program slices smaller than the original program to an extent that is useful to a software reviewer evaluating a program?
2. Can program slices be computed quickly enough to be useful?
3. Is unravel usable by a novice user?

Program slicing can help automate two tasks performed by reviewers:

1. A thread check traces a variable chosen for evaluation through the software. This includes reviewing relevant sections of program source code that currently must be manually located.
2. Evaluation of functional diversity is accomplished by attempting to determine if two application functions share source code. If source code is shared by two diverse application functions, then the reviewer must carefully evaluate the shared code for errors. The concept of functional diversity is used to defend against common mode failure in digital systems.

The first example a simplified safety system was developed in three versions. One version was written to conform to safety system diversity requirements while the other two were deliberately seeded with common code. Unravel was able to verify and display the presence of the common code in the seeded versions and show the absence of common code in the diverse version. Only the conforming version of the example is used in the size and timing analysis.

The second example, a commercial sample of safety related code, presented a realistic evaluation for unravel. While the code was not ANSI C, unravel was used after a few simple changes brought the commercial code into ANSI compliance. The commercial code was used by a software reviewer to evaluate the utility of unravel.

5.2 Timing Analysis

The unravel linker has two main components: map which scans the analysis files for main procedures and slink which merges the LIF files of a program into a single LINK file. The map component of the linker ran in less than 2 seconds on the unravel source files (55,000 lines) and should run in less than 5 seconds on 100,000 lines of code.

To evaluate the times to compute program slices, criteria were automatically generated by slicing on the last statement of the main procedure for each global variable and the last statement of the procedure where a local variable is declared for each local variable. Usually the timing results produce clusters of slices with similar times. It should be noted that we use these examples as performance benchmarks as unravel evolves. These results are for unravel version 2.1, different results are obtained as improvements are made to the slicing algorithm or as bugs are fixed.

The example code provided 193 slicing criteria. Most slices (183) were completed in under 1 second. The remaining ten slices were completed in less than ten seconds.

The commercial example provided 419 slicing criteria. The slicing times divided into four clusters, 354 slices were completed in under 1 minute. Fifty-eight slices required more than 1 minute but under 5 minutes. Six slices required between 35 minutes to one hour. One slice took 3 hours and 9 minutes.

The software review process as currently implemented is a manual process that is slow, tedious, and prone to human errors. With unravel, once a software reviewer has identified a variable for further investigation, the reviewer directs unravel to compute a program slice on the variable. Instead of examining the entire program, only the statements in the slice need to be examined by the reviewer. By speeding up the process of locating relevant code for examination by the reviewer, a larger sample of a commercial product can be inspected with greater confidence that some relevant section of source code has not been missed.

Once two computations that could be vulnerable to common mode failure have been identified, program slices can be computed to find statements relevant to each computation. Functional diversity of the two computations can be evaluated by intersecting slices to show any statements in common. Source program statements that have potential to cause common mode failure would be present in the intersection of the program slices. Without any tool, a software reviewer evaluates the software until it is determined that there is no common code, or that the common code present will not compromise the mission of the safety critical software.

The analyzer and linker components can process source code of up to 100,000 lines of code in less than 10 minutes. The linear behavior of the analyzer and linker leads to stable run time performance. The slicer component does not use a linear algorithm, but rather uses a quadratic algorithm that can have significant run time variability. The slicer performed well on the simplified example. Larger programs, such as parser with 7,500 lines, have slices (14%) that can take longer than one hour. It should be noted that there is potential for significant algorithm improvement. The slicer makes repeated passes over the program until no more changes occur. The slicer is sensitive to the order in which program statements are analyzed. For example, after one small change in the slicer code that controls the order of visiting nodes during the slice computation, the longest time to compute a slice on the commercial code dropped from 10 hours to 3 hours. Other areas that can be improved include loop analysis and procedure calls.

6 References

1. ANSI. American National Standard for Information Systems - Programming Language - C. Technical Report ANSI X3.159-189/FIPS PUB 160, American National Standards Institute, 1430 Broadway New York, New York 10018, December 1989.

2. M. Weiser. Program slicing. IEEE Transactions on Software Engineering, 10:352-357, July 1984.

3. K. Kennedy. A Survey of Data Flow Analysis Techniques. In Steven S. Muchnick and Neil D. Jones, editors, Program Flow Analysis: Theory and Applications. Prentice-Hall, Englewood Cliffs, New Jersey, 1981.

4. J. R. Lyle and M. D. Weiser. Experiments in slicing-based debugging aids. In Elliot Soloway and Sitharama Iyengar, editors, Empirical Studies of Programmers. Ablex Publishing Corporation, Noewood, New Jersey, 1986.

5. K. B. Gallagher and J. R. Lyle. Using Program Slicing in Software Maintenance. IEEE Transactions on Software Engineering, 17(8):751-761, August 1991.

6. M. Weiser. Programmers Use Slicing When Debugging. CACM, 25(7):446-452, July 1982.

7. S. Horwitz, J. Prins, T. Reps. Integrating Non-Interfering Versions of Programs. ACM Transactions on Programming Languages and Systems, 11(3):345-387, July 1989.

8. J. Ferrante, K. Ottenstein, and J. Warren. The Program Dependence Graph and Its Use In Optimization. ACM Transactions on Programming Languages, 9(3):319-349, July 1987.

9. FIPS PUB 151-2, "Portable Operating System Interface (POSIX)-System Application Program Interface [C Language]," U.S. Department of Commerce/National Institute of Standards and Technology, 1993 May 12.

10. FIPS PUB 158-1, "The User Interface Component of the Application Portability Profile," U.S. Department of Commerce/National Institute of Standards and Technology, 1993 October 8.

Appendix A: LIF Format

#ifndef _lif_h
#define _lif_h
#define LIF_H_SCCS_ID "           @(#)lif.h     1.8  5/23/94 "
/*
****************************************************************
*                                                              *
*         L I F    F O R M A T                                 *
*                                                              *
*  id   - variable id                                          *
*  node - source program statement (or fragment)               *
*  pid  - procedure id                                         *
*  name - variable or procedure name                           *
*  level- indirection level                                    *
*  addr - address number                                       *
*  chain- chain number of pointer chain on a node              *
*  field- sequence number of field in chain                    *
*  fid  - field offset in struct                               *
*  offset number of fields in a declared structure variable    *
*  A    - is an array                                          *
*  P    - is a pointer                                         *
*  S    - static object                                        *
*  X    - is declared extern                                   *
*  G    - is a goto statement                                  *
*  B    - is a break statement                                 *
*  C    - is a continue statement                              *
*  R    - returns an expression value                          *
*                                                              *
****************************************************************
*/

# define LIF_PROC_START  1  /*  1(node,pid,name)            */
# define LIF_PROC_END    2  /*  2(node[,S][,R])             */
# define LIF_FORMAL_ID   3  /*  3(id,name[,A][,P])          */
# define LIF_LOCAL_ID    4  /*  4(id,name[,S][,P][,X][,A])  */
# define LIF_GLOBAL_ID   5  /*  5(id,name[,S][,P][,X][,A])  */
# define LIF_FILE        6  /*  6(file_id,file_name)        */
# define LIF_REF         7  /*  7(node,id[,level])          */
# define LIF_DEF         8  /*  8(node,id[,level])          */
# define LIF_GREF        9  /*  9(node,id[,level])          */
# define LIF_GDEF       10  /* 10(node,id[,level])          */
# define LIF_CALL_START 11  /* 11(node,pid)                 */
# define LIF_ACTUAL_SEP 12  /* 12    *** void ***           */
# define LIF_CALL_END   13  /* 13    *** void ***           */
# define LIF_RETURN     14  /* 14(node,1|0)                 */
# define LIF_GOTO       15  /* 15(node,G|B|C)               */
# define LIF_SUCC       16  /* 16(from_node,to_node)        */
# define LIF_REQUIRES   17  /* 17(required_node,node[,to node])*/
# define LIF_SOURCE_MAP 18  /*18(node,fr_l,fr_c,to_l,to_c)     */
# define LIF_CHAIN      19  /* 19(chain,id)                    */
# define LIF_GCHAIN     20  /* 20(chain,id)                    */
# define LIF_FIELD      21  /* 21(chain,field,fid,name)        */
# define LIF_CREF       22  /* 22(node,chain)                  */
# define LIF_CDEF       23  /* 23(node,chain)                  */
# define LIF_AREF       24  /* 24(node,addr)                   */
# define LIF_ADDRESS    25  /* 25(addr,pid,id)                 */
# define LIF_STRUCT     26  /* 26(pid,id,offset)               */

#endif /* _lif_h */

Appendix B: YACC Grammar

B.1 Expressions

%%

primary_expr
       : identifier
    | CONSTANT
    | string_literal_list
    | '(' exprXX ')'
    ;
string_literal_list
    : STRING_LITERAL
    | string_literal_list STRING_LITERAL
    ;

postfix_expr
    : primary_expr
    | postfix_expr '[' exprXX ']'
    | postfix_expr '(' ')'
    | postfix_expr '(' argument_expr_list ')'
    | postfix_expr '.' identifier
    | postfix_expr PTR_OP identifier
    | postfix_expr INC_OP
    | postfix_expr DEC_OP
    ;

argument_expr_list
    : assignment_expr
    | argument_expr_list ',' assignment_expr
    ;

unary_expr
    : postfix_expr
    | INC_OP unary_expr
    | DEC_OP unary_expr
    | unary_operator cast_expr
    | SIZEOF unary_expr
    | SIZEOF '(' type_name ')'
    ;

unary_operator : '&' | '*' | '+' | '-' | '~' | '!'
    ;

binary_operator : '&' | '*' | '+' | '-' | '~' |
    '!' | '/' | '%' | '<<' | '>>' | '<' | '>' |
    '<=' | '>=' | '==' | '!=' | '^' | '&&' | '||'
    ;

cast_expr
    : unary_expr
    | '(' type_name ')' cast_expr
    ;

binary_expr
    : cast_expr
    | binary_expr binary_operator cast_expr
    ;

conditional_expr
    : binary_expr
    | binary_expr '?' expr ':' conditional_expr
    ;

assignment_expr
    : conditional_expr
    | unary_expr assignment_operator
assignment_expr
    ;

assignment_operator
    : '=' | MUL_ASSIGN | DIV_ASSIGN
    | MOD_ASSIGN
    | SUB_ASSIGN | LEFT_ASSIGN 
    | RIGHT_ASSIGN
    | XOR_ASSIGN | OR_ASSIGN 
    | ADD_ASSIGN | AND_ASSIGN
    ;

expr
    : exprXX
    ;

exprXX
    : assignment_expr
    | expr ',' assignment_expr
    ;

constant_expr
    : conditional_expr
    ;

B.2 Declarations

declaration
    : declaration_specifiers ';'
    | declaration_specifiers init_declarator_list 
    ';'
    ;

declaration_specifiers
    : storage_class_specifier
    | storage_class_specifier                
declaration_specifiers
    | type_specifier 
    | type_specifier declaration_specifiers 
    ;

init_declarator_list
    : init_declarator
    | init_declarator_list ',' init_declarator
    ;

init_declarator
    : declarator
    | declarator '=' initializer
    ;

storage_class_specifier
    : TYPEDEF | EXTERN | STATIC
    | AUTO | REGISTER
    ;

type_specifier
    : CHAR | SHORT | INT | LONG
    | SIGNED | UNSIGNED
    | DOUBLE | CONST | VOLATILE 
    | FLOAT  | TYPE_NAME  
    | struct_or_union_specifier 
    | enum_specifier | VOID
    ;

struct_or_union_specifier
    : struct_or_union identifier
        '{' struct_declaration_list '}'
    | struct_or_union
        '{' struct_declaration_list '}'
    | struct_or_union identifier 
    ;

struct_or_union
    : STRUCT | UNION
    ;

struct_declaration_list
    : struct_declaration
    | struct_declaration_list struct_declaration
    ;

struct_declaration
    : type_specifier_list struct_declarator_list 
    ';'
    ;

struct_declarator_list
    : struct_declarator
    | struct_declarator_list ',' struct_declarator
    ;

struct_declarator
    : declarator
    | ':' constant_expr
    | declarator ':' constant_expr
    ;

enum_specifier
    : ENUM '{' enumerator_list '}'
    | ENUM identifier '{' enumerator_list '}'
    | ENUM identifier
    ;

enumerator_list
    : enumerator
    | enumerator_list ',' enumerator
    | enumerator_list ','
    ;

enumerator
    : identifier
    | identifier '=' constant_expr
    ;

declarator
    : declarator2
    | pointer declarator2
    ;

parms_next : /* empty */
    ;

declarator2
    : identifier
    | '(' declarator ')'
    | declarator2 '[' ']'
    | declarator2 '[' constant_expr ']'
    | declarator2 parms_next '(' ')'
    | declarator2 parms_next
        '(' parameter_type_list ')'
    | declarator2 parms_next
        '(' parameter_identifier_list ')'
    ;

pointer
    : '*'
    | '*' type_specifier_list
    | '*' pointer
    | '*' type_specifier_list pointer
    ;

type_specifier_list
    : type_specifier
    | type_specifier_list type_specifier
    ;

parameter_identifier_list
    : identifier_list
    ;

identifier_list
    : identifier
    | identifier_list ',' identifier
    ;

parameter_type_list
    : parameter_list
    | parameter_list ',' '...'
    ;

parameter_list
    : parameter_declaration
    | parameter_list ',' parameter_declaration
    ;

parameter_declaration
    : type_specifier_list declarator
    | REGISTER type_specifier_list
declarator
    | type_name
    ;

type_name
    : type_specifier_list
    | type_specifier_list abstract_declarator
    ;

abstract_declarator
    : pointer
    | abstract_declarator2
    | pointer abstract_declarator2
    ;

abstract_declarator2
    : '(' abstract_declarator ')'
    | '[' ']'
    | '[' constant_expr ']'
    | abstract_declarator2 '[' ']'
    | abstract_declarator2 '[' constant_expr ']'
    | '(' ')'
    | '(' parameter_type_list ')'
    | abstract_declarator2 parms_next '(' ')'
    | abstract_declarator2 parms_next
            '(' parameter_type_list ')'
    ;

initializer
    : assignment_expr
    | '{' initializer_list '}'
    | '{' initializer_list ',' '}'
    ;

initializer_list
    : initializer
    | initializer_list ',' initializer
    ;

B.3 Statements

statement
    : labeled_statement
    | compound_statement
    | expression_statement
    | selection_statement
    | iteration_statement
    | jump_statement
    ;

labeled_statement
    : identifier ':' statement
    | CASE constant_expr ':' statement
    | DEFAULT ':' statement
    ;

decl_end    
    : declaration_list
    ;

decl_start  
    : /* empty */
    ;

compound_statement
    : '{' '}'
    | '{' statement_list '}'
    | '{' decl_start decl_end '}'
    | '{' decl_start decl_end statement_list '}'
    ;

declaration_list
    : declaration
    | declaration_list declaration
    ;

statement_list
    : statement
    | statement_list statement
    ;

expression_statement
    : ';'
    | expr ';'
    ;

selection_statement
    : IF '(' expr ')' statement
    | IF '(' expr ')' statement ELSE statement
    | SWITCH '(' expr ')' statement
    ;
oexpr : /* optional */
    | expr
    ;

iteration_statement
    : WHILE '(' expr ')' statement
    | DO statement WHILE '(' expr ')' ';'
    | FOR '(' oexpr ';' oexpr ';' oexpr ')'    
         statement
    ;

jump_statement
    : GOTO identifier ';'
    | CONTINUE ';'
    | BREAK ';'
    | RETURN ';'
    | RETURN expr ';'
    ;

B.4 External Objects

program : 
        | file
        ;

file
    : external_definition
    | file external_definition
    ;

external_definition
    : function_definition
    | declaration
    ;

function_start  
    : /* empty */
    ;

function_definition
    : declarator function_start ";"
    | declarator function_start function_body
    | declaration_specifiers declarator
            function_start function_body
    ;


function_body
    : compound_statement
    | declaration_list compound_statement
    ;

identifier
    : IDENTIFIER
    ;

%%