2023-10-11

Syntax Analysis 4

[!question]- What is the input to $FIRST()$ $(T \cup N \cup \varepsilon \cup EOF)^*$ Strings of the grammar

[!question]- What is the input to $FOLLOW()$ $N$

[!question]- Give the algorithm for computing $FIRST$ sets $for\ x\ in\ (T \cup EOF\ \cup \varepsilon)$ $FIRST(x) = {x}$ $for\ t \in N$ $FIRST(t) = \phi$

while thereAreChanges():
  for production in grammar:
  	rhs = FIRST(production.rhs[0]) - {eps}
  	i = 0
  	# Suppose there are multiple NT in the RHS and each of them can become eps, we need to add the FIRST of the next NT
  	# Not adding eps as we need to make sure that everything in the rhs can go to eps that is the only case when the lhs can fully become eps. If there is atleast on NT in the sequence that doesn't have eps then lhs can never go to eps
  	while (i < n-1) and (eps in FIRST(production.rhs[i]):
  		rhs = rhs + FIRST(production.rhs[i+1]) - {eps}
  		i += 1
  	# Add eps if everything went can go to eps
  	if i == n-1 and (eps in FIRST(production.rhs[i])):
  		rhs = rhs + {eps}
  	FIRST(production.lhs) += rhs

[!question]- What is $FOLLOW(S)$ $EOF$

[!question]- Write the algorithm for FOLLOW sets

for nt in NT:
  FOLLOW(nt) = {}
FOLLOW(S) = {EOF}
while FOLLOW is changing:
  for all production of the form A->B_1B_2B_3...B_k:
  	# trailer keeps track of the right context i.e the things that can come after B_i
  	# Since we are going down from k, we need right context for B_k
  	# That is follow(A)
  	trailer = follow(A)
  	for i = k down to 1:
  		if B_i in NT:
  			FOLLOW(B_i) += trailer
  			if eps in FIRST(B_i):
  				# Expand right context if B_i can go to eps
  				trailer += FIRST(B_i) - eps
  			else :
  				# Else truncate it as the symbols before B_i will have this as their FOLLOW as it won't go to eps
  				trailer = FIRST(B_i)
  		else:
  			# If it not a NT then truncate as well
  			trailer = {B_i}