为什么我需要重写语法？

Question

我正在尝试自己研究编译器构造。我正在看书，这是练习之一（我想强调一下，这不是家庭作业，我是自己做的）。

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

我已经解决了。下面提供了解决方案。但是，我对我的解决方案以及问题本身有疑问。他们在这里：

我没有修改我的解决方案中的语法，它似乎工作得很好。 Yacc/Bison spec 转换为 .c 文件时没有冲突。那为什么作者说我要重写一个语法呢？
我的解决方案是使用堆栈作为将运算符传递给 lexp-seq 的机制。有人可以建议一种不同的方法，即不使用堆栈的方法吗？

这是我对问题的解决方案（我没有发布堆栈操作代码，因为假设 reader 熟悉堆栈的工作原理）

%{
#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", ); };

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

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

           case '-':
             $$ = -;
             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 '+':
                 $$ =  + ;
                 break;
               case '-':
                 $$ =  - ;
                 break;
               case '*':
                 $$ =  * ;
                 break;
             }
           }

         | lexp { $$ = ; }
         ;
%%

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

如果重写语法，这里不需要使用堆栈。

一种方法是为每个运算符使用不同的非终端：

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

我不知道你的书的作者是不是这么想的。当然还有其他可能的实现方式。

在真正的 lisp-like 语言中，您需要以完全不同的方式执行此操作，因为 lexp 中的第一个对象可能是高阶值（即函数），甚至可能是函数调用，因此您无法将操作编码到语法中（并且您也不必在解析新参数时部分评估表达式）。

为什么我需要重写语法？

Why do I need to rewrite a grammar?

parsing

yacc

bison