www.angelfire.com/dragon/letstry
cwave04 at yahoo dot com
Free Guestbook
My Guestbook

Using the attributes

In the last page we have learned that bison allows a C attribute with each occurence of each token, and flex puts values in the attributes during lexical analysis. The next question is: How to use the attributes?

Recall that during syntax analysis bison constructs a derivation of the program, ie, step by step grouping of non terminals and tokens until we arrive at the non terminal program. Also recall that each step in the dervation is either a shift or a reduce. In a shift step we read the next token, in a reduce step we apply some grammer rule. Whenever a reduce step takes place bison can execute some C code of our choice. We have to write these C codes after the appropriate grammer rule in the third part of the bison input file.

Consider the line

startSpec : tok_START tok_IDENT
  {
    printf("startSpec : tok_START tok_IDENT(%s)", $2);
  }
  ;

This is a grammer rule followed by some C code. The C code inside the braces will be executed whenever this rule is used in a reduce step. Note the following points. First, the code is enclosed in a pair of braces. Second, the opening brace must not start from the first column. Third, the code is just plain C code except for the $2.

The $2 refers to the attribute of the 2nd entity in the righthand side of the BNF rule. Here this entity is the token tok_IDENT, which has an attribute of type char*. So here we have to treat the $2 as a char* variable.

Every entity in a grammer rule can have its own attribute, including non terminals and the lefthand side. They are all referred by a $ name. The attributes of the righthand side entities are denoted by $1, $2, etc. $$ refers to the attribute of the lefthand side type.
The C code segment associated with a BNF rule is called the action for that rule. To see how actions behave we have attached actions to each of the BNF rules in adv5.y. Each action consists of a printf just like the example above. Whenever a token in the righthand side has an attribute, we also print the attribute.

Follow the usual steps to compile and run our program:

flex adv4.lex
   [lex.yy.c is created]
bison -d -o compile.c adv5.y
   [compile.c and compile.h are created]
cc -o compile compile.c lex.yy.c
   [compile is created]
compile < toy.al

The output will consist of a list of BNF rules with the attribute values printed beside token the names that have them. Here are the first few lines from the output:

 nameSpec : tok_NAME tok_STRING(Your house)

 descrSpec : tok_DESCR tok_STRING(You are standing\nin front of your house.\nPaths lead towards east and west.)
exitList :

 exit : tok_DIRN(2) tok_IDENT(flag)
exitList : exitList exit

 exit : tok_DIRN(3) tok_IDENT(forest)
exitList : exitList exit


locnSpec : tok_LOCN tok_IDENT(house) nameSpec descrSpec exitList
locnSpecList : locnSpec 

Observe that each line in the output corresponds to a reduce step in the right most derivative of the program in toy.al.

Intermediate representation

An advlang program contains information. Eventually, the entire information should get translated into the final low-level output. However, except for absolutely trivial languages, this is not done in a single step. We strore the entire information in some intermediate form first, and then generate the low-level output based on that. The intermediate storage of information is used only internally by the compiler. For our case, it consists of the C data structures shown in the green box to the left.

typedef struct {
    char* name;
    char* descr;
    int exits[4]; 
}
  locStruct;

locStruct locList[50];
int nLoc, startLoc;

The structure locStruct stores information about a single location. The array locList stores the list of all the locations. We have arbitrarily chosen 50 as its length. You may later replace it by, say, a linked list. The exit array is of size 4, since there are as many directions. We code north as 0, south as 1, east 2, and west 3. Thus, if the north exit from location 3 leads to location 9 then we shall have

locList[3].exits[0] = 9

If there is no exit to the east from location 6, then we shall have

locList[6].exits[2] = -1

During semantic analysis we shall need some temporary variables, as well. These are listed in the red box to the right.


char tmp_idList[50][10];
char tmp_name[30], tmp_descr[80];
int  tmp_exit[4];

For the temporary variables we have used names starting with tmp_. Here tmp_idList stores the identifiers, we can store upto 50 of them, each of length at most 9 (=10-1, to allow for the trailing null character). tmp_name, tmp_descr and tmp_exit store the name, description and exits of a location while the location is being created. tmp_nId keeps track of the number of identifiers encountered so far.


int find(char *id) {
 int i;
 for(i=0;i<nLoc;i++) {
  if(!strcmp(id,tmp_idList[i]))
   return i;
 }
   
 strcpy(tmp_idList[nLoc],id);
 nLoc++;
 return (nLoc-1);
}
We shall need a C function (say, find(char *id)) to look up identifiers. It will check if id is already in the array tmp_idList. If so, it will return its index, else it will add id to the array, and then return its index. In the latter case nLoc will increase by 1.

A simple implementation is shown in the box to the left. In order to use this function in the actions in the bison input file, we have to write the function in the fourth part of that file. Also, the function uses strcmp to compare character strings, and strcpy to copy from one character string to another. These functions are declared in the C header string.h. So we need to insert the line

#include <string.h>

in the first part of the bison input file.

In the next page will show us how to use actions to obtain the intermediate representation of the information.

PrevNext
© Arnab Chakraborty (2007)

free html visitor counters
hit counter