正则表达式词法分析器性能剖析

Question

正则表达式词法分析器性能剖析

4

我在PHP中创建了一个路由器，它采用基于Rails 3路由的DSL，并将其转换为正则表达式。它具有可选段（由（嵌套）括号表示）。以下是当前的词法分析算法：

private function tokenize($pattern)
{
    $rules = array(
        self::OPEN_PAREN_TYPE  => '/^(\()/',
        self::CLOSE_PAREN_TYPE => '/^(\))/',
        self::VARIABLE_TYPE    => '/^:([a-z0-9_]+)/',
        self::TEXT_TYPE        => '/^([^:()]+)/',
    );

    $cursor = 0;
    $tokens = array();
    $buffer = $pattern;
    $buflen = strlen($buffer);

    while ($cursor < $buflen)
    {
        $chunk = substr($buffer, $cursor);

        $matched = false;
        foreach ($rules as $type => $rule)
        {
            if (preg_match($rule, $chunk, $matches))
            {
                $tokens[] = array(
                    'type'  => $type,
                    'value' => $matches[1],
                );

                $matched = true;
                $cursor += strlen($matches[0]);
            }
        }

        if (!$matched)
        {
            throw new \Exception(sprintf('Problem parsing route "%s" at char "%d".', $pattern, $cursor));
        }
    }

    return $tokens;
}

有没有明显的加速方法我没想到的？有没有放弃preg_*或将正则表达式合并成一个模式等方法？这里是xhprof调用图（基准测试使用约2500个唯一路由）：我知道最好的解决方案是不要为每个请求调用它（我计划使用APC缓存等），但希望尽可能地提高对未启用APC的用户使用此库的效率。编辑：我还编写了一个快速状态机版本，似乎表现更好。我仍然愿意听取任何建议，因为我认为第一段代码更优雅。

private function tokenize2($pattern)
{
    $buffer = '';
    $invariable = false;

    $tokens = array();
    foreach (str_split($pattern) as $char)
    {
        switch ($char)
        {
            case '(':
                if ($buffer)
                {
                    $tokens[] = array(
                        'type'  => $invariable ? self::VARIABLE_TYPE : self::TEXT_TYPE,
                        'value' => $buffer,
                    );
                    $buffer = '';
                    $invariable = false;
                }

                $tokens[] = array(
                    'type' => self::OPEN_PAREN_TYPE,
                );
                break;
            case ')':
                if ($buffer)
                {
                    $tokens[] = array(
                        'type'  => $invariable ? self::VARIABLE_TYPE : self::TEXT_TYPE,
                        'value' => $buffer,
                    );
                    $buffer = '';
                    $invariable = false;
                }

                $tokens[] = array(
                    'type' => self::CLOSE_PAREN_TYPE,
                );
                break;
            case ':':
                if ($buffer)
                {
                    $tokens[] = array(
                        'type'  => $invariable ? self::VARIABLE_TYPE : self::TEXT_TYPE,
                        'value' => $buffer,
                    );
                    $buffer = '';
                    $invariable = false;
                }

                $invariable = true;
                break;
            default:
                if ($invariable && !(ctype_alnum($char) || '_' == $char ))
                {
                    $invariable = false;
                    $tokens[] = array(
                        'type'  => self::VARIABLE_TYPE,
                        'value' => $buffer,
                    );

                    $buffer = '';
                    $invariable = false;
                }

                $buffer .= $char;
                break;
        }
    }

    if ($buffer)
    {
        $tokens[] = array(
        'type'  => $invariable ? self::VARIABLE_TYPE : self::TEXT_TYPE,
        'value' => $buffer,
        );
        $buffer = '';
    }

    return $tokens;

调用图

出于性能考虑，我最终选择使用状态机，并通过APC缓存整个词法分析过程（因为...为什么不呢）。

如果有人有什么贡献，我很乐意移到答案中。

- efritz

我理解的图表是每个测试路由需要大约3ms，是这样吗？ - mellamokb

@mellamokb 我相信那是正确的。 - efritz

1个回答

网页内容由stack overflow 提供, 点击上面的

可以查看英文原文，
原文链接

- preinheimer · Accepted Answer

有趣的代码 :).

我不太确定你在使用"使用APC缓存整个词法分析过程"这个说法时想表达什么，所以我可能会建议你已经在做的事情。

你能否只缓存输入URL和实际词法分析过程上面的结果？你似乎没有应用基于权限的限制，因此缓存是全局的。即使在大型网站上，路由也往往数量有限，只有几个非常热门的地方。完全绕过词法分析并在任何先前使用过的路由上命中缓存。