Warum muss ich eine Grammatik umschreiben?

Question

Ich versuche, Compiler-Konstruktion auf eigene Faust zu studieren. Ich lese ein Buch und das ist eine der Übungen (Ich möchte betonen, dass dies nicht Hausaufgaben ist, mache ich das auf eigene Faust).

Die folgende Grammatik stellt eine einfache arithmetische Ausdrücke in Lisp-like Präfixnotation

LEXP ->Nummer | (op lexp-seq)
op -> + | * | +
lexp-seq -> lexp-seq lexp | LEXP

beispielsweise die Expression (* (-2) 3 4) einen Wert von -24 aufweist. Schreiben Sie Yacc/Bison-Spezifikation für ein Programm, das den Wert von Ausdrücken in dieser Syntax berechnet und druckt. (Hinweis: Dies erfordert die Grammatik Umschreiben, sowie die Verwendung eines Mechanismus zum Hindurch der Bediener auf einen LEXP-seq

I es gelöst haben die Lösung unter I bereitgestellt jedoch.. . Fragen zu meiner Lösung sowie das Problem selbst Hier sind sie:

1. ich habe keine Grammatik in meiner Lösung ändern, und es scheint perfekt zu funktionieren es gibt keine Konflikte, wenn Yacc/Bison spec. Wird in eine .c-Datei konvertiert. Warum sagt der Autor, dass ich eine Grammatik umschreiben muss?

2. Meine Lösung verwendet einen Stapel als Mechanismus zum Übergeben des Operators an einen lexp-seq. Kann jemand eine andere Methode vorschlagen, die keinen Stapel verwendet?

Hier ist meine Lösung für das Problem (Ich bin nicht Code für Stapelmanipulations Posting als die Annahme, dass der Leser vertraut ist mit wie Stacks arbeiten)

%{ 
#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

einen Stapel hier verwenden ist unnötig, wenn Sie die Grammatik umschreiben.

Eine Möglichkeit ist, einen anderen nicht-Terminal für jeden Betreiber zu verwenden:

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; } 

Ich weiß nicht, ob das, was Autor Ihres Buches ist im Sinn hatte. Es gibt sicherlich andere mögliche Implementierungen.

In einer echten Lisp-ähnlichen Sprache müssten Sie dies ganz anders machen, da das erste Objekt in einem Lexp möglicherweise ein Wert höherer Ordnung (dh eine Funktion) wäre, der sogar das Ergebnis einer Funktion sein könnte rufen Sie auf, damit Sie die Operationen nicht in die Syntax codieren können (und Sie können den Ausdruck nicht unbedingt teilweise analysieren, wenn Sie neue Argumente parsen).