regex - 用于解析嵌套结构的正则表达式的对应部分

Question

正则表达式是用于解析多种语言的字符串的标准工具。但是，它们的适用范围受到限制。正则表达式只能匹配列表。无法使用正则表达式描述任意的深层嵌套结构。问题:什么是可以与树结构匹配(产生AST)的，被广泛使用/传播并且与常规实验一样标准的技术/框架。

Answer 1

正则表达式描述了有限状态自动机。

自1960年代后期以来，解析的“面包和黄油”(虽然不一定是“最新技术”)已经成为解析器生成器根据LALR(1)等“LR”算法生成的下推式自动机。

与正则表达式的联系是这样的:实际上，解析机确实使用与正则表达式非常相似的规则来识别可行的前缀。 “核心LR(0)项”之间的“移位”状态转变构成了有限的自动机，并且可以由正则表达式来描述。由于执行“移位”时将符号推入堆栈并删除它们(“减少”)的语义作用，可以处理递归。约简重写了堆栈的一部分，并执行“转到”到另一个状态。正则表达式自动机中不存在这种goto和堆栈。

语法分析语法也与正则表达式有关。正则表达式本身可以赋予递归。首先，我们可以接受一些正则表达式并为其命名，然后通过编写调用这些名称的表达式来构造更大的正则表达式。 (就像在lex工具中找到的功能一样，您可以在其中定义诸如letters [A-Za-z]+之类的命名表达式，以后再将其称为{letters}。现在假设您允许使用循环引用，例如letters [A-Za-z]{letters}?。您现在具有递归；唯一的问题是调整模型为了实现它。

实际上，各种现代语言和环境中所谓的“正则表达式”的实现都支持递归。例如，Perl兼容的正则表达式(PCRE)支持它。

经典NFA编译路径(可能转换为DFA)不处理具有递归或后向引用功能的表达式；他们不可能。

上面的letters递归如何处理与实际的递归有关。 ?运算符可以实现为尝试匹配其各自参数对象的函数。如果成功，那么它将消耗与其匹配的任何东西，否则将不消耗任何东西。也就是说，正则表达式可以转换为语法树，并按“原样”进行解释，而不是编译为状态机(或琐碎地编译为与树的节点相对应的函数)，并且这种解释自然可以处理递归。然后，该解释有效地构成了语法指导的递归下降解析器。 (请注意，在定义letters以使该示例与此方法兼容时，如何避免左递归)。

示例:括号匹配的正则表达式:

par-match := ({par-match})|

这被编译成树:

              branch-op    <-- "par-match" name points at this node
               /   \  
    catenate-op     <empty>
     /      \ 
   "("       catenate-op
             /          \        
          {par-match}    ")"

然后可以将其转换为递归下降解析器，或直接进行解释。

模式匹配从调用顶级“branch-op”开始。该运算符只是尝试所有替代方法。假设输入为空。然后，左选择将失败:它需要一个开放的括号。因此，正确的选择将会成功:空匹配为空。 (操作员“失败”或指示“成功”并消耗输入。)

但是，假设您输入的是 (())。左侧 catenate-op将依次调用其左侧子树，该子树匹配并使用左侧括号，剩下 ())。然后它将调用其右子树另一个 catenate-op。此 catenate-op匹配其左子树，后者通过命名的 par-match引用触发递归到顶层。该递归将匹配并使用 ()，而保留 )。然后， catenate-op调用与 )匹配的右子树。控件最多返回 branch-op。 (尽管 branch-op的左侧与某项匹配，但 branch-op仍必须尝试另一种选择；一个以上的分支可以匹配，某些分支可以比其他分支更长。)

这与 Parsing Expression Grammars工作密切相关。

实际上，可以将递归定义以某种方式编码为regex语法。假设我们发明了一些新的运算符，例如 (?name:definition)，这意味着“匹配 definition可以通过 name包含其自身的调用。调用语法可以是 (*name)，因此我们可以将 par-match的示例写为 (?par-match:\((*par-match)\)|)。 (?和 (*的组合在下面无效“经典”正则表达式语法，因此我们可以使用它们进行扩展。

最后一点，正则表达式对应于语法。这是正则表达式与解析之间的基本连接。也就是说，正则表达式对应于仅描述常规语言的特定语法子集。描述常规语言的语法示例:

S -> A | B
B -> b
A -> A a | c

尽管存在 A -> A ...递归，但这仍然是常规的，并且对应于regex ac*|b，这只是表示相同语言的一种更紧凑的方式。语法使我们可以标注非常规的语言，并且无法为其编写正则表达式，但是正如我们所看到的，我们可以扩展正则表达式的符号和语义来表达其中的某些内容。正则表达式与语法不是分开的。两者不是对应的，而是一个是特殊情况或另一个的子集。