|
|
| (29 intermediate revisions by the same user not shown) |
| Line 1: |
Line 1: |
| == Computing the FIRST Set ==
| | #REDIRECT [[ist:Introduction to Syntax]] |
| | |
| 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-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
| |
| #: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>
| |
| * 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> ε 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>)\{ε}) ∪ {ε}
| |