Recursive-descent-parser-Implementierung

Grundsätzlich in recursive-descent-parsing jedes nicht-terminal der Grammatik übersetzt, in einer Prozedur, dann in jede Prozedur, die Sie überprüfen, um zu sehen, ob das aktuelle token sind Sie auf der Suche übereinstimmt, was Sie erwarten würden, um zu sehen, auf der rechten Seite der nicht-terminal-symbol der entsprechenden Verfahren, wenn es dann funktioniert, weiterhin anwenden der Produktion, wenn nicht, dann haben Sie einen Fehler festgestellt und muss einige Maßnahmen ergreifen.

So, in Ihrem Fall, wie Sie oben erwähnt haben Sie Verfahren: S()L()und E() werde ich ein Beispiel geben, wie L() umgesetzt werden könnten, und dann können Sie versuchen und tun S() und E() auf Ihrem eigenen.

Es ist auch wichtig zu beachten, dass Sie benötigen, ein anderes Programm für die tokenisierung der Eingabe für Sie, dann können Sie nur bitten, das Programm für das nächste token aus der Eingabe.

/**
 * This procedure corresponds to the L non-terminal
 * L -> 'end'
 * L -> ';' S L
 */
public void L()
{
   if(currentToken == 'end')
   {
      //we found an 'end' token, get the next token in the input stream
      //Notice, there are no other non-terminals or terminals after 
      //'end' in this production so all we do now is return
      //Note: that here we return to the procedure that called L()
      getNextToken();
      return; 
   } 
   else if(currentToken == ';')
   {
      //we found an ';', get the next token in the input stream
      getNextToken();
      //Notice that there are two more non-terminal symbols after ';'
      //in this production, S and L; all we have to do is call those
      //procedures in the order they appear in the production, then return
      S();
      L();
      return;
   }
   else
   {
      //The currentToken is not either an 'end' token or a ';' token 
      //This is an error, raise some exception
      throw new IllegalTokenException(
          "Procedure L() expected an 'end' or ';' token "+
          "but received: " + currentToken);
   }
}

Nun versuchen Sie S() und E() und nach zurück.

Auch als Kristopher Punkte heraus, Ihre Grammatik hat, sowas nennt man dangling else, meaing, dass Sie eine Produktion beginnt mit der gleichen Sache bis zu einem Punkt:

S -> if E then S 
S -> if E then S else S

Also dies wirft die Frage auf, ob Ihre parser sieht eine 'wenn' - token, die Produktion sollte es wählen, Sie zu verarbeiten die Eingabe? Die Antwort ist, es hat keine Ahnung, was man zu wählen, weil im Gegensatz zum Menschen kann der compiler nicht, Blick nach vorne in die Eingabe-stream für die Suche nach einem 'else' - token. Dies ist ein einfaches problem zu beheben, durch die Anwendung einer Regel bekannt als Links-Factoring, sehr ähnlich wie Sie den Faktor einer algebra problem.

Alles, was Sie tun müssen ist, erstellen Sie ein neues nicht-terminal-symbol S' (E-prime), deren Rechte Seite halten die Stücke von den Produktionen, die nicht üblich, so dass Ihre S - Produktionen keine wird:

S  -> if E then S S'
S' -> else S 
S' -> e   
(e is used here to denote the empty string, which basically means there is no   
 input seen)

InformationsquelleAutor der Antwort Hunter McMillen

Habe ich gelernt (eigentlich nur, half) die Analyse-Abschnitt in einem PL-Klasse als letztes semester. Ich wirklich empfehlen, sich auf die Analyse von Folien, die von unserer Seite: hier. Grundsätzlich ist für die recursive-descent-parsing, Fragen Sie sich die folgende Frage:

Habe ich analysiert, ein wenig von einem non-Terminal, jetzt bin ich an einem Punkt, wo ich eine Entscheidung treffen kann, was soll ich analysieren weiter. Was sehe ich als Nächstes machen die Entscheidung was non-Terminal bin ich in.

Ihre Grammatik -- -- weist eine sehr häufige Mehrdeutigkeit sogenannte "dangling else", die seit dem Algol Tage. In shift reduzieren Parser (in der Regel produziert von parser-Generatoren) generiert dies ein shift /reduce-Konflikt, wo Sie in der Regel wählen, um beliebig verlagern, anstatt zu reduzieren, so dass Sie die gemeinsamen "maximal viel" - Prinzip. (Also, wenn Sie sehen, "wenn (b) dann if (b2) S1 else S2" Sie Lesen es als "if (b) then { if (b2) { s1; } else { s2; } }")

Let ' s werfen Sie dies aus Ihrer Grammatik, und arbeiten mit einem etwas einfacher Grammatik:

T -> A + T
 |   A - T
 |   A
A -> NUM * A
   | NUM /A
   | NUM

wir gehen auch davon ausgehen, dass NUM ist etwas, das man aus dem lexer (d.h., es ist nur ein token). Diese Grammatik ist LL(1), das heißt, Sie können analysieren, es mit einem recursive descent-parser implementiert, mit einem naiven Algorithmus. Der Algorithmus funktioniert wie folgt:

parse_T() {
  a = parse_A();
  if (next_token() == '+') {
    next_token();  //advance to the next token in the stream
    t = parse_T();
    return T_node_plus_constructor(a, t);
  }
  else if (next_token() == '-') {
    next_token();  //advance to the next token in the stream
    t = parse_T();
    return T_node_minus_constructor(a, t);
  } else {
    return T_node_a_constructor(a);
  }
}
parse_A() {
  num = token(); //gets the current token from the token stream
  next_token();  //advance to the next token in the stream
  assert(token_type(a) == NUM);
  if (next_token() == '*') {
    a = parse_A();
    return A_node_times_constructor(num, a);
  }
  else if (next_token() == '/') {
    a = parse_A();
    return A_node_div_constructor(num, a);
  } else {
    return A_node_num_constructor(num);
  }
}

Siehst du das Muster hier:

für jedes non-Terminal in Ihrer Grammatik: analysieren Sie die ersten Sache, dann sehen Sie, was Sie haben, zu betrachten, zu entscheiden, was Sie sollte analysieren nächsten. Weiter dies, bis Sie fertig sind!

Beachten Sie bitte auch, dass diese Art der Analyse in der Regel nicht produzieren, was Sie wollen, für Arithmetik. Recursive descent Parser (es sei denn, Sie verwenden einen kleinen trick mit tail recursion?) nicht produzieren leftmost-Ableitungen. Insbesondere können Sie nicht schreiben, Links-rekursive Regeln wie "a -> a - a", wo die Links-Assoziativität ist wirklich notwendig! Dies ist, warum Menschen in der Regel verwenden schicker parser-generator-tools. Aber der rekursive Abstieg trick noch Wert ist, wissen über und spielen, um mit.

InformationsquelleAutor der Antwort Kristopher Micinski