CODEWITHSUNDEEP
yacc
limp_chimp
limp_chimp

Reputation: 15163

Precedence rules not working in Yacc

I'm learning yacc, and this code snippet I got out of a book doesn't seem to be applying the precedence rules correctly.

Here's the yacc file:

%{

#include <stdio.h>
extern int yylex();
void yyerror (char const *msg);

%}

%token NAME NUMBER
%left '+' '-'
%left '*' '/'

%%

statement:  NAME '=' expression
    |       expression              { printf("= %d\n", $1); }
    ;

expression: expression '+' NUMBER   { $$ = $1 + $3; }
    |       expression '-' NUMBER   { $$ = $1 - $3; }
    |       expression '*' NUMBER   { $$ = $1 * $3; }
    |       expression '/' NUMBER   { if ($3) $$ = $1 / $3;
                                      else yyerror("divide by zero"); }
    |       '-' expression          { $$ = -$2; }
    |       '(' expression ')'      { $$ = $2; }
    |       NUMBER                  { $$ = $1; }
    ;

%%

Here's the lex:

%{
#include "y.tab.h"
#include <stdio.h>
extern int yylval;
%}

%%

[0-9]+      { yylval = atoi(yytext); return NUMBER; }
[ \t]       { ; }
\n          { return 0; }
.           { return yytext[0]; }

%%

I compile it with:

lex foo.l
yacc -d foo.y
clang -o foo lex.yy.c y.tab.c -ly -ll

Running it multiplication-first gives the right answer:

> ./foo
3 * 2 + 1
= 7

But when the multiplication happens second, it gives the wrong answer:

> ./foo
4 + 5 * 2
= 18

Adding the lines %left '+' '-' and %left '*' '/' in the yacc file were supposed to fix this, but they didn't. Can anyone tell me why?

Upvotes: 0

Views: 909

Answers (2)

Chris Dodd
Chris Dodd

Reputation: 126203

The precedence rules only serve to resolve ambiguities in the grammar. If your grammar directly encodes the precedences, then there are no ambiguities for the precedence rules to resolve.

Defining your grammar as expr: expr op NUMBER defines the precedence of all operators as being the same and evaluates them strictly left-to-right. You want to define the grammar as expr: expr op expr for each operator, so that the grammar is ambiguous, and the precendence rules can resolve the ambiguity.

Upvotes: 1

user529758
user529758

Reputation:

Your specification of the productions is wrong, though. It should be expression '+' expression instead of expression '+' NUMBER (and similarly in the case of each operator), i. e. both sides are expressions, you don't want to prohibit addition of two expressions, do you.

Upvotes: 2

Related Questions