Advertisement
Guest User

3. First sets

a guest
Oct 23rd, 2018
86
0
Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
text 1.09 KB | None | 0 0
  1. S -> a S e | B
  2. B -> b B e | C
  3. C -> c C e | d
  4.  
  5. Let's start with the C production. It can produce either "C C e" or "d", so the first terminal symbol of the first production rule is c, and it gets added to First(C). Likewise, the first symbol of "d" is just d, so that gets added to First(C). So First(C) is the set of {c, d}.
  6.  
  7. B produces either "b B e" or the nonterminal "C". So, we can see that in the first production rule, the first terminal symbol in "b B e" is "b", so we add that to the set of First(B). But then we see that B can also produce C, meaning that B could theoretically start with any of the starting characters also in C, so we union the sets First(C) and our current First(B) to produce the correct set of First(B) = {b, c, d}.
  8.  
  9. Likewise, First(S) is similar. We look and see what S begins with, and see that it can also produce B, so we end up unioning First(B) with the set of starting symbols of S to achieve the final First(S) set.
  10.  
  11. First(S) = {a} UNION First(S) = {a} UNION {b, c, d} = {a, b, c, d}
  12. First(B) = {b} UNION First(C) = {b} UNION {c, d} = {b, c, d}
  13. First(C) = {c, d}
Advertisement
Add Comment
Please, Sign In to add comment
Advertisement