4 ms·
Strong disagree on his comments about performance, unless you know that your inputs will never be "big". Modern computers are fast yes, but modern data sets ar
by gameswithgo 6y ago
Strong disagree on his comments about performance, unless you know that your inputs will never be "big". Modern computers are fast yes, but modern data sets are also often massive. Thousands of lines a second is not good, its like 1% of what the hardware is capable of. For a personal project or as part of a product with constrained input sizes that may be fine but don't release that to the world for unknown input sizes.
- cellularmitosis 6y ago"Don't release this to the world" strikes me as a bit hyperbolic, because parsing is rarely the bottleneck. Considering editors, individual source files are typically (relatively) small, even in a large project. Considering compilers, parsing is already the smallest portion of the run-time anyway.
- formerly_proven 6y agoMaybe it's my bias, but in a lot of applications I touched parsing or unparsing (and/or the associated inefficient I/O) would often be the single largest consumer of CPU time.
- rstuart4133 6y agoAssuming you are using a deterministic algorithm, like a Deterministic Finite Automaton for regular expressions for your Type-0 languages (eg, the lexer), and something like LL/LR for the Type-1 languages, then processing time is always O(n), where n is the number of tokens in the input. In the end they are all just table driven state machines, with one lookup per input token. I don't see how they could be made much faster. When he says LR parsers were hard for old machines to handle he was referring to the generating the parsing table which happens once, when the parser itself is created.