cyacclex

How to incorporate ++ operator in yacc


In Chapter 8 of the classic Kernighan & Pike book (The UNIX Programming Environment) hoc1 is presented as an example of simple calculator using yacc.

The book suggest to improve the source code to cover the unitary increment operator (++).

I have tried to implement the ++ operator in the yacc source code (which includes the lex functions and does not use the companion lex program) as follows:

%{
#define YYSTYPE double          /* DATA TYPE OF YACC STACK */ 
%}

%token NUMBER
%left '+' '-'                   /* LEFT ASSOCIATIVE, SAME PRECEDENCE */ 
%left '*' '/'                   /* LEFT ASSOC., HIGHER PRECEDENCE */ 
%left UNARYMINUS                /* LEFT ASSOC., HIGHER PRECEDENCE */ 
%right INC

/* GRAMMAR */

%% 
list:     /* nothing */ 
        | list '\n' 
        | list expr '\n'        { printf("\t%.8g\n", $2); } 

expr:     NUMBER                        { $$ = $1; } 
        | expr INC                      { $$ = $1 + 1; } 
        | '-' expr %prec UNARYMINUS     { $$ = -$2; }
        | expr '+' expr                 { $$ = $1 + $3; } 
        | expr '-' expr                 { $$ = $1 - $3; } 
        | expr '*' expr                 { $$ = $1 * $3; } 
        | expr '/' expr                 { $$ = $1 / $3; } 
        | expr '%' expr                 { $$ = fmod($1, $3); } 
        | '(' expr ')'                  { $$ = $2; }
%% 

/* GRAMMAR PROCESSING ROUTINES */

#include <stdio.h>
#include <ctype.h>
#include <math.h>

int yylex(void);
void yyerror(char *s);
void warning(char *s, char *t);

char    *progname;
int     lineno = 1;

int main(int argc, char *argv[]) {

        progname = argv[0];
        yyparse();
}

int yylex() {
        int c;

        while((c=getchar()) == ' ' || c == '\t')
                ;

        if(c==EOF) {
                return 0;
        }
        if(c=='.' || isdigit(c)) {
                ungetc(c,stdin);
                scanf("%lf", &yylval);
                return NUMBER;
        }
        if(c=='+') {
                if((c=getchar()) == '+') {
                        return INC;
                } else {
                        ungetc(c,stdin);
                        return '+';
                }
        }
        if(c=='\n')
                lineno++;
        return c;
}

void yyerror(char *s) {
        warning(s, (char *)0);
}

void warning(char *s, char *t) {
        fprintf(stderr, "%s: %s", progname, s);
        if(t) {
                fprintf(stderr, " %s", t);
        }
        fprintf(stderr, " near line %d\n", lineno);
}

First I generate the C source code with yacc and I get the shift/reduce conflicts, why those shift/reduce conflicts are present?

$ make
yacc -d hoc1.y
yacc: 11 shift/reduce conflicts.

Solution

  • The shift/reduce conflicts all come from the ambiguous '%' operator, as you haven't specified a precedence or associativity for it. If you add it to your precedence rules (same precedence as '*' and '/'), they will go away:

    %left '*' '/' '%'              /* LEFT ASSOC., HIGHER PRECEDENCE */