On Tue, Oct 11, 2022 at 9:02 AM Martin D Kealey <mar...@kurahaupo.gen.nz> wrote:
> Broadly I meant translating into a "preferably" Deterministic > (stackless/non-backtracking) Finite State Automaton. > > However I note that it's not always possible to make a Deterministic FSA > when you have repeatable groups which themselves don't have fixed lengths > (like a+(a|abbba|aabb*aba)b); either the extglob compiler would need to > start over and compile to a Non Deterministic (stacking) FSA, or just give > up and go back to the recursive approach. > > Personally I would favour the addition of «shopt -s dfa_extglob» that > would block the fall-back, causing extglobs that would need a stack to be > treated as magic match-never tokens. > > I say "extglob", but this would also speed up silly ordinary globs like > [a-z]*[a-z]*[a-z]*[a-z]*[a-z]*[a-z]*[a-z]*[a-z]*[a-z]*[a-z]*[a-z]*[a-z]*[a-z] > > -Martin > > Ok I see, that's true that when you see a glob pattern like +(a) one would think an optimiser could make it backtrack less. «shopt -s dfa_extglob» could be an option, Chet may say it is hard to explain when to use it... but we can go this path too, that is less of a hack regarding stack provision, but more of a hack regarding the extglob compiler :) Any implementation will please me :)