1

我正在尝试使用嵌套结构解析二进制文件格式。在过程伪代码中，过程如下：

// A structure contains:
// tag | oneof(a, b, c) | oneof(oneof(aa, ab, ac), oneof(ba, bb, bc), oneof(ca, cb, cc))
PROCEDURE parse() {
    RECORD read_type;

    read_tag(read_type);

    if (read_type == TYPE_A) {
        read_a(read_type);
        if (read_type == TYPE_AA) {
            read_aa();
        } else if (read_type == TYPE_AB) {
            read_ab();
        } else if (read_type == TYPE_AC) {
            read_ac();
        }
    } else if (read_type == TYPE_B) {
        // see above
    } else if (read_type == TYPE_C) {
        // see above
    }
}

如果没有来自其父对象 A 的上下文，则无法解释诸如 AA 之类的外部结构，这反过来又需要其标签/标题来解释。在使用这些结构时，操作包含 A、包含 AA 等的结构是有意义的，但绝不仅仅是结构的 A 或 AA 部分。

然后我的问题是如何为这个过程创建一个类模型。结构应该是：

class Base;
class A: Base;
class B: Base;
class C: Base;
class AA: A;
class AB: A;
class AC: A;
// ...

在这种情况下，AA 可以这样构造：

AA::AA(): A() {
    read_aa();
}

A::A(): Base() {
    read_a();
}

Base::Base() {
    read_tag();
}

但是，问题在于如果不首先构造基础对象，就不可能知道要构造什么派生对象。这可以通过使用复制构造其父级的构造函数 AA::AA(A*) 来解决，但这似乎是不必要的低效率。此外，这将需要一个外部工厂函数，例如：

Base *read_object() {
    Base *base = new Base();
    if (b->tag_type == TYPE_A) {
        A *a = new A(base);
        if (a->tag_type == TYPE_AA) {
            return new AA(a);
        } else if (a->tag_type == TYPE_AB) {
            // ...
        } else if (a->tag_type == TYPE_AC) {
            // ...
        }
    } else if (b->tag_type == TYPE_B) {
        // ...
    } else if (b->tag_type == TYPE_C) {
        // ...
    }
}

另一种选择是拥有引用结构子区域的类，例如：

class CompleteStructure;
class StructureA;
class StructureB;
class StructureC;
class StructureAA;
class StructureAB;
class StructureAC;
// ...

class CompleteStructure {
    union {StructureA a, StructureB b, StructureC c} sub;
}

class StructureA {
    CompleteStructure *parent;
    union {StructureAA aa, StructureAB ab, StructureAC ac} sub;
}

class StructureAA {
    StructureA *parent;
}

在这种情况下，构造函数 CompleteStructure::CompleteStructure() 将读取标记，然后构造 StructureA、StructureB 或 StructureC 之一，而后者又会构造自己的子结构。这样做的问题是，每个子结构都需要对其父级的显式引用，以便“投射”层次结构并实现其方法/功能。

在空间/时间效率和“清洁度”方面，这些方法中的一种是否比另一种更好？有没有更好的第三种方法？

编辑：为了回答下面的两个答案，问题是关于解析和对象行为。我最初的目标只是从文件中读取结构，打印出它们的字段，然后以相同的顺序将它们写回磁盘。稍后，将有其他目标，例如查找 A 派生结构的所有实例并按某些字段对它们进行排序或检查结构的非法组合（例如同时具有 BA 和 BB）。

EDIT2：这是我引用的结构之一的示例架构（带有通用字段名称）。u8/16/32指的是整数类型，sz是C字符串，大写的名字是需要读取的字段，常量前加下划线。

DEF AA {
    // Identifies and deliminates complete records.
    TAG {
        u32 SYNC_CODE = 0xFFFFFFFF;
    }

    // Metadata for high level identification of data.
    A {
        u32 TYPE = __TYPE_A;
        u16 CATEGORY = __CATEGORY_1; // A defines the "category" of the following file data
        u32 NUM_OF_KV_PAIRS;
        for (int i = 0; i < NUM_OF_KV_PAIRS; ++i) { // unspecified metadata
            sz KEY;
            sz VALUE;
        }
        u8 HAS_EXTENSION_FLAG = true; // indicates presence of next record
        if (!HAS_EXTENSION_FLAG) {
            DEFAULT_PARAMS; // legacy
        }
    }

    // Indicates a specific data layout and version.
    AA {
        u32 TYPE = __TYPE_AA;
        u8[16] ACCESS_KEY;
        u32 NUM_OFFSETS;
        for (int i = 0; i < NUM_OFFSETS; ++i) {
            // stuff
        }
    }
}
4

2 回答 2

0

如果没有更具体的问题描述，很难回答某种方法在效率方面是否更好。您可以在下面找到一些值得深思的东西。

第 1 点：在考虑类设计时，还需要检查所需的行为而不仅仅是数据。用于存储的二进制格式可能暗示或不暗示层次结构这一事实当然应该考虑在内，但它不应该是主要关注点。

例如，假设我们有一个Person类有一个height字段和一个Rectangle类也有一个height字段。它们都共享一些数据，但只有这些信息使它们彼此无关。如果我们定义上下文并说我们想在屏幕上绘制它们，那么该height字段突然具有更具体的含义。现在继承 aDrawable可能更有意义。

您的问题是我们将如何使用它们？{A, B}如果我们有一个or{AA, BB}甚至的列表，我们可以做哪些常见的操作{A, BB}？我们能以某种方式一起管理它们吗？这是您应该考虑的重要一点。

第 2 点：您说“操作包含 A、包含 AA 等的结构是有意义的，但绝不仅仅是结构的 A 或 AA 部分”。所以我理解AA is-a A，但反之亦然。如果是这种情况，那么Base, A, B, C作为抽象类并且只能直接实例化最后一个级别AA, BB等是有意义的。

第3点：另一方面，如果不同的结构只定义一些数据而不是一些行为，那么使用组合而不是继承可能会更好。例如，我们会在它们上调用一个方法，就像process()对数据进行操作一样吗？还是我们想将结构本身用作数据？

class X {
    Base base;
    A a;
    AA aa;
    process() {
        // this is different than calling base.process() + a.process() + aa.process()
        // do we need one over the other? both?
        process(base) + process(a) + process(aa);
    }
}

第4点：关于读取时的实例化顺序，这应该不是问题。也许您可以在临时存储信息时读取信息，并且仅在您知道其完整类型后才实例化一个类（即您到达最后一级）。

我希望这会有所帮助

于 2013-07-27T07:46:38.900 回答
0

这个问题没有清楚地解释你认为你在做什么，或者实际问题是什么（即你应该做什么）。

您需要非常清楚地定义 A、AA、AB 中的哪些是具有自己独特存在的实体- 以及您应该解析的子关系在哪里。您说的是嵌套结构，但没有详细说明。

正如提到的另一个答案 - OO 是关于行为，而不是关于数据建模。

严重依赖继承，尤其是因为您不知道自己在构建什么，听起来这将是一个完全错误。通常，继承层次结构仅在您需要行为（计算或做事的方法）时才有用，并且可以通过某些类层次结构有效地划分该行为空间并从中受益。

如上所述，您的问题只是一个解析问题。您也可以使用 Stack 和一些内部状态（比如 StringBuilder，最简单的）来读取和构建解析状态，同时使用 Stack 推送和弹出嵌套级别。

事实上，上述方法是实现大多数类型的解析器的好方法。

一个更复杂的替代方案（在解析器中也很常见）是构建一个 AST。这些构建和遍历非常有效且重量轻。

class AstNode {
    protected AstNode down;     // first child.
    protected AstNode across;   // next sibling.

    public void addChild (AstNode child) {
        if (getDown() == null) {
            // First Child;
            this.down = child;
            return;
        }
       // Sibling to existing Children.
       AstNode last = down;
       while (last.getAcross() != null)
           last = last.getAcross();
       last.across = child;
       // done.
    }
}

使用 AST，您还可以为 NodeType、Data、Type（词法）等添加属性/成员，并有效地构建强大的数据结构。

希望这可以帮助。

于 2013-07-27T09:29:33.250 回答