<p>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. </p>

<p>What is known about the case when it <em>is</em>? That is, what is known about grammars for which the corresponding LR(k) automata (both $k=0$ and $k&gt;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?) </p>

<p>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. </p>

CC BY-SA 3.0
2015-11-20T14:58:40.520Z
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$).
Sylvain
CC BY-SA 3.0
2015-11-20T16:21:54.780Z
@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....
Neel Krishnaswami
<fl.formal-languages><parsing>
Grammars whose LR automata have singleton item sets?
Neel Krishnaswami
# Grammars whose LR automata have singleton item sets?

(Asked by: username_0 on 2015-11-20)

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.

**Tags:** fl.formal-languages, parsing

> **Comments:**
> **username_1**: 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$).  
> **username_0**: @username_1: 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....  

---

## 0 answers

