Made Easy test series

Question

SR conflict in LR(0) and SLR(1) will always be equal for some context free grammar?

Answer 1

That question statement feels weird… still

Answer : Yes.

SR conflict in LR(0) and SLR(1) will always be equal for CFG?

No, not for all CFG as SLR(1) accepts all LR(0) grammars as well as some non LR(0) grammars.

Now are there “SOME” CFG for which both have equal SR conflicts , yes.

LR(0) writes reduce in entire row of production while SLR(1) writes reduce only in FOLLOW of LHS of production .

So if SR conflicts in LR(0) are under column which are also FOLLOW of LHS of production  then SLR(1) will have same SR conflict.

another example is if there are “Zero” SR conflicts then both LR(0) and SLR(1) will have equal SR conflicts .

Answer 2

@Nitesh_Yadav

The LR(0) algorithm will produce shift-reduce conflicts in any state with a mixture of shift and reduce actions, because there is no lookahead available...

An SLR(1) parser can resolve those conflicts when the token to be shifted is not in the FOLLOW set for the symbol to be reduced.

Thus, the LR(0) parser has shift-reduce conflicts which are not in the SLR(1) parser for the same grammar, but every conflict in the SLR(1) parser is also in the LR(0) grammar...

LR parsers are a type of bottom-up parser that analyses deterministic context-free languages in linear time...

There are several variants of LR parsers: SLR parsers, LALR parsers, Canonical LR(1) parsers, Minimal LR(1) parsers, GLR parsers...

LR parsers can be generated by a parser generator from a formal grammar defining the syntax of the language to be parsed.

They are widely used for the processing of computer languages...

 

1. https://web.stanford.edu/class/archive/cs/cs143/cs143.1128/handouts/110%20LR%20and%20SLR%20Parsing.pdf

 

2. https://en.wikipedia.org/wiki/LR_parser