Groups | Search | Server Info | Keyboard shortcuts | Login | Register [http] [https] [nntp] [nntps]

Groups > comp.compilers > #3716 > unrolled thread

LALR look-ahead sets from item right context grammar?

Back to article view | Back to comp.compilers

Contents

  LALR look-ahead sets from item right context grammar? Richard Rogers <rprogers@seanet.com> - 2026-02-07 01:42 +0000
    LALR look-ahead sets from item right context grammar? Richard Rogers <rprogers@seanet.com> - 2026-02-28 13:43 +0000

#3716 — LALR look-ahead sets from item right context grammar?

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.

[toc] | [next] | [standalone]

#3722

Qwen3-coder just pointed out that what I've described is actually "LALR(1)
with context-sensitive look-aheads," also known by a couple other names. To
get true LALR(1), you'd have to take the union of the FIRST(RCG(i,j)) over
states j containing item i. But that seems silly since it's better and less
code without doing the union :)

[toc] | [prev] | [standalone]

Back to top | Article view | comp.compilers

csiph-web