Zur Komplexität von rekursiven Descent-Parsern

Question

Es ist bekannt, dass rekursive Descent-Parser in einigen Fällen exponentielle Zeit erfordern können; Könnte mich jemand auf die Proben hinweisen, wo das passiert? Besonders interessiert an Fällen für PEG (d. H. Mit priorisierten Entscheidungen).

Answer 1

Es ist weil Sie am Ende die gleichen Dinge (überprüfen Sie die gleiche Regel an der gleichen Position) oft in verschiedenen Rekursionszweigen analysieren können. Es ist ungefähr so, als würde man die n-te Fibonacci-Zahl mit Rekursion berechnen.

Grammar: 

A -> xA | xB | x 
B -> yA | xA | y | A 
S -> A 

Input: 
xxyxyy 

Parsing: 
xA(xxyxyy) 
    xA(xyxyy) 
     xA(yxyy) fail 
     xB(yxyy) fail 
     x(yxyy) fail 
    xB(xyxyy) 
     yA(yxyy) 
      xA(xyy) 
       xA(yy) fail 
       xB(yy) fail 
       x(yy) fail 
      xB(xyy) 
       yA(yy) 
        xA(y) fail 
        xB(y) fail 
        x(y) fail 
       xA(yy) fail * 
      x(xyy) fail 
     xA(yxyy) fail * 
     y(yxyy) fail 
     A(yxyy) 
      xA(yxyy) fail * 
      xB(yxyy) fail * 
      x(yxyy) fail * 
    x(xyxyy) fail 
xB(xxyxyy) 
    yA(xyxyy) fail 
    xA(xyxyy) * 
     xA(yxyy) fail * 
     xB(yxyy) fail * 
     ... 

* - wo wir eine Regel in der gleichen Position zu analysieren, wo wir haben es bereits in einem anderen Zweig analysiert. Wenn wir die Ergebnisse gespeichert hätten - welche Regeln an welchen Positionen versagen - würden wir wissen, dass xA (xxyxy) das zweite Mal fehlschlägt und wir würden nicht noch einmal durch den gesamten Teilbaum gehen. Ich wollte die ganze Sache nicht schreiben, aber Sie können sehen, dass es die gleichen Unterbäume viele Male wiederholen wird.

Wenn es passiert - wenn Sie viele überlappende Transformationen haben. Priorisierte Auswahl ändert nichts - wenn die Regel mit der niedrigsten Priorität die einzig richtige ist (oder keine korrekt ist), mussten Sie trotzdem alle Regeln überprüfen.

Answer 2

Jeder Top-Down-Parser, einschließlich des rekursiven Sinkens, kann theoretisch exponentiell werden, wenn die Kombination von Eingabe und Grammatik so groß ist, dass eine große Anzahl von Rückverfolgungen erforderlich ist. Dies geschieht, wenn die Grammatik derart ist, dass am Ende von langen Sequenzen bestimmende Entscheidungen getroffen werden. Wenn Sie zum Beispiel ein Symbol wie & haben, das bedeutet "alle vorherigen Minuswerte sind tatsächlich plus" und dann Daten wie "((((a - b) - c) - d &)" dann muss der Parser gehen rückwärts und ändere alle Plus- und Minuszeichen. Wenn Sie damit beginnen, geschachtelte Ausdrücke entlang dieser Zeilen zu erstellen, können Sie eine praktisch nicht endende Menge von Eingaben erstellen.

Sie müssen erkennen, dass Sie hier in ein politisches Problem einsteigen, denn die Realität ist, dass die meisten normalen Grammatiken und Datensätze nicht so sind, aber es gibt eine Menge Leute, die rekursive Abstammung systematisch verschlingen, weil es nicht ist einfach RD automatisch zu machen. Alle frühen Parser sind LALR, weil sie viel einfacher automatisch als RD zu machen sind. Was passierte, war, dass alle nur LALR geschrieben und RD abgekanzelt hatten, denn in der alten Zeit war der einzige Weg, um einen RD zu machen, es von Hand zu programmieren. Zum Beispiel, wenn Sie das Drachenbuch lesen, werden Sie feststellen, dass Aho & Ullman nur einen Absatz auf RD schreiben, und es ist im Grunde nur eine ideologische Takedown sagen: "RD ist schlecht, mach es nicht".

Natürlich, wenn Sie Hand Codierung RDs (wie ich) starten, werden Sie feststellen, dass sie aus einer Vielzahl von Gründen viel besser als LALRs sind. Früher konnte man einem Compiler, der eine Hand-codierte RD hatte, immer sagen, dass er aussagekräftige Fehlermeldungen mit Ortsgenauigkeit hatte, während Compiler mit LALRs den Fehler wie 50 Zeilen entfernt von der tatsächlichen Position aufzeigten. Die Dinge haben sich seit den alten Zeiten stark verändert, aber man sollte sich darüber im Klaren sein, dass wenn man anfängt, die FUD auf RD zu lesen, dass es aus einer langen, langen Tradition stammt, RD in "bestimmten Kreisen" zu verbalen.