The states in LR parsers correspond to sets of items (ie, sets of productions from the original grammar, with a "dot" marking how far into the rule the parser has gotten). In general, states correspond to multiple items, since in general it is not possible to predict which rule will be used for reduction.

What is known about the case when it is? That is, what is known about grammars for which the corresponding LR(k) automata (both $k=0$ and $k>0$) have states with singleton item sets? Has this class been studied, and does it correspond to any well-known class of grammars? (Eg, does it correspond to LL(k), or operator precedence, or similar?)

I'm curious about this case since the singleton item restriction means that the size of the parse automaton will be bounded by the size of the grammar.

  • $\begingroup$ Having singleton item sets means that there are no nonterminals on the right-hand side $\alpha$ of the productions $S\to\alpha$ of the axiom, since closure would immediately add new items. That corresponds to grammars generating a single word (or no word at all if there is no production $S\to\alpha$). $\endgroup$ – Sylvain Nov 20 '15 at 14:58
  • $\begingroup$ @Sylvain: huh, you're right. The parser generator I'm looking at (Pottier's Menhir) can print out the item set of its automaton, and for many of the grammars I'm looking at it prints a singleton. I suppose it must be printing only a subset of the item set.... $\endgroup$ – Neel Krishnaswami Nov 20 '15 at 16:21

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.