Cho văn phạm gồm các luật sinh: epsilon; epsilon; S → A; A → BC hoặc A-> DBC; B → bBʼ hoặc B-> epsilon; B’→ bB’ hoặc B’- > C → c hoặc C-> D → a hoặc D-> d, FIRST(D) =?

Để tìm FOLLOW(C), ta xét các luật sinh có C ở vế phải.

• A → BC
• A → DBC

Từ A → BC, theo định nghĩa FOLLOW, FOLLOW(C) chứa FOLLOW(A).

Từ A → DBC, theo định nghĩa FOLLOW, FOLLOW(C) chứa FOLLOW(A).

Ta cần tìm FOLLOW(A):

• S → A, suy ra FOLLOW(A) chứa $ (ký hiệu kết thúc chuỗi).

Vậy FOLLOW(C) = { $ }.

Để tìm Follow(B), ta cần xem xét các quy tắc sinh ra B ở vế phải và vế trái:

• Ở vế phải:

+ S -> BCD: First(CD) = First(C) = {c}. Do đó, c ∈ Follow(B).

+ A -> BBA: First(BA) = First(B) = {b}. Do đó, b ∈ Follow(B).

• Ở vế trái:

+ B -> bEc: Theo sau B không có gì, xét S -> BCD, D -> a hoặc D -> BDb, ta có nếu B là cuối chuỗi thì ta thêm $ (ký hiệu kết thúc chuỗi) vào Follow(B) vậy $ ∈ Follow(B)

Vậy Follow(B) = {b, c, $}

Đáp án A, B, C, D đều không chính xác

Để tìm Follow(D), ta cần xem xét các vị trí mà D xuất hiện ở vế phải của các luật sinh và áp dụng các quy tắc sau:

• Quy tắc 1: Nếu có luật sinh A → αBβ, thì mọi phần tử trong First(β) (ngoại trừ ε) đều thuộc Follow(B).
• Quy tắc 2: Nếu có luật sinh A → αB, hoặc A → αBβ mà First(β) chứa ε (tức là β ⇒* ε), thì mọi phần tử trong Follow(A) đều thuộc Follow(B).

Áp dụng vào văn phạm đã cho:

• D xuất hiện trong B → BDc. Áp dụng quy tắc 1, First(c) = {c} nên c ∈ Follow(D).
• D xuất hiện trong D → BDb. Áp dụng quy tắc 1, First(b) = {b} nên b ∈ Follow(D).
• D là cuối cùng trong B → BDc. Follow(B) cần được thêm vào Follow(D). Để tìm Follow(B), ta xét các luật sinh có B:
  • S → BCD => First(CD) = {c}. Vậy c thuộc Follow(B).
  • A → BBA => First(BA). First(B) = {b}, vậy b thuộc Follow(A)
  • B → bEc => Không liên quan trực tiếp đến Follow(B)
  • B → BC => First(C) = {c}. Vậy c thuộc Follow(B)
  • B → BDc => First(Dc) = {a, b}. Vậy a và b thuộc Follow(B).
• D → BDb => b thuộc Follow(D)

Như vậy, Follow(B) chứa {c}. Xét S → BCD, Follow(S) = {$}, vậy Follow(B) phải chứa {$}.

Vậy Follow(D) = {a, b, c, $}.