| Line 4: | Line 4: | ||
# If '''a''' is a terminal symbol, then FIRST('''a''') = {'''a'''} | # If '''a''' is a terminal symbol, then FIRST('''a''') = {'''a'''} | ||
| − | # If X is a non-terminal symbol and X -> | + | # If X is a non-terminal symbol and X -> ε is a production then add ε to FIRST(X) |
# If X is a non-terminal symbol and X -> Y<sub>1</sub>...Y<sub>n</sub> is a production, then | # If X is a non-terminal symbol and X -> Y<sub>1</sub>...Y<sub>n</sub> is a production, then | ||
| − | #:a | + | #:a ∈ FIRST(X) if a ∈ FIRST(Y<sub>i</sub>) and ε ∈ FIRST(Y<sub>j</sub>), i<j (i.e., Y<sub>j</sub> <amsmath>\overset{*}{\Rightarrow}</amsmath> ε) |
As an example, consider production X -> Y<sub>1</sub>...Y<sub>n</sub> | As an example, consider production X -> Y<sub>1</sub>...Y<sub>n</sub> | ||
| − | * If Y<sub>1</sub> <amsmath>\overset{*}{\nRightarrow}</amsmath> | + | * If Y<sub>1</sub> <amsmath>\overset{*}{\nRightarrow}</amsmath> ε then FIRST(X) = FIRST(Y<sub>1</sub>) |
| − | * If Y<sub>1</sub> <amsmath>\overset{*}{\Rightarrow}</amsmath> | + | * 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> | + | * 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. | 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. | ||
| Line 19: | Line 19: | ||
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 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 X is the grammar's initial symbol then {$} | + | # If X is the grammar's initial symbol then {$} ⊆ FOLLOW(X) |
| − | # If A -> | + | # If A -> αXβ is a production, then FIRST(β)\{ε} ⊆ FOLLOW(X) |
| − | # If A -> | + | # If A -> αX or A -> αXβ (β <amsmath>\overset{*}{\Rightarrow}</amsmath> ε), then FOLLOW(A) ⊆ FOLLOW(X) |
The algorithm should be repeated until the FOLLOW set remains unchanged. | 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.