Lab Materials

1. Yacc Slides

2. Helpful Notes on Yacc

3. Lab Source Files

Lab Assignment

The purpose of the this laboratory is to use the tokens returned by your lexical analyzer in the fourth laboratory to create a function call dependency graph. For instance, given the source code shown in Figure 1 you should produce the graph shown in Figure 2.

int funca( int a ) { return a*a; } int funcb( int b ) { return funca( b ); } int main( int argc, 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.

A basic project template is provided for this lab. This template contains a skeleton scanner that should be replaced with the scanner that you constructed in the fourth laboratory. The template also contains a basic Yacc parser and a Makefile that will build the entire project into an executable.

For this laboratory, you will not be parsing the full C language. To simplify things, you can assume any input into your program will be of the following form:

• A file will consist only of function definitions, which are composed of a function signature followed by a function body enclosed in curly braces.

• A function signature is composed of a type, an identifier, and a comma separated list of parameters enclosed in parentheses.

• A parameter is a typed identifier.

• A function definition's body will consist only of declarations and statements.

• A declaration is a typed identifier followed by a semicolon.

• A statement is one of the following:

  1. An assignment: ID = expression;

  2. A return: return expression;

  3. A block of statements: { statement statement ... }

  4. A function call: ID (expression, expression, ...);

  5. An if statement with an optional else clause: if( expression ) statement else statement OR if ( expression ) statement

  6. A while loop: while( expression ) statement

• An expression is one of following:

  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, as described above (no trailing semi-colon, obviously)

  8. An identifier

• A binary operator is one of the following:

  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

• A type is one of the following:

  1. void

  2. char

  3. short

  4. int

  5. long

  6. float

  7. double

Note: Your parser will also have to deal with pointer (type *ID) and array (type ID[]) types correctly.

Additionally, for binary expressions, you need to 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 for binary operations.

Before submitting, make sure to remove any ambiguities in your grammar rules (meaning, eliminate all conflict warnings). Your lecture notes contain examples you can consult, should you need a hint.

Question

If you were permitted to use Yacc's built-in operator precedence support for binary operations, what parts of your specification would change and why? A short answer of a few sentences and a few small code snippets is all I'm looking for. Please do not write an entire separate specification. Information you need to answer this question is easily found in Yacc manual.