Я работал над проектом, связанным с парсером, и я его реализовал с использованием recursive descent parser. Однако проблема может привести к переполнению стека. Каковы методы решения этой проблемы?избежать stackoverflow в рекурсивном алгоритме в парсере рекурсивного спуска
Для иллюстрации, это простой синтаксический анализатор математического выражения, с добавлением, вычитанием, умножением и поддержкой разделения. Можно использовать группирующие скобки, и они, очевидно, вызывают рекурсию.
вот полный код:
#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;
}
если вы бежите, вы можете ввести простые математические выражения, как 1+2*3+4*(5+6*7) и правильно рассчитать 195. Я также добавил оценку простого выражения, это также вызывает рекурсию и вызывает переполнение стека даже проще, чем синтаксический анализ. В любом случае, синтаксический анализ является простым и очевидным, как я могу его переписать без внесения больших изменений в код и полностью избежать рекурсии? В моем случае я использую выражение, подобное этому (((((1))))), чтобы вызвать рекурсию, и если у меня будет всего несколько сотен круглых скобок, я получаю переполнение стека. Если я пройду через дерево рекурсии отладчика (в Visual Studio), если только три функции: [term ->] expression ctor ->prod ->term и из проверки регистра эти три функции занимают 700-1000 байт пространства стека. С настройками оптимизации и программным кодом немного могу сделать это меньше, а с настройками компилятора я могу увеличить пространство стека, или в этом случае я мог бы также использовать Dijksta's shunting-yard algorithm, но это не вопрос: я хочу знать, как переписать чтобы избежать рекурсии и в то же время, если это возможно, без полного переписывания кода анализа.
посмотреть на «оптимизацию хвостовой рекурсии». Основная идея состоит в том, чтобы передать частичные результаты в рекурсивную функцию. Затем компилятор будет знать, что повторно использует один и тот же фрейм для каждого рекурсивного вызова – DanielS
* если у меня всего несколько сотен круглых скобок * - В реальном сценарии вы действительно ожидаете 200+ вложенных круглых скобок? – PaulMcKenzie
@PaulMcKenzie в реальной жизни У меня не было этой проблемы, но я хотел выяснить для себя, как обращаться с такими вещами. – Pavel