Konvertieren von BNF-Grammatikregeln in tatsächliche C++ - Funktionen/Code

Question

Ich versuche, einen rekursiven Descent-Parser zu erstellen. Bis jetzt habe ich alle Grundlagen festgelegt, ich muss nur ein paar Funktionen implementieren, um die Grammatik zu erzwingen. Ich dachte, alles war richtig, es sieht so aus, aber ich denke, meine Aop, Expr oder Term Funktion macht etwas falsch. Manchmal wird der Eingabestrom abgeschnitten und Dinge werden nicht erkannt. Ich sehe nicht wie.

Gibt es eine Website oder Quelle, die dies ausführlicher mit Codebeispielen erklärt? Alles, was ich gesehen habe, ist sehr generisch, was gut ist, aber ich bleibe bei der Implementierung hängen.

HINWEIS: Bearbeiten Sie 17. April 2016: Meine Funktionen waren ziemlich gut und gut strukturiert für den Kontext meines Programms. Das Problem, das ich hatte und nicht erkannte, war, dass ich in bestimmten Fällen, wenn ich getToken anrief, Zeichen aus dem Eingabestrom "auffrischte". Manchmal ist das in Ordnung, manchmal nicht und der Eingabestream musste zurückgesetzt werden. Also füge ich einfach eine kleine Schleife in Fällen hinzu, in denen ich Zeichenketten durch Zeichen zurücksetzen musste. Z. B:

if(t.getType() !=Token::EQOP) 
    { 
     //cout<<"You know it" << endl; 
     int size = t.getLexeme().size(); 


     while(size>0) 
     { 
     br->putback(t.getLexeme().at(size-1)); 
     size--; 
     } 

     return ex; 
    } 

Also mit diesem wird gesagt, ich war so ziemlich der Lage, mein Programm entsprechend zu bearbeiten und alles hat funktioniert, wenn ich sah, was die Charaktere wurde auffressen.

Dies ist die Grammatik:

Program::= StmtList 
    StmtList::= Stmt | StmtList 
    Stmt::= PRINTKW Aop SC | INTKW VAR SC | STRKW VAR SC | Aop SC 
    Expr::= Expr PLUSOP Term | Expr MINUSOP Term | Term 
    Term::= Term STAROP Primary | Primary 
    Primary::= SCONST | ICONST | VAR | LPAREN Aop RPAREN 

Hier ist das Hauptprogramm mit allen Funktionen: http://pastebin.com/qMB8h8vE

Die Funktionen, die ich scheinen die meisten Probleme zu haben mit AssignmentOperator(Aop) ist, Expression(Expr) und Term . Ich werde sie hier auflisten.

ParseTree* Aop(istream *br) 
{ 
    ParseTree * element = Expr(br); 
    if(element!=0) 
    { 
     if(element->isVariable()) 
     { 
      Token t= getToken(br); 

      if(t==Token::EQOP) 
      {     
       cout<<"No" << endl; 
       ParseTree * rhs = Aop(br); 
       if(rhs==0) 
        return 0; 
       else 
       { 
        return new AssignOp(element, rhs); 
       } 
      } 
      else 
      { 
       return element; 
      } 
     } 
    } 

    return 0; 
} 

ParseTree* Expr(istream *br) 
{ 
    ParseTree * element = Term(br); 
    if(element!=0) 
    { 
     Token t=getToken(br); 
     if(t==Token::MINUSOP || t==Token::PLUSOP) 
     { 
      if(t==Token::PLUSOP) 
      { 
       ParseTree* rhs = Expr(br); 
       if(rhs==0) 
        return 0; 
       else 
       { 
        return new AddOp(element, rhs); 
       } 
      } 

      if(t==Token::MINUSOP) 
      { 
       ParseTree* rhs = Expr(br); 
       if(rhs==0) 
        return 0; 
       else 
       { 
        return new SubtractOp(element, rhs); //or switch the inputs idk 
       } 
      } 
     } 
     else 
     { 
      return element; 
     } 
    } 

    return 0; 
} 

ParseTree* Term(istream *br) 
{ 
    ParseTree *element = Primary(br); 

    if(element!=0) 
    { 
     Token t=getToken(br); 
     if(t==Token::STAROP) 
     { 
      ParseTree* rhs =Term(br); 
      if(rhs==0) 
       return 0; 
      else 
      { 
       return new MultiplyOp(element, rhs); 
      } 
     } 
     else 
     { 
      return element; 
     } 
    } 

    return 0; 
} 

Answer 1

Um einen recusrive Abstieg Parser zu schreiben, müssen Sie Ihre Grammatik in LL Form konvertieren, von left recursion loszuwerden. Für die Regeln

Term::= Term STAROP Primary | Primary 

Sie bekommen so etwas wie:

Term ::= Primary Term' 
Term' ::= epsilon | STAROP Primary Term' 

diese dann verwandeln sich in eine Funktion so etwas wie:

ParseTree *Term(istream *br) { 
    ParseTree *element = Primary(br); 
    while (element && peekToken(br) == Token::STAROP) { 
     Token t = getToken(br); 
     ParseTree *rhs = Primary(br); 
     if (!rhs) return 0; 
     element = new MulOp(element, rhs); } 
    return element; 
} 

Beachten Sie, dass Sie ein peekToken brauchen werden Funktion, um auf das nächste Token zu schauen, ohne es zu verbrauchen. Es ist auch möglich, getToken + ungetToken zu verwenden, um das Gleiche zu tun.