The one-more-re-nightmare compiler
one-more-re-nightmare is a pretty fast regular expression engine. The most recent versions use a new technique for producing Mealy machines, and benefit greatly from SIMD-accelerated substring search. However, I had initially started programming one-more-re-nightmare to study outside of university classes on automata, since the classes moved very slowly, and did not expect to produce a fast regula
Regex affordances
Python regexes have a number of features that bring new power to text manipulation. I’m not talking about fancy matching features like negative look-behinds, but ways you can construct and use regexes. As a demonstration, I’ll show you some real code from a real project. Coverage.py will expand environment variables in values read from its configuration files. It does this with a function called s
Matching Regexps 200 Times Faster
You might have seen @byroot’s excellent blog post series on optimizing the json gem. From the first blog post it’s clear most of the time for generating JSON is spent in generate_json_string() and specifically in convert_UTF8_to_JSON(), i.e., in converting Ruby Strings to JSON Strings. Because this is such a hot part of JSON generation, it has received a lot of attention. In part 3 @byroot shows a
「7」の倍数を表す正規表現の解説 - Panda Noir
「7の倍数」を表す正規表現 #正規表現 - Qiita ↑この記事について、「2進数だったら現実的なサイズの正規表現で書けそう」と思ったので書いてみます おさらい: 7の倍数かを判定するオートマトン 7の倍数であるというのは、言い換えると 7で割ったときにあまりが0である ということです。これをもとに、ある数字を7で割ったときの余りを状態に持つオートマトンを考えます。このオートマトンは状態が0のときに受理状態になります(=7の倍数)。 このオートマトンの遷移には筆算の考え方が使えます。筆算ではまず一番上の桁をみて7で割り、そのあまりを10倍して次の桁での計算に利用していく、という流れです。それをもとにオートマトンを書いてみるとこんな感じになります。 12345 を 7で割ってみる オートマトンの状態に1 mod 7を格納 (状態: 1) 状態を10倍して、次の桁を足す (状態: 1*10
Bad Apple but it's 6,500 regexes that I search for in vim · eieio.games
Why should I leave vim to watch a video? Jan 10, 2025 Well the title of this post promised you Bad Apple in vim only using search queries. So here’s Bad Apple in vim, but the only thing that’s changing is the search query: Let’s talk about how this works! Wait, sorry, what is Bad Apple Bad Apple is a visually compelling music video that folks enjoy embedding in surprising places. It’s a meme in th
Regex Chess: A 2-ply minimax chess engine in 84,688 regular expressions
let regex_list = [/* a very long list of regular expressions */] let board = "rnbqkbnr / pppppppp / 8 / 8 / 8 / 8 / PPPPPPPP / RNBQKBNR w KQkq - 0 1"; for (regex of regex_list) { board = re.replace(regex.pattern, regex.target) } display(board) By the end of this post you'll (hopefully) understand why this sequence of regular [a] Now some snobby people when they see this are going to say something
Steven Kalt
SummaryThis is a cautionary tale about how I ended up writing a (bad) regular expression parser and evaluator in pure TypeScript types. type HexStr<S extends string> = Recognize<"[0-9a-fA-F]+", S>; type IsMatch<S extends string> = HexStr<S> extends S ? true : false; const isHex: IsMatch<"deadbeef"> = true const notHex: IsMatch<"nope"> = false The novelty here is parsing and evaluating regular expr
making regex from scratch in GO
Making Regex From Scratch in GoThis series is a step by step guide to creating an (almost) fully fledged Regex engine using Go. It explores the basics of Finite State Automata, incrementally creates a parser and compiler for turning strings into state machines, walks through the setup of a visualizer for the FSM node graph. All of the development is structured as a TDD project, and uses modern Go
Needle: A DFA Based Regex Library that Compiles to JVM ByteCode
Needle: A DFA Based Regex Library that Compiles to JVM ByteCode Many years ago, Kragen complained about the implementation and performance of Java regexes, and suggested that an implementation that emitted JVM bytecode could perform better. It's been a minute, but I'm happy to report that complaining on the Internet has served its purpose. Today, I'm releasing the 0.0.1 version of needle, a librar
Regexide
Why XML Comments matter XML is a popular format for storing and sharing data. It was explicitly designed for people and programs to read and write data.[1] From spreadsheets to save states, most modern software and games parse and write XML. XML comments are special notes that parsers should not treat as data. XML comments start with <!-- and end with -->. Technically XML comments must not contain
Regex character “$” doesn't mean “end-of-string”
Published 2024-03-09 by Seth Larson ★ Reading time: 1 minute This article is about a bit of surprising behavior I recently discovered using Python's regex module (re) while developing SBOM tooling for CPython. Folks who've worked with regular expressions before might know about ^ meaning "start-of-string" and correspondingly see $ as "end-of-string". So the pattern cat$ would match the string "lol
はじめに - 作って学ぶ正規表現エンジン
はじめに 正規表現は様々なプログラミング言語で利用されている、テキスト処理のためのパターン言語です。 正規表現はテキストエディタでの検索や置換、入力文字列のバリデーションなどプログラミングの様々な分野で実用されています。 ある程度の規模のプログラムにおいて、正規表現を全く利用しない (利用していない) ということはほとんど無く、正規表現は今日のプログラミングにおいて非常に重要なパーツだと言えます。 JavaScriptやRubyといったプログラミング言語では正規表現はファーストクラスのリテラルとして実装されているため、とても簡単に利用できます。 例えば次のRubyプログラミングでは変数fooに入った文字列の部分にfizzかbuzzが含まれるかどうかを、正規表現/fizz|buzz/を使ってチェックしています。 foo =~ /fizz|buzz/ さらに、計算機科学 (コンピューターサイエ
アイヌ語仮名「ㇷ゚」に対する正規表現の罠
導入 アイヌ語は日本語と異なり、閉音節（子音で終わる音節）も存在するので、表記の際音素文字であるラテン文字なら、そのまま p, t, k, m, n, s, r などの子音文字を後ろの付ければ良いわけなので、アイヌ語ローマ字表記では、何も問題が生じない。しかし、元々開音節言語である日本語に特化したカタカナのような仮名文字で表記する際、鼻音 n は「ン」でなんとかなる（実はそれでもまずい事になっているけどここでは割愛する）が、p, t, k, m, n, s, r, h はどうしようもないので、特殊の捨て仮名（小書き仮名文字）を利用することになっている。 具体的には以下のような特殊仮名文字（通称 アイヌ語仮名）である。 ㇷ゚ -p ッ -t ㇰ -k ㇺ -m ㇱ -s ㇻ -(a)r, ㇼ -(i)r, ㇽ -(u)r, ㇾ -(e)r, ㇿ -(o)r お分かり頂けただろうか… 問題 r
Pike VMとEarley法の関係についてRubyで実装して考えてみる | makenowjust-labs/blog
正規表現マッチングの実装手法の1つとしてPike VMと呼ばれるものがあります。 これはGo言語の正規表現実装やRustのregex crateで使われている手法であり、正規表現rrrと入力文字列wwwに対してO(∣r∣×∣w∣)O(|r| \times |w|)O(∣r∣×∣w∣)の計算量でマッチングができるのが特徴です。 Earley法はJay Earleyの提案した文脈自由文法 (CFG) の構文解析手法の1つです。 すべてのCFGを構文解析できる手法で最悪計算量はO(∣w∣3)O({|w|}^3)O(∣w∣3)ですが、無曖昧であればO(∣w∣2)O({|w|}^2)O(∣w∣2)で、決定的であればO(∣w∣)O({|w|})O(∣w∣)で構文解析ができます。 実装してみると分かりますが、Pike VMとEarley法には類似している点があり、Earley法をPike VMの発展系の
正規表現とは何なのか、makenowjustが正規表現に興味を持ったきっかけ。深掘りRubyKaigi 2023 with spikeolaf & makenowjust 文字起こしレポート vol.1 - STORES Product Blog
2023年6月15日に『深掘りRubyKaigi 2023 with spikeolaf & makenowjust』を開催しました。イベントの内容をほぼ全文文字起こし形式でお届けします。この記事は第1部です。 hey.connpass.com イベントのアーカイブはYouTubeでも公開しています。 www.youtube.com 登場人物 ゲスト makenowjust/藤浪 大弥さん spikeolaf/金子 雄一郎さん STORES fujimura/藤村 大介 shyouhei/卜部 昌平 hogelog/小室 直 正規表現に興味を持ったきっかけ fujimura：最初は藤浪さん、makenowjustさんに正規表現の発表について伺おうと思います。まずは改めてRubyKaigi 2023でどんなことを発表したかを紹介いただけないでしょうか？ makenowjust：Rubyの正規
Regex engine internals as a library - Andrew Gallant's Blog
Over the last several years, I’ve rewritten Rust’s regex crate to enable better internal composition, and to make it easier to add optimizations while maintaining correctness. In the course of this rewrite I created a new crate, regex-automata, which exposes much of the regex crate internals as their own APIs for others to use. To my knowledge, this is the first regex library to expose its interna
プログラム中の文字列抽出機能を自動修正する技術を世界に先駆けて実現～専門知識をもたない開発者でも正規表現の修正が容易に～ | ニュースリリース | NTT
日本電信電話株式会社（本社：東京都千代田区、代表取締役社長：島田 明、以下「NTT」）と学校法人早稲田大学（本部：東京都新宿区 理事長：田中愛治 以下、「早稲田大学」）は、情報漏洩やサービス停止の原因となりうる文字列抽出機能の誤りを自動修正する技術を世界で初めて実現しました。Webサービスにおけるユーザの入力値などから任意の文字の並び（文字列）を抽出する場合、一般的に文字列パターンを表すために正規表現（※1）と呼ばれる記法が利用されています。正規表現は複雑な文字列パターンを簡潔に記述可能である反面、非常に難解であり、誤った記述が修正されないまま残っている事例が確認されています。 本技術により、専門知識を持たない開発者でも正規表現の誤りを自動修正することが可能になるため、安全なサービスの実現が期待できます。 本技術の詳細は、2023年6月17日に開催されるプログラミング言語分野の最難関国際会
リリース、障害情報などのサービスのお知らせ
最新の人気エントリーの配信
j次のブックマーク
k前のブックマーク
lあとで読む
eコメント一覧を開く
oページを開く
Fast(er) regular expression engines in Ruby
How on Earth does ^.?$|^(..+?)\1+$ produce primes?
Regex Isn't Hard - Tim Kellogg