4 ms·

How does the "sets of strings" model express the difference between: /x/ and /x?/

How does the "sets of strings" model express the difference between: /x*/ and /x*?/

chubot 6y ago
Good question, and here's something I wrote a couple weeks ago to the author of the Regex Lingua Franca paper [1]: I admit I occasionally use non-greedy repetition in Python, but I think that is the only construct I use that's not in the shell-ish engines. I believe it's usually pretty easy to rewrite without non-greedy, but I haven't tested that theory. ---- OK so I started testing that theory. I collected all the times I used .*? https://github.com/oilshell/blog-code/blob/master/regular-languages/survey.txt https://github.com/oilshell/blog-code/blob/master/regular-la... With a cursory inspection, most of them are unnecessary in an automata-based "regular language" engine. They are "nice to have" in a Perl-style regex engine for PERFORMANCE. But automata-based engines don't have that performance problem. They don't backtrack. The distinction between .* and .*? doesn't affect whether it matches or not, by definition. It does affects how much it backtracks. (And it affects where the submatches are, which I need to test out) So I think most of my own usages ARE "nice to have" in Python, but unnecessary in awk because it uses an automata-based engine. But I'd like to look at it more carefully, and I'm interested in answering this question more thoroughly (feel free to contact me about it, e-mail in profile). I started a demo here. Still needs work. https://github.com/oilshell/blog-code/blob/master/regular-languages/greedy.sh https://github.com/oilshell/blog-code/blob/master/regular-la... ---- So here's another conjecture: regexes are bad because they force you to make UNNECESSARY DISTINCTIONS in the name of performance. You have to care about greedy vs. nongreedy, because there is backtracking. In contrast, with regular languages, you just write what you mean, and they do it quickly for you. You can't write a slow expression for a regular language. There are some caveats around that, like submatch extraction with nongreedy repetition, which I will test out. If anyone has specific examples or use cases, send them my way. I can't see where I really rely on nongreedy submatches, but I'll have to look more closely. I think the nongreedy use case is usually just "skip quickly until this other string appears", e.g. the one in pgen2/tokenize.py that I didn't write. ---- As far as I remember submatch extraction works fine in automata-based engines, and Cox's articles are in a large part about the (then) little known algorithms for doing it in automata-based engines. re2c also has a 2017 paper for their algorithm to do it in DFAs: http://re2c.org/2017_trofimovich_tagged_deterministic_finite_automata_with_lookahead.pdf http://re2c.org/2017_trofimovich_tagged_deterministic_finite... ---- [1] thread: https://news.ycombinator.com/item?id=23687478 https://news.ycombinator.com/item?id=23687478
- ridiculous_fish 6y ago
  I don't agree it's primarily about performance. /".+"/ will find a quoted string, but you will certainly prefer the non-greedy match instead. Now you may torture the greedy regex to make it work (/"[^"]+"/), but the point stands. "Did it match" is rarely enough; the regex author usually wishes to know where it matched, and to exercise control over which match is preferred if there are multiple possibilities. It's indeed possible to do this with DFAs but the theory is comparatively hard, as a cursory reading of your linked paper will show!
  - chubot 6y ago
    Yeah that is a good example, and I recorded it here: https://github.com/oilshell/blog-code/blob/master/regular-languages/greedy.sh#L44 https://github.com/oilshell/blog-code/blob/master/regular-la... I don't mind the rewrite, but I'm not surprised that some would be inconvienced by it. (Though that is part of the reason for the Eggex syntax) ---- On the other side I'll offer that I wrote a lexer for bash and all its sublanguages without any nongreedy repetitions. It's dozens if not hundreds of regexes. https://github.com/oilshell/oil/blob/master/frontend/lexer_def.py https://github.com/oilshell/oil/blob/master/frontend/lexer_d... Though, regular languages are more like a building block for the lexer than the lexer itself. As mentioned elsewhere, they're too limited to express the entire lexer. They're too limited to express syntax highlighters (but so are regexes! They also need some logic outside the model, e.g. for lexing shell here docs) ----- So I pose the question of whether there's a more powerful abstraction that's still linear time and constant space: http://www.oilshell.org/blog/2020/07/ideas-questions.html#more-powerful-linear-time-constant-space-languages http://www.oilshell.org/blog/2020/07/ideas-questions.html#mo... Of course there is, but it's a matter of picking one that will address a lot of use cases effectively. I think re2c has grown something like .*? for example. grep needs something like that too. Often you want to be able to skip input in a linear fashion, without invoking the pattern matching logic at all. Regexes are OK if you know how to use them, but evidently most people have lots of problems with them (the necessity of OP's demo being an example of that.) I think there's something better out there built on top of regular languages.
    - 6y ago
chubot 6y ago
Update: I tested it out a little more here. https://github.com/oilshell/blog-code/blob/master/regular-languages/greedy.sh#L61 https://github.com/oilshell/blog-code/blob/master/regular-la... Basically everything you want with regard to greedy-nongreedy can be done through automata-based engines. They jump through a lot of hoops to make them work! However I would also argue that when you're using them, you're doing it as a performance hack in a Perl-style regex engine. In an automata-based engine, you can just write /x*/ /(x*)/ and it's what you want, and it runs fast.

How does the "sets of strings" model express the difference between: /x*/ and /x*?/

Good question, and here's something I wrote a couple weeks ago to the author of the Regex Lingua Franca paper [1]: I admit I occasionally use non-greedy repetition in Python, but I think that is the only construct I use that's not in the shell-ish engines. I believe it's usually pretty easy to rewrite without non-greedy, but I haven't tested that theory. ---- OK so I started testing that theory. I collected all the times I used .*? https://github.com/oilshell/blog-code/blob/master/regular-languages/survey.txt https://github.com/oilshell/blog-code/blob/master/regular-la... With a cursory inspection, most of them are unnecessary in an automata-based "regular language" engine. They are "nice to have" in a Perl-style regex engine for PERFORMANCE. But automata-based engines don't have that performance problem. They don't backtrack. The distinction between .* and .*? doesn't affect whether it matches or not, by definition. It does affects how much it backtracks. (And it affects where the submatches are, which I need to test out) So I think most of my own usages ARE "nice to have" in Python, but unnecessary in awk because it uses an automata-based engine. But I'd like to look at it more carefully, and I'm interested in answering this question more thoroughly (feel free to contact me about it, e-mail in profile). I started a demo here. Still needs work. https://github.com/oilshell/blog-code/blob/master/regular-languages/greedy.sh https://github.com/oilshell/blog-code/blob/master/regular-la... ---- So here's another conjecture: regexes are bad because they force you to make UNNECESSARY DISTINCTIONS in the name of performance. You have to care about greedy vs. nongreedy, because there is backtracking. In contrast, with regular languages, you just write what you mean, and they do it quickly for you. You can't write a slow expression for a regular language. There are some caveats around that, like submatch extraction with nongreedy repetition, which I will test out. If anyone has specific examples or use cases, send them my way. I can't see where I really rely on nongreedy submatches, but I'll have to look more closely. I think the nongreedy use case is usually just "skip quickly until this other string appears", e.g. the one in pgen2/tokenize.py that I didn't write. ---- As far as I remember submatch extraction works fine in automata-based engines, and Cox's articles are in a large part about the (then) little known algorithms for doing it in automata-based engines. re2c also has a 2017 paper for their algorithm to do it in DFAs: http://re2c.org/2017_trofimovich_tagged_deterministic_finite_automata_with_lookahead.pdf http://re2c.org/2017_trofimovich_tagged_deterministic_finite... ---- [1] thread: https://news.ycombinator.com/item?id=23687478 https://news.ycombinator.com/item?id=23687478

ridiculous_fish 6y ago
I don't agree it's primarily about performance. /".+"/ will find a quoted string, but you will certainly prefer the non-greedy match instead. Now you may torture the greedy regex to make it work (/"[^"]+"/), but the point stands. "Did it match" is rarely enough; the regex author usually wishes to know where it matched, and to exercise control over which match is preferred if there are multiple possibilities. It's indeed possible to do this with DFAs but the theory is comparatively hard, as a cursory reading of your linked paper will show!
- chubot 6y ago
  Yeah that is a good example, and I recorded it here: https://github.com/oilshell/blog-code/blob/master/regular-languages/greedy.sh#L44 https://github.com/oilshell/blog-code/blob/master/regular-la... I don't mind the rewrite, but I'm not surprised that some would be inconvienced by it. (Though that is part of the reason for the Eggex syntax) ---- On the other side I'll offer that I wrote a lexer for bash and all its sublanguages without any nongreedy repetitions. It's dozens if not hundreds of regexes. https://github.com/oilshell/oil/blob/master/frontend/lexer_def.py https://github.com/oilshell/oil/blob/master/frontend/lexer_d... Though, regular languages are more like a building block for the lexer than the lexer itself. As mentioned elsewhere, they're too limited to express the entire lexer. They're too limited to express syntax highlighters (but so are regexes! They also need some logic outside the model, e.g. for lexing shell here docs) ----- So I pose the question of whether there's a more powerful abstraction that's still linear time and constant space: http://www.oilshell.org/blog/2020/07/ideas-questions.html#more-powerful-linear-time-constant-space-languages http://www.oilshell.org/blog/2020/07/ideas-questions.html#mo... Of course there is, but it's a matter of picking one that will address a lot of use cases effectively. I think re2c has grown something like .*? for example. grep needs something like that too. Often you want to be able to skip input in a linear fashion, without invoking the pattern matching logic at all. Regexes are OK if you know how to use them, but evidently most people have lots of problems with them (the necessity of OP's demo being an example of that.) I think there's something better out there built on top of regular languages.
  - 6y ago

chubot 6y ago

Update: I tested it out a little more here. https://github.com/oilshell/blog-code/blob/master/regular-languages/greedy.sh#L61 https://github.com/oilshell/blog-code/blob/master/regular-la... Basically everything you want with regard to greedy-nongreedy can be done through automata-based engines. They jump through a lot of hoops to make them work! However I would also argue that when you're using them, you're doing it as a performance hack in a Perl-style regex engine. In an automata-based engine, you can just write /x*/ /(x*)/ and it's what you want, and it runs fast.