How to generate LALR parsing tables
from: Compilers -- Principles, Technicques, and Tools
Aho, Sethi, and Ullman, Addison-Wesley, 1987 (original version 1986)


TYPE
an LR (1) item has form [core, T], where
core has the form NT -> X1..Xi . Z1..Zj
where NT is a nonterminal, T is a terminal, and Xi, Zi and Y are any
symbol in the grammar.
a parsing action has the form s/r,state
a goto entry has the form state
a state is simply an encoding of one of the parsing states


simple algorithm (p. 238)
function lalr (G: augmented grammar with start production S' -> S) =>
parsing action table, goto table.

LALR (grammar)
collection = ITEMS (grammar)
cores = {}
forall itemset in collection
	cores = cores U itemset.core
endforall
new = {}
for (i = 1; i <= size (cores); i++)
	newis.core = cores [i]		this is a set assignment
	newis.terms = {}		this is also a set assignment
	forall itemset in collection
		if itemset.core = core then
			newis.terms = newis.terms U itemset.terms
		endif		the above is a union over sets
	endforall
	new = new U newis
endfor
for (i = 1; i <= size (new); i++)
	itemset = new [i]
	forall term in grammar
		if ([NT -> X1..Xi . term Z1..Zj, T] in itemset) then
			state = index (goto (itemset, term, grammar), new);
			action [i, term] = shift state
		else if ([NT -> X1..Xi . , term] in itemset) then
			action [i, term] = reduce NT -> X1..Xi
		else if ([S' -> S . , $] in itemset) then
			action [i, term] = accept
		else
			action [i, term] = error
		endif
	(if more than one 'if' is true, there is a shift-reduce conflict)
	endforall
endfor
for (i = 1; i <= size (new); i++)
	itemset = new [i]
	forall nonterm in grammar
		state = index (goto (itemset, term, grammar), new);
		gototab [itemset, term] = state;
	endforall
endfor

example: grammar 4.21 (p 231); see below for I0..I9
S' -> S
S -> CC
C -> cC | d

FIRST (S') = FIRST (S) = FIRST (C) = {c, d} (see below)
ITEMS (G') => { I0, I1, I2, I3, I4, I5, I6, I7, I8, I9 }
cores => { cI0, cI1, cI2, cI36, cI47, cI5, cI89 }
new => { I'0, I'1, I'2, I'3, I'4, I'5, I'6 }
I'0 = {[S'->.S, $], [S->.CC, $], [C->.cC, c/d], [C->.d, c/d]}	(s1)
I'1 = {[S'->S., $]}						(s6)
I'2 = {[S->C.C, $], [C->.cC, $], [C->.d, $]}			(s2)
I'3 = {[C->c.C, c/d/$], [C->.cC, c/d/$], [C->.d, c/d/$]}	(s0)
I'4 = {[C->d., c/d/$]}						(s4)
I'5 = {[S->CC., $]}						(s5)
I'6 = {[C->cC., c/d/$]}						(s3)

action:					goto:
	i	c	d	$		S	C
	0	s3	s4	-		1	2
	1	-	-	acc		-	-
	2	s3	s4	-		-	5
	3	s3	s4	-		-	6
	4	C->d	C->d	C->d		-	-
	5	-	-	S->CC		-	-
	6	C->cC	C->cC	C->cC		-	-



function items (G: augmented grammar with start production S' -> S) =>
the collection of sets of LR (1) items
function closure (I: set of LR (1) items, G: augmented grammar) =>
a set of LR (1) items
function goto (I: set of LR (1) items, X: grammar symbol, G: grammar) =>
a set of LR (1) items

code (p. 232)
ITEMS (grammar)
items = { closure ({[S'->.S, $]}) }	items is a collection of sets of items
olditems = {}
while (olditems # items)
	olditems = items
	forall I in items
		forall X in grammar_symbols (grammar)
			new = goto (I, X, grammar)
			if (new != {}) then items = items U new
		endforall
	endforall
endwhile

CLOSURE (itemset, grammar)
oldclose = { }
closure = itemset
while (closure # oldclose)
	oldclose = closure
	forall [A -> X1..Xi . Y Z1..Zj , T ] in closure
		forall Y -> W1..Wk in grammar
			forall S in FIRST (Z1..Zj T)
				closure = closure U { [ Y -> . W1..Wk , S ] }
			endforall
		endforall
	endforall
endwhile

GOTO (itemset, symbol, grammar)
withsym = {}
forall [A -> X1..Xi . Y Z1..Zj , T ] in itemset
	if Y = symbol then withsym = withsym U [A -> X1..Xi Y . Z1..Zj , T ]
endforall
goto = CLOSURE (withsym, grammar)

example: grammar 4.21 (p 231)
S' -> S
S -> CC
C -> cC | d

FIRST (S') = FIRST (S) = FIRST (C) = {c, d} (see below)
ITEMS (G') =>
{ I0, I1, I2, I3, I4, I5, I6, I7, I8, I9 }

initially we get
I0 = { [ S' -> . S, $ ], [ S -> . C C, $ ], [ C -> . c C, c ],
       [ C -> . c C, d ], [ C -> . d, c ], [ C -> . d, d ] }

from I0 we have (on S, C, c, and d, respectively)
I1 = { [ S' -> S ., $ ]}
I2 = { [ S -> C . C, $ ], [ C -> . c C, $ ], [ C -> . d, $ ] }
I3 = { [ C -> c . C, c ], [ C -> . c C, c ], [ C -> . d, c ],
       [ C -> c . C, d ], [ C -> . c C, d ], [ C -> . d, d ] }
I4 = { [ C -> d . , c ], [ C -> d . , d ] }

from I2 we have (on C, c, and d, respectively)
I5 = { [ S -> C C . , $ ] }
I6 = { [ C -> c . C , $ ], [ C -> . c C, $ ], [ C -> . d, $ ] }
I7 = { [ C -> d . , $ ]}

from I3 we have
I8 = { [ C -> c C . , c ], [ C -> c C . , d ] }

from I6 we have
I9 = { [ C -> c C . , $ ] }



function FIRST (a: string of grammar symbols) =>
set of terminals that begin the strings derived from a. if a =>* epsilon,
epsilon is also in the set.

code (p. 189)
FIRST (a [1..I], grammar)
first = RECFIRST (a, {}, grammar)

RECFIRST (a [1..I], seen, grammar)
X = a [1]
if Terminal (X) then first = {X}
else
	recfirst = {}
	if (X not in seen) then
		foreach X->Y[1]..Y[J] in grammar
			recfirst = recfirst U
				   RECFIRST (Y[1]..Y[J], seen + {X}, grammar)
		endforeach
	endif
	if (X->epsilon in grammar) then
		if (I > 1) then
			recfirst = recfirst U RECFIRST (a [2..I], seen, grammar)
		else
			recfirst = recfirst U {epsilon}
		endif
	endif
endif

example: grammar 4.11 (p 189)
E -> TE'
E' -> +TE' | eps
T -> FT'
T' -> *FT' | eps
F -> ( E ) | id

FIRST (E) = FIRST (T) = FIRST (F) = {(, id}
FIRST (E') = {eps, +}
FIRST (T') = {eps, *}


ambiguities:
on each shift-reduce conflict, use precedence and associativity to
determine what to do. Note that most programming languages would
have the above be left-associative, i.e. a+b+c = (a+b)+c
YACC: attaches a precedence and associativity to each production
in a conflict.
shifting a vs reduce A->X1..Xn:
reduces iff (prec (A->X1..Xn) > prec (a) |
	     (prec (A->X1..Xn) = prec (a) & assoc (A->X1..Xn) = left))
shifts otherwise (i.e. also in case of no information)
prec (A->X1..Xn) = prec (Xn),  or as specified by %prec

example grammar:
S -> E
E -> E + E | E * E | ( E ) | id

parsing table for above grammar, assuming * has higher precedence
and all operators are left-associative:
action:							goto:
state	id	+	*	(	)	$		E
  0	s3	-	-	s2	-	-		1
  1	-	s4	s5	-	-	acc		-
  2	s3	-	-	s2	-	-		6
  3	-	r4	r4	-	r4	r4		-
  4	s3	-	-	s2	-	-		8
  5	s3	-	-	s2	-	-		8
  6	-	s4	s5	-	s9	-		-
  7	-	r1	s5	-	r1	r1		-
  8	-	r2	r2	-	r2	r2		-
  9	-	r3	r3	-	r3	r3		-
where r1 = E->E+E, r2 = E->E*E, r3 = E->(E), r4 = E->id


if precedence and associativity offer no help, as in S-> iSeS | iS
(the dangling-else problem), simply shift whenever possible (on input 'e'),
and reduce otherwise

example grammar:
S' -> S
S -> i S e S | i S | a

parsing table
action:							goto:
state	i	e	a	$		S
  0	s2	-	s3	-		1
  1	-	-	-	acc		-
  2	s2	-	s3	-		4
  3	-	r3	-	r3		-
  4	-	s5	-	r2		-
  5	s2	-	s3	-		6
  6	-	r1	-	r1		-
where r1 = S -> iSeS, r2 = S -> iS, r3 = S -> a


in case of reduce-reduce conflicts, generally select the reduction
with the lower-numbered (earlier) production.

example grammar:
E -> E sub E sup E
E -> E sub E
E -> E sup E
E -> { E }
E -> c
