2

我有一个表示 C# 代码的数据结构，如下所示：

class Namespace:
    string Name;
    List<Class> Classes;

class Class:
    string Name;
    List<Property> Properties;
    List<Method> Methods;
    List<Method> Constructors;
    List<Field> Fields;
    List<Class> InnerClasses;
    Class Parent;
    List<Interface> Implements;

...我正在使用简单的词法分析器/解析器组合构建它。我需要遍历树并应用大量规则（超过 3000 条）。规则在遇到树中不同（且相当复杂）的模式时运行。例如，当一个类仅在同一个程序集中实现接口时，就会运行一条规则。

我最初的幼稚实现迭代每个规则，然后每个规则遍历树以查找其特定模式。当然，这需要相当多的时间，即使是少量的源代码。

我想这可以比作防病毒软件的工作原理，识别大量二进制代码上的复杂模式。

你会如何建议使用这种软件？

EDT：只是想补充一下：不，我不会重新实现 FxCop。

谢谢

4

3 回答 3

1

您可以尝试汇总您的 3000 条规则。3000 中的一些，我猜想假设 3000 中的另一个成员。假设规则 12 检查“类实现接口”。规则 85 可能是“一个类只在同一个程序集中实现接口”。如果规则 12 失败，则根本不需要运行规则 85。

这种方法（alpha-beta pruning）要么需要您重新构建算法以搜索类树，同时查找所有规则模式。或者存储先前规则通过已识别当前规则通过不相关的记录。

评论：我有一个小块级别的帐户，所以我不能直接评论。你能举一个可能还有 2 条规则的例子吗？我目前认为您的算法是 0(n*n) （从大 0 符号帖子复制后）

O(n*log(n))：一种执行某种分而治之策略的算法。对大 n 有害。典型例子：归并排序

O(n*n)：某种嵌套循环。即使 n 很小也会很痛。常见于朴素矩阵计算。如果可以的话，你想避免这种算法。

于 2009-01-09T23:34:43.697 回答
0

我会考虑为模式/上下文创建某种表示形式，然后创建一个从模式到一组动作的哈希映射。在不了解更多需求的情况下，很难更具体，但作为示例，字符串"Namespace/Class"可能是一组操作的键，这些操作依赖于知道命名空间和它包含的单个类，"Class/Interface"可能是集合的键处理单个类和它实现的单个接口的操作等。

树遍历算法可以跟踪它自己的上下文（父节点、当前节点等），根据它在树中的位置形成一个键，检索该键的动作集，然后触发所有这些动作，给每个参数结构，该结构提供与键模式相对应的实际节点。

这相当于创建了一个特殊用途的规则引擎，它处理形式为“如果我有一个类C，并且它实现了一个接口I，那么……用C和I”。

于 2009-01-10T00:18:18.960 回答
0

@吉米麦克纳尔蒂

这是一个很好的方法。Alpha-beta pruning 你说它叫什么？它正在重新安排规则，这样如果一个人失败了，它就会排除其他人。我对吗？我要调查一下。

以下是其他规则的一些示例：

  • 类是最终的，并且不实现/扩展程序集之外的类。
  • 方法是虚拟的，但类是私有的或内部的。
  • 类或方法具有特定的属性。
  • 方法参数在编译时是已知的。

我很想听听任何其他可以让我更快/更智能地执行这种逻辑的技术。

谢谢

于 2009-01-10T02:49:20.057 回答