Laboratory 4

In the fourth laboratory you will be constructing a yacc parser and connecting it to the scanner that you constructed in the third laboratory. The purpose of the laboratory is to create a function call dependency graph. For instance, given the source code show in figure 1 you should produce the graph show in figure 2.

int funca( int a ) {
    return a*a;
}

int funcb( int b ) {
    return funca(b);
}

int main( int argc, const char *argv[] ) {
    int a;
    int b;

    a = funca(5);
    b = funcb(5);
}

Figure 1: Example Program

Figure 2: Function Call Graph

To accomplish this you will be producing a graph using the DOT graph language. As an example, the graph in figure 2 was produced from this description:

digraph funcgraph {
    funca;
    funcb;
    funcb -> funca;
    main;
    main -> funca;
    main -> funcb;
}

This example constructs three nodes and three directed edges using the DOT language. Nodes are constructed using simple names, such as "main", and directed edges are constructed using arrows. These two constructs are all that are required for this laboratory. If you have never used the DOT graph language before then you can find out more information here and here.

A basic project template can be downloaded here. This template contains a skeleton scanner that should be replaced with the scanner that you constructed in the third laboratory. The template also contains a basic yacc parser and a Makefile that will build the entire project into an executable.

Note, that there is no header file that defines token constants, unlike laboratory 3. In this laboratory we are using the yacc tool to create the header file for us. This eliminates the error prone process of creating the constants and eases the construction of the program.

For this laboratory you will not be parsing the full C language. You can assume any input into your program will be of this form:

1. A file will consist only of function definitions.
2. Function definitions will consist only of declarations and statements
3. Declarations will be a type followed by a single identifier and then a semicolon
4. Statements will be  one of:
   1. an assignment: ID = expression ;
   2. a return: return expression ;
   3. a block statement: { statements }
   4. a function call with any number of arguments: func( arguments ) ;
   5. an if statement with optional else: if ( expression ) statement [else statement]
   6. a while loop: while( expression ) statement
5. An expression will be one of:
   1. an integer literal
   2. a string literal
   3. a character literal
   4. a double floating point literal
   5. a floating point literal
   6. a binary expression: expression OP expression
   7. a function call: func( arguments )
   8. a variable name: a
6. A binary operator will be one of:
   1. equal, not equal, less than, greater than, less than equal, greater than equal
   2. add, subtract, multiply, divide, modulo
   3. left shift, right shift
   4. bitwise and, bitwise or, bitwise xor
7. Types will be one of:
   1. void
   2. char
   3. short
   4. int
   5. long
   6. float
   7. double
   8. a pointer
   9. an array type

Note that array types in the C language have the form "type ID[]" where the square brackets come after the identifier name. Your parser will have to deal with this correctly. Additionally, for binary expressions you must respect the operator precedence of the C language (listed here). You must encode the operator precedence manually; do not use Yacc's built-in operator precedence support.