5.8.2 评价

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

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

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

results matching ""

    No results matching ""