Simple symbol table with yacc

In the last post about yacc, we got yacc to evaluate expressions and print out the evaluated value.

In programs that involve setting and looking up variable values, there is usually some kind of symbol table. At the top of the yacc file, I've added the following global symbol table and related functions:

%{
#include <stdio.h>

#define TABLE_SIZE 26
#define UNSET -1

int SYMBOL_TABLE[TABLE_SIZE];
int lookup(int symbol_num);
void set(int symbol_num, int value);
void reset_table();

%}

In this example, the table symbol is just big enough to fit one variable per letter of the alphabet. The table is expected to be initialized with a special "unset" value before use.

The rule section of the yacc file has been modified to include an "assignment statement" type expression. When an assignment statement is encountered, the symbol table is modified. When a variable is encountered and is being used for its value, the value of the expression is looked up in the symbol table.

%%

start   : stmt { printf($1 ? "true\n" : "false\n"); }
        | expr { printf($1 ? "true\n" : "false\n"); }
        ;

expr    : NOT expr { $$ = ! $2; }
        | expr AND expr { $$ = ($1 && $3); }
        | expr OR expr { $$ = ($1 || $3); }
        | LPAREN expr RPAREN { $$ = $2; }
        | NAME { $$ = lookup($1); }
        | FALSE { $$ = 0; }
        | TRUE { $$ = 1; }
        ;

stmt    : NAME ASSIGN expr { set($1, $3); $$ = $3; }
        ;

%%

We're using two new tokens, so they have to be included in the lex file rules section:

=   { return ASSIGN; }
[a-z] { yylval = yytext[0] - 'a'; return NAME; }

The set and lookup functions still have to be defined, and they can be defined at the bottom of the yacc file after the rules section:

int lookup(int symbol_num) {
  printf("lookup %d\n", symbol_num);
  if (SYMBOL_TABLE[symbol_num] == UNSET ||
      symbol_num < 0 || symbol_num >= TABLE_SIZE) {
    return 0;  // false by default
  }
  return SYMBOL_TABLE[symbol_num];
}

void set(int symbol_num, int value) {
  printf("set %d %d\n", symbol_num, value);
  if (symbol_num < 0 || symbol_num >= TABLE_SIZE) {
    return;  // do nothing by default
  }
  SYMBOL_TABLE[symbol_num] = value;
}

After this is added, the parser also accepts assignment expressions and looks up variables in a table.

> a = not true      
false
> b = (true and true)
true
> a or b
true
> a and b
false

Giving values to expressions in yacc

In the last post, I started to use yacc, but in that example, when rules were matched, the action for each message was just to print out a message; the tokens were not combined or evaluated in any way.

Inside an action block after a grammar rule expr : X Y Z, $$ is the value of the left-hand side (the output when that rule is used to reduce a sequence of expressions), and expressions on the right hand side are in the variables $1, $2, $3, etc.

For example, in our logic expression grammar we can have:

expr    : NOT expr { $$ = ! $2 }
        | expr AND expr { $$ = ($1 && $3); }
        | expr OR expr { $$ = ($1 || $3); }
        | LPAREN expr RPAREN { $$ = $2; }
        | TRUE { $$ = 1; }
        | FALSE { $$ = 0; }
        ;

Each alternative (separated by |) can have an action associated with it; each of these rules can combine the right hand side values in a different way to set $$.

With this, we can now parse and evaluate complex expressions:

File: logic.y

%{
#include 
%}

%token TRUE FALSE AND OR NOT LPAREN RPAREN
%left OR
%left AND
%left NOT

%%

start   : expr {
          if ($1) {
            printf("true\n");
          } else {
            printf("false\n");
          }
        }

expr    : NOT expr { $$ = ! $2; }
        | expr AND expr { $$ = ($1 && $3); }
        | expr OR expr { $$ = ($1 || $3); }
        | LPAREN expr RPAREN { $$ = $2; }
        | TRUE { $$ = 1; }
        | FALSE { $$ = 0; }
        ;

%%

extern FILE *yyin;

int main() {
  do {
    printf("> ");
    yyparse();
  } while (!feof(yyin));
}

yyerror(s) char *s; {
  fprintf(stderr, "yyerror called with: %s\n", s);
}

The %token section at the top, as before, specifies the tokens and allows yacc to generate a header file that's also used by the lexer. the %left rules above specify operator precedence order and associativity so that the rules are not ambiguous.

The first rule, start has one action associated with it, which is to print out the value of a parsed expression. In this grammar, there are several possible patterns that can comprise an expr; all of these rules are recursive except for true and false, which have primitive values.

In this example, the main function now prints a prompt, reads a sequence of tokens and parses, and repeats until EOF (ctrl-D on the terminal) is entered.

Example:

$ ./calc
> false and false and false and false 
false
> true and (false or not false)
true
> true and
yyerror called with: syntax error
>