Famous examples: despite so many initial good intentions, html tags don’t need to be closed, JSON numbers are too often encoded as strings, YAML can look like what most people expect or it can look progressively more like JSON… and on and on.
If what you're parsing is within the capacity of humans to interact with (so in the range of tens of kilobytes), a grammar that requires an O(N^2) parser is totally fine.
A simple recursive-descent parser is easy to write by hand and runs in linear time.
I'd be quite surprised if an optimizing compiler generated C++ code somewhere in its pipeline!
https://felix-lang.github.io/felix/
Ignore the 'scripting' language claim.
I do have to wonder though - do you know what proportion of the C++ compiler time is spent parsing your generated C++ code vs. optimizing it?
Felix is quite old at this point. It's a very interesting language, with many interesting ideas. It did not quite take off though.
It has many other interesting capabilities, for example, the ability to change its own grammar, that is rather too much, not for a pleb like me. It has unique (linear and affine) types too. It is really quite a handful.
Go did bring coroutines back into limelight but Felix predates Go by a margin.
Skaller, Felix's author, used Felix as a playground for novel language design ideas, so it was always in a state of flux.
This would be a good starting point. More in the manual.
In the face of backtracking the time depends on the complexity of the grammar, since it's basically a brute force search through all the rules.
Recursive descenrs parsers are not linear.
They are generally O(n^2) and can even can go exponential with some grammars if written naively.
It can be pretty easy to do adverserival attacks on most naive descent parser and bring it to its knees.
Packrat parser [^1] are linear, but they are by no means "trivial 200 lines" type of parsers.
We spend years learning basic arithmetic like the addition of integers. You could very well argue that there is no need for that either because everyone has a calculator app on their phone. This is how dark ages begin.
If someone is taking malicious stabs at your API then you have a problem
What good is a perfect linear-time constant-space parser if the next thing the system does is to allocate hundreds of megabytes of objects representing some deserialized data structure?
The parser is usually the least interesting part.
There's a good reason for that, since JSON comes from JavaScript, many JSON parsers treat numbers as double-precision floats. By encoding your number as a string, you ensure that the JSON parser has not modified your number.
https://blog.json-everything.net/posts/numbers-are-numbers-n...
This is compounded by the fact that you need the semantics involved, the environment (ie: everything on scope), the source (that means you need to keep carrying big strings around).
And what is efficient means to be destructive, but you need instead the opposite for semantics, error messages, optimizations and the like.
That's a very explicit and much debated feature, even self closing tags. It is also one of the main factors that makes HTML distinct from xml. And a big reason why xhtml was created.
I agree that it makes for a much more complicated interpretation.