Cho văn phạm gồm các luật sinh: S → A; A → BC hoặc A-> DBC; B → bBʼ hoặc B-> epsilon; B’→ bB’ hoặc B’- > epsilon; C → c hoặc C-> epsilon; D → a hoặc D-> d, FOLLOW (S) =?
Đáp án đúng: D
Để tìm FOLLOW(S), ta xét các luật sinh có S ở vế trái hoặc vế phải.
- Ta có luật sinh S → A, nên FOLLOW(S) sẽ chứa tất cả các phần tử của FOLLOW(A).
- Bây giờ ta cần tìm FOLLOW(A). Xét các luật sinh có A ở vế phải: S → A; A → BC; A → DBC.
+ Từ S → A, ta suy ra FOLLOW(A) chứa FOLLOW(S). Vì S là ký hiệu bắt đầu, nên $ thuộc FOLLOW(S).
+ Từ A → BC, ta suy ra FIRST(C) - {ε} thuộc FOLLOW(B). Vì C → c hoặc C → ε, nên FIRST(C) = {c, ε}. Do đó, c thuộc FOLLOW(B).
+ Từ A → DBC, ta suy ra FIRST(C) - {ε} thuộc FOLLOW(B). Vì C → c hoặc C → ε, nên FIRST(C) = {c, ε}. Do đó, c thuộc FOLLOW(B).
+ Từ A → BC, ta suy ra nếu C → ε thì FOLLOW(A) chứa FOLLOW(BC) = FOLLOW(A) chứa FOLLOW(C) (nếu C dẫn xuất ra ε). FOLLOW(A) chứa FIRST(C) - {ε} = {c}. Ngoài ra, nếu C dẫn xuất ra ε, thì FOLLOW(A) chứa FOLLOW(A) chứa FOLLOW(S)={$} .
+ Từ A → DBC, ta suy ra FOLLOW(A) chứa FIRST(C) - {ε} = {c}. Ngoài ra, nếu C dẫn xuất ra ε, thì FOLLOW(A) chứa FOLLOW(BC) = FOLLOW(A) chứa FOLLOW(S)={$} .
Vậy FOLLOW(A) chứa {$}. Do đó, FOLLOW(S) chứa {$}.
Đáp án đúng là D.
