CODEWITHSUNDEEP
parsingcompiler-constructionlr-grammarautomaton
Afaria
Afaria

Reputation: 393

LR(0) Parser conflicts

I have a doubt about lr(0) parsers. For example I have the follow grammar: 

S -> S N
   | 

N -> terminalsymbol

If I try to construct the first state of lr0 automaton, I get the following first state:

S ' -> . S $ 

S -> . S N
S -> .

So here appears to me a stupid doubt. Since I have "S -> ." in the first state, is this a situation of a shift/reduce in lr0 parser? Cause the parser can go to shift action by nonterminal S, or reduce action by empty transition (I think).

I already searched across the web looking for a example with empty transitions, but I didn't found one.

Upvotes: 0

Views: 3227

Answers (1)

rici
rici

Reputation: 241721

If you start with the augmented grammar, it's not a conflict.

In the initial state, there is no possible shift action, and only one reduce action. So the reduce action must take place, unconditionally.

Once you reduce the S, you end up in the state:

S' -> S . $
S  -> S . N
N  -> . nonterminal

which will either shift the end-of-input mark, or the following non-terminal. Assuming that it's the non-terminal, we end up in:

N  -> nonterminal .

which is another forced reduce, which leads us to

S  -> S N .

and then we're back to:

S' -> . S $
S  -> . S N
S  -> .

However, the original unaugmented grammar is not LR(0). (No language which includes both the empty string and some other string can be LR(0).)

Upvotes: 1

Related Questions