| 1 |
The tt(FIRST) set defines all terminal tokens that can be encountered when |
| 2 |
beginning to recognize a grammatical symbol. For each grammatical symbol |
| 3 |
(terminal and nonterminal) a tt(FIRST) set can be determined as follows: |
| 4 |
itemization( |
| 5 |
it() The tt(FIRST) set of a terminal symbol is the symbol itself. |
| 6 |
it() The tt(FIRST) set of an empty alternative is the empty set. The empty |
| 7 |
set is indicated by epsilon() and is considered an actual element of the |
| 8 |
tt(FIRST) set (So, a tt(FIRST) set could contain two elements: |
| 9 |
tt('+') em(and) epsilon()). |
| 10 |
it() If X has a production rule tt(X: X1 X2 X3..., Xi, ...Xn), then |
| 11 |
initialize fst(X) to empty (i.e., not even holding epsilon()). Then, |
| 12 |
for each Xi (1..n): |
| 13 |
itemization( |
| 14 |
it() add fst(Xi) to fst(X) |
| 15 |
it() stop when fst(Xi) does not contain epsilon() |
| 16 |
) |
| 17 |
If fst(Xn) does not contain epsilon() remove epsilon() from fst(X) (unless |
| 18 |
analyzing another production rule) epsilon() is already part of fst(X). |
| 19 |
) |
| 20 |
|
| 21 |
When starting this algorithm, only the nonterminals need to be |
| 22 |
considered. Also, required tt(FIRST) sets may not yet be available. Therefore |
| 23 |
the above algorithm iterates over all nonterminals until no changes were |
| 24 |
observed. In the algorithm tt($) is not considered. |
| 25 |
|
| 26 |
Applying the above algorithm to the rules of our grammar we get: |
| 27 |
table(4)(llll)( |
| 28 |
rowline() |
| 29 |
fstrow(nonterminal)(rule)(FIRST set) |
| 30 |
rowline() |
| 31 |
fstrow(tt(start_$)) (tt(start)) (not yet available) |
| 32 |
fstrow(tt(start)) (tt(start expr)) (not yet available) |
| 33 |
fstrow(tt(start)) (tt(// empty)) (epsilon()) |
| 34 |
fstrow(tt(expr)) (tt(NR)) (tt(NR)) |
| 35 |
fstrow(tt(expr)) (tt(expr '+' expr)) (tt(NR)) |
| 36 |
rowline() |
| 37 |
row(cell(changes in the next cycle:)) |
| 38 |
fstrow(tt(start)) (tt(start expr)) (tt(NR) epsilon()) |
| 39 |
fstrow(tt(start)) (tt(// empty)) (tt(NR) epsilon()) |
| 40 |
rowline() |
| 41 |
row(cell(changes in the next cycle:)) |
| 42 |
fstrow(tt(start_$)) (tt(start)) (tt(NR) epsilon()) |
| 43 |
rowline() |
| 44 |
row(cell(no further changes)) |
| 45 |
) |