1
$\begingroup$

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.

$\endgroup$
  • $\begingroup$ 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. $\endgroup$ – Sylvain Apr 17 '11 at 8:27
  • $\begingroup$ 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. $\endgroup$ – NoWhereMan Apr 17 '11 at 12:00
  • $\begingroup$ Something like DeRemer and Pennello's technique to compute LALR(1) sets? $\endgroup$ – Sylvain Apr 18 '11 at 8:56
  • $\begingroup$ @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) $\endgroup$ – NoWhereMan Apr 27 '11 at 12:36

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.