6 ms·
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 par
by haileys 1mo ago
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.
- mhast 1mo agoI 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 1mo agoNot 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 1mo agoC++ 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 1mo ago> 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!
- pjmlp 1mo agoC++26 reflection?
- aw1621107 1mo agoOh, true! That's on me for not being specific enough. I was thinking about the optimization pipeline.
- srean 1mo agoTake a look at Felix. https://felix-lang.github.io/felix/ https://felix-lang.github.io/felix/ Ignore the 'scripting' language claim.
- aw1621107 1mo agoOh, 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 1mo agoUnfortunately 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 1mo agoWhat favorite feature(s) do you miss when working in other languages?
- srean 1mo agoCoroutines, 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 1mo agoHuh, 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!
- nly 1mo agoRecursive 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.
- adev_ 1mo ago> 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 https://arxiv.org/abs/cs/0603077