Производительность токенизации CSS в PHP - PullRequest
Новая
       74

Производительность токенизации CSS в PHP

4 голосов
/ 09 апреля 2010

Это вопрос новичка от того, кто никогда раньше не писал парсер / лексер.

Я пишу токенайзер / парсер для CSS в PHP (пожалуйста, не повторяйте «OMG, почему в PHP?»). Синтаксис записан W3C аккуратно здесь (CSS2.1) и здесь (CSS3, черновик) .

Это список из 21 возможных токенов, все (кроме двух) не могут быть представлены в виде статических строк.

Мой текущий подход состоит в том, чтобы циклически перебирать массив, содержащий 21 шаблон, делать if (preg_match()) и уменьшать совпадение исходной строки на соответствие. В принципе это работает действительно хорошо. Однако для строки CSS из 1000 строк это занимает от 2 до 8 секунд, что слишком много для моего проекта.

Теперь я ломаю голову над тем, как другие парсеры токенизируют и , анализируют CSS за доли секунды. Хорошо, C всегда всегда быстрее, чем PHP, но, тем не менее, есть ли очевидные D'Oh! s, в которые я попал?

Я произвел некоторые оптимизации, например, проверил '@', '#' или '"' в качестве первого символа оставшейся строки и затем применил только соответствующее регулярное выражение, но это не принесло существенного повышения производительности.

Мой код (фрагмент) пока: 

$TOKENS = array(
  'IDENT' => '...regexp...',
  'ATKEYWORD' => '@...regexp...',
  'String' => '"...regexp..."|\'...regexp...\'',
  //...
);

$string = '...CSS source string...';
$stream = array();

// we reduce $string token by token
while ($string != '') {
    $string = ltrim($string, " \t\r\n\f"); // unconsumed whitespace at the
        // start is insignificant but doing a trim reduces exec time by 25%
    $matches = array();
    // loop through all possible tokens
    foreach ($TOKENS as $t => $p) {
        // The '&' is used as delimiter, because it isn't used anywhere in
        // the token regexps
        if (preg_match('&^'.$p.'&Su', $string, $matches)) {
            $stream[] = array($t, $matches[0]);
            $string = substr($string, strlen($matches[0]));
            // Yay! We found one that matches!
            continue 2;
        }
    }
    // if we come here, we have a syntax error and handle it somehow
}

// result: an array $stream consisting of arrays with
// 0 => type of token
// 1 => token content

Ответы [ 5 ]

3 голосов
/ 10 апреля 2010

Используйте генератор лексера .

0 голосов
/ 15 сентября 2013

Это старый пост, но он все еще приносит мои 2 цента. единственное, что серьезно тормозит оригинальный код в вопросе, это следующая строка: 

$string = substr($string, strlen($matches[0]));

вместо того, чтобы работать со всей строкой, возьмите только ее часть (скажем, 50 символов), которой достаточно для всех возможных регулярных выражений. затем примените к нему ту же строку кода. когда эта строка уменьшается до заданной длины, загрузите в нее еще несколько данных.

0 голосов
/ 11 апреля 2010

Не используйте регулярные выражения, сканируйте символ за символом. 

$tokens = array();
$string = "...code...";
$length = strlen($string);
$i = 0;
while ($i < $length) {
  $buf = '';
  $char = $string[$i];
  if ($char <= ord('Z') && $char >= ord('A') || $char >= ord('a') && $char <= ord('z') || $char == ord('_') || $char == ord('-')) {
    while ($char <= ord('Z') && $char >= ord('A') || $char >= ord('a') && $char <= ord('z') || $char == ord('_') || $char == ord('-')) {
      // identifier
      $buf .= $char;
      $char = $string[$i]; $i ++;
    }
    $tokens[] = array('IDENT', $buf);
  } else if (......) {
    // ......
  }
}

Однако это делает код не поддерживаемым, поэтому генератор синтаксического анализатора лучше.

0 голосов
/ 10 апреля 2010

(возможно) более быстрый (но менее дружественный к памяти) подход состоял бы в том, чтобы токенизировать весь поток сразу, используя одно большое регулярное выражение с альтернативами для каждого токена, например 

 preg_match_all('/
       (...string...)
       |
       (@ident)
       |
       (#ident)
       ...etc
   /x', $stream, $tokens);

 foreach($tokens as $token)...parse
0 голосов
/ 09 апреля 2010

Первое, что я хотел бы сделать, это избавиться от preg_match(). Основные строковые функции, такие как strpos(), намного быстрее, но я не думаю, что вам это даже нужно. Похоже, что вы ищете конкретный токен в начале строки с preg_match(), а затем просто берете переднюю длину этой строки в качестве подстроки. Вы можете легко сделать это с помощью простого substr(), например: 

foreach ($TOKENS as $t => $p)
{
    $front = substr($string,0,strlen($p));
    $len = strlen($p);  //this could be pre-stored in $TOKENS
    if ($front == $p) {
        $stream[] = array($t, $string);
        $string = substr($string, $len);
        // Yay! We found one that matches!
        continue 2;
    }
}

Вы можете дополнительно оптимизировать это, предварительно рассчитав длину всех ваших токенов и сохранив их в массиве $TOKENS, чтобы вам не приходилось постоянно вызывать strlen(). Если бы вы отсортировали $TOKENS по группам по длине, вы могли бы также уменьшить количество вызовов substr() еще больше, поскольку вы можете взять substr($string) текущей анализируемой строки только один раз для каждой длины токена и пройти через все токены этой длины, прежде чем перейти к следующей группе токенов.

...