Хабрахабр

Профессиональный лексический анализ на регулярных выражениях

Существует простой способ решить эту задачу практически для любого языка с помощью регулярных выражений. Синтаксический анализ текста всегда начинается с лексического анализа или tokenizing-а. Еще одно применение старым добрым regexp-ам.

Для простых задач, вроде анализа введенного пользователем значения, достаточно базового функционала регулярных выражений. Я часто сталкиваюсь с задачей синтаксического анализа текстов. Но мне часто попадаются задачи промежуточного уровня, когда регулярных выражений не хватает, а тянуть в проект тяжеловесный инструментарий не хочется. Для сложных и тяжелых задач вроде написания компилятора или статического анализа кода можно использовать специализированные инструменты (AntLR, JavaCC, Yacc). К тому же эти инструменты обычно работают на этапе compile-time и в run-time не позволяют изменить параметры анализа (например сформировать список ключевых слов из файла или таблицы БД).

Мы анализировали логи наших SQL запросов и хотели по определенным правилам находить "плохие" запросы. Как пример приведу задачу, которая возникла у нас в процессе ускорения SQL запросов. Например запросы, в которых одно и тоже поле проверяется на набор значений с помощью OR

name = 'John' OR name = 'Michael' OR name = 'Bob'

Мы хотели заменить такие запросы на

name IN ('John', 'Michael', 'Bob')

Можно было бы просто провести лексический анализ (tokenizing), получить список токенов для каждого запроса и простым кодом, без всяких специализированных инструментов сделать синтаксический анализ. Регулярные выражения уже не справляются, но создавать полноценный SQL парсер с помощью AntLR тоже не хотелось.

Попробуем разбить на токены SQL запрос. Эту задачу можно решить с помощью базового функционала регулярных выражений. Для создания полноценного SQL лексера придется написать чуть более сложные регулярные выражения. Мы рассмотрим упрощенный вариант SQL, чтобы не перегружать текст деталями.

Вот набор выражений для основных лексем языка SQL:

1. keyword : \b(?:select|from|where|group|by|order|or|and|not|exists|having|join|left|right|inner)\b
2. id : [A-Za-z][A-Za-z0-9]*
3. real_number : [0-9]+\.[0-9]*
4. number : [0-9]+
5. string : '[^']*'
6. space : \s+
7. comment : \-\-[^\n\r]*
8. operation : [+\-\*/.=\(\)]

Хочу обратить внимание на регулярное выражение для keyword

keyword : \b(?:select|from|where|group|by|order|or|and|not|exists|having|join|left|right|inner)\b

В нем есть две особенности.

  1. Используется оператор \b в начале и в конце, чтобы например не отсекать от слова organization префикс or, который является ключевым словом и который некоторые regex engine выделят в отдельную лексему без использования оператора \b .
  2. все слова сгруппированы non-capturing скобками (?: ), которые не захватывают совпадение. Это в дальнейшем будет использоваться, чтобы не нарушать индекcирование частичных регулярных выражений внутри общего выражения.

Теперь можно объединить все эти выражения в одно целое, с помощью группировки и оператора |

(\b(?:select|from|where|group|by|order|or|and|not|exists|having|join|left|right|inner)\b)|([A-Za-z][A-Za-z0-9]*)|([0-9]+\.[0-9]*)|([0-9]+)|('[^']*')|(\s+)|(\-\-[^\n\r]*)|([+\-\*/.=\(\)])

Теперь можно попробовать применить это выражение к SQL выражению, например к такому

SELECT count(id) -- count of 'Johns' FROM person
WHERE name = 'John'

Перейдя по ссылке можно поиграться с выражением и результатом анализа. Вот результат на Regex Tester. Видно, что например SELECT соответствует сразу 1- группе, которая соответствует типу keyword.

image

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

Вот небольшой класс, который реализует это на Java. Оформить приведенный алгоритм в программу на любом яззыке программирования, который поддерживает регулярные выражения не составит особого труда.

RegexTokenizer.java (+ еще пара классов)

package org.example; import java.util.ArrayList;
import java.util.Enumeration;
import java.util.List;
import java.util.regex.Matcher;
import java.util.regex.Pattern;
import java.util.stream.Collectors; /** * Токенайзер на регулярных выражениях. * Использует именованные группы, чтобы не зависеть от способа группировки базовых регулярных выражений. */
public class RegexTokenizer implements Enumeration<Token> String regex = regexList.stream().collect(Collectors.joining("|")); Pattern pattern = Pattern.compile(regex, Pattern.CASE_INSENSITIVE); // Запускаем первый поиск matcher = pattern.matcher(content); matcher.find(); } @Override public boolean hasMoreElements() { return currentPosition < content.length(); } @Override public Token nextElement() { boolean found = currentPosition > matcher.start() ? matcher.find() : true; int start = found ? matcher.start() : content.length(); int end = found ? matcher.end() : content.length(); if(found && currentPosition == start) { currentPosition = end; // Лексема найдена- определяем тип for (int i = 0; i < tokenTypes.length; i++) { String si = "g" + i; if (matcher.start(si) == start && matcher.end(si) == end) { return createToken(content, tokenTypes[i], start, end); } } } throw new IllegalStateException("Не удается определить лексему в позиции " + currentPosition); } /** * Создаем токен-лексему по параметрам, можно переопределить этот метод, чтобы например ускорить работу алгоритма, * например не вырезать текст токена из оригинальной строки для некоторых токенов (пробел, комментарий) * @param content оригинальная строка для анализа * @param tokenType тип токена * @param start начало токена в оригинальной строке * @param end конец токена в оригинальной строке * @return объект токена-лексемы */ protected Token createToken(String content, ITokenType tokenType, int start, int end) { return new Token(content.substring(start, end), tokenType, start); } /** * Список типов токенов для SQL */ public enum SQLTokenType implements ITokenType { KEYWORD("\\b(?:select|from|where|group|by|order|or|and|not|exists|having|join|left|right|inner)\\b"), ID("[A-Za-z][A-Za-z0-9]*"), REAL_NUMBER("[0-9]+\\.[0-9]*"), NUMBER("[0-9]+"), STRING("'[^']*'"), SPACE("\\s+"), COMMENT("\\-\\-[^\\n\\r]*"), OPERATION("[+\\-\\*/.=\\(\\)]"); private final String regex; SQLTokenType(String regex) { this.regex = regex; } @Override public String getRegex() { return regex; } } public static void main(String[] args) { String s = "select count(id) -- count of 'Johns' \n" + "FROM person\n" + "where name = 'John'"; RegexTokenizer tokenizer = new RegexTokenizer(s, SQLTokenType.values()); while(tokenizer.hasMoreElements()) { Token token = tokenizer.nextElement(); System.out.println(token.getText() + " : " + token.getType()); } }
} /** * Класс- токен (лексема) */
public class Token { // Текст токена private final String text; // Тип токена private final ITokenType type; // Начало токена в исходном тексте private final int start; public Token(String text, ITokenType type, int start) { this.text = text; this.type = type; this.start = start; } public String getText() { return text; } public ITokenType getType() { return type; } public int getStart() { return start; }
}
/** * Интерфейс для типа токена */
public interface ITokenType { /** * Регулярное выражение для данного типа токена */ String getRegex();
}

Эта возможность позволяет обращаться к группам не по индексам, а по имени, что немного удобнее чем обращение по индексу. В этом классе алгоритм реализован с помощью именованных групп, которые присутствуют не во всех движках.

3GHz этот класс демонстрирует скорость анализа 5-20 МБ в секунду (зависит от сложности выражений). На моем I7 2. Алгоритм можно распараллелить, анализируя сразу несколько файлов, увеличивая общую скорость работы.

Это работает примерно в 10-20 раз медленнее, требует больше памяти и алгоритм получается сложнее. В сети я нашел несколько подобных алгоритмов, но мне попадались варианты, которые не формируют общего регулярного выражения, а последовательно применяют регулярные выражение для каждого типа лексем к началу строки, потом отбрасывают найденный токен из начала строки и снова пытаются применить все регэкспы. В regex движках обычно используется НКА — недетерминированный конечный автомат). Я добивался большей скорости работы лишь используя свою реализацию регулярных выражений основанную на ДКА (детерминированный конечный автомат). ДКА в 2-3 раза быстрее, но регулярные выражения для него писать сложнее из-за ограниченного набора операторов.

Я же в своей практике применял этот подход и создавал полноценные лексические анализаторы для SQL, Java, C, XML, HTML, JSON, Pascal и даже COBOL (с ним пришлось повозиться). В своем примере для SQL я немного упростил регулярные выражения и полученный токенайзер нельзя считать полноценным лексическим анализатором SQL запросов, но цель статьи- показать принцип, а не создать реальный SQL tokenizer.

Приведу еще несколько простых правил для написания регулярных выражений для лексического анализа.

  1. Если одна и та же лексема может быть отнесена к разным типам (например любое ключевое слово может быть распознано как идентификатор), то более узкий тип нужно определять в начале. Тогда регулярное выражение для него будет применяться первым и именно оно определит тип лексемы. Например в моем примере keyword определены раньше id и лексема select будет распознана как keyword, а не id
  2. Определяйте сначала более длинные лексемы, потом более короткие. Например сначала нужно определить <=, >= и потом уже отдельные >, <, = В этом случае текст <= правильно будет распознан как единая лексема оператора "меньше либо равно", а не две отдельные лексемы < и =
  3. Научитесь использовать lookahead и lookbehind. Например, символ * в SQL имеет значение оператора умножения и указания всех полей в таблице. Можно в помощью простого lookbehind отделить эти два случая, например здесь регэксп (?<=.\s|select\s)* находит символ * только в значении "все поля таблицы".
  4. Иногда полезно определить регулярные выражения для ошибок, которые бывают в тексте. Например если вы делаете подсветку синтаксиса, можно определить тип лексемы "незаконченная строка" как '[^\n\r]*. В процессе редактирования текста пользователь может не успеть закрыть кавычку в строке, но ваш токенайзер сможет правильно распознать такую ситуацию и правильно подсветить ее.

Используя эти правила и применяя данный алгоритм вы быстро сможете разбивать текст на токены практически для любого языка.

Теги
Показать больше

Похожие статьи

Добавить комментарий

Ваш e-mail не будет опубликован. Обязательные поля помечены *

Кнопка «Наверх»
Закрыть