Path: csiph.com!weretis.net!feeder9.news.weretis.net!news.misty.com!news.iecc.com!.POSTED.news.iecc.com!nerds-end
From: Richard Rogers <rprogers@seanet.com>
Newsgroups: comp.compilers
Subject: LALR look-ahead sets from item right context grammar?
Date: Sat, 07 Feb 2026 01:42:35 +0000
Organization: Compilers Central
Sender: johnl%iecc.com
Approved: comp.compilers@iecc.com
Message-ID: <26-02-004@comp.compilers>
MIME-Version: 1.0
Content-Type: text/plain; charset="UTF-8"
Injection-Info: gal.iecc.com; posting-host="news.iecc.com:2001:470:1f07:1126:0:676f:7373:6970"; logging-data="48130"; mail-complaints-to="abuse@iecc.com"
Keywords: parse, LALR
Posted-Date: 07 Feb 2026 13:46:15 EST
X-submission-address: compilers@iecc.com
X-moderator-address: compilers-request@iecc.com
X-FAQ-and-archives: http://compilers.iecc.com
Xref: csiph.com comp.compilers:3716

The right context grammar for item i in state j of the LR(0) automaton
of CFG G describes all  of the suffixes that can follow any prefix
arriving at (i, j) when parsing a string in L(G). If the start symbol of
the right context grammar is nullable, it would mean a string in L(G)
could end at (i, j). If we augment G with S' -> S $ then S' -> S $ *
should be the only item with a nullable right context grammar start
symbol, and FOLLOW would also be the empty string.

And my hypothesis is that FIRST(RCG(i,j)) is the LALR look-ahead set for
(i, j), where RCG(i, j) is the start symbol of the right context grammar
for item i in state j of the LR(0) automaton of the augmented G.

The RCG computing algorithm gives a right-regular grammar for the right
contexts if the non-terminals of G are treated as terminals in the RCG.
For making an LR-Regular parser, G's non-terminals are replaced by their
approximate regular envelopes to give a regular approximation of the
right contexts. But if we include G's non-terminals and productions in
the RCG, the RCG is an accurate CFG for the right contexts.