Blog by nikic. Find me on GitHub, StackOverflow and Twitter. Learn more about me.
« Back to article overview.

Improving lexing performance in PHP

Lexing isn’t something you would normally do in PHP, simply because other languages like C can easily outperform PHP by several orders of magnitude. Still it sometimes is desirable to write lexers in PHP, e.g. for tokenizing templates, doccomments and other DSLs. So I want to share some thoughts on how to write fast lexers in PHP.

Lexing CSV files

PHP already provides functions for parsing CSV files and strings. I will use CSV lexing as an example anyways, simply because it’s so simple. Here an example of a CSV line (as PHP implements it):

Field,Another Field,"comma -> , <- comma","quote -> \" <- quote"

If we define the tokens in terms of regular expressions, they would look roughly like this:

$tokenMap = array(
    '~[^",\r\n]+~A'                     => T_PLAIN_FIELD,
    '~"[^"\\\\]*(?:\\\\.[^"\\\\]*)*"~A' => T_QUOTED_FIELD,
    '~,~A'                              => T_FIELD_SEPARATOR,
    '~\r\n?|\n~A'                       => T_LINE_SEPARATOR,
);

Looping through the regexes

The most obvious approach to lexing in PHP is to simply loop through the regexes and match them against the current position, until there are no characters left:

function lex($string, array $tokenMap) {
    $tokens = array();

    $offset = 0; // current offset in string
    while (isset($string[$offset])) { // loop as long as we aren't at the end of the string
        foreach ($tokenMap as $regex => $token) {
            if (preg_match($regex, $string, $matches, null, $offset)) {
                $tokens[] = array(
                    $token,      // token ID      (e.g. T_FIELD_SEPARATOR)
                    $matches[0], // token content (e.g. ,)
                );
                $offset += strlen($matches[0]);
                continue 2; // continue the outer while loop
            }
        }

        throw new LexingException(sprintf('Unexpected character "%s"', $string[$offset]));
    }

    return $tokens;
}

The drawback of this code is fairly obvious: On every new offset one needs to iterate through all regexes and match them one at the time. This maybe isn’t such a problem in this case as we only have four regexes, but when lexing some real language one usually deals with hundreds of them.

Compiling into a single regex

The solution is to compile all regexes into a single big one. Our above regex would be converted to:

$regex = '~
    ([^",\r\n]+)
  | ("[^"\\\\]*(?:\\\\.[^"\\\\]*)*")
  | (,)
  | (\r\n?|\n)
~xA';

But how can we use this? How can we know which of the four subregexes matched the string? Simple: As all the subregexes are enclosed in parenthesis they are capturing groups. So our $matches array will contain the matched string at position [0] and at the position of the matched subregex. All other groups will be empty.

An example: If the regex matched the , subregex, we would get this $matches array:

array(
    0 => ',',
    1 => '',
    2 => '',
    3 => ',',
    4 => '',
);

From this we know that the 3rd subregex matched, as it is the one which has a value.

The resulting code for an abstract lexer class would be:

class Lexer {
    protected $regex;
    protected $offsetToToken;

    public function __construct(array $tokenMap) {
        $this->regex = '((' . implode(')|(', array_keys($tokenMap)) . '))A';
        $this->offsetToToken = array_values($tokenMap);
    }

    public function lex($string) {
        $tokens = array();

        $offset = 0;
        while (isset($string[$offset])) {
            if (!preg_match($this->regex, $string, $matches, null, $offset)) {
                throw new LexingException(sprintf('Unexpected character "%s"', $string[$offset]));
            }

            // find the first non-empty element (but skipping $matches[0]) using a quick for loop
            for ($i = 1; '' === $matches[$i]; ++$i);

            $tokens[] = array($matches[0], $this->offsetToToken[$i - 1]);

            $offset += strlen($matches[0]);
        }

        return $tokens;
    }
}

How much does this really change?

I am seeing approximately 30% performance improvement for the average case (online demo). But this value varies with different regexes and input. If the number of regexes increases the performance improvement is bigger. Additionally in the compiled-regex variant the order of the regexed has less influence on the execution time (online demo). I.e. it is not that important to put the more probable regexes first and the less probable ones last. (But it still is important, only less important!)