Комментарии 70
Отказ от RE совсем не означает, что надо написать свой универсальный парсер. Ровно наоборот – надо обрабатывать данные кодом специально для них написанным. Данные ведь бывают разными.
А RE плох потому что совершенно нечитабельный. Даже если человек эксперт в RE.
Особенно хорошо специальный код обновлять, когда оказывается, что формат данных надо немного поменять.
А если RE, что, не понадобиться обновлять, что ли? А, да, только придется прежде чем менять, понять что же именно делал прежний RE написанный 3 года назад программистом, который давно уже уволился. :D
А таки что проще обновлять — конкретный RE или NFA, в который он скомпилировался?
Вы мне соломенное чучело не подсовывайте. Код, который написан для специальной обработки частного случая, всегда будет намного проще, чем универсальный RE и то что компилятор из него нагенерирует. Так что пока вы разбираете прежний RE, я три раза разберусь что здесь было и как сделать по другому.
Могу. А что этот код делает? Я же ваши языки не понимаю.
О, понятно. Я такое писал вроде. Найти только… Вот:
P.S. Только у меня более универсально, вроде писал по какому-то RFC.
В-четвёртых, как вы это проверяете на корректность? Для кода выше я могу написать совершенно офигенный набор из нескольких тестов (через property-based-тестирование), который, как показывает практика, очень сильно помогает понять, что что-то не так. Не доказательства, но уже близко.
Ровно те же самые тесты можно написать на любой код разбора URL...
Во-первых, как вы сообщаете об ошибках? Ну вот заматчилось ли у вас что-то или нет?
Так, это же парсер. Он просто разделяет URL на компоненты. Проверка об ошибках делает тот кто вызвал парсер. Ведь, кому-то схема например, или порт обязательны, а кому-то нет.
Во-вторых, что у вас происходит вон там вначале со схемой? Это в RFC проверки на 0-9, что ли?
Это проверка на порт ":123". Ведь, может быть URL например такое: "http://:1234/" – тогда, scheme="http", host="", port="1234";
Ну и про модификации: предположим, что мы хотим сделать слеш на конце и часть после него опциональной.
Ну, у меня слеш в конце и так опциональный, как и вообще все элементы URL.
Давайте сделаем по другому. Вы правы, что мы сравниваем разные вещи.
Давайте напишите более подробно что делает ваш код. (Можно с тестовыми примерами – что на входе, что на выходе) Потом я напишу более простой код для этого частного случая, а вы преобразуете ваш код в классическое RE. (мы обсуждаем именно его) И сравним результаты на читабельность.
Потом поищем добровольцев которые сделают какое-то изменение в коде. (потому что сразу после написания и мне и вам все будет понятно и менять легко).
Тогда и оценим насколько код или RE удобны для изменений и поддержки.
Под регулярными выражениями вы наверное понимаете язык записи Perl Regular Expression, который, как и все в перле, - совершенно не читаем если нет опыта. Но кроме них еще есть GNU Regular Expressions, например. Они более читаемы.
Особенно хорошо специальный код обновлять, когда оказывается, что формат данных надо немного поменять.
Вообще-то это работа программиста — писать код, и менять его, если условия изменились. И менять структурированный и документированный код, который написан специально, что бы хорошо делать конкретную работу гораздо проще и приятнее, чем универсальное заклинание на регэкспах.
Регеспы по сути это нотация для компактной записи грамматик. Писать структурированный и документированный код это ацкая мука, когда перед вами лишь командная строка). В общем я не спорю, тут все сводится к банальному - инструмент под задачу.
Ого, сколько снобизма.
Впрочем, похоже, современному программисту очень тяжело понять эту идею даже с примерами эквивалентного, но читабельного синтаксиса под носом — нет времени думать, надо менять код, если условия изменились.
Ну, да, дело, конечно, в современных программистах, хотя мысль о том, что если при решении проблемы воспользовался регулярками, то у тебя теперь две проблемы, возникла уж точно не сегодня, и даже не вчера, и возникла у тех самых не современных программистов, на знаниях которых и выросли современные.
Честно говоря подход выше едва ли можно назвать хорошим примером, таки ассемблер это вещь специфичная. Но твой код больше похож на парсер-комбинаторный, чем регулярный, а это совсем иной класс. Может быть проблема регулярок в том, что они просто так записываются, но тем не менее под регуляркой подразумевают обычно "стринга по правилам рфц/исо/...". Например вот эта — я уверен что почти любой код доработать/изменить проще чем эту регулярку.
Регекспы — это класс языков, а не конкретный синтаксис со всеми этими |*?
Все верно, регкэспы это этот конкретный синтаксис. Так же как RJ45 это конкретно 8P8C а не что-то ещё, а копировальная машина — исключительно "ксерокс".
johnfound регулярно топит за то, что на ассемблере можно писать так же хорошо, как на более других языках, и никто его за язык (или пальцы) не тянул. Кстати, на предложение просто поставить мне задачу, которую я потом решу, он тоже что-то сдулся, но, видимо, это просто не судьба.
Ну он известный оригинал, подобное утверждение делать любит легко. доказывать в силу невозможности — не очень.
Ты про класс в формальном смысле (всякие там Хомские) или как фигура речи?
Фигура речи
Во-первых, про различие в синтаксисе я указал в первом же своём комментарии. Если есть несогласие с этим тезисом, то имело бы смысл, ну, спорить именно с этим тезисом.
Я увидел эту ремарку только когда написал б0льшую часть своего комментария, и решил дописать раз уж начал.
Во-вторых, ключевой тезис моего исходного собеседника — что заточенный под задачу написанный руками парсер будет по каким-то там критериям лучше написанного с абстракциями. Тут про синтаксис вообще ничего нет, аппликативные комбинаторы (включающие в себя подмножество регулярных языков) ничем не менее абстрактны, чем вот эти привычные pcre- и им подобные уродцы.
Насколько я помню, парсер-комбинаторы не очень хорошо умеют в сложные ошибки парсинга. Я-то не эксперт-языковед, у меня грамматики обычно были не сложнее какого-нибудь расписания для cron, но товарищи кто для ЯПов парсеры писал говорили что нормальную обработку ошибок на комбинаторах сделать нереально. Ещё вроде хвалили перф, но тут уж не знаю, хотя не удивился бы.
А RE плох потому что совершенно нечитабельный. Даже если человек эксперт в RE.
В большинстве случаев требуется что-то относительно простое, и регекс вполне читабелен. Там, где сложная логика, будет одна строчка регекса и, пара строчек коментариев, так что результат получится вполне читабельный. Уж во всяком случае сильно читабельнее, чем несколько экранов какой-то замудреной логики с кучей условных переходов.
Ну и комментарий к следующему комментарию: :)
А если RE, что, не понадобиться обновлять, что ли? А, да, только придется прежде чем менять, понять что же именно делал прежний RE написанный 3 года назад программистом, который давно уже уволился. :D
Если надо обновить какой-то сложный и непонятный регекс, просто вставьте его в какую-нибудь онлайн тулзу вроде приведенного раннее regex101.com и можно будет достаточно быстро разобраться, сильно быстрее, чем разобраться в каком-то коде с запутанной логикой "написанный 3 года назад программистом, который давно уже уволился. :D" и поправить его.
До определенного размера сложности это ок. А ещё, я всех в команде заставляю писать коммент к каждому регексу с пояснением что происходит и зачем.
И главный лайфхак - если попросить chatGPT написать регекс, то он пишет офигенный коммент что там и как. Можно его и в код положить. Но только чат иногда ошибается в самом регексе. Так что тут как с стековерфлоу - нужно проверять.
Мне кажется, что в ходе дальнейшего обсуждения автор опровергает своё же утверждение. Приводится портянка на ассемблере с неясными именами и полным отстуствием комментариев (StrSplitURL). У меня есть большие сомнения, что даже неудачно написанный RE для этой задачи будет сложнее понимать и модифицировать в будущем новому разработчику
Ну почему велосипед, parser combinator'ы вполне имеют право на существование.
Меня больше зацепило что автора беспокоит перфоманс, но при этом он пишет на питоне.
Мне кажется, что эта статья - это не мануал о том как писать парсеры. А скорее пример того насколько крутые штуки можно делать с использованием композиции функций. Эдакий аккуратный ввод в функциональное программирование. Тут даже каррирование применяется, просто автор не стал использовать это слово.
Честно говоря и парсер у него крайне сомнительный вышел без традиционных комбинаторов а ля one_of, many0, many1 и прочих. Кишка лямбд в кишке лямбд.
Я недавно использовал ANTLR, так что могу про него рассказать. Так вот, это та ещё хрень.
Во-первых, у него уродские умолчания — при любой ошибке разбора он просто возвращает null, причём не обязательно на верхнем уровне. Мне пришлось реализовать 3 интерфейса и основательно покопаться во внутренностях просто чтобы заставить его кидать нормальные исключения.
Во-вторых, у токенов лексера нет значений. В итоге все токены приходится парсить два раза — сначала лексером, а потом вручную чтобы "достать" из них то что внутри лежит.
В-третьих, совершенно интуитивно непонятное API, нарушающее каноны самодокументируемого кода. К примеру, в его рантайме на .NET есть свойство, возвращающее изменяемый список перехватчиков не помню чего. Если список изменяемый, значит туда можно что-то добавить? А вот и нет, генерируется новый список при каждом обращении к свойству!
Ну и последнее — сложно что ли было создателям формат EBNF взять для грамматик?..
Да, сейчас вот добрался до кода и вспомнил:
В-четвёртых, несмотря на то, что у них в их дереве разбора кишки парсера торчат наружу отовсюду (из-за чего невозможно использовать дерево разбора в качестве AST), информацию о местоположении узла в исходном тексте они надёжно инкапсулировали. Казалось бы, стандартная функциональность — сообщать где именно в исходном тексте произошла ошибка, но чтобы этого добиться — надо лезть в дебри их абстракций.
PS вот кусок кода, который пришлось написать чтобы эта штука начала адекватно работать:
public (ITokenStream, MyFilterParser.FilterContext) Parse(string filter)
{
var output = new LogWriter(logger, LogLevel.Information);
var errOutput = new LogWriter(logger, LogLevel.Error);
var charStream = CharStreams.fromString(filter);
var lexer = new MyFilterLexer(charStream, output, errOutput);
lexer.RemoveErrorListeners();
lexer.AddErrorListener(new ThrowingErrorListener(filter));
var tokenStream = new CommonTokenStream(lexer);
var parser = new MyFilterParser(tokenStream, output, errOutput);
parser.RemoveErrorListeners();
parser.AddErrorListener(new ThrowingErrorListener(filter));
return (tokenStream, parser.filter());
}
// …
private Range GetLocation(ISyntaxTree context)
{
var interval = context.SourceInterval;
var start = tokenStream.Get(interval.a).StartIndex;
var stop = tokenStream.Get(interval.b).StopIndex;
return start..(stop+1);
}
К сожалению, ANTLR все больше устаревает, а автор почти не принимает новые риквесты и не дает мэинтейнить проект.
Во-первых, у него уродские умолчания — при любой ошибке разбора он просто возвращает null, причём не обязательно на верхнем уровне.
Да, такое вполне может быть.
Во-вторых, у токенов лексера нет значений. В итоге все токены приходится парсить два раза — сначала лексером, а потом вручную чтобы "достать" из них то что внутри лежит.
Строго говоря, у токенов они не обязательно должны быть, парсер в теории может работать и без лексера. Однако в подавляющем большинстве случаев парсятся тексты, а значит лексер присутствует.
Но два раза парсить точно не стоит — нужно использовать локацию токена, а по ней уже извлекать строку из входного текста.
В-третьих, совершенно интуитивно непонятное API, нарушающее каноны самодокументируемого кода. К примеру, в его рантайме на .NET есть свойство, возвращающее изменяемый список перехватчиков не помню чего. Если список изменяемый, значит туда можно что-то добавить? А вот и нет, генерируется новый список при каждом обращении к свойству!
Да, с этим много проблем, но вряд ли что-то изменится в рамках ANTLR 4, т.к. поломается обратная совместимость и в связи со стагнацией проекта.
Ну и последнее — сложно что ли было создателям формат EBNF взять для грамматик?..
А вот это спорно — как раз язык ANTLR лаконичней EBNF и в нем больше возможностей. Хотя тут тоже есть что улучшать.
Казалось бы, стандартная функциональность — сообщать где именно в исходном тексте произошла ошибка, но чтобы этого добиться — надо лезть в дебри их абстракций.
Это опять-таки объясняется тем, что парсер не обязательно подразумевает лексер, поэтому инфу о позиции нужно доставать через уровень лексера. Хотя и согласен — можно было получше сделать.
Но два раза парсить точно не стоит — нужно использовать локацию токена, а по ней уже извлекать строку из входного текста.
Вот её-то и придётся парсить второй раз. Простейший пример:
STRING_LITERAL : '"' ([^"\\]* | '\\' .)* '"'Эта конструкция выделит токен строкового литерала с учётом возможного наличия экранированных кавычек внутри. Однако если необходимо получить значение литерала — всё экранирование придётся обрабатывать самому, несмотря на то что лексер его уже обрабатывал.
А вот это спорно — как раз язык ANTLR лаконичней EBNF и в нем больше возможностей. Хотя тут тоже есть что улучшать.
Только вот в итоге получается, что невозможно просто взять и сгенерировать код по куску грамматики из RFC, приходится каждую конструкцию переписывать, потенциально допуская ошибки на пустом месте.
Эта конструкция выделит токен строкового литерала с учётом возможного наличия экранированных кавычек внутри. Однако если необходимо получить значение литерала — всё экранирование придётся обрабатывать самому, несмотря на то что лексер его уже обрабатывал.
А как это по вашему должно выглядеть? Как определить, что символ является экранирующим? Есть ли пример генератора, где реализовано такое извлечение значений?
Только вот в итоге получается, что невозможно просто взять и сгенерировать код по куску грамматики из RFC, приходится каждую конструкцию переписывать, потенциально допуская ошибки на пустом месте.
По крайней мере у ANTLR есть репозиторий грамматик, и, я думаю, самый большой.
Ага, и там наступает отдельное веселье: переиспользовать чужие грамматики можно только копипастом, внимательно изучая всё что копируешь.
Потому что лексический анализ происходит независимо от синтаксического, и если в двух импортах окажутся одинаковые токены — один из них "поглотит" второй. Для борьбы с этим вроде и есть режимы — только вот оператор импорта не позволяет этот режим переопределить.
А как это по вашему должно выглядеть? Как определить, что символ является экранирующим?
Ну, всяческие -> skip и -> channel(HIDDEN) уже есть, могли бы туда же добавить и переопределение значения токена. Или хотя бы разрешить тот же skip для фрагментов использовать.
Есть ли пример генератора, где реализовано такое извлечение значений?
Генератора-нет, но после детального знакомства с Antlr мне всё больше нравятся комбинаторные парсеры.
Ага, и там наступает отдельное веселье: переиспользовать чужие грамматики можно только копипастом, внимательно изучая всё что копируешь.
Ну такое правило применимо ко всему, что копируешь, не только к грамматикам.
Ну, всяческие -> skip и -> channel(HIDDEN) уже есть, могли бы туда же добавить и переопределение значения токена. Или хотя бы разрешить тот же skip для фрагментов использовать.
Это не так просто, как кажется. Скорее переопределить или игнорировать части значения токена. О, кажется я когда-то даже создавал подобную issue: Skip action for chars in token. Вроде это похоже на вполне реализуемую идею.
не понимаю, почему люди считают, что re нечитабельные.
Может неправильно их учат? Вместо того, чтобы изучить основные структуры в регулярках, пытаются запомнить сами символы. Но это не нужно.
re - язык лексического разбора, и для него есть готовые IDE типа regex101.com и др.
Кроме того, не обязательно писать килобайтные регулярки, если нужно что-то простое на 10-15 символов, без атомарных выражений и сверхжадных квантификаторов.
В общем, регулярки - это хороший и удобный инструмент
И знать его на уровне чуть больше чем средний нужно не только, чтобы знать "всякие сложные символы", а чтобы быстро определять, когда пользоваться регуляркой, а когда искать другой инструмент.
Я когда-то очень давно тоже смотрел на RE как баран на новые ворота. А потом я просто понял как они работают (ну, и так, ради интереса закрепил это прочтением очень годной книжечки). Сейчас RE воспринимаются более чем легко, особенно если есть подсветка кода и нормальное форматирование с комментами (/x). Не понимаю эту боязнь регулярок... Да, HTML конечно ими парсить нельзя, но прям повсеместно от них избавляться — излишне и не нужно)
Кто слишком ленивый, я закинул эту статью в chatGPT и вот вам короткое и понятное содержание
"Знаете, как в фильмах про Хэллоуин злые духи берут на себя облик того, что хотят? Так вот, регулярные выражения - это как злые духи Хэллоуина для текста! Они могут принимать на себя любой облик, чтобы найти и заменить нужную вам информацию в строках. Будьте осторожны, чтобы не взорвать ваш мозг при написании слишком сложных регулярок!"
Есть риск, что поговорю с копипастой.
Хотел написать, что вы изобретаете parser combinators, но они были упомянуты в конце (думаю, следовало бы задекларировать вначале).
Чего люди хейтят regexp, кроме слабо предсказуемой вычислительной сложности сверху (ну еще контекст кастомный не прикрутить, или не знаю как), мне не понятно, наверное про regex101.com не знают. В парсер комбинаторах можно и regexp применить на уровне повыше символов, если религия позволяет.
Вы попытались использовать функциональщину в python, но он, на мой взгляд с ней плохо дружит. И с итераторами, когда вместо красивого chain call надо писать бесконечные вложенные вызовы. Для написания кастомных парсеров и, в частности, применения parser combinators советую потрогать rust с его строковыми слайсами, там ('H', "ellow world") норм будет работать, если не чудить.
Пытался писать когда-то свой protobuf-like протокол с парсером dsl на нескольких языках по приколу, rust больше Java, js и C++ понравился, Kotlin ещё не плох был. Если бы сегодня собирался, питон бы не взял по своей воле (3 года на нем пишу по рабочим задачам - плююсь, если бы только нашлась либа, делающая 90% всей задачи, (f)lex, yacc, bison не предлагать).
вы изобретаете parser combinators
Это перевод, автор вряд-ли ответит). Вообще он преподаватель, изучил подход к теме в хаскеле и решил сделать так же питоне. Это решение не для продакшна.
Просто, если вы сможете реализовать принцип на другом языке, который может для этого не особо и предназначен, значит вы разобрались в теме, а не просто заучили мануал. Заодно это помогает лучше понять сильные и слабые стороны, а так же границы применимости того или иного подхода.
Я пишу парсеры опираясь на концепцию "автоматное программирование". Код получается тупой, понятный, быстрый и полностью контролируемый.
Это автоматный код-то получается понятным? Ну-ну...
Вы таки не поверите, но регулярки - это и есть язык описания автоматов, который в них компилируется.
Регулярки — это не язык описания автоматов, они просто через него реализуются и всех возможностей не покрывают. Плюс очевидная характерность регэкспов в том, что их сложность растёт экспоненциально сложности задачи, и отлаживать и редактировать выражения типа такого (отсюда)
"~^(,[ \\t]*)*([!#$%&'*+.^_`|~0-9A-Za-z-]+=([!#$%&'*+.^_`|~0-9A-Za-z-]+|\"([\\t \\x21\\x23-\\x5B\\x5D-\\x7E\\x80-\\xFF]|\\\\[\\t \\x21-\\x7E\\x80-\\xFF])*\"))?(;([!#$%&'*+.^_`|~0-9A-Za-z-]+=([!#$%&'*+.^_`|~0-9A-Za-z-]+|\"([\\t \\x21\\x23-\\x5B\\x5D-\\x7E\\x80-\\xFF]|\\\\[\\t \\x21-\\x7E\\x80-\\xFF])*\"))?)*([ \\t]*,([ \\t]*([!#$%&'*+.^_`|~0-9A-Za-z-]+=([!#$%&'*+.^_`|~0-9A-Za-z-]+|\"([\\t \\x21\\x23-\\x5B\\x5D-\\x7E\\x80-\\xFF]|\\\\[\\t \\x21-\\x7E\\x80-\\xFF])*\"))?(;([!#$%&'*+.^_`|~0-9A-Za-z-]+=([!#$%&'*+.^_`|~0-9A-Za-z-]+|\"([\\t \\x21\\x23-\\x5B\\x5D-\\x7E\\x80-\\xFF]|\\\\[\\t \\x21-\\x7E\\x80-\\xFF])*\"))?)*)?)*$"
лично мне не особо интересно. Особенно учитывая то, что автоматное программирование использовать регэкспы никак не запрещает, равно как и другие вспомогательные инструменты для синтаксического разбора.
В четверг сдавал ЕГЭ по информатике.
Несколько задач решил практически одной строчкой регекса, потратив на каждую по паре минут.
Мне кажется, что эта статья больше документации по re. Практически никто (исключения есть везде) не пишет гигантские и непонятные регекспы. Все, что я встречал и использовал в многолетней практике, это очень лаконичные шаблоны в одну не длинную строчку, которая сразу интерпретировалась мозгом. Ну, реально, выучить базу re и потренироваться чтоб отложилось в памяти, это день. Никто ж не заставляет их тулить везде, но там где они к месту, гораздо удобнее чем прыгать глазами по вызовам новых (которые надо изучать) функций написанных программистом, которому пренепременно надо сделать без ре
Приходится часто писать regexp для разбора различных security-logs в SIEM-системах.
Частенько логи сделаны так, что одно и тоже значение надо вытаскивать из разных мест, в зависимости от окружающего контекста, и тогда регекс становится негуманным для мозга.
Но видать лучше ничего человечество пока не придумало, так что навык писать и читать регексы считай что базовый.
К сожалению, на самом деле это не работает, потому что в нашей методике
парсинга используется поиск с возвратом, особенно при принятии решения в
функциях either(), maybe() и choice(). При обработке either()
парсинг какое-то время может выполняться успешно, а потом внезапно
завершиться неудачно. Когда такое происходит, всё откатывается назад и
проверяется другая ветвь парсинга.
Поиск с возвратом можно написать с использованием continuations, но они не включены в штатный питон, тут stackless python в помощь.
Не любите регекспы? Да вы просто не умеете их готовить!
import re
DIGIT = '\d' # при желании
DOT = '\.' # эти две строчки можно и опустить.
INTEGER = f'{DIGIT}+'
FLOAT = f'{INTEGER}{DOT}(?:{INTEGER})?|{DOT}{INTEGER}'
NUMBER = f'^((?P<integer>{INTEGER})|(?P<float>{FLOAT}))$'
m = re.match(NUMBER, '15')
m.groupdict()
# {'integer': '15', 'float': None}
m = re.match(NUMBER, '15.2')
m.groupdict()
# {'integer': None, 'float': '15.2'}
m = re.match(NUMBER, '.15')
m.groupdict()
# {'integer': None, 'float': '.15'}
m = re.match(NUMBER, '1e3')
m is None
# True - при желании можно и это предусмотреть, тогда надо только поправить определение FLOAT.
PS Если такая запись кажется сложной:
FLOAT = f'{INTEGER}{DOT}({INTEGER})?|{DOT}{INTEGER}' то её можно разбить на две части:
F1 = f'{INTEGER}{DOT}(?:{INTEGER})?'
F2 = f'{DOT}{INTEGER}'
FLOAT = f'{F1}|{F2}' проще некуда.
это ужасно.
Если вам нужно сравнивать является ли что-то числом, надо не делать макросы на регулярках, а написать функцию и спрятать регулярки в их родном виде внутри.
Или поискать есть ли что-то вроде isDigit в вашем языке программирования
is_digit пропустит флоат, равно как и отрицательное число в питоне. Так что если бы числа были бы отрицательными, то пользы от этой функции было бы меньше.
изначальная задача была парсить ключ-значение, где значение - число, целое или вещественное, при том нам очень хочется отличать целое цисло от вещественного. Регулярки делают тоже самое похожим образом без необходимости самому писать парсер. Просто не стал добисывать полный вариант разбора.
Да, можно сделать что-то типа try:int(v) except: try: float(v) except: riase ValueError(). Почему бы и нет, совершенно другой подход.
Я писал это скорее как демонстрацию к более общему случаю. Любую трёхэтажную регулярку можно разбить на несколько частей, внятно их задокументировать (в т.ч. названием переменной) и проблем с пониманием того, что же это такое, не возникнет. Также поддержка такой регулярки не будет проблемой по той же самой причине.
Если вы отказались от регулярных выражений, то теперь у вас три проблемы