Is state splitting the LR equivalent of LL nonterminal replication

Question

The grammar classes SLR and strong LL are similar in that they both use FOLLOW sets to resolve conflicts. For still unresolved conflicts, state splitting always works for SLR grammars, if the grammar is LR. Similarly, Aho/Ullman have shown that nonterminal replication can make any LL grammar strong. If the form of the LL grammar is EBNF, the replication is intrinsic if identical EBNF forms are implemented as different nonterminals at each occurrence in the grammar.

I wonder if the nonterminal replication provided by an EBNF formed SLR grammar would provide something equivalent to state splitting such that the grammar would have LR recognition power.

More specifically, for a fixed k, given any LR(k) grammar, if that grammar contains at most one occurrence of each nullable nonterminal on the right hand sides of all productions, must that grammar also be SLR(k)? What I am looking for is a counter example grammar.

Answer 1

It is indeed well-known that LR($k$) languages for $k>0$ coincide with SLR($1$) languages, see e.g. M. Dennis Mickunas, Ronald L. Lancaster, and Victor B. Schneider, Transforming LR($k$) Grammars to LR(1), SLR(1), and (1,1) Bounded Right-Context Grammars, J. ACM 23(3):511--533, 1976, doi: 10.1145/321958.321972; it's not clear to me what EBNF syntax has to do with it: could you be more specific?

---

Edit: in answer to the more specific question regarding nullable nonterminals and LR($k$) vs. SLR($k$), the grammar with rules $$S\to aAa\mid bAb\mid aBb\mid bBa, A\to a, B\to a$$ is LR(1) but neither SLR(1) nor LALR(1) and does not have any nullable nonterminal.

Another issue is that there is no "perfect" definition of LR($k$) for EBNF syntax---unless you convert to BNF in some specific way and ask the resulting grammar to be LR($k$); see Heilbrunner, Definition of ELR($k$) and ELL($k$) Grammars, Acta Inf. 11(2):169--176, 1979, doi: 10.1007/BF00264023. The issue is with the reduction operation: how much of the stack should be reduced when reducing, say, $A\to a^\ast$? Answering this question might require inspecting the stack contents, or adding special stack markers, or $\dots$, and is likely to restrict the class of accepted grammars below ELR($k$).

Finally, I do not know about SLR($k$) techniques for EBNF grammars; a survey on the subject of parsing for EBNF was recently written by Hemerik, Towards a Taxonomy for ECFG and RRPG Parsing, LATA'09, LNCS 5457:410--421, 2009, doi: 10.1007/978-3-642-00982-2_35.