GNU bug report logs - #29909
non-greedy matching (RE2)

Previous Next

Package: sed;

Reported by: Shawn Landden <slandden <at> gmail.com>

Date: Sat, 30 Dec 2017 17:18:02 UTC

Severity: wishlist

Done: Assaf Gordon <assafgordon <at> gmail.com>

Bug is archived. No further changes may be made.

Full log

View this message in rfc822 format

From: Shawn Landden <slandden <at> gmail.com>
To: 29909 <at> debbugs.gnu.org
Subject: bug#29909: non-greedy matching (RE2)
Date: Sat, 30 Dec 2017 05:01:12 -0800

It is well known that sed lacks non-greedy regular expression matches.
This means that sed can only match a subset of regular languages[1].
Would a proper patch to add re2 support[2], so that sed implements ALL
regular languages correctly, in O(n) time, be considered?

Thanks,

Shawn Landden

[1] https://en.wikipedia.org/wiki/Regular_language#Location_in_the_Chomsky_hierarchy
And because that link isn't very good, 28c3: The Science of Insecurity
https://www.youtube.com/watch?v=3kEfedtQVOY
[2] https://github.com/google/re2
This bug report was last modified 7 years and 205 days ago.

Previous Next

GNU bug tracking system
Copyright (C) 1999 Darren O. Benham, 1997,2003 nCipher Corporation Ltd, 1994-97 Ian Jackson.