(New page: == Computing the FIRST Set == The FIRST set for a given string or symbol can be computed as follows: # If '''a''' is a terminal symbol, then FIRST('''a''') = {'''a'''} # If X is a non-te...) |
|||
| Line 12: | Line 12: | ||
* If Y<sub>1</sub> <amsmath>\overset{*}{\Rightarrow}</amsmath> ε and Y<sub>2</sub> <amsmath>\overset{*}{\nRightarrow}</amsmath> ε then FIRST(X) = FIRST(Y<sub>1</sub>) \ {ε} ∪ FIRST(Y<sub>2</sub>) | * If Y<sub>1</sub> <amsmath>\overset{*}{\Rightarrow}</amsmath> ε and Y<sub>2</sub> <amsmath>\overset{*}{\nRightarrow}</amsmath> ε then FIRST(X) = FIRST(Y<sub>1</sub>) \ {ε} ∪ FIRST(Y<sub>2</sub>) | ||
* If Y<sub>i</sub> <amsmath>\overset{*}{\Rightarrow}</amsmath> ε (∀i) then FIRST(X) = ∪<sub>i</sub>(FIRST(Y<sub>i</sub>)\{ε}) ∪ {ε} | * If Y<sub>i</sub> <amsmath>\overset{*}{\Rightarrow}</amsmath> ε (∀i) then FIRST(X) = ∪<sub>i</sub>(FIRST(Y<sub>i</sub>)\{ε}) ∪ {ε} | ||
| + | |||
| + | The FIRST set can also be computed for a string Y<sub>1</sub>...Y<sub>n</sub> much in the same way as in case 3 above. | ||
| + | |||
| + | == Computing the FOLLOW Set == | ||
| + | |||
| + | The FOLLOW set is computed for non-terminals and indicates the set of terminal symbols that are possible after a given non-terminal. The special symbol $ is used to represent the end of phrase (end of input). | ||
| + | |||
| + | # If A is the grammar's initial symbol then {$} ⊆ FOLLOW(A) | ||
| + | # If A -> αBβ is a production, then FIRST(β)\{ε} ⊆ FOLLOW(A) | ||
| + | # If A -> αB or A -> αBβ (β <amsmath>\overset{*}{\Rightarrow}</amsmath> ε), then FOLLOW(A) ⊆ FOLLOW(B) | ||
| + | |||
| + | The algorithm should be repeated until the FOLLOW set remains unchanged. | ||
The FIRST set for a given string or symbol can be computed as follows:
As an example, consider production X -> Y1...Yn
The FIRST set can also be computed for a string Y1...Yn much in the same way as in case 3 above.
The FOLLOW set is computed for non-terminals and indicates the set of terminal symbols that are possible after a given non-terminal. The special symbol $ is used to represent the end of phrase (end of input).
The algorithm should be repeated until the FOLLOW set remains unchanged.