Wie schreibt man eine rekursive Funktion mit einem nicht rekursiven Stack?

Question

Um zu versuchen, ein PEG in JavaScript zu implementieren, das ältere Browser nicht von Stapelüberläufen abstürzen lässt, möchte ich eine syntaktische Ausdruckgrammatik erstellen, die eine Zeichenfolge auf nichtrekursive Weise analysiert. Wie machst Du das? Es fühlt sich geistesabwesend an.

Sagen Sie bitte eine Struktur wie dieses:

• A grammar viele Ausdrücke hat
• Ein expression hat viele matchers
• A matcher hat viele tokens (oder was auch immer ist ein besseres Wort dafür)
• Ein token kann entweder auf einen anderen expression zeigen oder eine primitive Zeichenfolge oder ein regulärer Ausdruck sein. Wenn es also auf einen anderen Ausdruck zeigt, startet die Rekursion.

So sagen Sie die Hierarchie wie folgt definieren:

var grammar = new Grammar('math'); 
var expression = grammar.expression; 

expression('math') 
    .match(':number', ':operator', ':number', function(left, operator, right){ 
    switch (operator) { 
     case '+': return left + right; 
     case '-': return left - right; 
     case '*': return left * right; 
     case '/': return left/right; 
    } 
    }); 

expression('number') 
    .match(/\d+/, parseInt); 

expression('operator') 
    .match('+') 
    .match('-') 
    .match('*') 
    .match('/'); 

var val = grammar.parse('6*8'); // 42 

Wenn Sie grammar.parse nennen, ist es an der Wurzel Ausdruck beginnt (die den gleichen Namen wie es hat, so „Mathematik“). Dann durchläuft es jeden Matcher, dann jedes Token, und wenn das Token ein Ausdruck ist, rekursiv. Im Grunde ist dies (der Parser wird der Überblick über die Offset/Position der Zeichenfolge es die Muster gegen einstimmt; dies ist nur Pseudo-Code):

function parse(str, expression, position) { 
    var result = []; 

    expression.matchers.forEach(function(matcher){ 
    matcher.tokens.forEach(function(token){ 
     var val; 
     if (token.expression) { 
     val = parse(str, token.expression, position); 
     } else { 
     val = token.parse(str, position); 
     } 
     if (val) result.push(val); 
    }); 
    }); 

    return result; 
} 

parse('6*8', grammar.root, 0); 

Also für einen einfachen Ausdruck wie 6*8 gibt es sehr wenig Rekursion, aber man kann schnell zu einem komplexen Ausdruck mit vielen Ebenen der Verschachtelung. Plus multipliziere die Verschachtelung mit all diesen verschachtelten for-Schleifen, und der Stapel wird groß (ich verwende nicht forEach, ich benutze for-Schleifen, aber in der for-Schleife ruft er die meiste Zeit eine Funktion auf, so dass er hübsch wird Ziemlich das gleiche).

Die Frage ist, Wie können Sie dies "abflachen"? Statt Rekursion zu tun, wie machen Sie das so im Wesentlichen es ist dies wie:

while (token = stack.pop()) { 
    val = token.parse(val); 
    if (val) result.push(val); 
} 

Ich bin nicht für die Details, wie suche eine Lösung für dieses spezifische PEG Problem zu implementieren, ich bin nur mehr suchen die allgemeine Art und Weise, wie Sie den rekursiven Zustand nicht rekursiv verfolgen.

Answer 1

Im Allgemeinen schreiben Sie einen Stapel im Code und Sie setzen Ihre "lokalen" Variablen in ein "Stapelrahmen" -Kontextobjekt, das Sie auf diesem Stapel behalten. Dann, wo Sie einen "rekursiven Aufruf" hätten, speichern Sie den aktuellen Stack-Frame und erstellen einen neuen für den neuen aktuellen Kontext. Die "Rückkehr" ist nur eine Frage der Umkehrung der Operation. Es ist nicht besonders kompliziert, aber es macht den Code ein wenig durcheinander. Die einzige Sache, auf die Sie achten sollten, ist, dass Sie zu dem Zeitpunkt, an dem Sie den Ausdruck analysiert haben, an den unteren Rand des Stapels gelangen (so dass nachgestellte und fehlende Token keine Probleme verursachen).

Es ist sehr ähnlich wie bei einem Stack, der im Maschinencode gepflegt wird, außer dass Sie nicht auf primitive Werte beschränkt sind und die Dinge dadurch (auf der Datenstrukturebene) wesentlich besser machen können.

Wenn Sie Zeit haben, sollten Sie den LR (1) -Parser schreiben (oder einen anderen verwenden).Diese behalten einen sehr kleinen Systemstapel und behandeln eine Anzahl übler Fälle in Grammatiken besser als Ihre selbstgewollte LL (k) Grammatik. Allerdings sind sie erheblich mysteriöser in wie sie arbeiten als das, was Sie jetzt haben.

Answer 2

Suche mehr nur für die allgemeine Art und Weisen Sie den Überblick über den rekursive Zustand in einer nicht-rekursive Art und Weise zu halten.

Verwenden Sie pushen und popping in Stapeln (Arrays).
Und es wäre einfacher, wenn Sie Gotos hatten.
Ein (Fakultät) Ansatz in VBA (deutlicher wegen der Goto's).

Option Explicit 
Sub Main() 
    MsgBox fac(1) 
    MsgBox fac(5) 
End Sub 
Function fac(n&) 
    Dim answer&, level&, stackn&(99) 
    level = 0 
zentry: 
    If n = 1 Then answer = 1: GoTo zreturn 
    level = level + 1 ' push n 
    stackn(level) = n 
    n = n - 1 ' call fac(n-1) 
    GoTo zentry 
zreturn: 
    If level = 0 Then fac = answer: Exit Function 
    n = stackn(level) ' pop n 
    level = level - 1 
    answer = n * answer ' factorial 
    GoTo zreturn 
End Function 

Der gleiche Ansatz in Javascript.

console.log(fac(1)); 
console.log(fac(5)); 
function fac(n) { // non-recursive 
    var answer, level; 
    var stackn = []; 
    level = 0; 
    while (true) { // no goto's 
    if (n == 1) { answer = 1; break; } 
    level = level + 1; // push n 
    stackn[level] = n; 
    n = n - 1; } // call fac(n-1) 
    while (true) { // no goto's 
    if (level == 0) { return answer; } 
    n = stackn[level]; // pop n 
    level = level - 1; 
    answer = n * answer; } // factorial 
    }