Wie funktioniert dieser C++ Parser?

Question

Ich lese gerade "Programmierung: Prinzipien und Praxis mit C++" von Bjarne Stroustrup und ich habe Probleme zu verstehen, wie diese bestimmte Grammatik implementiert ist. Hier

ist die Grammatik und seine Regeln:

Expression: 
    Term 
    Expression "+" Term 
    Expression "-" Term 
Term: 
    Primary 
    Term "*" Primary 
    Term "/" Primary 
    Term "%" Primary 
Primary: 
    Number 
    "(" Expression ")" 
Number: 
    floating-point literal 

Dies ist jedoch, wie Zeit implementiert:

double term() 
{ 
    double left = primary(); 
    Token t = ts.get();  // get the next token from token stream 

    while(true) { 
     switch (t.kind) { 
     case '*': 
      left *= primary(); 
      t = ts.get(); 
      break; 
     case '/': 
     { 
      double d = primary(); 
      if (d == 0) error("divide by zero"); 
      left /= d; 
      t = ts.get(); 
      break; 
     } 
     default: 
      ts.putback(t);  // put t back into the token stream 
      return left; 
    } 
    } 
} 

Warum wir in der switch-Anweisung, left *= primary(); nennen, wenn das Token gleich "*" anstelle von left *= term()?

Ich habe versucht, left *= primary(); durch left *= term() zu ersetzen (tat das gleiche für Division) und das Programm funktionierte immer noch gut. Ich verstehe jedoch nicht die Design-Entscheidung, die Bjarne im Sinn hatte, das heißt, warum er die Funktion so implementiert hat, wie er es getan hat. Vielleicht vermisse ich hier etwas?

Vielen Dank im Voraus!

Answer 1

Warum wir in der switch-Anweisung, rufen left *= primary(); wenn das Token zu "*" gleich, statt left *= term()?

Da die Grammatik sagt:

Term: 
    Primary 
    Term "*" Primary 
    Term "/" Primary 
    Term "%" Primary 

Beachten Sie, dass, wenn C++ (und C) hatte einen Potenzierungsoperator, oder seine Beispielgrammatik hatte unäre Operatoren, was Sie gesehen hätten, ist das üblichere:

Expression: 
    Term 
    Expression "+" Term 
    Expression "-" Term 
Term: 
    Factor 
    Term "*" Factor 
    Term "/" Factor 
    Term "%" Factor 
Factor: 
    Primary 
    Primary "**" Factor /* note right-associativity */ 
Primary: 
    "+" Primary 
    "-" Primary 
    Number 
    "(" Expression ")" 
Number: 
    floating-point literal 

Answer 2

Weil die Produktion nicht Term "*" Term ist.

Es ist Term "*" Primary.

Der Grund dafür in der Grammatik selbst ist so, dass, wenn Sie verschachtelte Term s im Ausdruck haben, sie gezwungen sind, auf der linken Seite aus einer Parsing-Perspektive "erscheinen". Die rechte Seite ist effektiv davon überzeugt, nur primäre Ausdrücke zu enthalten (die keine anderen Operatoren enthalten). Wenn dies angewendet wird, um Ihr "Programm" rekursiv zu analysieren, ist das Ergebnis, dass die Operatoren linksassoziativ sind, was zu ((a*b)*c) anstelle von (a*(b*c)) führt.

Eine solche Grammatik wird nur "nach unten" gehen, nicht "nach oben", sonst landen Sie in einer großen Unordnung oder zumindest einer unnatürlichen Assoziativität, die Menschen verwirrt, die versuchen, in Ihrer Sprache Arithmetik zu schreiben.

Natürlich ist das arithmetische Ergebnis für die Multiplikation theoretisch gleich. Wenn Sie jedoch verschiedene Operatoren verwenden, wird das Problem klar: ((a*b)/c) ist nicht dasselbe wie (a/(b*c)).