如何解决正则表达式无限递归问题并实现C#表达式解析器？

首先，你的问题核心是左递归导致的正则无限循环——原BNF里的<expr_num> := <expr_num><operator_num><expr_num>是左递归结构，直接用递归正则组会让引擎陷入无限尝试匹配开头的<expr_num>，根本无法终止。下面分两部分帮你解决：

一、修正递归正则（消除左递归） #

要处理这种表达式结构，首先得把左递归的BNF转换成右递归形式，或者用迭代模式处理重复的操作符。重新梳理后的BNF应该是这样：

<expr_num> := <term> (<operator_num> <term>)*
<term> := <var> | <sign> | "(" <expr_num> ")"

这样就彻底消除了左递归，对应的C#递归正则可以写成：

// 定义正则模式，使用命名组和递归，忽略空白方便阅读
string regexPattern = @"
(?<expr_num>
    (?<term>
        (?<var>\w+)                  # 变量：至少一个字母/数字/下划线（避免匹配空串）
        | (?<sign>[+-])              # 符号：+或-（字符集里不用|）
        | \( (?&expr_num) \)         # 带括号的嵌套表达式
    )
    ( (?<operator_num>[+\-*/]) (?&term) )*  # 重复匹配「操作符+项」
)$";

// 编译正则，启用忽略空白和编译优化
Regex regex = new Regex(regexPattern, RegexOptions.IgnorePatternWhitespace | RegexOptions.Compiled);

关键说明： #

• 把原左递归的<expr_num><operator_num><expr_num>拆成<term> (<operator_num> <term>)*，递归只会出现在<term>里的括号表达式，避免了无限循环。
• 修正了变量匹配规则（\w+而非\w*），防止匹配空字符串导致的意外问题；操作符字符集里的-做了转义，避免被当成范围符。

二、C#中实现表达式解析器（更可靠的方案） #

正则虽然能完成匹配，但处理操作符优先级（比如先乘除后加减）和结合性时会非常吃力。如果要做真正的表达式解析，更专业的方式是手写递归下降解析器，或者用语法分析工具。

方案1：手写递归下降解析器 #

以下是一个极简的可运行示例，支持变量、符号、括号、四则运算，还自动处理操作符优先级：

public class ExprParser
{
    private readonly string _input;
    private int _pos = 0;
    private readonly Dictionary<string, double> _variables;

    public ExprParser(string input, Dictionary<string, double>? variables = null)
    {
        _input = input.Replace(" ", ""); // 先去掉所有空格
        _variables = variables ?? new Dictionary<string, double>();
    }

    // 解析顶层表达式（处理加减运算）
    public double Parse()
    {
        double result = ParseTerm();
        while (_pos < _input.Length && "+-".Contains(_input[_pos]))
        {
            char op = _input[_pos];
            _pos++;
            double term = ParseTerm();
            result = op == '+' ? result + term : result - term;
        }
        return result;
    }

    // 解析项（处理乘除运算）
    private double ParseTerm()
    {
        double result = ParseFactor();
        while (_pos < _input.Length && "*/".Contains(_input[_pos]))
        {
            char op = _input[_pos];
            _pos++;
            double factor = ParseFactor();
            result = op == '*' ? result * factor : result / factor;
        }
        return result;
    }

    // 解析原子因子：变量、带符号数字、括号表达式
    private double ParseFactor()
    {
        if (_pos >= _input.Length)
            throw new InvalidOperationException("Unexpected end of input");

        char c = _input[_pos];
        if (c == '(')
        {
            _pos++;
            double result = Parse();
            if (_pos >= _input.Length || _input[_pos] != ')')
                throw new InvalidOperationException("Mismatched parentheses");
            _pos++;
            return result;
        }
        else if (char.IsLetter(c))
        {
            // 解析变量名
            string varName = "";
            while (_pos < _input.Length && char.IsLetterOrDigit(_input[_pos]))
            {
                varName += _input[_pos];
                _pos++;
            }
            if (!_variables.TryGetValue(varName, out double value))
                throw new InvalidOperationException($"Undefined variable: {varName}");
            return value;
        }
        else if (char.IsDigit(c) || c == '+' || c == '-')
        {
            // 解析带符号的数字
            string numStr = "";
            if (c == '+' || c == '-')
            {
                numStr += c;
                _pos++;
                if (_pos >= _input.Length || !char.IsDigit(_input[_pos]))
                    throw new InvalidOperationException("Invalid number format");
            }
            while (_pos < _input.Length && char.IsDigit(_input[_pos]))
            {
                numStr += _input[_pos];
                _pos++;
            }
            return double.Parse(numStr);
        }
        else
        {
            throw new InvalidOperationException($"Unexpected character: {c}");
        }
    }
}

// 使用示例
var variables = new Dictionary<string, double> { { "x", 10 }, { "y", 20 } };
var parser = new ExprParser("(x + 5) * 2 - y", variables);
double result = parser.Parse();
Console.WriteLine(result); // 输出：10

方案2：使用ANTLR生成解析器 #

如果你的表达式规则后续会变得复杂，推荐用ANTLR这样的专业语法分析工具：

1. 编写.g4语法文件定义你的BNF规则。
2. 用ANTLR生成C#解析器代码。
3. 在项目中引用生成的代码，快速实现表达式解析。

这种方式能自动处理左递归、操作符优先级，扩展性极强。

总结 #

• 正则处理表达式时，必须消除左递归，通过拆分BNF为「原子项+重复操作符」的形式避免无限循环。
• 追求可靠性和扩展性的话，手写递归下降解析器或使用ANTLR是更好的选择——正则更适合简单匹配场景，而非复杂表达式的语法解析。

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