7 ms·

I often wonder if the existence of lexer and parser generator tools like this is indicative that common general purpose languages are lacking the expressiveness

by ginko 3y ago

I often wonder if the existence of lexer and parser generator tools like this is indicative that common general purpose languages are lacking the expressiveness to implement things like this directly. I feel like parsing is common enough that this could be a language feature or a core library making use of higher-level language functionality.

megous 3y ago
Indeed, it would be great as a language feature.
- emmanueloga_ 3y ago
  See Raku's grammars [1], probably the most direct language support for parsing in a mainstream language (errr... or lang that _wants_ to be mainstream :-). -- 1: https://docs.raku.org/language/grammars https://docs.raku.org/language/grammars
dist1ll 3y ago
I suspect that lexer generators mostly exist because that's what people who want to implement compilers are being taught. But there's nothing difficult about writing a lexer. It can be done in less than 100 LoC, easily half that if your language has good string ergonomics and support for pattern matching.
- remexre 3y ago
  Wouldn't the hand-written one be more work to write and measurably slower than the re2c-generated one?
  - dist1ll 3y ago
    It's really not much work, and it removes another source of dependency/build bloat. Also, if you care about speed, hand-rolling your lexer will always be the fastest (and even naive implementations can rival/outcompete generators).
    - ceronman 3y ago
      Not only that, but a manually written lexer has much more flexibility. It allows you to easily implement things that lexer generators struggle with. Think of significant indentation, nested comments, interpolation inside string literals. Sometimes you can't do this at all with generators, sometimes you can, but code becomes a mess. That's the reason why many popular programming language implementations use a hand written lexer and parser.
      - fanf2 3y ago
        re2c makes it easy to drop into hand-written code where necessary. For example, in C backslash-newline makes a huge mess of everything unless you can handle it underneath the lexer, which works nicely in re2c. In C++, raw string literals are not even context-free, let alone regular, so they have to be parsed with hand-written code. This is straightforward with re2c.
- o11c 3y ago
  The problem with hand-written lexers/parsers (and some generated parsers, notably PEG these days) is that you have no idea if you can actually trust it. There are so many weird edge cases for lexing and parsing that I would never dare to do it without machine verification.
whizzter 3y ago
It's historically a regular expression compiler for C (hence re2c), C (and C++ until recently) didn't include a Regular Expression engine. I used an earlier version of re2c for one project since it was a far easier to get started with compared to lex/flex (that iirc also wasn't object local/thread safe in the past). Perl, Javascript, Java, C#,etc all include regexp engines these days so you can quickly build an abstraction that provides roughly what re2c gives. One huge benefit of re2c style generators still have however is that they're precompiled and quite efficient compared to generic regexp libraries if performance matters. If you want something like re2c with the same performance the target language would first require macro or precompiled facilities (iirc there are C++ regexp systems now that are compile-time compiled and should have similar performance to re2c).
- fanf2 3y ago
  C on Unix and POSIX has had regular expressions in the standard library since the 1980s https://pubs.opengroup.org/onlinepubs/007908799/xsh/regex.h.html https://pubs.opengroup.org/onlinepubs/007908799/xsh/regex.h....
  - whizzter 3y ago
    Still not the language, would be interesting to know why someone pushed this to POSIX and didn't propose it for the language. Today Windows is the biggest non-POSIX system remaning afaik (apart from Android and consoles) but back in the 80s and 90s there was MacOS, STOS, AmigaOS,etc so saying it was in Unix/POSIX has little connection to the language at large.
- ginko 3y ago
  > If you want something like re2c with the same performance the target language would first require macro or precompiled facilities. Yeah, I think you could build something like that in Zig with comptime.
- electroly 3y ago
  C# has compile-time precompiled regular expressions now, too. The enabling C# feature is source generators.
whiterknight 3y ago
Different tasks are best served by a different mode of evaluation, not just a library. This is why the lisp community advocates a many DSL design approach.
chubot 3y ago
After using re2c, I actually think it should have been built into C. Why? - Because Ken Thompson was co-inventor of C, and he ALSO brought regular languages to computing. IIRC he basically wrote the first version of grep, and compilers like re2c use the same automata-based methods as the original grep. https://www.oilshell.org/archive/Thompson-1968.pdf https://www.oilshell.org/archive/Thompson-1968.pdf - Because C is really bad at string processing. Regular languages would be a huge improvement. Looking through the implementation of most shells should convince of you that. Thompson also wrote the very first Unix shell, of course! https://www.oilshell.org/blog/2021/08/history-trivia.html https://www.oilshell.org/blog/2021/08/history-trivia.html

by ginko 3y ago

megous 3y ago

Indeed, it would be great as a language feature.

emmanueloga_ 3y ago
See Raku's grammars [1], probably the most direct language support for parsing in a mainstream language (errr... or lang that _wants_ to be mainstream :-). -- 1: https://docs.raku.org/language/grammars https://docs.raku.org/language/grammars

dist1ll 3y ago

I suspect that lexer generators mostly exist because that's what people who want to implement compilers are being taught. But there's nothing difficult about writing a lexer. It can be done in less than 100 LoC, easily half that if your language has good string ergonomics and support for pattern matching.

remexre 3y ago
Wouldn't the hand-written one be more work to write and measurably slower than the re2c-generated one?
- dist1ll 3y ago
  It's really not much work, and it removes another source of dependency/build bloat. Also, if you care about speed, hand-rolling your lexer will always be the fastest (and even naive implementations can rival/outcompete generators).
  - ceronman 3y ago
    Not only that, but a manually written lexer has much more flexibility. It allows you to easily implement things that lexer generators struggle with. Think of significant indentation, nested comments, interpolation inside string literals. Sometimes you can't do this at all with generators, sometimes you can, but code becomes a mess. That's the reason why many popular programming language implementations use a hand written lexer and parser.
    - fanf2 3y ago
      re2c makes it easy to drop into hand-written code where necessary. For example, in C backslash-newline makes a huge mess of everything unless you can handle it underneath the lexer, which works nicely in re2c. In C++, raw string literals are not even context-free, let alone regular, so they have to be parsed with hand-written code. This is straightforward with re2c.
o11c 3y ago
The problem with hand-written lexers/parsers (and some generated parsers, notably PEG these days) is that you have no idea if you can actually trust it. There are so many weird edge cases for lexing and parsing that I would never dare to do it without machine verification.

whizzter 3y ago

It's historically a regular expression compiler for C (hence re2c), C (and C++ until recently) didn't include a Regular Expression engine. I used an earlier version of re2c for one project since it was a far easier to get started with compared to lex/flex (that iirc also wasn't object local/thread safe in the past). Perl, Javascript, Java, C#,etc all include regexp engines these days so you can quickly build an abstraction that provides roughly what re2c gives. One huge benefit of re2c style generators still have however is that they're precompiled and quite efficient compared to generic regexp libraries if performance matters. If you want something like re2c with the same performance the target language would first require macro or precompiled facilities (iirc there are C++ regexp systems now that are compile-time compiled and should have similar performance to re2c).

fanf2 3y ago
C on Unix and POSIX has had regular expressions in the standard library since the 1980s https://pubs.opengroup.org/onlinepubs/007908799/xsh/regex.h.html https://pubs.opengroup.org/onlinepubs/007908799/xsh/regex.h....
- whizzter 3y ago
  Still not the language, would be interesting to know why someone pushed this to POSIX and didn't propose it for the language. Today Windows is the biggest non-POSIX system remaning afaik (apart from Android and consoles) but back in the 80s and 90s there was MacOS, STOS, AmigaOS,etc so saying it was in Unix/POSIX has little connection to the language at large.
ginko 3y ago
> If you want something like re2c with the same performance the target language would first require macro or precompiled facilities. Yeah, I think you could build something like that in Zig with comptime.
electroly 3y ago
C# has compile-time precompiled regular expressions now, too. The enabling C# feature is source generators.

whiterknight 3y ago

Different tasks are best served by a different mode of evaluation, not just a library. This is why the lisp community advocates a many DSL design approach.

chubot 3y ago

After using re2c, I actually think it should have been built into C. Why? - Because Ken Thompson was co-inventor of C, and he ALSO brought regular languages to computing. IIRC he basically wrote the first version of grep, and compilers like re2c use the same automata-based methods as the original grep. https://www.oilshell.org/archive/Thompson-1968.pdf https://www.oilshell.org/archive/Thompson-1968.pdf - Because C is really bad at string processing. Regular languages would be a huge improvement. Looking through the implementation of most shells should convince of you that. Thompson also wrote the very first Unix shell, of course! https://www.oilshell.org/blog/2021/08/history-trivia.html https://www.oilshell.org/blog/2021/08/history-trivia.html