Unary operator precedence in yacc

Question

I'm getting a strange error in my YACC parser. It's a simple boolean algebra expression evaluator.

Everything works except the following type of situation:

> True and False
False
> (True and False)
False
> not (True and False)     <--- interpreted as (not True and False)
False

example.y:

%{
#include <stdio.h>
int yylex();
void yyerror(const char *err);

%}

%token NEWLINE EQUIV IMPL OR AND NOT CONST

%union {
    bool value;
}

%type <value> CONST value not and or impl equiv expr

%%

program:
    |
    program expr NEWLINE
    ;

expr:
    equiv               { printf("%s\n", $1?"True":"False"); }             
    ;

equiv:
    impl                { $$ = $1; }                   
    |
    equiv EQUIV impl    { $$ = $1 == $3; }     
    ;

impl:
    or              { $$ = $1; }               
    |
    impl IMPL or    { $$ = !$1 || $3; }
    ;

or:
    and             { $$ = $1; }   
    |
    or OR and       { $$ = $1 || $3; } 
    ;

and:
    not             { $$ = $1; }           
    |
    and AND not     { $$ = $1 && $3; }     
    ;

not:
    value           { $$ = $1; }           
    |
    NOT not         { $$ = !$2; }
    ;

value:
    CONST           { $$ = $1; }           
    |
    '(' expr ')'    { $$ = $2; }
    ;

%%

void yyerror(const char *err) {
    fprintf(stderr, "%s\n", err);
}

int main() {
    yyparse();
}

example.l:

%{
#include "y.tab.h"
extern "C" int yywrap();
%}

%%

True                yylval.value = true; return CONST;
False               yylval.value = false; return CONST;

"<=>"               return EQUIV;
=>                  return IMPL;
or                  return OR;
and                 return AND;
not                 return NOT;

[ \t]               ;
\n                  return NEWLINE;
.                   ;

%%

int yywrap() {
    return 1;
}

Compiled with

bison -dy example.y
flex -l example.l
g++ y.tab.c lex.yy.c

Please post an minimal reproducible example, what you posted is not enough to reproduce the problem. — sepp2k

sepp2k sepp2k · Accepted Answer · 2019-05-27T23:47:16

The only rule in your lexer that matches parentheses is the . rule, which does not return anything (or give any indication that a character has been ignored, which is a bad idea exactly because it makes problems like this so much easier to miss). Thus the parentheses in your input are completely ignored, the '(' and ')' in your grammar can never be matched and the input the parser sees is simply not True and False.

Unary operator precedence in yacc

1 Answers