Comment Comment by adev_ > 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 parent adev_ 2 months ago
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