5.8.2 评价

自顶向下正则表达式的优点是显而易见的：该算法很容易用编程实现，并且几乎不涉及正则表达式的预处理，具体取决于结构线程（例如after_subexpression()）的实现。其他优势不那么明白可见。例如，这个技术允许命名正则表达式的一部分，并检查其在输入中其他位置的重复状态；这是个让人惊喜的强大功能。举个简单的例子，(.* )=x\x模式表示：匹配输入中的任意段，标记为x，然后用已经识别的x去匹配输入的其余所有内容；\x称为反向引用（backreference）。（另一个更有用但也更不明显的有点是，对于相同的正则表达式 (. )\1*，其中 \1表示：匹配包含在 **（**和 **）**中的第一个子表达式。）

面对输入abab，识别器将x的值设为ε, a, ab, aba和abab，然后尝试将每种情况下的尾部于x的当前值进行匹配。仅当x=ε和x=ab时能成功，并且只在最后一种情况时才识别整个输入。因此，上述表达式识别由两个相同部分组成的所有字符串的语言：ww，其中w是给定字母表上的任意字符串。由于这是一种上下文相关语言，我们惊奇的看到，跳过整个2型语言，那么具有反向引用的3型正则表达式识别出了一个1型语言！广泛使用这个属性的系统是§-微积分（§-calculus）（Jackson [285, 291]），这个将在第15.8.3节进一步论述。

自顶向下正则表达式的主要缺点就是时间需求。虽然它们通常是具有非常小的乘积常量的线性存在，但有时候这个乘积常量也可以大的可怕。*O(n^k)时间复杂度出现在类似a ^*a ^*...a （*a 重复k次）的模式中，所以原则上时间复杂度可以是输入长度的任意多项式，但是通常不会比指数式更差。在本书中查找于表达式 *. )**匹配的所有10000行耗时36秒；而找到匹配 **)**的11000行的耗时就无法计算了。