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

    Синтаксический анализ текста всегда начинается с лексического анализа или 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')

    Регулярные выражения уже не справляются, но создавать полноценный 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> {
    
        // Строка, которую необходимо разбить на лексемы
        private final String content;
    
        // Массив типов токенов с регулярными выражениями для анализа
        private final ITokenType[] tokenTypes;
    
        private final Matcher matcher;
    
        // Текущая позиция анализа
        private int currentPosition = 0;
    
        /**
         * @param content строка для анализа
         * @param tokenTypes Массив типов токенов с регулярными выражениями для анализа
         */
        public RegexTokenizer(String content, ITokenType[] tokenTypes) {
            this.content = content;
            this.tokenTypes = tokenTypes;
    
            // Формируем общее регулярное выражение для анализа
            List<String> regexList = new ArrayList<>();
            for (int i = 0; i < tokenTypes.length; i++) {
                ITokenType tokenType = tokenTypes[i];
                regexList.add("(?<g" + i + ">" + tokenType.getRegex() + ")");
            }
            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();
    }
    

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


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


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


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


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


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

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

    AdBlock похитил этот баннер, но баннеры не зубы — отрастут

    Подробнее
    Реклама

    Комментарии 26

      +2
      Раз уж затронули эту тему… По своему опыту парсинга исходного кода регулярками могу сказать, что самые большие проблемы в этом подходе связаны:
      • со всяческими группировками с открывающими/закрывающими скобками всевозможных видов и их вложенностью в произвольном порядке;
      • с разного вида комментариями в коде;
      • со строками, в которых могут быть кавычки разных видов;
      • с экранированием внутри строк;
      • с меняющейся семантикой одних и тех же конструкций в зависимости от контекста
      • и, естественно, с комбинациями всего этого «адового ада».

      Есть ли у вас какие-то отработанные подходы к решению этих вопросов?
        +2

        По порядку:


        со всяческими группировками с открывающими/закрывающими скобками всевозможных видов и их вложенностью в произвольном порядке;

        В Java есть именованные скобки (named capturing group) и с их помощью можно не переживать за скобки внутри регэкспов, которые прилетают снаружи.
        Либо объявить контракт, что в регэкспах для типов лексем мы не используем скобки, либо используем non-captuiring скобки (вместо (select|from) пишем (?:select|from) ) — тогда проблем не будет.


        с разного вида комментариями в коде;

        самый сложный комментарий я видел в HTML вот регэксп который его распознает:


        \<\!\-\-(?:.|\n|\r)*?-->

        Можно поиграться


        со строками, в которых могут быть кавычки разных видов;
        с экранированием внутри строк;

        Вот пример для JS строк


        \"(?:[^\"\n\t\\]|\\[nrt\\"])*"|\'(?:[^\'\n\t\\]|\\[nrt\\'])*'

        С примером


        с меняющейся семантикой одних и тех же конструкций в зависимости от контекста

        У меня такое было при написании парсера JavaDoc комментариев, когда внутри комментария вида:


        /**
         *
         * @param name Описание параметра
         */

        Нужно было анализировать структуру. В этом случае я просто создавал второй лексер, который заточен под Javadoc.
        Самый сложный случай — COBOL, где есть зависимость от колонки, то есть там первые восемь символов в строке- это просто нумерация строк, потом 72 символа- текст программы, потом с 80-го символа- комментарии. Пришлось повозиться, чтобы сделать подсветку синтаксиса, но тоже решилась проблема.
        Ну и как я уже написал очень помогает в таких случаях LOOKAHEAD/LOOKBEHIND, хотя они очень замедляют скорость работы.


        и, естественно, с комбинациями всего этого «адового ада».

        Жизнь-боль, парсинг-труд :) На самом деле я хочу написать еще одну статью, как можно даже синтаксический анализ делать с помощью регэкспов, не прибегая ко всяким LL1/LR0… Скорость конечно сильно падает, зато проще раз в пятьсот )))

          +3
          А как вы относитесь к разбору HTML при помощи regex? (см например stackoverflow.com/a/1732454)
            0

            Помните что Билл Гейтс говорил, что он не понимает зачем компьютеру может понадобиться больше 640КБ памяти )))
            Если серьезно, но представьте что вместо


            <div class="h1" style="border:1px">
              <h1>
                Header
              </h1>
              <p class="sub-header">
                Sub header
              </p>
            </div>

            Вы преобразуете в вид


            <div-1 div-1-att-class="v1" div-1-att-style="v2"><h1-2>$c1 #h1-2 <p-3 p-3-att-class="v3">$c2 #p-3 #div-1

            Такое преобразование можно сделать довольно легко с помощью лексического анализатора. После преобразования, в тексте символ < всегда будет означать открытие тега, и не будет встречаться в значениях атрибутов, тексте или в закрывающем теге. Закрывающий тег будет отличаться от открывающего и однозначно соответствовать открывающему (можно будет использовать back reference).
            Так вот после этого преобразования вы легко пишете регэксп, с помощью которого находите все теги и его границы (закрывающий теш), находите его атрибуты, содержание, внутренние теги… Вам придется применить одни и теже регулярные выражения много раз к одному и тому же тексту (к разным его частям), это будет не оптимальный алгоритм, но в итоге вы сможете получить полную структуру HTML документа.
            Говоря кратко, чистым regexp-ом нельзя проанализировать HTML (как и любой другой нерегулярный язык), но регулярные выражения могут очень упростить синтаксический анализ, выполняя 90% всей работы.

              0
              Если говорить о HTML, то далеко не всегда у вас на входе будет полностью валидная разметка.
              Бывало, конечно, и такое, что приходилось делать анализ, например, списка объявлений переменных на Pascal/C/C# при помощи регулярного выражения (сыну маминой подруги в университете задавали), но это максимум хорошая задача для того, чтобы прокачаться в регулярных выражениях. В реальных проектах почему-то мне всегда гораздо проще сделать отдельно простой лексер (из кучи маленьких и понятных регулярок) и уже отдельно анализировать синтаксис рекурсивным спуском или табличными парсерами.
            +2
            На самом деле я хочу написать еще одну статью, как можно даже синтаксический анализ делать с помощью регэкспов…

            Я очень сильно за то, чтобы такая статья появилась
              +1

              Проблема с регулярками в синтаксическом анализе в том, что они не работают.
              Точнее — работают только на некотором строго ограниченном подмножестве всех возможных входных строк, причём точные границы этого подмножества знает (далеко не всегда, замечу) только автор парсера.
              Пока вы парсите строго свои строки — это будет работать.
              В чужом же всегда найдется контрпример, на котором регулярка будет сбоить.
              Шутку про регексп и 2 проблемы не зря придумали.

                0
                Вот пример для JS строк

                А потом вы натыкаетесь на template literal. Три раза вложенный друг в друга.

                  +1

                  Такие вещи должны разрешаться синтаксическим анализом, а не лексическим. Токенайзер- тупой как пробка. Есть поток символов, он просто дробит поток на куски и каждому куску сопоставляет тип.

                  0
                  На самом деле я хочу написать еще одну статью, как можно даже синтаксический анализ делать с помощью регэкспов, не прибегая ко всяким LL1/LR0… Скорость конечно сильно падает, зато проще раз в пятьсот )))

                  На чем основано утверждение, что это проще? Как вы собрались просто обрабатывать рекурсивные правила с помощь регулярок? К тому же LL1 алгоритм как раз очень легко реализовать, поскольку для выбора следующей альтернативы нужна всего лишь одна лексема.

                    0
                    Как вы собрались просто обрабатывать рекурсивные правила с помощь регулярок?

                    Как обычно — преобразуем рекурсивные правила в нерекурсивные и применяем регулярки. Есть другие решения?

                  +1
                  я бы добавил сюда (и даже поставил на первое место) очень низкую скорость работы регекспов, — их разумно использовать только на этапе исследования, а в «боевом» коде регулярки лучше избегать.
                    0

                    Есть регэксп движки на ДКА (сам делал). Вряд ли вы что-то сделаете быстрее ДКА.

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

                        Дело в том, что для ДКА в отличии от НКА все равно насколько сложные регэкспы вы ему скормите и готов спорить решение с ДКА в общем случае будет всегда быстрее.
                        Вот посмотрите например на скорость работы алгоритмов поиска подстроки в строке.


                        https://ru.wikipedia.org/wiki/%D0%9F%D0%BE%D0%B8%D1%81%D0%BA_%D0%BF%D0%BE%D0%B4%D1%81%D1%82%D1%80%D0%BE%D0%BA%D0%B8


                        Чего только не придумали разные авторы. Но Автоматный алгоритм Ахо-Корасика всегда выдает одну и ту же самую быструю скорость для худшего случая. Да- иногда, для особых случаев, некоторые алгоритмы на основе эвристик находят строку быстрее, но в худшем случае они проваливаются. Автомату все равно с чем иметь дело- он все находит (бьет по токенам) за один проход.

                          0
                          Всё же зависит, как вы правильно говорите, от движка. В .Net, например, используется недетерминированный конечный автомат, чтобы обеспечить поддержку хотя бы backtracking. Если вы используете backtracking (и другие расширения базового синтаксиса regex), производительность будет оставлять желать лучшего, я уверен.
                            +1

                            Да, вы правы, backtracking бьет по производительности поиска. Но тут возникает вопрос, какая производительность вам нужна? Возможно вы делаете разметку синтаксиса для сайта- тогда вы просто кешируете результат в базе и как быстро вы его сформировали- за 10 мс или 100 мс- не так уж важно. Не все пишут реальный компилятор или редактор кода, где скорость действительно важна. Я например обычно пишу статические анализаторы, которые собирают статистику или находят ошибки в коде. В таких задачах вообще неважно придет отчет через минуту или через полторы минуты. Самый лучший способ выиграть бой- уклониться от него. Не надо биться за скорость, если она вам на самом деле не важна.


                            Если же скорость важна- искользуйте движки на ДКА- там нет бэктрекинга и быстрее чем ДКА вы вряд ли что-то сможете создать в общем случае. Для каких-нибудь примитивных языков- вполне возможно, но для реальных ЯП-XML-HTML-JSON-HTML-Markdown-YML очень сомневаюсь. Регэкспы для ДКА не такие мощные, но их мне обычно хватает.

                  +4

                  Лексический анализ, конечно, делается если не ручным кодированием, то регулярными выражениями.


                  Один вопрос. Почему вы так парсеров боитесь?

                    –1

                    Я всю жизнь парсеры пишу ))) Написал штук 20-30 для разных языков, чего-чего, а парсеров я точно не боюсь )))

                      0

                      Где можно с ними ознакомиться?

                    +1
                    Я когда-то решал задачу «отрезать путь к файлу, оставить только имя с расширением eif» и написал регулярку (для Vim):
                    %s/^.*\(\\\(\w\|\s\)\+(.*)\.eif$\).*$/\1/g

                    Потом подумал, что, должен же быть способ лучше, и переписал это же самое на Python:

                    function! LeaveBasename()
                    python << EOF
                    import vim
                    import os
                    r = vim.current.range
                    r[0] = os.path.basename(r[0])
                    EOF
                    endfunction
                    


                    Конечно, тут за меня все сделала функция os.path.basename, но к первому способу возвращаться не хочется совсем.
                      0

                      Больше всего при написании парсеров меня порадовал shell:


                      export export=export

                      Эта конструкция объявляет переменную export со значением "export". Какие токены вы здесь видите? :)

                        0

                        Косил косой косой косой )))
                        Лексический анализатор тут беспомощен- вся надежда на синтаксический!

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

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


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

                        Да, они заточены под compile-time. Но и в run-time их также можно исползовать при необходимости. В какой задаче вам требовалось формировать список слов из файла или БД?


                        Например запросы, в которых одно и тоже поле проверяется на набор значений с помощью OR

                        Не разбираюсь в тонкостях оптимизаторов SQL запросов, но разве такую простейшую оптимизацию они выполнить не в состоянии?


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

                        С его помощью можно создать и лексер, что и вам и нужно, судя по заголовку и контенту. Кстати, правильно — ANTLR.


                        Мы рассмотрим упрощенный вариант 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 : [+\-\*/.=\(\)]

                        И строите регулярку для него:


                        (\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]*)|([+\-\*/.=\(\)])

                        При этом пишете о каких-то вещах, о которых не нужно было бы задумываться, если сразу использовали нормальные лексеры. Про использование оператора \b и non-capturing скобки.


                        Лексер ANTLR почти что повторяет вышеописанные лексемы в простом формате:


                        Keyword
                            : 'select'
                            | 'from'
                            | 'where'
                            | 'group'
                            | 'by'
                            | 'order'
                            | 'or'
                            | 'and'
                            | 'not'
                            | 'exists'
                            | 'having'
                            | 'join'
                            | 'left'
                            | 'right'
                            | 'inner'
                            ;
                        Id         : [A-Za-z][A-Za-z0-9]*;
                        RealNumber : [0-9] '.' [0-9]*;
                        Number     : [0-9]+;
                        String     : '\'' ~'*' '\'';
                        Space      : [ \t\r\n]+ -> channel(HIDDEN);
                        Comment    : '--' ~[\r\n]* [\r\n] -> channel(HIDDEN);
                        Operation  : [+\-*/.=()];

                        Но на самом деле я бы каждое ключевое слово выделил в отдельный тип — так гибче.


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


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

                        Ага, только в лексере с такими заморачиваться вообще не нужно, поскольку у каждого токена уже есть тип. Более того, можно игнорить определенные лексемы (skip) или же заносить их в отдельный скрытый канал (-> channel(HIDDEN)).


                        На моем I7 2.3GHz этот класс демонстрирует скорость анализа 5-20 МБ в секунду (зависит от сложности выражений).

                        На моем Core i5 3.5GHz скорость PL/SQL лексера (https://github.com/antlr/grammars-v4/blob/master/plsql/PlSqlLexer.g4) — 30 Мб за 2.5 сек, т.е. примерно 12 МБ в секундну. При этом этот лексер имеет намного больше возможностей, чем ваша регулярка. В принципе эта скорость все равно высокая, даже если будет на порядок меньше. Синтаксический и семантический анализы будут куда медленней.


                        Я добивался большей скорости работы лишь используя свою реализацию регулярных выражений основанную на ДКА

                        Так зачем все же в итоге писать свой велосипед, если это давно уже реализовано и оптимизировано в лексерах?


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

                        Можно ознакомиться с этими регулярками? С ANTLR лексерами можно в официальном репозитории (файлы с суффиксом Lexer): https://github.com/antlr/grammars-v4


                        Например, символ * в SQL имеет значение оператора умножения и указания всех полей в таблице.

                        Это потенциальное замедление скорости. Лучше определять тип токена в поспроцессинге — если слева есть ключевое слово SELECT, то после него — звездочка. В противном случае — это умножение. Ах, да, это же регулярки, там нет токенов...


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

                        Резюмирую: легкости нет вообще. Я бы не рекомендовал использовать регулярки для лексического анализатора, не говоря уже о синтаксическом.

                          0

                          Что заставляет думать вас, что я вам навязываю свою точку зрения или претендую на истину в последней инстанции. Я рассказал про один из способов, который вы можете либо использовать либо нет. Ни в коем случае не предлагаю никому срочно бросать AntLR и начинать использовать Regex.
                          Пусть расцветают тысячи цветов!
                          Мира вам!

                          +1

                          Использую ту же идею в своём токенайзере. На самом деле можно использовать и капчуринг. Просто надо для каждой регулярки посчитать сколько в ней капчуров. И использовать эту инфу при поиске совпавшей регулярки.
                          https://github.com/eigenmethod/mol/tree/master/syntax2

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

                          Самое читаемое