FIRST sets for terminals and non-terminals FIRST sets for non-terminals are calculated by applying the following rules repeatedly until no FIRST set changes. The rules are applied iteratively We assume that all FIRST sets are initially empty The rules we use to calculate the FIRST sets are the following, assuming initially FIRST sets are empty: I. FIRST(x)-X if X is a terminal II. FIRST(e) e. Note that this is not covered by the first rule because e is not a terminal. Ill. If A Xa, then add FIRST(X)-{c) to FIRST(A) IV. If A A1A2A3 . . . AA,+1 . . . Ak and E FIRST(A) and e e FIRST (A2) and. and e E FIRST(A then add FIRST(A)- e to FIRST(A). 24 CHAPTER 2. GRAMMARS AND PARSING V. If A> A1A2A.Ak and E FIRST(A) and e e FIRST(A2) and.. and e E FIRST(Ak) then add e to FIRST(A) Note that if c e FIRST(A) if and only if A Problem I. Parsing. Consider the grammar SAg BC (1) ACB B dBc where S, A, B, and C are the non-terminals, S is the start symbol, and a, c, d, e, f, and g are the terninals 1. Calculate the FIRST and FOLLOW sets for this grammar. For FIRST sets (a) Do an initialization pass by applying FIRST sets rules I and II. (b) Do successive passes, on the grammar rules in the order they are listed and apply to each grammar rule FIRST set rules III, then FIRST set rule IV then FIRST set rule V In your answer, you should show the FIRST sets after each pass. You do not have to use the notation I used in class to indicate the order in which the elements are added to the sets. For FOLLOW sets, you should do: (a) Do an initialization pass by applying FOLLOW sets ruleI (b) Do one pass on all grammar rules, in the order they are listed, and apply to each grammar rule FOLLOW set rules IV and V. c) Do successive passes on all grammar rules in the order they are listed and apply to each grammar rule FOLLOW set rules II and III until there is no change. In your answer, you should show the FOLLOW sets after each pass. You do not have to use the notation I used in class to indicate the order in which the elements are added to the sets. FIRST sets for terminals and non-terminals FIRST sets for non-terminals are calculated by applying the following rules repeatedly until no FIRST set changes. The rules are applied iteratively We assume that all FIRST sets are initially empty The rules we use to calculate the FIRST sets are the following, assuming initially FIRST sets are empty: I. FIRST(x)-X if X is a terminal II. FIRST(e) e. Note that this is not covered by the first rule because e is not a terminal. Ill. If A Xa, then add FIRST(X)-{c) to FIRST(A) IV. If A A1A2A3 . . . AA,+1 . . . Ak and E FIRST(A) and e e FIRST (A2) and. and e E FIRST(A then add FIRST(A)- e to FIRST(A). 24 CHAPTER 2. GRAMMARS AND PARSING V. If A> A1A2A.Ak and E FIRST(A) and e e FIRST(A2) and.. and e E FIRST(Ak) then add e to FIRST(A) Note that if c e FIRST(A) if and only if A Problem I. Parsing. Consider the grammar SAg BC (1) ACB B dBc where S, A, B, and C are the non-terminals, S is the start symbol, and a, c, d, e, f, and g are the terninals 1. Calculate the FIRST and FOLLOW sets for this grammar. For FIRST sets (a) Do an initialization pass by applying FIRST sets rules I and II. (b) Do successive passes, on the grammar rules in the order they are listed and apply to each grammar rule FIRST set rules III, then FIRST set rule IV then FIRST set rule V In your answer, you should show the FIRST sets after each pass. You do not have to use the notation I used in class to indicate the order in which the elements are added to the sets. For FOLLOW sets, you should do: (a) Do an initialization pass by applying FOLLOW sets ruleI (b) Do one pass on all grammar rules, in the order they are listed, and apply to each grammar rule FOLLOW set rules IV and V. c) Do successive passes on all grammar rules in the order they are listed and apply to each grammar rule FOLLOW set rules II and III until there is no change. In your answer, you should show the FOLLOW sets after each pass. You do not have to use the notation I used in class to indicate the order in which the elements are added to the sets
