Lex was a dog. Flex, which as far as I know was a complete rewrite
that shared no code with lex, are not bad.
Yes, "it's true what they say about lex" was a common phrase. (I think I
first saw it in the pathalias paper.)
There was a Usenix presentation -- late 80's (Washington?) but I couldn't
find it. -- by Vern Paxson about his rewrite called flex. I think he said
that the main reason lex was slow was the clever folding it had to do of
its internal tables to fit. Sadly Vern never got his paper in, but the
presentation showed a group with three lines, one at the top being slow
lex, the next two much lower on the Y axis being very close. He said the
second line was flex. Someone said what about the third, fastest, line? His
answer "that's cat"
Vern worked with Van on early network improvements (web-search the both of
them for a fun time).
Flex first posted to Usenet in 1988,
https://groups.google.com/g/comp.sources.unix/c/LZ_EHqd7XBg