Ich arbeitete an einem Parser-Projekt und ich implementierte es mit recursive descent parser. Das Problem könnte jedoch leicht Stapelüberlauf verursachen. Was sind die Techniken, um mit dieser Art von Problem umzugehen?Vermeiden Sie stackoverflow im rekursiven Algorithmus in rekursiven Abstieg Parser
Zur Veranschaulichung, hier ist einfache mathematische Ausdruck Parser, mit Addition, Subtraktion, Multiplikation und Division zu unterstützen. Gruppierungsklammern könnten verwendet werden, und sie lösen offensichtlich eine Rekursion aus.
hier ist voll Code:
#include <string>
#include <list>
#include <iostream>
using namespace std;
struct term_t;
typedef list<term_t> prod_t;
typedef list<prod_t> expr_t;
struct term_t
{
bool div;
double value;
expr_t expr;
};
double eval(const expr_t &expr);
double eval(const term_t &term)
{
return !term.expr.empty() ? eval(term.expr) : term.value;
}
double eval(const prod_t &terms)
{
double ret = 1;
for (const auto &term : terms)
{
double x = eval(term);
if (term.div)
ret /= x;
else
ret *= x;
}
return ret;
}
double eval(const expr_t &expr)
{
double ret = 0;
for (const auto &prod : expr)
ret += eval(prod);
return ret;
}
class expression
{
public:
expression(const char *expr) : p(expr)
{
prod();
for (;;)
{
ws();
if (!next('+') && *p != '-') // treat (a-b) as (a+-b)
break;
prod();
}
}
operator const expr_t&() const
{
return expr;
}
private:
void term()
{
expr.back().resize(expr.back().size() + 1);
term_t &t = expr.back().back();
ws();
if (next('('))
{
expression parser(p); // recursion
p = parser.p;
t.expr.swap(parser.expr);
ws();
if (!next(')'))
throw "expected ')'";
}
else
num(t.value);
}
void num(double &f)
{
int n;
if (sscanf(p, "%lf%n", &f, &n) < 1)
throw "cannot parse number";
p += n;
}
void prod()
{
expr.resize(expr.size() + 1);
term();
for (;;)
{
ws();
if (!next('/') && !next('*'))
break;
term();
}
}
void ws()
{
while (*p == ' ' || *p == '\t')
++p;
}
bool next(char c)
{
if (*p != c)
return false;
++p;
return true;
}
const char *p;
expr_t expr;
};
int main()
{
string expr;
while (getline(cin, expr))
cout << "= " << eval(expression(expr.c_str())) << endl;
}
, wenn Sie ausführen, können Sie einfache mathematische Ausdrücke wie 1+2*3+4*(5+6*7) Typ und wird 195 korrekt berechnen. Ich habe auch einfache Ausdruck Auswertung hinzugefügt, es verursacht auch Rekursion und Ursachen Stapelüberlauf noch einfacher als das Parsen. Wie auch immer, das Parsen selbst ist einfach und offensichtlich, wie kann ich es umschreiben, ohne große Änderungen im Code vorzunehmen und die Rekursion vollständig zu vermeiden? In meinem Fall verwende ich einen ähnlichen Ausdruck wie diese (((((1))))), um Rekursion zu verursachen, und wenn ich nur ein paar hundert Klammern habe, bekomme ich Stapelüberlauf. Wenn ich mit Debugger (in Visual Studio) die Rekursionsbaumstruktur durchtrete, wenn nur drei Funktionen: [term ->] expression ctor -> ->term und aus der Registerprüfung nehmen diese drei Funktionen 700-1000 Bytes Stapelspeicherplatz. Mit den Optimierungseinstellungen und dem Fiddling-Code kann ich etwas weniger machen, und mit den Compiler-Einstellungen kann ich den Stack-Speicherplatz erhöhen, oder in diesem Fall könnte ich auch Dijksta's shunting-yard algorithm verwenden, aber das ist nicht der Punkt der Frage: Ich möchte wissen, wie man umschreibt um Rekursion zu vermeiden und gleichzeitig, wenn möglich, ohne den Parsing-Code komplett neu zu schreiben.
siehe "Tail-Rekursion-Optimierung". Die Grundidee besteht darin, Teilergebnisse in eine rekursive Funktion zu überführen. Dann wird der Compiler den gleichen Frame für jeden rekursiven Aufruf verwenden. – DanielS
* wenn ich nur ein paar hundert Klammern habe * - Erwarten Sie in einem realen Szenario wirklich mehr als 200 verschachtelte Klammern? – PaulMcKenzie
@PaulMcKenzie im wirklichen Leben Ich hatte dieses Problem nicht, aber ich wollte herausfinden, wie man mit so etwas umgeht. – Pavel