The hardest thing about writing a parser is cognitively accepting what is going to be considered valid input. You can make the best parser that is fast and well specified but invariably someone will (ab)use it in an unexpected way.

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.

▲

simonask 21 hours ago | parent | next [-]

I think the second-hardest thing is to accept that CS spent decades optimizing parsing algorithms and grammars, and this is still a significant part of CS curricula in many places. But the practical reality is that parsing is almost never a bottleneck.

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.

▲

bregma 20 hours ago | parent | next [-]

I don't think it is difficult to accept that fundamentals should be taught.

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.

	▲	sacado2 19 hours ago \| parent [-]
		It drives me crazy how so many people (of all ages) can't do basic math in their head, at least approximately. You need it constantly and it's so much faster than picking up your phone, starting the app, and typing in the operation. I'm so glad my teachers back in the 80s and 90s told me "you won't always have a calculator in your pocket". They were wrong (I do have one) but they were right (it's not always convenient to rely on a calculator).

▲

haileys 21 hours ago | parent | prev | next [-]

An O(n^2) parser is not fine for the mere reason that I don't know how one would make such a mess of the job in the first place.

A simple recursive-descent parser is easy to write by hand and runs in linear time.

▲

adev_ 20 hours ago | parent | next [-]

> A simple recursive-descent parser is easy to write by hand and runs in linear time.

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.

[^1]: https://arxiv.org/abs/cs/0603077

▲

nly 20 hours ago | parent | prev | next [-]

Recursive descent isnt guaranteed linear time

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.

▲

mhast 20 hours ago | parent | prev [-]

I think the point was that even if you managed to make a O(n*2) parser it will ve fast enough for human entered problems.

▲

srean 20 hours ago | parent [-]

Not for C++ code generated by whole program optimizing compilers. Your "human entered" is doing the heavy lifting. Now that AI is writing code your assertion might be on shaky ground.

▲

simonask 19 hours ago | parent | next [-]

C++ can be slow to compile, but as I said, parsing is not the bottleneck. Even for really huge automatically generated C++ files, or old-school concatenated "unity builds", the parsing step is generally tiny compared to everything else.

▲

aw1621107 19 hours ago | parent | prev [-]

> Not for C++ code generated by whole program optimizing compilers.

I'd be quite surprised if an optimizing compiler generated C++ code somewhere in its pipeline!

▲

srean 19 hours ago | parent | next [-]

Take a look at Felix.

https://felix-lang.github.io/felix/

Ignore the 'scripting' language claim.

▲

aw1621107 19 hours ago | parent [-]

Oh, that is certainly not what I was expecting at all. I stand corrected!

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?

▲

srean 19 hours ago | parent [-]

Unfortunately no.

Felix is quite old at this point. It's a very interesting language, with many interesting ideas. It did not quite take off though.

▲

aw1621107 18 hours ago | parent [-]

What favorite feature(s) do you miss when working in other languages?

▲

srean 18 hours ago | parent [-]

Coroutines, cooperative threading using fibres, type classes, generics, type deduction, easy interface with C++. The functional style, pattern matching. Flow based programming using 'chips and wires' abstraction.

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.

▲

aw1621107 15 hours ago | parent [-]

Huh, that does sound like quite the grab bag of features. Think I'll have to find time to further investigate. Thanks for taking the time to elaborate!

	▲	srean 12 hours ago \| parent [-]
		https://felix-tutorial.readthedocs.io/en/latest/ This would be a good starting point. More in the manual.

▲

pjmlp 19 hours ago | parent | prev [-]

C++26 reflection?

	▲	aw1621107 19 hours ago \| parent [-]
		Oh, true! That's on me for not being specific enough. I was thinking about the optimization pipeline.

▲

nly 20 hours ago | parent | prev [-]

It's "fine" is you ignore adversarial situations.

If someone is taking malicious stabs at your API then you have a problem

	▲	simonask 19 hours ago \| parent [-]
		Yeah, absolutely. I would be worried about a JSON parser facing the internet that had these kinds of problems, for example. But it's only the very first in a long line of potential vulnerabilities such a system has to consider. 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.

▲

craftkiller 18 hours ago | parent | prev | next [-]

> JSON numbers are too often encoded as strings

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

▲

mamcx 16 hours ago | parent | prev | next [-]

And harder than that? Report the error, in a way that make some sense.

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.

▲

trashb 19 hours ago | parent | prev | next [-]

> html tags don’t need to be closed

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.

▲

microgpt 20 hours ago | parent | prev [-]

[flagged]