Comments 26
- со всяческими группировками с открывающими/закрывающими скобками всевозможных видов и их вложенностью в произвольном порядке;
- с разного вида комментариями в коде;
- со строками, в которых могут быть кавычки разных видов;
- с экранированием внутри строк;
- с меняющейся семантикой одних и тех же конструкций в зависимости от контекста
- и, естественно, с комбинациями всего этого «адового ада».
Есть ли у вас какие-то отработанные подходы к решению этих вопросов?
По порядку:
со всяческими группировками с открывающими/закрывающими скобками всевозможных видов и их вложенностью в произвольном порядке;
В 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… Скорость конечно сильно падает, зато проще раз в пятьсот )))
Помните что Билл Гейтс говорил, что он не понимает зачем компьютеру может понадобиться больше 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% всей работы.
Бывало, конечно, и такое, что приходилось делать анализ, например, списка объявлений переменных на Pascal/C/C# при помощи регулярного выражения (сыну маминой подруги в университете задавали), но это максимум хорошая задача для того, чтобы прокачаться в регулярных выражениях. В реальных проектах почему-то мне всегда гораздо проще сделать отдельно простой лексер (из кучи маленьких и понятных регулярок) и уже отдельно анализировать синтаксис рекурсивным спуском или табличными парсерами.
На самом деле я хочу написать еще одну статью, как можно даже синтаксический анализ делать с помощью регэкспов…
Я очень сильно за то, чтобы такая статья появилась
Проблема с регулярками в синтаксическом анализе в том, что они не работают.
Точнее — работают только на некотором строго ограниченном подмножестве всех возможных входных строк, причём точные границы этого подмножества знает (далеко не всегда, замечу) только автор парсера.
Пока вы парсите строго свои строки — это будет работать.
В чужом же всегда найдется контрпример, на котором регулярка будет сбоить.
Шутку про регексп и 2 проблемы не зря придумали.
Вот пример для JS строк
А потом вы натыкаетесь на template literal. Три раза вложенный друг в друга.
На самом деле я хочу написать еще одну статью, как можно даже синтаксический анализ делать с помощью регэкспов, не прибегая ко всяким LL1/LR0… Скорость конечно сильно падает, зато проще раз в пятьсот )))
На чем основано утверждение, что это проще? Как вы собрались просто обрабатывать рекурсивные правила с помощь регулярок? К тому же LL1 алгоритм как раз очень легко реализовать, поскольку для выбора следующей альтернативы нужна всего лишь одна лексема.
Есть регэксп движки на ДКА (сам делал). Вряд ли вы что-то сделаете быстрее ДКА.
Дело в том, что для ДКА в отличии от НКА все равно насколько сложные регэкспы вы ему скормите и готов спорить решение с ДКА в общем случае будет всегда быстрее.
Вот посмотрите например на скорость работы алгоритмов поиска подстроки в строке.
Чего только не придумали разные авторы. Но Автоматный алгоритм Ахо-Корасика всегда выдает одну и ту же самую быструю скорость для худшего случая. Да- иногда, для особых случаев, некоторые алгоритмы на основе эвристик находят строку быстрее, но в худшем случае они проваливаются. Автомату все равно с чем иметь дело- он все находит (бьет по токенам) за один проход.
Да, вы правы, backtracking бьет по производительности поиска. Но тут возникает вопрос, какая производительность вам нужна? Возможно вы делаете разметку синтаксиса для сайта- тогда вы просто кешируете результат в базе и как быстро вы его сформировали- за 10 мс или 100 мс- не так уж важно. Не все пишут реальный компилятор или редактор кода, где скорость действительно важна. Я например обычно пишу статические анализаторы, которые собирают статистику или находят ошибки в коде. В таких задачах вообще неважно придет отчет через минуту или через полторы минуты. Самый лучший способ выиграть бой- уклониться от него. Не надо биться за скорость, если она вам на самом деле не важна.
Если же скорость важна- искользуйте движки на ДКА- там нет бэктрекинга и быстрее чем ДКА вы вряд ли что-то сможете создать в общем случае. Для каких-нибудь примитивных языков- вполне возможно, но для реальных ЯП-XML-HTML-JSON-HTML-Markdown-YML очень сомневаюсь. Регэкспы для ДКА не такие мощные, но их мне обычно хватает.
Лексический анализ, конечно, делается если не ручным кодированием, то регулярными выражениями.
Один вопрос. Почему вы так парсеров боитесь?
%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, но к первому способу возвращаться не хочется совсем.
Больше всего при написании парсеров меня порадовал shell:
export export=export
Эта конструкция объявляет переменную export со значением "export". Какие токены вы здесь видите? :)
Но мне часто попадаются задачи промежуточного уровня, когда регулярных выражений не хватает, а тянуть в проект тяжеловесный инструментарий не хочется.
Почему? Других зависимостей вообще нет? Да и не такой уж он тяжелый. При этом, судя по статье, подобный тяжеловесный инструментарий вы сами и реализовали.
К тому же эти инструменты обычно работают на этапе 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, то после него — звездочка. В противном случае — это умножение. Ах, да, это же регулярки, там нет токенов...
Используя эти правила и применяя данный алгоритм вы быстро сможете разбивать текст на токены практически для любого языка.
Резюмирую: легкости нет вообще. Я бы не рекомендовал использовать регулярки для лексического анализатора, не говоря уже о синтаксическом.
Что заставляет думать вас, что я вам навязываю свою точку зрения или претендую на истину в последней инстанции. Я рассказал про один из способов, который вы можете либо использовать либо нет. Ни в коем случае не предлагаю никому срочно бросать AntLR и начинать использовать Regex.
Пусть расцветают тысячи цветов!
Мира вам!
Использую ту же идею в своём токенайзере. На самом деле можно использовать и капчуринг. Просто надо для каждой регулярки посчитать сколько в ней капчуров. И использовать эту инфу при поиске совпавшей регулярки.
https://github.com/eigenmethod/mol/tree/master/syntax2
Профессиональный лексический анализ на регулярных выражениях