can't figure out why yacc/bison grammar doesn't work

Question

This is not homework, though it is from a book.

I'm given a yacc/bison spec file. The task is to add a new production

number -> number digit
digit -> 0 | 1 | 2 | 3 | 4 | 5 | 6 | 7 | 8 | 9

to calculate the value of a number and do away with a NUMBER token. The grammar is provided below.

%{
#include <stdio.h>
#include <ctype.h>

int yylex();
int yyerror();
%}

%token NUMBER

%%

command : exp { printf("%d\n", $1); }
        ; /* allows printing of the result */

exp : exp '+' term { $$ = $1 + $3; }
    | exp '-' term { $$ = $1 - $3; }
    | term { $$ = $1; }
    ;

term : term '*' factor { $$ = $1 * $3; }
     | factor { $$ = $1; }
     ;

factor : NUMBER { $$ = $1; }
       | '(' exp ')' { $$ = $2; }
       ;

%%

int main() {
  return yyparse();
}

int yylex() {
  int c;
  while((c = getchar()) == ' ');
  /* eliminate blanks*/
  if (isdigit(c)) {
    ungetc(c, stdin);
    scanf("%d", &yylval);
    return (NUMBER);
  }
  if (c == '\n') return 0;
  /* makes the parse stop */
  return (c);
}

int yyerror(char * s) {
  fprintf(stderr, "%s\n", s);
  return 0;
} /* allows for printing of an error message */

As an experiment to make sure that I'm doing everything correctly I eliminated the number token, added the following production:

number : '1' {$$ = $1;}

changed the factor production to

factor : number {$$ = $1;}

and eliminated

if (isdigit(c)) {
  ungetc(c, stdin);
  scanf("%d", &yylval);
  return (NUMBER);
}

from the yylex() function. In other words the spec file looks like the following:

%{
#include <stdio.h>
#include <ctype.h>

int yylex();
int yyerror();
%}


%%

command : exp { printf("%d\n", $1); }
        ; /* allows printing of the result */

exp : exp '+' term { $$ = $1 + $3; }
    | exp '-' term { $$ = $1 - $3; }
    | term { $$ = $1; }
    ;

term : term '*' factor { $$ = $1 * $3; }
     | factor { $$ = $1; }
     ;

factor : number { $$ = $1; }
       | '(' exp ')' { $$ = $2; }
       ;

number : '1' { $$ = $1; }
       ;

%%

int main() {
  return yyparse();
}

int yylex() {
  int c;
  while((c = getchar()) == ' ');
  /* eliminate blanks*/

  if (c == '\n') return 0;
  /* makes the parse stop */
  return (c);
}

int yyerror(char * s) {
  fprintf(stderr, "%s\n", s);
  return 0;
} /* allows for printing of an error message */

However after I run the code on the following expression: 1+1, I get an answer of 0.

Come someone help me out? What am I doing wrong?

oh no, i got downgraded by 1 vote. why is this question wrong? — flashburn
Probably because debugging questions are off-topic here. You're looking for StackOverflow. — Ixrec
@lxrec I see. i was afraid that if I ask it on overflow they'll tell me to move it here. I had hat happen to me. — flashburn
@lxrec It is my understanding that it is possible to move questions between stack exchange websites, but one needs enough "points" to do so. I don't have them. Do you mind moving the question for me? — flashburn

rici rici · Accepted Answer · 2016-05-17T23:22:43

number : '1' { $$ = $1; }

This says that the parser can reduce the terminal '1' (a single character token) to a number and that when it does so, it should copy the semantic value.

Very good. But what is the semantic value of '1'? As with any other token, it is the value stored into yylval by yylex when it returns the token type. In the original code, for example, yylex used scanf("%d", &yylval) to set the semantic value of the NUMBER token. But in the new code, yylex isn't living up to its contract. It never sets yylval to anything, so the semantic value of any token it returns is undefined. (That's perfectly OK as long as the parser never uses the semantic value of the token. '+' isn't given a semantic value either, but the parser isn't expecting one.)

In the case of the token '1', the parser really doesn't need the scanner's assistance: it's clear what the semantic value should be:

number : '1' { $$ = 1; }

Alternatively, the scanner could help out:

if (isdigit(c)) yylval = c - '0';
return c;

can't figure out why yacc/bison grammar doesn't work

1 Answers