3 ms·

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 tortu

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.
- ridiculous_fish 6y ago
  You hit upon an important cleavage: features vs worst-case perf. A generous lexer supports partial input, syntax highlighting, helpful error messages, etc., while a strict one is not so nice, but guarantees protection against malicious input. But the way you write these are very different! I also would like to write one lexer that can operate in both modes, but with one syntax. BTW, high five from one shell author to another :)
  - chubot 6y ago
    Yeah I've been looking at fish. Definitely has the cleanest code out of any shell I've looked at :) (e.g. bash, dash, zsh, mksh) And I came to realize what a huge effort it is on top of the language: http://www.oilshell.org/blog/2020/02/recap.html#fish-oil-is-a-good-idea-link http://www.oilshell.org/blog/2020/02/recap.html#fish-oil-is-... Also I wonder if you knew of the existence of ble.sh, a fish-like UI written in pure bash! I think it's the biggest shell program in the world: http://www.oilshell.org/cross-ref.html?tag=ble.sh#ble.sh http://www.oilshell.org/cross-ref.html?tag=ble.sh#ble.sh https://github.com/oilshell/oil/wiki/The-Biggest-Shell-Programs-in-the-World https://github.com/oilshell/oil/wiki/The-Biggest-Shell-Progr... ---- I did add little hack in the lexer for autocompletion of partial input. But my hope though is to keep most of that logic in the parser and not the lexer? Though it is true I was thinking of breaking up the exact regex we talked about for similar reasons, e.g. a single token: ' [^']* ' vs. 3 tokens ' [^']* ' I think the latter could be better for completion of paths in quotes, which bash does, but I haven't revisited it yet.

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.

ridiculous_fish 6y ago
You hit upon an important cleavage: features vs worst-case perf. A generous lexer supports partial input, syntax highlighting, helpful error messages, etc., while a strict one is not so nice, but guarantees protection against malicious input. But the way you write these are very different! I also would like to write one lexer that can operate in both modes, but with one syntax. BTW, high five from one shell author to another :)
- chubot 6y ago
  Yeah I've been looking at fish. Definitely has the cleanest code out of any shell I've looked at :) (e.g. bash, dash, zsh, mksh) And I came to realize what a huge effort it is on top of the language: http://www.oilshell.org/blog/2020/02/recap.html#fish-oil-is-a-good-idea-link http://www.oilshell.org/blog/2020/02/recap.html#fish-oil-is-... Also I wonder if you knew of the existence of ble.sh, a fish-like UI written in pure bash! I think it's the biggest shell program in the world: http://www.oilshell.org/cross-ref.html?tag=ble.sh#ble.sh http://www.oilshell.org/cross-ref.html?tag=ble.sh#ble.sh https://github.com/oilshell/oil/wiki/The-Biggest-Shell-Programs-in-the-World https://github.com/oilshell/oil/wiki/The-Biggest-Shell-Progr... ---- I did add little hack in the lexer for autocompletion of partial input. But my hope though is to keep most of that logic in the parser and not the lexer? Though it is true I was thinking of breaking up the exact regex we talked about for similar reasons, e.g. a single token: ' [^']* ' vs. 3 tokens ' [^']* ' I think the latter could be better for completion of paths in quotes, which bash does, but I haven't revisited it yet.