CODEWITHSUNDEEP
parsingcompiler-constructionll-grammar
user3603634
user3603634

Reputation: 125

Follow sets Top-Down parsing

I have a question for the Follow sets of the following rules:

L -> CL'
L' -> epsilon
       | ; L
C -> id:=G
      |if GC
      |begin L end

I have computed that the Follow(L) is in the Follow(L'). Also Follow(L') is in the Follow(L) so they both will contain: {end, $}. However, as L' is Nullable will the Follow(L) contain also the Follow(C)?

I have computed that the Follow(C) = First(L') and also Follow(C) subset Follow(L) = { ; $ end}.

In the answer the Follow(L) and Follow(L') contain only {end, $}, but shouldn't it contain ; as well from the Follow(C) as L' can be null?

Thanks

Upvotes: 0

Views: 73

Answers (1)

Shahbaz
Shahbaz

Reputation: 47493

However, as L' is Nullable will the Follow(L) contain also the Follow(C)?

The opposite. Follow(C) will contain Follow(L). Think of the following sentence:

...Lx...

where X is some terminal and thus is in Follow(L). This could be expanded to:

...CL'x...

and further to:

...Cx...

So what follows L, can also follow C. The opposite is not necessarily true.

To calculate follows, think of a graph, where the nodes are (NT, n) which means non-terminal NT with the length of tokens as follow (in LL(1), n is either 1 or 0). The graph for yours would look like this:

     _______
   |/_      \
(L, 1)----->(L', 1)         _(C, 1)
 |  \__________|____________/| |
 |             |               |
 |             |               |
 |   _______   |               |
 V |/_      \  V               V
(L, 0)----->(L', 0)         _(C, 0)
    \_______________________/|

Where (X, n)--->(Y, m) means the follows of length n of X, depend on follows of length m of Y (of course, m <= n). That is to calculate (X, n), first you should calculate (Y, m), and then you should look at every rule that contains X on the right hand side and Y on the left hand side e.g.:

Y -> ... X REST

take what REST expands to with length n - m for every m in [0, n) and then concat every result with every follow from the (Y, m) set. You can calculate what REST expands to while calculating the firsts of REST, simply by holding a flag saying whether REST completely expands to that first, or partially. Furthermore, add firsts of REST with length n as follows of X too. For example:

S -> A a b c
A -> B C d
C -> epsilon | e | f g h i

Then to find follows of B with length 3 (which are e d a, d a b and f g h), we look at the rule:

A -> B C d

and we take the sentence C d, and look at what it can produce:

"C d" with length 0 (complete):
"C d" with length 1 (complete):
    d
"C d" with length 2 (complete):
    e d
"C d" with length 3 (complete or not):
    f g h

Now we take these and merge with follow(A, m):

follow(A, 0):
    epsilon
follow(A, 1):
    a
follow(A, 2):
    a b
follow(A, 3):
    a b c

"C d" with length 0 (complete) concat follow(A, 3):
"C d" with length 1 (complete) concat follow(A, 2):
    d a b
"C d" with length 2 (complete) concat follow(A, 1):
    e d a
"C d" with length 3 (complete or not) concat follow(A, 0) (Note: follow(X, 0) is always epsilon):
    f g h

Which is the set we were looking for. So in short, the algorithm becomes:

  • Create the graph of follow dependencies
  • Find the connected components and create a DAG out of it.
  • Traverse the DAG from the end (from the nodes that don't have any dependency) and calculate the follows with the algorithm above, having calculated firsts beforehand.

It's worth noting that the above algorithm is for any LL(K). For LL(1), the situation is much simpler.

Upvotes: 3

Related Questions