Constructing a Follow Set

While creating a first set for a given grammar, I noticed a scenario not described in my reference for the algorithm.

Namely, how does one calculate the follow set for a nonterminal with a rule such as this.

<exp-list_tail> --> COMMA <exp> <exp-list_tail>

Expressions surrounded by <..> are nonterminals, COMMA is a terminal.

My best guess is I should just add the empty string to the follow set, but开发者_如何转开发 I'm not sure.

Normally, for the case of a nonterminal being at the end of a production rule, you would just compute the follow list for the left nonterminal, but you can see how this would be a problem.

To answer this properly, it would be helpful to know your entire grammar. However, here is an attempt for a general answer:

Here is the algorithm for calculating follow groups:

Init all follow groups to {}, except S which is init to {$}.
While there are changes, for each A∈V do:
  For each Y → αAβ do:
    follow(A) = follow(A) ∪ first(β)
    If β ⇒* ε, also do: follow(A) = follow(A) ∪ follow(Y)

Note that this is a deterministic algorithm, it will give you a single answer, depending only on your (entire) grammar.

Specifically, I don't think that this particular rule will affect <exp-list_tail>'s follow set (it could, but probably wouldn't).