Computer Science Stack Exchange is a question and answer site for students, researchers and practitioners of computer science. It only takes a minute to sign up.
Sign up to join this community
What is the difference between time complexity of SLR(k) and SLR(1)? and also what about LALR(k) and LALR(1)?
How can I calculate time complexity of parsers? I think time complexity of LR(k) is O(n) but I'm not sure there is a relation between LR(k) and SLR(k) or LALR(k)!
They all run linear time with regards to input length ($O(n)$). The different algorithms have different memory trade offs for making it easier to write grammar for. That is not all grammars that work for LR(1) work for SLR for example. However LR(1) uses more memory than SLR which used to be a problem, but not really a problem anymore for modern machines.
LR(k) is rarely used. It hogs up an exponential amount of memory with regards to $k$. However any grammar for LR(k) can be rewritten for LR(1). And LR(1) handles all the languages LR(k) can, and vice versa. So most stick to LR(1) instead of LR(k).
LALR(1) uses less memory again than LR(1). And doesn't handle as many languages as LR(1) does. However LALR(1) is powerful enough to parse Java.
LALR(k) once again is a memory hog, and all grammar suitable for LALR(k) can be rewritten for LALR(1). And they can both handle the same languages as each other.
All of those shift reduce parsers mentioned do a fixed maximum amount of work (with regards to the grammar itself) for each token feed to them. So they are all $O(n)$.
If you going to implement one for sake of learning it, go with LR(1). Because the other algorithms are similar but with missing features (remove a feature to get the other implementation). Learning LR(1) first makes it easiest to learn them all imo.
