Also, like other people already have pointed out, the time complexity calculations in the academic literature are not always relevant for practical parsing:
1) A parser that might have exponential-time complexity might still beat a polynomical/linear-time complexity parser in practice, depending on the grammar and actual code parsed.
2) For real-world grammars, constants (i.e. the c in O(c*n)) will be the determining factor between two alternative parsing techniques with identical time-complexity. As an example, memoization-based (packrat) parsing in combination with PEG achieves the same time complexity as shift-reduce style parsers for many grammars, but in practice the memory allocations and bookkeeping required to do the memoization make the latter approach much faster.
I have implemented several different parsers myself, and while it is pretty straightforward to write a parser for a real-world language (e.g. Python) today, achieving very good parsing speed is not. As an example, on my machine, the Python parser can process about 100-300k lines of code per second (including AST generation) while a comparable packrat PEG parser is slower by a factor of 5-10 (for many use cases, parsing at 10.000 loc / second is still good enough though, but it should not be considered fast)
1) A parser that might have exponential-time complexity might still beat a polynomical/linear-time complexity parser in practice, depending on the grammar and actual code parsed.
2) For real-world grammars, constants (i.e. the c in O(c*n)) will be the determining factor between two alternative parsing techniques with identical time-complexity. As an example, memoization-based (packrat) parsing in combination with PEG achieves the same time complexity as shift-reduce style parsers for many grammars, but in practice the memory allocations and bookkeeping required to do the memoization make the latter approach much faster.
I have implemented several different parsers myself, and while it is pretty straightforward to write a parser for a real-world language (e.g. Python) today, achieving very good parsing speed is not. As an example, on my machine, the Python parser can process about 100-300k lines of code per second (including AST generation) while a comparable packrat PEG parser is slower by a factor of 5-10 (for many use cases, parsing at 10.000 loc / second is still good enough though, but it should not be considered fast)