Hacker News Reader

Comment by ginko | Hacker News Reader

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.

View on HN

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).

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....

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.

> 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.

C# has compile-time precompiled regular expressions now, too. The enabling C# feature is source generators.

They are extremely fast too (way faster than re2): https://github.com/BurntSushi/rebar?tab=readme-ov-file#summa...

NOTE re2 is not the same as re2c here

re2 is Google's safe regexp engine that works as a state-machine and isn't suspectible to exponential runtime attacks that can affect backtracking engines, it trades some performance for guaranteed non-fatal worst case scenarios.

the C# compiled regexps is backtracking (fast by default) JIT compiled searchers so it's extremely fast (on the level of source-compiled matchers).

Note that .NET has a non-backtracking engine now too. It's included in the rebar measurements.

Yeah noticed, just pointing out that it's not 2x faster (still faster though and that's impressive!).

I implemented an basic DFA based engine like re2 once as an exercise and there was a performance cost (and building it cost a bit) so I wonder if they JIT non backtracking variant also?

Not sure. But rust/regex (of which I am the author) is above pcre2/jit in rebar's measurements. Hyperscan is too. All of rust/regex, Hyperscan and RE2 use finite automata, no JIT and no backtracking.

There is more to the perf of a regex engine than whether it uses a JIT or not. :)

Many of the curated rebar benchmarks (in the README) do not just list numbers. They also try to contextualize those numbers. (I am only one person though with limited expertise, so they tend to bias toward what I know. But still, it's miles better than what you'll see in most benchmarks IMO.)

And of course, make sure to read the BIAS document.

Note that rebar doesn't include C#'s compile time regexes in the benchmark. The only reason it doesn't is because nobody has implemented it yet. In rebar's model, it will require writing a C# program that compiles another C# program. It's pretty annoying. It's the same reason why CTRE isn't in rebar either. There's nothing preventing it other than the work to make it happen.

This is correct but both source-generated and runtime-compiled regexes should be within the same ballpark performance-wise (if somewhat favoring the former) therefore it's worth a mention :)

Oh yeah absolutely. Sorry, I only meant to give a very narrow clarification. :-) I just didn't want folks thinking that rebar was providing measurements for C# compile time regexes. You're absolutely right that that might mean compile time regexes are even faster than what rebar reports.

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

- 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

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.

Indeed, it would be great as a language feature.

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

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.

Wouldn't the hand-written one be more work to write and measurably slower than the re2c-generated one?

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).

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.

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.

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.

Reply on news.ycombinator.com