Parsing - Introduction to Compiler Construction in a Java World - page 78

The numbers in the table's entries refer to the numbers assigned to BNF rules in the
example grammar (3.21). An empty entry indicates an error: when the parser has the given
non-terminal on top of the stack and the given token as the next input symbol, the parser
is in an erroneous state. The LL(1) parsing algorithm is parameterized by this table. As we
mentioned earlier, it makes use of an explicit pushdown stack.
Algorithm 3.1 LL(1) Parsing Algorithm
Input: LL(1) parsing table table, production rules rules, and a sentence w, where w is a
string of terminals followed by a terminator #
Output: a left-parse, which is a left-most derivation for w
Stack stk initially contains the terminator # and the start symbol S, with S on top
Symbol sym is the first symbol in the sentence w
while true do
Symbol top stk.pop()
if top = sym = # then
Halt successfully
else if top is a terminal symbol then
if top = sym then
Advance sym to be the next symbol in w
else
Halt with an error: a sym found where a top was expected
end if
else if top is a non-terminal Y then
index table[Y;sym]
if index 6= err then
rule rules[index]
Say rule is Y ::= X 1 X 2 :::X n ; push X n ;:::;X 2 ;X 1 onto the stack stk, with X 1
on top
end if
else
Halt with an error
end if
end while