Немного о лексическом анализе04.01.2019 04:19

Давным-давно, когда небо было голубым, трава зеленее и по Земле бродили динозавры… Нет, забудьте про динозавров. Ну, в общем, когда-то тогда пришла в голову мысль отвлечься от стандартного web-программирования и заняться чем-то более безумным. Можно было, конечно, чем угодно, но выбор пал на написание своего интерпретатора. Что я могу сказать… Никогда не пишите свои языки программирования. Но некоторый опыт из всего этого я извлёк, так что вот и решил поделиться. Начнём с самой основы — лексера.

Предисловие

Перед тем, как начать понимать что за животное такое «лексер» — стоит разобраться из чего вообще состоят ЯП.

В современном мире каждый компилятор/интерпретатор/транспайлер/что-то-там-ещё-подобное (давайте, я просто буду называть далее это «компилятором», без разграничений на типы) делится на два куска. В терминологии умных дядек подобные куски называются «фронтендом» и «бекендом». Нет, это совсем не то, работая с web, что мы привыкли называть и фронт не написан на JS с HTML. Хотя… Ладно.

Задача первого, фронтенда — взять текст и превратить его в AST (абстрактное синтаксическое дерево), по дороге проверив правильность синтаксиса (и иногда семантики). Задача второго, бекенда — заставить всё это работать. Если код собирается внутри интерпретатора, то из AST создаётся набор команд для виртуального процессора (виртуальной машины), если компилятор, то набор команд для реального процессора. В жизни всё довольно сложнее и реализовываться может не совсем так. Например, в случае с GCC компилятором — там всё вперемешку, а вот Clang уже более каноничен, LLVM — это типичный представитель «бекенда» для компиляторов.

А теперь давайте познакомимся с куском, называемым «фронтендом».

Лексический анализ

Задача лексера и стадии лексического анализа — это получить на вход много-много букв и сгруппировать их по каким-то категориям — «токенам». По этому лексический анализ ещё называют «токенизацией». Это самая первая стадия обработки текста, которую производит каждый существующий компилятор.

Примерно вот так:

$tokens = ['class', '\w+', '}', '{'];

var_dump(lex('class Example {}', $tokens));
// array(4) {
//  [0] => string(5) "class"
//  [1] => string(7) "Example"
//  [2] => string(1) "{"
//  [3] => string(1) "}"
// }

К слову, тут у нас уже понаписана куча инструментов для облегчения жизни. Те же самые функции preg, которые мы привыкли использовать для парсинга текста — вполне себе справляется с данной задачей. Однако существуют и более удобные инструменты для этого дела:

— Phlexy, написанный Никитой Поповым.
— Hoa — инструментарий, состоящий из Лексера + Парсера + Грамматики.
— Порт Yacc, написанный Энтони Феррара, который так же представляет из себя комплексный инструментарий, и на котором написан небезызвестный PHP парсер Попова, применимый в инструментах, использующих анализ кода.
— Railt Lexer моя реализация под PHP 7.1+
— Parle — расширение для PHP, допускающее ограниченный набор PCRE выражений (нет lookahead и некоторых других синтаксических конструкций).
— Ну и наконец стандартная функция php token_get_all, которая предназначена непосредственно для лексического анализа PHP.

Ладно, понятно что штуковин, которые умеют делить текст по токенам — уйма, возможно я даже что-то забыл, вроде лексера Doctrine. Но что дальше?

Типы лексеров

И как всегда всё не так просто, как казалось. Существует как минимум две разных категории лексеров. Есть обычный вариант, довольно тривиальный, которому подсовываешь правила, а он уже делит всё на токены. Конфигурация оного мало чем отличается от примера, показанного мною выше. Однако есть и другой вариант, который называется multistate. Такие лексеры чуть сложнее для понимания, поэтому, хочется поговорить о них чуть подробнее.

Задача multistate лексера выводить различные токены в зависимости от предыдущего состояния. Ну например в PHP такие «переходные» состояния образовываются с помощью тегов , внутри строк, комментариев и HEREDOC/NOWDOC конструкций.

Помните предыдущий пример с 4 мя токенами выше? Давайте его чуть-чуть модифицируем, чтобы понимать что это за состояния такие:

class Example 
{
    // class Example {}
}

В данном случае, если мы имеем простейший лексер без широких возможностей PCRE, то получим следующий набор токенов:

var_dump(lex(...));

// array(9) {
//  [0] => string(5) "class"
//  [1] => string(7) "Example"
//  [2] => string(1) "{"
//  [3] => string(2) "//"
//  [4] => string(5) "class"
//  [5] => string(7) "Example"
//  [6] => string(1) "{"
//  [7] => string(1) "}"
//  [8] => string(1) "}"
//}

Как видно, мы получили совершенно банальный косяк на элементах 3–5: Комментарий воспринялся совершенно неожиданно и сам поделился на токены, хотя должен был считаться как цельный кусок.

Конечно, при наличии функционала PCRE такой токен можно было бы выдрать с помощью простенькой регулярки »//[^\n]*\n», но если его нет? Ну или мы руками хотим запилить? Короче, в случае с multistate лексером — можно сказать, что все токены должны быть в группе No1, как только будет найден токен »//», то должен произойти переход в группу No2. А внутри второй группы обратный переход, если найден токен »\n» — переход обратно в первую группу.

Примерно как-то так:

$tokens = [
    'group-1' => [
        'class',
        '\w+',
        '{',
        '}',
        '//' => 'group-2' // Переход после слешей в группу 2
    ],
    'group-2' => [
        "\n" => 'group-1', // Переход в группу 1 после переноса строки
        '.*'
    ]
];

Думаю теперь становится понятнее как парсится какой-нибудь HEREDOC, ведь даже при наличии всей мощи PCRE написать регулярку для этого дела крайне проблематично, учитывая то, что этот синтаксис HEREDOC поддерживает интерполяцию переменных. Просто попробуйте распарсить что-нибудь такое с помощью встроенной функции token_get_all (обратите внимание на >12 токен):

     */
    private $tokens = [];

    /**
     * @param array $tokens
     */
    public function __construct(array $tokens)
    {
        foreach ($tokens as $name => $definition) {
            $this->tokens[$name] = \sprintf('/\G%s/isSum', $definition);
        }
    }

    /**
     * @param string $sources
     * @return iterable&\Traversable
     * @throws RuntimeException
     */
    public function lex(string $sources): iterable
    {
        [$offset, $length] = [0, \strlen($sources)];

        while ($offset < $length) {
            [$name, $token] = $this->next($sources, $offset);

            yield $name => $token;

            $offset += \strlen($token);
        }
    }

    /**
     * @param string $sources
     * @param int $offset
     * @return array
     * @throws RuntimeException
     */
    private function next(string $sources, int $offset): array
    {
        foreach ($this->tokens as $name => $pcre) {
            \preg_match($pcre, $sources, $matches, 0, $offset);

            $token = \reset($matches);

            if (\count($matches) && \strpos($sources, $token, $offset) === $offset) {
                return [$name, $token];
            }
        }

        throw new \RuntimeException('Unrecognized token at offset ' . $offset);
    }
}

$lexer = new SimpleLexer([
    'T_CLASS'       => 'class',
    'T_CONST'       => '\w+',
    'T_BRACE_OPEN'  => '{',
    'T_BRACE_CLOSE' => '}',
    'T_WHITESPACE'  => '\s+',
]);

echo \sprintf('| %-10s | %-20s |', 'VALUE', 'NAME') . "\n";
foreach ($lexer->lex('class Example {}') as $name => $token) {
    echo \sprintf('| %-10s | %-20s |', '"' . \trim($token, "\n") . '"', $name) . "\n";
}

class PregReplaceLexer
{
    /**
     * @var array
     */
    private $tokens = [];

    /**
     * @param array $tokens
     */
    public function __construct(array $tokens)
    {
        foreach ($tokens as $name => $definition) {
            $this->tokens[] = \sprintf('(?<%s>%s)', $name, $definition);
        }
    }

    /**
     * @param string $sources
     * @return iterable&\Traversable
     */
    public function lex(string $sources): iterable
    {
        $result = [];

        \preg_replace_callback($this->compilePcre(), function (array $matches) use (&$result) {
            foreach (\array_reverse($matches) as $name => $value) {
                if (\is_string($name) && $value !== '') {
                    $result[] = [$name, $value];
                    break;
                }
            }
        }, $sources);

        foreach ($result as [$name, $value]) {
            yield $name => $value;
        }
    }

    /**
     * @return string
     */
    private function compilePcre(): string
    {
        return \sprintf('/\G(?:%s)/isSum', \implode('|', $this->tokens));
    }
}