Continuing summary of Recursive Descent Parsing

Parsing table for LL parser is of form

choice : Nonterminal -> Token -> Set[Int]

We computing it for each nonterminal X by looking at all right-hand sides of X. Denote i-th right-hand side of X by p(X,i):

X ::= p(X,1) | ... | p(X,i) | ... | p(X,n)

Compute choice(X)(t) as follows:

choice(X)(t) = {i | t in first(p(X,i)) or (p(X,i) nullable and t in follow(X)}

(Z(1)…Z(k) is nullable if all Z(1),…,Z(k) are nullable non-terminals.)

Size of choice(X)(t):

• we require that each entry choice(X)(t) has at most one element (otherwise not LL(1))
• empty entries are normal, if encountered they indicate syntax error in input