c# - 用自定义解析器替换简单正则表达式的好方法是什么？

Question

我正在用 C# 编写一些数据处理程序，在做了一些分析之后，我发现我使用的正则表达式是最大的瓶颈。它们占用了整个算法大约 80% 的时间，这不仅仅是解析，所以我决定改为手动解析数据。

格式很简单，我基本上是解析=XXX+YYY形式的简单算术表达式，其中XXX和YYY 是术语，+ 表示可应用于这些术语的一组有限运算符中的一个。始终只有两个术语和一个运算符，尽管这些术语可以用几种不同的方式表示。

到目前为止，我的方法基本上是编写一个类似于 (matchXXX)([+-*/...])(matchYYY) 的正则表达式，然后在每个正则表达式上应用另一个正则表达式操作数以查看它们是什么类型。我在编写高性能解析器方面并没有太多经验。我只在 Haskell 中使用过 Parsec，它具有非常独特的方法，并且可能需要大量工作才能实现。

那么问题是，为这种表达式编写解析器的好方法是什么？有没有在大多数情况下都行之有效的通用方法？

我不是在寻找解析器生成器。我需要的是一个可以手动实现的简单解决方案。

更新:目前最慢的正则表达式是 ([A-Z]+\d+)([+\-*/])([A-Z]+\d+)

Answer 1

我要尝试的第一条攻击线是优化正则表达式本身。由于您的表达式结构缺少嵌套，因此可能有一个简单的优化可以显着减少引擎花费的时间。

接下来我要尝试的是通过预编译表达式更好地使用正则表达式引擎，即使用 Regex 的非静态方法，而不是静态方法。

在这两种方法中都不起作用，我会选择一个简单的 recursive descent parser .这些解析器是迄今为止编写代码最简单的，但它们为简单语言提供了良好的性能(而且您的语言绝对是简单的)。