I read about LL(1), LR(0), SLR(1) and LALR(1) in many online sources and even in dragon book. However I found that no one talks about LL(0), SLR(0) and LALR(0). So I googled and come up against these two links which talk about LL(0): 1 and 2. These answers are quite satisfiable in explaining LL(0) grammars. However I still dont find anything on SLR(0) and LALR(0). Do they even exist? If yes, in what form?

  • $\begingroup$ Without lookahead, there's no difference between LR algorithms. (But it's pretty common to call the no-lookahead version SLR(0).) $\endgroup$ – rici Jun 28 '19 at 19:58
  • $\begingroup$ Do you mean to say LR(0) = SLR(0) = LALR(0)? Also I never read anyone refer non lookahead version as SLR(0). I guess even dragon book explains SLR(1) in which it puts reduce moves in the columns corresponding to $FOLLOW$ of left hand sides of final items / productions (that is $A\rightarrow B.$ goes in columns corresponding to $FOLLOW(A)$) of LR(0) automaton. In LR(0) parser, reduce moves goes in whole row corresponding to $A$. Is it (LR(0) parser) what you refer to as no-lookahead version and refer to it as SLR(0) instead? $\endgroup$ – anir Jun 28 '19 at 20:25
  • 1
    $\begingroup$ Yes, all the *LR(0) algorithms are identical. So LR(0) and SLR(0) are the same. Without lookahead, if a reduce is possible it must be required, otherwise there is a conflict. So the whole row is either (the same) reduce, or all shifts and errors. If you ran an algorithm with some lookahead, you might find that some reduce actions turn into error actions. But if there's no lookahead, you have to wait until you reach a state with an error action on that shift. $\endgroup$ – rici Jun 28 '19 at 23:00
  • $\begingroup$ Need more clarification about. (1) "So the whole row...shifts and errors."- as in case of state 0,2,3 in this example? (2) "If you ran ... (till end of comment)": Are u referring to fact that parsers with lookaheads detect invalid string earlier by hitting error cell of parsing table for which non lookahead parsers might have done reduction. Non lookahead parsers flag errors late in the parsing when they fail to shift. (1) "Without lookahead, if a reduce is possible it must be required, otherwise there is a conflict." - didnt get italics. $\endgroup$ – anir Jun 29 '19 at 8:30
  • 1
    $\begingroup$ (1) Yes. Also row 1, because in this machine, accept is a kind of shift action. (2) Yes, again. Lookahead on a reduce action can indicate that the reduction is futile. But if you do the reduce anyway, the parser will eventually find that it can't shift. (3) If a reduce is possible and some other action is also possible, how do you decide? With lookahead, no? So if you have no lookahead, what do you have? A conflict! If that's not obvious, you need to think more clearly about what a conflict is. $\endgroup$ – rici Jun 29 '19 at 15:12

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Browse other questions tagged or ask your own question.