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
I am talking in reference to this question from this compiler test. I think it is actually true that a GOTO and REDUCE can't be present in the same set, but am having a hard time coming up with an example or counterexample.
Pls provide and example and explanation to make me understand.
This isn't what you asked, but let me start by saying that I suspect the answer they're looking for in the question you link is (D), "A LR(0) parser can parse any regular grammar".
That statement is clearly false; an LR(0) grammar can only parse languages with the "prefix property", which holds if no sentence in the language is a prefix of another sentence in the language. Many regular languages do not have the prefix property, including, for example, $\{a, aa\}$. (You can create an augmented language by adding an explicit end-of-input marker –conventionally written $\\\$$– to the end of every sentence. The language thus augmented is regular and has the prefix property. That still doesn't let you parse "any regular grammar" with LR(0); it just means that every augmented regular language has an LR(0) parser, which is quite a different statement.)
An LR(0) automaton has no lookahead; that's what the $(0)$ means. So if a language includes $u$ and $uv$, where $|v|\ge 1$ (in other words, it does not have the prefix property), then once the parser reads $u$, it cannot decide whether to accept or continue.
Another consequence of not having any lookahead is that if a REDUCE action is available in a state, it must be unconditional. No SHIFT action is possible for that state (that would be a shift/reduce conflict) and no other REDUCE action is possible (that would be a reduce/reduce conflict). None of those restrictions immediately implies the action of GOTO actions, though.
It's pretty common to see two claims about LR(0) grammars:
In fact, neither of the above claims are strictly true. Consider the following simple grammar: $$\begin{align}S&\to M A\\ M&\to\\ A&\to a \end{align}$$
That grammar recognizes the language $\{a\}$, which is not a particularly interesting language, other than as an example. Of course, that language is LR(0) –any language whose sentences are all the same length are LR(0). That doesn't mean that all grammars for that language are LR(0), but the above grammar certainly is; here's the LR(0) state machine generated by the grammophone tool, which happily classifies the grammar as LR(0):
Looking at that state machine, it's evident that state 0 has a REDUCE action ($M\to$) and two GOTO actions, one on $M$ and the other on $S$. (Of course, it has no SHIFT actions. In an LR(0) grammar, the generated parser can't have both REDUCE and SHIFT actions in the same state.)
(Perhaps it's worth noting that you can tell what types of actions are possible for a state by looking at the symbol following each • in the itemset: if the • is at the end of a production, there is a REDUCE action; if the • comes before a terminal, there is a SHIFT action, and if the the • comes before a non-terminal, there is a GOTO action.)
Certainly, the "marker" non-terminal $M$ contributes nothing to the recognition of sentences. We could simply remove $M$ from the grammar without doing anything more than deleting every reference to it in every production, and if we did so, there would no longer be a reduction action for it.
The point of marker non-terminals is to attach some syntax-directed semantic action to a production which is evaluated before the production is reduced. (Parser generators which provide this facility automatically call these "mid-rule actions".) Marker non-terminals are always ε-productions, and they don't necessarily invalidate the LR(0) property. But they are not essential for recognition, and so possibly there is some way of rephrasing the "no ε-production" criterion which more precisely characterises LR(0) grammars. I haven't seen one, though, and my inclination is to think that the GATE question is not really correct (and it wouldn't be the first GATE question I've seen which has led me to think that).
