Bug 10496

Summary: lazy matches in regular expressions
Product: Busybox Reporter: Shawn Landden <slandden>
Component: OtherAssignee: unassigned
Status: NEW ---    
Severity: normal CC: busybox-cvs
Priority: P5    
Version: unspecified   
Target Milestone: ---   
Hardware: All   
OS: Linux   
Host: Target:
Build:

Description Shawn Landden 2017-11-17 10:54:43 UTC 
The lack of lazy matching in regular expressions makes certain regular languages impossible to parse. https://stackoverflow.com/a/39752929/8890015 but that only matches one occurrence.

TRE is a minimal library, 64KB in Debian amd64, that has the O(n) guarantee that all regular expressions engines SHOULD have, and supports lazy matching. I was told once that libc++ used TRE, but I can't find proof right now...

I am talking about:

.*?

https://github.com/laurikari/tre/

An example of something impossible to parse:

Foo: bar
Diz: harf

Two: newlines
Requires: lazymatches
When: number of keys
Is: variable

You: can't parse this
Without: lazy matches