Definitions
Function Result
NULL(x) true if symbol x is null deriving.
LHS(x) left hand side symbol of rule x.
RHSLEN(x) length of the right hand side of rule x.
RHS(x,y) symbol y of rule x not counting the LHS(x).
FIRST(x) first set for non-terminal x.
LAST(x) last set for non-terminal x.
FOLLOW(x) follow set for symbol x.
SELECT(x,y) selection value for NT x and T y
Note:
Whenever a change is made to a set the flag CHANGES is
incremented by one. NRULES is a variable which contains the
number of rules in the current grammer. NT will be used to
specify non-terminals and T will be used to specify
terminals
Algorithm for Generating the NULL set
CHANGES=1
while CHANGES
CHANGES=0
for I = each rule
if NULL(LHS(I)) break for next I
for J = each rhs symbol
if not NULL(RHS(I,J)) break for next I
next J
LHS(I) is NULL
next I
end while
Algorithm for Generating the First Set
for I = each rule
for J = first rhs to last rhs
add RHS(I,J) to FIRST(LHS(I))
if not NULL(RHS(I,J)) then break for next I
next J
next I
CHANGES=1
while CHANGES
CHANGES=0
for I = each NT
for J = each NT in FIRST(I)
add FIRST(J) to FIRST(I)
next J
next I
end while
Algorithm for Generating the Last Set
for I = each rule
for J = last rhs to first rhs
add RHS(I,J) to LAST(LHS(I))
if not NULL(RHS(I,J)) then break for next I
next J
next I
CHANGES=1
while CHANGES
CHANGES=0
for I = each NT
for J = each NT in LAST(I)
add LAST(J) to LAST(I)
next J
next I
end while
Algorithm for Generating the Follow Set
CHANGES=1
while CHANGES
CHANGES=0
for I = each rule
for J = each rhs symbol
for K = J + 1 to RHSLEN(I) + 1
if K > RHSLEN(I) then
add Follow(LHS(I)) to Follow(RHS(I,J))
else
add RHS(I,K) to Follow(RHS(I,J))
add FIRST(RHS(I,K)) to Follow(RHS(I,J))
if !NULL(RHS(I,K)) then break to next J
next K
next J
next I
next while
Algorithm for finding reachable symbols
CHANGES=1
set REACHABLE(start_symbol)
while CHANGES
CHANGES=0
for I = each rule
if REACHABLE(LHS(I)) then
for J = each rhs symbol
if not REACHABLE(J) CHANGES=1
set REACHABLE(J)
next J
next I
for I = each symbol
if not REACHABLE(I)
print I
next I
Algorithm for finding resolvable symbols
for I = each terminal symbol
set RESOLVABLE(I)
next I
CHANGES=1
while CHANGES
CHANGES=0
for I = each rule
if RESOLVABLE(LHS(I))continue;
for J = each rhs symbol
if not RESOLVABLE(J) break for next I
next J
set RESOLVABLE(LHS(I))
CHANGES=1
next I
for I = each non-terminal
if not RESOLVABLE(I)
print I
next I
Algorithm for Generating the Selection Set
for I = each rule
for J = 1 to RHSLEN(I)+1
if J > RHSLEN(I) then
for K = each T in FOLLOW(LHS(I))
if SELECT(LHS(I),K)==0 then
SELECT(LHS(I),K)=I
else
for K = each T in FIRST(RHS(I,J))
SELECT(LHS(I),K)=I
if not NULL(RHS(I,J)) break for next I
next J
next I
Algorithm for using Grammer and Selector set
push start symbol to stk
input=scanner()
while stack is not empty
if tos is NT then
I = Select(tos,input)
if I==0 then
error()
pull from stk
for J = RHSLEN(I) to 1
push RHS(I,J)
else if tos is T
if input == tos then
push tos to pstk
pull stk
input=scanner()
else error()
else if tos is semantic action
do semantic routine
pull semantic action from stk
end while