Why do I need to rewrite a grammar?

Question

I'm trying to study compiler construction on my own. I'm reading a book and this is one of the exercises (I want to stress that this is not homework, I'm doing this on my own).

The following grammar represents a simple arithmetic expressions in LISP-like prefix notation

lexp -> number | ( op lexp-seq )
op -> + | * | +
lexp-seq -> lexp-seq lexp | lexp

For example, the expression (* (-2) 3 4) has a value of -24. Write Yacc/Bison specification for a program that will compute and print the value of expressions in this syntax. (Hint: this will require rewriting the grammar, as well as the use of a mechanism for passing the operator to an lexp-seq

I have solved it. The solution is provided below. However I have questions about my solution as well as the problem itself. Here they are:

1. I don't modify a grammar in my solution and it seems to be working perfectly. There are no conflicts when Yacc/Bison spec is converted to a .c file. So why is the author saying that I need to rewrite a grammar?

2. My solution is using a stack as a mechanism for passing the operator to an lexp-seq. Can someone suggest a different method, the one that will not use a stack?

Here is my solution to the problem (I'm not posting code for stack manipulation as the assumption is that the reader is familiar with how stacks work)

%{
#include <stdio.h>
#include <stdlib.h>
#include <ctype.h>
#include <string.h>
#include "linkedstack.h"

int yylex();
int yyerror();

node *operatorStack;

%}

%token NUMBER

%%
command : lexp { printf("%d\n", $1); };

lexp : NUMBER { $$ = $1; }
     | '(' op lexp_seq ')' 
       { 
         int operator;
         operatorStack = pop(operatorStack, &operator); 
         switch(operator) {
           default: 
             yyerror("Unknown operator");
             exit(1);
             break;

           case '+':
           case '*':
             $$ = $3;
             break;

           case '-':
             $$ = -$3;
             break;
         }
       }
     ;

op : '+' { operatorStack = push(operatorStack, '+'); } 
   | '-' { operatorStack = push(operatorStack, '-'); } 
   | '*' { operatorStack = push(operatorStack, '*'); }
   ; 

lexp_seq : lexp_seq lexp 
           {
             switch(operatorStack->data) {
               default:
                 yyerror("Unrecognized operator");
                 exit(1);
                 break;
               case '+':
                 $$ = $1 + $2;
                 break;
               case '-':
                 $$ = $1 - $2;
                 break;
               case '*':
                 $$ = $1 * $2;
                 break;
             }
           }

         | lexp { $$ = $1; }
         ;
%%

int main(int argc, char** argv) {
  int retVal;

  init(operatorStack);

  if (2 == argc && (0 == strcmp("-g", argv[1])))
    yydebug = 1;

  retVal = yyparse();

  destroy(operatorStack);

  return retVal;
}

int yylex() {
  int c;

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

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

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

  return (c);
}

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

Answer 1

Using a stack here is unnecessary if you rewrite the grammar.

One way is to use a different non-terminal for each operator:

command : lexp '\n'      { printf("%d\n", $1); }
lexp    : NUMBER
        | '(' op_exp ')' { $$ = $2; }
op_exp  : plus_exp | times_exp | minus_exp
plus_exp: '+' lexp       { $$ = $2; }
        | plus_exp lexp  { $$ = $1 + $2; }
times_exp: '*' lexp      { $$ = $2; }
        | times_exp lexp { $$ = $1 * $2; }
minus_exp: '-' lexp      { $$ = -$2; }
        | minus_exp lexp { $$ = $1 - $2; }

I don't know if that is what your book's author had in mind. There are certainly other possible implementations.

In a real lisp-like language, you would need to do this quite differently, because the first object in an lexp could be a higher-order value (i.e. a function), which might even be the result of a function call, so you can't encode the operations into the syntax (and you can't necessarily partially evaluate the expression as you parse new arguments, either).