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