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

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


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

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

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

  • Профессиональный лексический анализ на регулярных выражениях
    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


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

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

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

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

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

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

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

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

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

  • Профессиональный лексический анализ на регулярных выражениях
    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% всей работы.

  • Профессиональный лексический анализ на регулярных выражениях
    +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… Скорость конечно сильно падает, зато проще раз в пятьсот )))

  • Оптимизация запросов базы данных на примере B2B сервиса для строителей
    0
    У нас эта связка никогда не меняется- доставка не имеет шансов быть привязанной к другому счету-запросу-заявке, счет к другому запросу и запрос к другой заявке… Так что тут все оправдано.
  • Оптимизация запросов базы данных на примере B2B сервиса для строителей
    0
    Буду рад, если вы посоветуете, что нам еще сделать, чтобы ускорить нашу БД.
  • 46 навыков и характеристик, из которых складывается портрет идеального менеджера продукта
    0
    На ютубе есть видео «от проектного IT-бизнеса к продуктовому», так вот там один докладчик сформулировал интересную мысль: «директор по продукту- это человек, главная обязанность которого- всех посылать на хрен».
  • Генерация больших объемов полезных данных
    0
    Генерацию желательно запускать заранее, чтобы на момент ввода накладной наименование товара было в таблице. Но мы предусмотрели возможность ввода накладной, без этого требования. Но тогда просто накладная не попадает на следующий шаг, пока не будет добавлена «правильная» запись в таблицу товаров.
    Поля для отбора мы тоже генерируем- есть дополнительная таблица атрибутов товара (да, это антипаттерн Entity-Attribute-Value)
    CREATE TABLE `good_attribute` (
      `id` int(11) NOT NULL AUTO_INCREMENT,
      `name` varchar(32) NOT NULL,
      `value` varchar(32) NOT NULL,
      `good_id` int(11) NOT NULL,
      PRIMARY KEY (`id`),
    )
    

    Но пока эта таблица не используется- оставлена на будущее, т.к. мы используем обычный текстовый поиск, т.е. пользователь вводит что-то вроде

    Шур 4 10
    

    И мы показываем ему первые 10 вариантов, где встречаются эти подстроки. Работает довольно быстро- из нескольких миллионов позиций выборка происходит за 1-5 секунд.
    Разные таблицы для параметров мы не используем т.к. заранее мы не знаем какие параметры нужны будут пользователю (для метизов это одни параметры, для труб или оборудования- совсем другие), а генерацией таблиц «на лету» мы решили не увлекаться.