构建可组合的有向图（扫描仪生成器的 Thompson 构造算法）

Question

我目前正在编写一个基于 Thompson's construction algorithm 的扫描仪生成器，以将正则表达式转换为 NFA。基本上，我需要解析一个表达式并从中创建一个有向图。我通常将我的有向图存储为邻接表，但这次，我需要能够非常有效地将现有有向图组合成一个新的有向图。我不能每次读到一个新字符时都复制我的邻接表。

我正在考虑创建一个非常轻量级的 NFA 结构，它不会拥有自己的 nodes/states。

struct Transition {
  State* next_state;
  char transition_symbol;
};

struct State {
  std::vector<Transition> transitions;
};

struct NFA {
  State* start_state;
  State* accepting_state;
};

这样我就可以简单地重新分配指针来创建新的 NFA。我的所有状态都将存储在一个中央位置（NFABuilder？）。组合将通过外部函数完成，如下所示：

NFA create_trivial_nfa(char symbol) {
  State* start_state = new State();
  State* accepting_state = new State();
  start_state->transitions.emplace_back(accepting_state, symbol);
  // Something must own start_state and accepting_state
  return NFA{start_state, accepting_state};
}

NFA concatenate_nfas(NFA&& nfa0, NFA&& nfa1) {
  nfa0.accepting_state->transitions.emplace_back(nfa1.start_state, '[=11=]');
  return NFA{nfa0.start_state, nfa1.accepting_state};
}

在这里，我将使用移动语义来明确 nfa0 和 nfa1 不再用作独立的 NFA（因为我修改了它们的内部状态）。

这种方法是否有意义，或者是否存在我尚未预料到的问题？如果确实有意义，那么所有这些状态的所有者应该是什么？我还预计我的过渡会出现填充问题。当打包在向量中时，Transition 的大小为 16 个字节而不是 9 个（在 64 位架构上）。这是我应该担心的事情，还是只是宏伟计划中的噪音？（这是我的第一个编译器。我正在关注 Engineering a Compiler, by Cooper & Torczon）

Answer 1

Thompson构造的本质在于它创建了一个具有以下特征的NFA：

最多有2|R|个状态，其中|R|是正则表达式的长度。
每个状态要么恰好有一个标有字符的 out 转换，要么最多有两个 ε 转换。（也就是说，没有状态同时具有标记转换和 ε 转换。）

后一个事实表明将状态表示为

struct State {
  std::vector<std::tuple<char, State*>> transitions;
}

（这是您的代码的略微缩写）是一种非常高的开销表示，其中开销与 std::vector 的开销有很大关系，该 std::vector 用于恰好保持一个或两个转换单个过渡的填充。此外，上述表示没有提供表示 ε 转换的明确技术，除非打算为 ε 保留一个字符代码（因此无法在正则表达式中使用该字符代码）。

更实际的表示可能是

enum class StateType { EPSILON, IMPORTANT };
struct State {
  StateType type;
  char      label;
  State*    next[2];
};

（假设我们可以使用标记值来指示 next[1] 不适用，该公式不会将转换数存储在 next 中。或者，我们可以在这种情况下只需设置 next[1] = next[0];。记住它只对 ε 状态有影响。）

此外，由于我们知道 NFA 中不超过 2|R| State 个对象，我们可以用小整数替换 State* 指针。这将对可以处理的正则表达式的大小设置某种限制，但是遇到千兆字节的正则表达式是非常罕见的。使用连续的整数而不是指针也会使某些图算法更易于管理，特别是对子集构造至关重要的传递闭包算法。

关于 Thompson 算法构建的 NFA 的另一个有趣的事实是，States 的入度也被限制为 2（同样，如果有两个 in-transitions，两者都是 ε transitions）。这使我们能够避免过早地创建子机的最终状态（如果子机是连接的左侧参数，则不需要）。相反，我们可以只用三个索引来表示子机：起始状态的索引，以及最多两个内部状态的索引，一旦添加，就会转换到最终状态。

我认为以上内容与 Thompson 的原始实现相当接近，尽管我确信他使用了更多的优化技巧。但值得一读 Aho、Lam、Sethi 和 Ullman ("Dragon Book") 的第 3.9 节，它描述了优化状态机构造的方法。

独立于理论归约，值得注意的是，除了关键字模式的 trie 之外，词法分析中的大多数状态转换都涉及字符集而不是单个字符，而且这些字符集通常非常大，特别是如果词法分析的单位是 Unicode 代码点而不是 ascii 字符。使用字符集而不是字符确实会使子集构建算法复杂化，但通常会显着减少状态计数。

构建可组合的有向图（扫描仪生成器的 Thompson 构造算法）

Building composable directed graphs (Thompson's construction algorithm for scanner generator)

c++

compiler-construction

graph

directed-graph

lexer