Главная » Хабрахабр » Немного о лексическом анализе

Немного о лексическом анализе

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

Предисловие

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

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

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

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

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

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

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

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

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

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

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

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

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

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

Давайте его чуть-чуть модифицируем, чтобы понимать что это за состояния такие: Помните предыдущий пример с 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", но если его нет? А внутри второй группы обратный переход, если найден токен "\n" — переход обратно в первую группу. Короче, в случае с multistate лексером — можно сказать, что все токены должны быть в группе No1, как только будет найден токен "//", то должен произойти переход в группу No2.

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

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

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

<?php
$example = 42;
$a = <<<EOL Your answer is $example !!!
EOL; var_dump(token_get_all(file_get_contents(__FILE__)));

Ладно, кажется мы уже готовы приступать к практике.

Практика

Давайте вспомним что у нас есть в PHP для подобных дел? Ну конечно, preg_match! Ладно, сойдёт. Алгоритм на основе preg_match реализован в Hoa и вот в этой реализации Phelxy. Задача его довольно проста:

1) Имеем на руках исходный текст и массив из регулярок.
2) Матчим до тех пор, пока что-то не найдётся подходящее.
3) Как только нашли кусок, вырезаем его из текста и матчим дальше.

В виде кода он будет выглядеть примерно так:

Кодопростыня

<?php
class SimpleLexer
{ /** * @var array<string> */ private $tokens = []; /** * @param array<string> $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<string> * @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<string,string> * @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";
}

В районе $this->tokens достаточно добавить что-то вроде $this->tokens[$this->state]. Такой подход довольно тривиален и позволяет парой тычков по клавиатуре модифицировать лексер в районе метода next(), добавив переход между состояниями и превратив это поделие рукоблудства в примитивный multistate лексер.

На i7 7600k, обладателем которого я по чистой случайности оказался — подобный алгоритм обрабатывает примерно 400 токенов в секунду, а при увеличении их вариаций (т.е. Однако, помимо самого примитивизма есть ещё один недостаток, не фатальный как могло оказаться, но всё же… Подобная реализация невероятно медленно работает. Я хотел сказать, конечно, что будет работать очень медленно. определений, которые мы передали в конструктор) — может замедлиться до скорости смены президентов в РФ… кхм, простите.

Для начала можно понять что же идёт не так. Ладно, что мы можем сделать? 3 уже PCRE2). Дело в том, что каждый раз, когда мы вызываем preg_match внутри дебрей языка поднимается компилятор со своим JIT, называемый PCRE (А с PHP 7. Звучит чуть-чуть странно и тавтологично. Он каждый раз парсит сами регулярки и собирает для них парсер, с помощью которого мы парсим текст для создания токенов. При этом, стоит заметить, что даже применённый флаг "S" и оптимизация с помощью "\G" в конструкторе, где формируются регулярные выражения для токенов, не помогают. Но если кратко, то каждый токен требует компиляции от 1 до N регулярок, где N — это количество определений этих токенов.

с помощью выполнения лишь одной функции preg_match. Выход из этой ситуации напрашивается один — надо парсить весь этот текст в один проход, т.е. Осталось решить две проблемы:

Т.е. 1) Как обозначить что результат регулярного выражения N1 соответствует токену N2? Как известно, результат preg_match или preg_match_all будет содержать всё вперемешку. как обозначить, что "\w+", например — это именно T_CONST.
2) Как определить последовательность токенов в результате. И даже с помощью флагов, передаваемых в качестве четвёртого аргумента ситуация не изменится.

Ну или нет. Тут можно сделать паузу и чуть-чуть подумать.

С помощью правил: "(?<T_WHITESPACE>\s+|<T_WORD>\w+|...)" можно за один проход выгрести все токены сопоставив с их именами. Решение первой проблемы — это именованные группы PCRE, которые так же именуются «подмасками». В результате матчинга будет образовываться ассоциативный массив, состоящий из пар "[TOKEN_NAME => TOKEN_VALUE]".

Но тут можно применить тактическую хитрость и воспользоваться функцией preg_replace_callback. Со второй чуть сложнее. Особенность её в том, что анонимка, переданная в качестве второго аргумента будет вызываться строго последовательно, для каждого токена, от первого до последнего.

Дабы не томить — реализация следующая:

Ещё одна портянка кода

class PregReplaceLexer
{ /** * @var array<string> */ private $tokens = []; /** * @param array<string> $tokens */ public function __construct(array $tokens) { foreach ($tokens as $name => $definition) { $this->tokens[] = \sprintf('(?<%s>%s)', $name, $definition); } } /** * @param string $sources * @return iterable&\Traversable<string,string> */ 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)); }
}

При этом скорость работы возрастает с 400 до 57000 токенов в секунду. А её использование ничем не отличается от предыдущего варианта. К слову, если воспользоваться Parle, то можно выжать до 600000 токенов в секунду. Именно этот алгоритм я применил в своей реализации, взявшись за переписывание исходников Hoa. 1, так что цифры тут ниже, но соотношение можно приблизительно представить). А общая картина выглядит примерно следующим образом (с включённым XDebug на PHP 7.

  • Жёлтый — нативное расширение Parle.
  • Голубой — реализация через preg_replace_callback с предварительно собранной регуляркой.
  • Красный — всё тоже самое, но с генерируемой регуляркой во время вызова preg_replace_callback.
  • Зелёный — реализация через preg_match.

Зачем?

В абстрактном мире PHP, где главенствует принцип «фигак-фигак-и-сайт-готов» — подобные библиотеки не нужны, будем честными. Ладно, всё это, конечно, замечательно, но нетерпеливые жаждут задать вопрос: «Кому это вообще нужно?». Аннотации в Symfony — это такой же подязык внутри PHP, требующий отдельного лексического и синтаксического разбора. Но если говорить об экосистеме в целом, то можно вспомнить небезызвестные библиотеки, вроде symfony/yaml или Doctrine. Ну или Yay и preprocess, основанный на нём. Помимо этого есть ещё чуть менее известные транспайлеры CoffeeScript, Less и Scss/Sass, написанные на PHP. Да и генераторы документации, вроде phpDocumentnor или Sami — довольно тривиальны. Я даже не буду упоминать инструменты анализа кода, вроде phpmd или phpcs. Каждый и этих проектов в той или иной степени использует лексический анализ на первой стадии разбора текста/кода.

Это далеко не полный список проектов и возможно, надеюсь, мой рассказ поможет вам открыть что-то новое и пополнить его.

Послесловие

Забегая вперёд, если есть кто-либо заинтересованный в тематике парсеров и компиляторов, то есть несколько интересных докладов по этой теме, в частности от ребят из JetBrains:

Видео

Ещё, конечно, большинство выступлений Андрея Бреслава, которые можно найти на просторах YouTube — советую к просмотру.

Ну а для любителей чтива есть вот такой ресурс, который был лично для меня крайне полезным: ps-group.github.io/compilers

Если где-то опечатался на просторах сего эпоса, то можете смело сообщать автору в любой удобной для вас форме. Пост пост скриптум.

Хотя кого я обманываю, от регулярок глаза кровоточат. В качестве бонуса, хотел бы привести пример простого лексера PHP, кажется это не так уж теперь и страшно, и теперь даже понятно что он делает, верно? =)

Спасибо!


Оставить комментарий

Ваш email нигде не будет показан
Обязательные для заполнения поля помечены *

*

x

Ещё Hi-Tech Интересное!

Киберпреступники пять месяцев контролировали ASUS Live Update

Злоумышленники разместили на сервере вредоносный файл с бэкдором, подписанный валидным сертификатом ASUS. Как сообщает «Лаборатория Касперского», хакеры из APT-группировки ShadowHammer 5 месяцев контролировали сервис обновлений ASUS Live Update и заразили более полумиллиона компьютеров по всему миру.Исследователи из «Лаборатории Касперского» обнаружили, ...

Kubernetes 1.14: обзор основных новшеств

14. Этой ночью состоится очередной релиз Kubernetes — 1. По сложившейся для нашего блога традиции, рассказываем о ключевых изменениях в новой версии этого замечательного Open Source-продукта. 14 и сооветствующих issues, pull requests, Kubernetes Enhancement Proposals (KEP). Информация, использованная для подготовки ...