5.8.1 识别器

自上而下的识别器遵循正则表达式的语法,总结如下:

图1

识别器保留了两个指针,一个在正则表达式中一个在输入中,并尝试同时移动两个指针:当有一个令牌匹配时,两个指针同时向前一步,但是如果simple_re必须重复一次时,正则表达式的指针要向后一步,且输入指针保持原位。当正则表达式指针指向正则表达式末尾时,识别器根据输入指针的移动距离来之策一个匹配项。

当识别器尝试识别compound_re时,首先会判断它是否是repeat_r。如果是的话,它会检测标记。如果标记是 +那表示必须要有simple_re,则识别器接下来会先查找simple_re,但如果simple_re是可选项(即标记为 *、? ),那么接下来的查找分为两条路:一条查找simple_re,另一条查找正则表达式的这个repeat_re之后的其余部分。当识别器完成一个repeat_re之后,接下来它会继续查找标记。如果是一个 ?,那么继续,但如果是 *或者 +,那么查找又分为两条路:一个跳回repeat_re的开头,一个继续搜索剩下的正则表达式。

如果识别器发现simple_re是一个令牌,会将这个令牌和输入指针的令牌进行比较。如果他们匹配,那么两个指针都向前移动;如果不匹配,那么搜索终止。

还有两个问题:我们如何实现搜索拆分,以及如何处理记录下来的匹配项。第一个问题,我们通过按顺序执行来实现搜索拆分:我们先执行完整的首次搜索直到结束或者失败,包括所有的子搜索;然后,无论结果如何我们都进行第二次搜索。这看起来有些麻烦,无论是编码还是效率,但实际上并不会。选项repeat_re的核心代码如下:

图1

其中rp和ip代表正则表达式指针和输入指针。该算法通常很高效,因为搜索几乎都是立马失败,因为两个令牌并不匹配。

记录的匹配项的处理取决于应用程序。如果我们想知道正则表达式是否匹配整个字符串,例如文件名匹配,我们就看看是否同时到达输入的结尾处,如果同时到达,那么直接返回成功;如果不是同时到达,那么就继续搜索。如果我们想要的是找到最长匹配项,那么我们就将每个匹配项的长度记录下来,然后进行搜索直到所有搜索都结束。

results matching ""

    No results matching ""