<p>If LR(0) condition for a grammar G is formulated as follows:</p>

<ol>
<li>Every state is either reduction or a shift state and it can't be both at the same time</li>
<li>if it is a reduction state, it contains exactly one item</li>
</ol>

<p>and LALR :</p>

<ol>
<li>Every reduction candidate has a look-ahead set disjoint from the set of the terminal labels of the arcs leaving the state</li>
<li>in case of multiple reduction candidates, their look-ahead sets are disjoint</li>
</ol>

<p>I'm looking for the name (if any) of the LALR subset corresponding to the following conditions:</p>

<ol>
<li>Every reduction candidate has a look-ahead set disjoint from the set of the terminal labels of the arcs leaving the state</li>
<li>Each reduction state contains exactly one reduction candidate</li>
</ol>

<p>which is a hybrid between LR(0) and LALR itself.</p>

<p>Thank you.</p>

CC BY-SA 3.0
2011-04-17T08:27:30.743Z
I don't know any such variant of the LALR condition (or any lookahead variant of LR(0), really, for instance what you describe also applies to SLR($k$) or LR($k$)).  I can even risk an explanation for why I doubt anyone did: if you go through the trouble of computing LALR lookahead sets, why not fully exercise this information?  Of course you might have a specific problem in mind where this makes sense.
Sylvain
CC BY-SA 3.0
2011-04-17T12:00:53.733Z
during the development of my master thesis I've written an algorithm to visit the LR(0) graph which appears to allow for parsing languages generated by grammars respecting those conditions (I'm still working on it); I was looking for pre-existing works in literature. Thank you for your help.
NoWhereMan
CC BY-SA 3.0
2011-04-18T08:56:47.650Z
Something like [DeRemer and Pennello](http://dx.doi.org/10.1145/69622.357187)'s technique to compute LALR(1) sets?
Sylvain
CC BY-SA 3.0
2011-04-27T12:36:31.980Z
@Sylvain: I did read that before asking here: there are references to NQLALR which is kind of a particular beast, but which doesn't seem the same as what I have described; it is indeed a superset of LR(0) and a proper subset of LALR(1)
NoWhereMan
<reference-request><fl.formal-languages><terminology><grammars><parsing>
LALR grammars subsets
NoWhereMan
# LALR grammars subsets

(Asked by: username_0 on 2011-04-16)

If LR(0) condition for a grammar G is formulated as follows:

1. Every state is either reduction or a shift state and it can't be both at the same time
2. if it is a reduction state, it contains exactly one item

and LALR :

1. Every reduction candidate has a look-ahead set disjoint from the set of the terminal labels of the arcs leaving the state
2. in case of multiple reduction candidates, their look-ahead sets are disjoint

I'm looking for the name (if any) of the LALR subset corresponding to the following conditions:

1. Every reduction candidate has a look-ahead set disjoint from the set of the terminal labels of the arcs leaving the state
2. Each reduction state contains exactly one reduction candidate

which is a hybrid between LR(0) and LALR itself.

Thank you.

**Tags:** reference-request, fl.formal-languages, terminology, grammars, parsing

> **Comments:**
> **username_1**: I don't know any such variant of the LALR condition (or any lookahead variant of LR(0), really, for instance what you describe also applies to SLR($k$) or LR($k$)).  I can even risk an explanation for why I doubt anyone did: if you go through the trouble of computing LALR lookahead sets, why not fully exercise this information?  Of course you might have a specific problem in mind where this makes sense.  
> **username_0**: during the development of my master thesis I've written an algorithm to visit the LR(0) graph which appears to allow for parsing languages generated by grammars respecting those conditions (I'm still working on it); I was looking for pre-existing works in literature. Thank you for your help.  
> **username_1**: Something like [DeRemer and Pennello](http://dx.doi.org/10.1145/69622.357187)'s technique to compute LALR(1) sets?  
> **username_0**: @username_1: I did read that before asking here: there are references to NQLALR which is kind of a particular beast, but which doesn't seem the same as what I have described; it is indeed a superset of LR(0) and a proper subset of LALR(1)  

---

## 0 answers

