title: Coding First and Follow sets in a CFG
body: <pre><code>COMPUTING First[A]
  ------------------
  
  // Procedure computeFirst
  //
  // Input: productions P_1, P_2, ..., P_m where P_i = A::=X_1 X_2 X_3 ...X_n
  //    with no alternations allowed in the productions.
  //
  // Output: Computes first of a term or nonterm accounting for nullability
  // and multiple productions for the same nonterm.
  //
  //  First is an array indexed by a terminal or
  //  nonterminal and its value is a set of terminals and/or \epsilon.
  //
  // First[A] for nonterminal A is the set of all possible tokens that 
  //    can occur as the first token of a sentence derived from A.
  // First[A] for terminal A is simply the set { A }.
  //
  // Compute the first sets for all tokens from productions P_1, P_2, ..., P_m
  //  where no production contains an alternation
  //
  // CALLS: computeFirstOfList(X_1, X_2, ... X_n)
  procedure computeFirst({P_1, P_2, ...P_m})  // works on a list of productions
      // initial value for the First of anything
      foreach A \elemof TERMS do First[A] = {A} 
      foreach A \elemof NONTERMS do First[A] = {} 
  
      // loop until nothing new happens updating the First sets
      while stillchanging any First[A] do
          foreach production P_i = A::=X_1, X_2, ... X_n do
               First[A] &lt;- First[A] \union computeFirstOfList(X_1, X_2, ... X_n)
          end foreach
      end while
  end
  
  // Procedure computeFirstOfList
  //
  // Computes the First of a rhs rather than just a token!
  //
  // This computes the set of tokens that can occur as the first
  // token of a sentence derived from this rhs (right hand side) of
  // of production.  That is X_1, X_2, ... X_n is a concatenation of
  // terminals and nonterminals often found on the right hand side
  // of a production.  This is nontrivial because some of the leading
  // nonterminals on the rhs can go to epsilon.
  //
  // REFS: First[X_i]  (does not use Follow)
  //
  procedure computeFirstOfList(X_1, X_2, ... X_n)
      Tmp = {}
      k=0
      do
            k++
            Tmp &lt;- Tmp \union First[X_k]-{\epsilon}
      while k&lt;n &amp; \epsilon isin First[X_k]
  
      // \epsilon only if X_1, X_2, ... X_n -&gt; \epsilon
      // Note: this test can only possibly work if k==n:
      if \epsilon isin First[X_k] then Tmp &lt;- Tmp \union {\epsilon}
  
      return Tmp
  end
  
  Note:
  
  1. IMPORTANT: if grammar has no \epsilon then the procedure
     computeFirstOfList(X_1, X_2, ... X_n) simply returns First[X_1] 
  
  2. since \epsilon is removed when adding to First inside the do/while
  \epsilon can only appear when the entire argument list can be
  replaced by \epsilon (called this production is called NULLABLE). 
  
  3. First Sets can contain \epsilon as an element.  Follow Sets cannot as we'll see.
  
  4. Conceptually, computeFirst generates a relation of the form:
  First[A] = First[\alpha] \union First[\beta] \union ... \union { \epsilon },
  for each production where A occurs on the left hand side (lhs).
  This is based on the next point.
  
  5. Conceptually, computeFirstOfList generates a relation of the form:
  computeFirstOfList(X_1, X_2, ... X_n) = First[\alpha] \union First[\beta]
  \union ... \union { \epsilon } where terms are added based on if
  all of the terms before it in the rhs are nullable.
  </code></pre>
  
  <p>I'm trying to create this pseudo-code in python. This concerns First/Follow sets in a Context Free Grammar. The issue i face is that in computeFirst, it says that the loop proceeds for each production which leads me to assume that a single production will be sent into computeFirstOfList. But in that function, it looks like it loops through multiple functions as k &lt; n. I also don't understand what this line does.</p>
  
  <pre><code>Tmp &lt;- Tmp \union First[X_k]-{\epsilon}
  </code></pre>
  
  <p>Does this line mean </p>
  
  <pre><code>union(tmp,First[k]) 
  </code></pre>
  
  <p>or </p>
  
  <pre><code>union(First[k],epsilon)
  </code></pre>
  
  <p>I don't really understand. I still have to make the union function as well and I was hoping to get some guidance. Here is my code</p>
  
  <pre><code>NONTERMS = ['S','E','I','A','T','O','M','F']
  TERMS = ['+','-','*','(',')','n','e']
  epsilon='e'
  FIRST ={}
  grammar = {'E':[['T','I'],[epsilon]],
             'I':[['A','T','I'],[epsilon]],
             'A':[['+'],['-']],
             'T':[['F','O']],
             'O':[['M','F','O'],[epsilon]],
             'M':[['*']],
             'F':[['(','E',')'],[epsilon]]}
  
  
  def computeFirst(g):
      for a in TERMS:
          FIRST[a]=set(a)
  
      for i in NONTERMS:
          FIRST[i]=set()
  
      for times in g:
          for key in g:
              Updating= True
              while Updating:
                  tmp=FIRST[key].copy()
                  for production in g[key]:
                      z=computeFirstOfList(production)
                      FIRST[key].update(FIRST[key].union(z))
                  if tmp==FIRST[key]:
                      Updating=False
  
  def computeFirstOfList(p):
  
      tmp=set()
      k=0
      n=len(p)
      while k&lt;n:
          if(p[k]) in NONTERMS:
              tmp.update(tmp.union(FIRST[p[k]].difference(set(epsilon))))
          k+=1
  
      return tmp
  
  computeFirst(grammar)
  print(FIRST)
  </code></pre>