Lex and Yacc symbol table generation and manipulation

Question

I am trying to build a simple C compiler using lex for the lexical ananlysis phase and yacc for syntax analysis. I am building the symbol table in lex and populating it with all the identifiers (just the name, line number and scope of the identifier for now) that I come across in the lexical analysis. The symbol table itself is in the form of a linked list and a pointer points to the head of the linked list. Now I wanna be able to access this symbol table in yacc to update the value and datatype for each identifier. How do i access the symbol table in yacc?

I have defined the head pointer in lex as extern but it's not helping. Here's the complete code for reference -

Lex (ngrammar.l) -

%{
    #include
    #include
    #include
    #define MAX 1000
    extern int yylval;
    int scope = 0;
    int lineno = 1;
    int paran = 0;
    typedef struct node{
        int index;
        int scope;
        char symbol[MAX];
        char lineno[MAX];
        char type[MAX];
        char value[MAX];
        struct node* next; 
    }node;
    extern node* head;
    head = NULL;
    node* InsertSymbol(node*,int,char*,int,int);
    void display(node* head);
    node* InsertSymbol(node* head, int scope, char* symbol, int lineno, int paran){
        if(paran>0){
            scope++;
        }
        else{;
        }
        if(head == NULL){
            node* temp = (node*)malloc(sizeof(node));
            temp->index = 1;
            temp->scope = scope;
            strcpy(temp->symbol,symbol);
            char str[4];
            sprintf(str, "%d", lineno);
            strcpy(temp->lineno,str);
            temp->next = NULL;
            head = temp;
        }
        else{
            node* cur= head;
            node* prev = NULL;
            int present = 0;
            while(cur != NULL){
                if((cur->scope == scope) && (strcmp(cur->symbol,symbol)==0)){
                    char str[4];
                    sprintf(str, ", %d", lineno);
                    strcat(cur->lineno,str);
                    present = 1;
                }
                prev = cur;
                cur = cur->next;
            }
            if(present == 0){
                node* temp = (node*)malloc(sizeof(node));
                temp->index = (prev->index)+1;
                temp->scope = scope;
                strcpy(temp->symbol,symbol);
                char str[4];
                sprintf(str, "%d", lineno);
                strcpy(temp->lineno,str);
                temp->next = NULL;
                prev->next = temp;
            }
        }
        return head;
    }
    void display(node* head){
        node* p = head;
        printf("\t\t\t SYMBOL TABLE \t\t\t\n\n");
        printf("\t Index \t\t Symbol \t Scope \t\t Line Number \n");
        if(p == NULL){
            printf("nothing");
            return;
        }
        else{
            while(p != NULL){
            //printf("enter");
                printf("\t %d \t\t %s \t\t %d \t\t %s \n",p->index,p->symbol,p->scope,p->lineno);
                p = p->next;
            }
        }
    }
%}

alpha [A-Za-z]
digit [0-9]
und [_]
space [ ]
tab [   ]
line [\n]
acc [^"*/"]
str [^"]

%%
//(.*)[\n]* {;}
/\*({acc}*\n)*{acc}*\*/[\n]* {;}
for {return FOR;}
if {return IF;}
char {return CHAR;}
float {return FLOAT;}
int {return INT;}
continue {return CONTINUE;}
return {return RETURN;}
bool {return BOOL;}
main {return MAIN;}
else {return ELSE;}
printf {return PRINT;}
break {return BREAK;}
TRUE {return BOOLTRUE;}
FALSE {return BOOLFALSE;}
\|\| {return OR;}
\%d|\%c|\%f {return FORMATSPEC;}
$ {return OPENBRACES;paran++;}
$ {return CLOSEBRACES;paran--;}
\{ {return OPENCURLYBRACES;scope++;}
\} {return CLOSECURLYBRACES;scope--;}
[.] {return DOT;}
= {return ASSIGNOP;}
\+\+|\-\- {return UNARYOP;}
\+|\-|\*|/ {return ARITHOP;}
>|<|>=|<=|!=|== {return RELOP;}
&& {return AND;}
[,] {return COMMA;}
[;] {return SEMICOLON;}
['] {return SINGLEQUOTES;}
["] {return DOUBLEQUOTES;}
["]{str}*["] {return STRING;}
{alpha}({alpha}|{digit}|{und})* {return IDENTIFIER;
                                head = InsertSymbol(head,scope,yytext,lineno,paran);}
{digit}+ {return INTCONST;}
({digit}+)\.({digit}+) {return FLOATCONST;}
[\n] {lineno++;}
[\t] {;}
[ ] {;}
. {return yytext[0];}
%%

int yywrap()
{
    return 1;
}

Yacc (ngrammar.y) -

%{
    #include
    #include
    int valid=1;
%}

%token CHAR INT FLOAT BOOL MAIN FOR IF ELSE PRINT BREAK CONTINUE BOOLTRUE BOOLFALSE FORMATSPEC OPENBRACES CLOSEBRACES OPENCURLYBRACES CLOSECURLYBRACES UNARYOP ARITHOP RELOP ASSIGNOP COMMA SEMICOLON SINGLEQUOTES DOUBLEQUOTES UNDERSCORE RETURN AND OR DOT STRING IDENTIFIER INTCONST FLOATCONST

%%
start: INT MAIN OPENBRACES CLOSEBRACES OPENCURLYBRACES statement return_statement CLOSECURLYBRACES;
statement: compound_statement | expression_statement | jump_statement | print_statement | for_loop | if_else;
for_loop: FOR OPENBRACES declaration condition_statement SEMICOLON for_expression_statement CLOSEBRACES statement;
if_else: IF OPENBRACES condition_statement CLOSEBRACES statement ELSE statement;
return_statement: RETURN identifier SEMICOLON | RETURN intconstant SEMICOLON;

declaration: declaration_specifiers init_declarator_list SEMICOLON | init_declarator_list SEMICOLON;
declaration_specifiers: CHAR | INT | FLOAT | BOOL;
init_declarator_list: init_declarator | init_declarator COMMA init_declarator_list;
init_declarator: identifier | identifier ASSIGNOP initializer;
initializer: numconstant | identifier;

compound_statement: OPENCURLYBRACES CLOSECURLYBRACES | OPENCURLYBRACES block_item_list CLOSECURLYBRACES | block_item_list;
block_item_list: block_item block_item | block_item;
block_item: declaration | statement |;
expression_statement: identifier ASSIGNOP expression SEMICOLON | identifier UNARYOP SEMICOLON | UNARYOP identifier SEMICOLON;
expression: identifier ARITHOP identifier | identifier ARITHOP numconstant | numconstant ARITHOP numconstant;
for_expression_statement: identifier ASSIGNOP expression  | identifier UNARYOP | UNARYOP identifier;

condition_statement: identifier RELOP identifier | identifier RELOP numconstant | numconstant RELOP identifier | condition_statement AND condition_statement | condition_statement OR condition_statement | BOOLTRUE | BOOLFALSE;
jump_statement: BREAK SEMICOLON | CONTINUE SEMICOLON;

print_statement: PRINT OPENBRACES stringconstant CLOSEBRACES SEMICOLON | PRINT OPENBRACES DOUBLEQUOTES FORMATSPEC DOUBLEQUOTES COMMA identifier CLOSEBRACES SEMICOLON;

identifier: IDENTIFIER;
intconstant: INTCONST;
numconstant: INTCONST | FLOATCONST;
stringconstant: STRING;
%%
#include "lex.yy.c"
int yyerror()
{
    printf("\nDoes not satisfy the grammar\n");
    valid=0;
    return 0;
}
int main()
{
    yyin = fopen("in.c","r");
    yyparse();
    if(valid)
    {
        printf("\nSatisfies the grammar \n");
    }
    display(head);  
}

The screenshots below show the warnings and output on execution -

(I have not wirtten the code to update value and dataype yet. This is just to display the symbol table in yacc.)

user_1566221 · Answer

The top level of a C program can only contain declarations and definitions. It cannot contain statements. So the following is not legal in the top level of a C program:

extern node* head;
head = NULL;

The second line is converted into a declaration because GCC still allows pre-Standard C declarations with implicit type (the type defaults to int). It does warn you about that, but the warning isn't very helpful.

The upshot is that the above is interpreted as though it had been

extern node* head;
int head = NULL;

Which is clearly illegal since you can't give the same name to two global definitions. GCC then proceeds to use the second definition, and the rest of the errors cascade.

This has nothing to do with flex or bison, and very little to do with yoir symbol table implementation, which I didn't look at. But it's a good illustration of why you should think about generating good error messages when you are writing a parser.

Lex and Yacc symbol table generation and manipulation

1 Answers