使用Nom解析递归枚举遇栈溢出问题，求正确实现方式

问题根源 #

你的解析函数形成了无限递归调用链：parse_arithexp优先调用parse_ae_add，而parse_ae_add又直接调用parse_arithexp。当解析像"3"这样的常量时，这个递归链会无限循环，直到栈被撑爆。

修复方案一：用循环替代递归处理加法（推荐） #

把表达式拆分为原子表达式（仅常量）和加法组合表达式，用循环处理连续的加法操作，彻底避免递归栈溢出：

use nom::{
    character::complete::{digit1, multispace0},
    combinator::terminated,
    multi::many0,
    bytes::complete::tag,
    sequence::pair,
    IResult,
};
use std::rc::Rc;

#[derive(Debug, PartialEq, Eq)]
enum ArithExp {
    Const(i32),
    Add(Rc<ArithExp>, Rc<ArithExp>),
}

// 解析常量表达式
fn parse_ae_const(input: &str) -> IResult<&str, ArithExp> {
    let (input, numb) = terminated(digit1, multispace0)(input)?;
    Ok((input, ArithExp::Const(numb.parse::<i32>().unwrap())))
}

// 解析原子表达式：目前仅包含常量
fn parse_atom(input: &str) -> IResult<&str, ArithExp> {
    parse_ae_const(input)
}

// 解析加法表达式：先解析一个原子，再循环处理后续的 "+ 原子"
fn parse_add_expr(input: &str) -> IResult<&str, ArithExp> {
    let (input, mut current_exp) = parse_atom(input)?;
    let (input, additions) = many0(pair(tag(" + "), parse_atom))(input)?;
    
    for (_, next_exp) in additions {
        current_exp = ArithExp::Add(Rc::new(current_exp), Rc::new(next_exp));
    }
    
    Ok((input, current_exp))
}

// 顶层解析函数：直接调用加法表达式解析
fn parse_arithexp(input: &str) -> IResult<&str, ArithExp> {
    parse_add_expr(input)
}

#[test]
fn arithexp1() {
    assert_eq!(parse_ae_const("3"), Ok(("", ArithExp::Const(3))));
}

#[test]
fn arithexp2() {
    assert_eq!(parse_arithexp("3"), Ok(("", ArithExp::Const(3))));
}

#[test]
fn arithexp3() {
    assert_eq!(
        parse_arithexp("3 + 5"),
        Ok((
            "",
            ArithExp::Add(Rc::new(ArithExp::Const(3)), Rc::new(ArithExp::Const(5)))
        ))
    );
}

#[test]
fn arithexp4() {
    assert_eq!(
        parse_arithexp("3 + 5 + 7"),
        Ok((
            "",
            ArithExp::Add(
                Rc::new(ArithExp::Add(Rc::new(ArithExp::Const(3)), Rc::new(ArithExp::Const(5)))),
                Rc::new(ArithExp::Const(7))
            )
        ))
    );
}

这种方式不仅解决了栈溢出，还天然支持连续加法，符合算术表达式的常规语义，执行效率也更高。

修复方案二：用Nom的recursive组合子处理递归 #

如果需要处理更复杂的嵌套表达式（比如带括号的结构），可以用Nom提供的recursive组合子延迟递归调用，避免栈溢出：

use nom::{
    branch::alt,
    bytes::complete::tag,
    character::complete::{digit1, multispace0},
    combinator::{terminated, recursive},
    sequence::separated_pair,
    IResult,
};
use std::rc::Rc;

#[derive(Debug, PartialEq, Eq)]
enum ArithExp {
    Const(i32),
    Add(Rc<ArithExp>, Rc<ArithExp>),
}

fn parse_ae_const(input: &str) -> IResult<&str, ArithExp> {
    let (input, numb) = terminated(digit1, multispace0)(input)?;
    Ok((input, ArithExp::Const(numb.parse::<i32>().unwrap())))
}

// 调整加法解析函数，接收递归解析器作为参数
fn parse_ae_add(input: &str, parser: impl Fn(&str) -> IResult<&str, ArithExp>) -> IResult<&str, ArithExp> {
    let (input, (exp1, exp2)) = terminated(
        separated_pair(parser, tag(" + "), parser),
        multispace0,
    )(input)?;
    Ok((input, ArithExp::Add(Rc::new(exp1), Rc::new(exp2))))
}

// 用recursive包装递归逻辑，延迟求值避免栈溢出
fn parse_arithexp(input: &str) -> IResult<&str, ArithExp> {
    recursive(|parser| {
        alt((
            |i| parse_ae_add(i, parser),
            parse_ae_const,
        ))(input)
    })
}

#[test]
fn arithexp1() {
    assert_eq!(parse_ae_const("3"), Ok(("", ArithExp::Const(3))));
}

#[test]
fn arithexp2() {
    assert_eq!(parse_arithexp("3"), Ok(("", ArithExp::Const(3))));
}

#[test]
fn arithexp3() {
    assert_eq!(
        parse_arithexp("3 + 5"),
        Ok((
            "",
            ArithExp::Add(Rc::new(ArithExp::Const(3)), Rc::new(ArithExp::Const(5)))
        ))
    );
}

这种方式适合扩展到更复杂的语法，但相比循环方式有一定的递归栈开销。

内容的提问来源于stack exchange，提问作者cptkidd