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
>