c - 正则表达式如何翻译成汇编？

Question

我了解到 C 被翻译成汇编，然后汇编被翻译成机器代码。我还学会了如何将基本的 C 结构（如指针和循环）转换为 32 位 MIPS 程序集。但是我没有学习如何将 C 中的正则表达式翻译成程序集，有秘诀吗？

Answer 1

C 不支持正则表达式。组装也不行。您必须编写一些用于模式匹配的算法代码，然后，如果它还没有在汇编/机器代码中，则将其翻译/编译成它。没有魔法。

Answer 2

几十年前，将正则表达式翻译成汇编语言似乎已经过时了。相反，如今它们通常被编译为确定性有限自动机 (DFA)，通常带有一个中间步骤作为非确定性有限自动机 (NFA)。如果您不熟悉这些术语，请参阅：

• http://en.wikipedia.org/wiki/Deterministic_finite_automaton
• http://en.wikipedia.org/wiki/Nondeterministic_finite_automaton

对应于正则表达式的 NFA 很容易构建；只需将正则表达式中的每个点视为一个状态，以及可以匹配并将您移动到正则表达式中的下一个点的字符集，作为从该状态到下一个状态的转换。

其他流行的正则表达式引擎，包括 PCRE，根本不编译正则表达式，而是使用回溯匹配器，这很容易编写，但内存使用非常糟糕（许多递归调用帧，如果作为实际函数实现，则会导致堆栈溢出调用）和病态糟糕的大 O 性能（可能是指数时间）。

Answer 3

通常，这取决于您如何实现正则表达式。例如，您可以：

• 使用 PCRE 或 POSIX 正则表达式之类的东西。在这种情况下，通过使用特定于您的体系结构/ABI 的调用约定进行正确调用，对该 API 的函数调用被简单地转换为机器（汇编）代码。
• 使用类似的工具flex。在这种情况下，该工具将生成大量 C 代码，通常以表格和状态机的形式，并且这些代码将使用编译器进行翻译。

如果你实现某种特殊的正则表达式解析方案，它就是编译器为你的代码生成的任何东西。