On Tue, Oct 11, 2022 at 12:38:44PM -0700, Koichi Murase wrote:
> As far as I know, glob/extglob
> does not have constructs that cannot be represented by formal regular
> languages so should always be able to be represented by NFAs and thus DFAs.
It's been too many decades since I studied this stuff in college, but
earlier while reading the thread I was pondering converting extglobs
into (ERE) regular expressions.
Extglobs add 5 features:
?(pattern-list)
Matches zero or one occurrence of the given patterns
*(pattern-list)
Matches zero or more occurrences of the given patterns
+(pattern-list)
Matches one or more occurrences of the given patterns
@(pattern-list)
Matches one of the given patterns
!(pattern-list)
Matches anything except one of the given patterns
The first 4 can be converted directly into ERE without any issues at all.
The last one cannot. At least not easily.
The part I can't remember is whether !(foo) can be expressed in a regular
language. My gut says "no", but there might be some trick that I've
forgotten. A regular language has concatenation (abc), union (abc|def),
and close (a*bc*) but not negation.
